AUTO a CDR - CAR and CDR

Pro další použití viz CAR (disambiguation), CDR (disambiguation), a CADR (disambiguation).

v programování, AUTO (auto) /k.r/ (O tomto zvukuposlouchat) a CDR (cdr) (/ˈkʌd.r/ (O tomto zvukuposlouchat) nebo /ˈkʊd.r/ (O tomto zvukuposlouchat)) jsou primitivní operace na nevýhody buňky (nebo „jiné než atomové S-výrazy ") zavedený v Programovací jazyk Lisp. Buňka proti se skládá ze dvou ukazatele; the auto operace extrahuje první ukazatel a cdr operace extrahuje druhou.

Tedy výraz (auto (záp X y)) hodnotí na X, a (cdr (záp X y)) hodnotí na y.

Když jsou k implementaci použity buňky proti jednotlivě propojené seznamy (spíše než stromy a další komplikovanější struktur ), auto operace vrací za prvé prvek seznamu, zatímco cdr vrátí zbytek seznamu. Z tohoto důvodu jsou operace někdy pojmenovány za prvé a zbytek nebo hlava a ocas.

Etymologie

Lisp byl původně implementován na IBM 704 počítač, na konci 50. let.

Populární vysvětlení AUTO a CDR zkratka pro „Obsah registru adres“ a „Obsah registru dekrementů“[1] neodpovídá zcela architektuře IBM 704; IBM 704 nemá programově přístupný registr adres a tři registry úpravy adres se IBM nazývají „rejstříky indexů“.

704 a jeho nástupci mají 36-bit slovo délka a 15 bitů adresní prostor. Tyto počítače měly dva návod formáty, z nichž jeden, typ A, měl krátký, 3bitový, provozní kód předpona a dva 15bitové pole oddělené 3bitovou značkou. První 15bitové pole byla adresa operandu a druhé obsahovalo dekrement nebo počet. Značka zadala jednu ze tří rejstříky rejstříků. Indexování bylo na 704 subtraktivním procesem, a proto se hodnota, která se má načíst do rejstříku indexů, nazývala „dekrement“.[2]:p. 8 Hardware 704 měl speciální pokyny pro přístup k polím adresy a dekrementace jedním slovem.[2]:p. 26 Ve výsledku bylo efektivní použít tato dvě pole k uložení dvou ukazatelů potřebných pro seznam do jednoho slova.[3]:Intro.

„CAR“ je tedy „obsah adresy část Pojem „registr“ v tomto kontextu označuje „umístění paměti“.[4][5]

Předchůdci[6][7] do funkcí Lisp:

  • auto („obsah adresové části registračního čísla“),
  • cdr ("obsah zmenšené části čísla registru"),
  • cpr ("obsah předponové části registračního čísla") a
  • ctr ("obsah části tagu z registračního čísla"),

každý z nich vzal adresu stroje jako argument, načetl odpovídající slovo z paměti a extrahoval příslušné bity.

704 maker

Makro 704 assembleru pro auto byl:[8][9][10]

LXD JLOC 4  # C (Snížení JLOC) → C (C) # Načte Snížení umístění JLOC do rejstříku Registr CCLA 0,4     # C (0 - C (C)) → C (AC) # Registr AC obdrží počáteční adresu seznamuPAX 0,4     # C (Adresa AC) → C (C) # Načte adresu AC do rejstříkového registru CPXD 0,4     # C (C) → C (Snížení AC) # Vymaže AC a načte indexový registr C do Snížení AC

Makro 704 assembleru pro cdr byl:[8][9][10]

LXD JLOC 4  # C (Snížení JLOC) → C (C) # Načte Snížení umístění JLOC do rejstříku Registr CCLA 0,4     # C (0 - C (C)) → C (AC) # Registr AC obdrží počáteční adresu seznamuPDX 0,4     # C (Snížení AC) → C (C) # Načte Snížení AC do indexového registru CPXD 0,4     # C (C) → C (Snížení AC) # Vymaže AC a načte indexový registr C do Snížení AC

Mohlo by se znovu sestavit strojové slovo nevýhody, který vzal čtyři argumenty (A,d,p,t).

Předpony a části značek byly vynechány v raných fázích designu Lisp, takže CAR, CDR a dvou argumenty CONS.[3]

Skladby

Skladby z auto a cdr mohou být dána krátká a více či méně vyslovitelná jména stejné formy. V Lispu (cadr '(1 2 3)) je ekvivalentem (auto (cdr '(1 2 3))); jeho hodnota je 2. Podobně, (caar '((1 2) (3 4))) je stejné jako (auto (auto '((1 2) (3 4)))); jeho hodnota je 1. Například většina Lisps Společný Lisp a Systém, systematicky definovat všechny varianty dvou až čtyř kompozic auto a cdr.

Jiné počítačové jazyky

Mnoho jazyků (zejména funkční jazyky a jazyky ovlivněné funkční paradigma ) použijte a jednotlivě propojený seznam jako základní datová struktura a poskytuje primitivní funkce nebo funkce podobné auto a cdr. Ty jsou pojmenovány různě za prvé a zbytek, hlava a ocasatd. V Lispu se však buňka cons nepoužívá pouze k vytváření propojených seznamů, ale také k vytváření párových a vnořených párových struktur, tj. cdr buňky zápory nemusí být seznam. V tomto případě většina ostatních jazyků poskytuje různá primitiva, protože obvykle rozlišují párové struktury od struktur seznamů buď typicky, nebo sémanticky. Zejména v zadaných jazycích budou mít seznamy, páry a stromy všechny různé funkce přistupujícího objektu s různými podpisy typů: v Haskell, například, auto a cdr stát se první a snd když jednáte s typem páru. Přesné analogy auto a cdr jsou tedy v jiných jazycích vzácné.

Reference

  1. ^ Viz například Mitchell, John C. (2003), Koncepty v programovacích jazycích, Cambridge University Press, s. 28–29, ISBN  9781139433488, Oddíl 3.4, Inovace v designu Lispu. Odkaz identifikuje IBM 704 a správně vysvětlí adresu a zmenšovací část buňky proti, ale pak vynechá „část“ ve McCarthyho vysvětlení.
  2. ^ A b 704 - stroj na elektronické zpracování dat http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf
  3. ^ A b McCarthy, Johne (1979-02-12). "Historie Lispu".
  4. ^ McCarthy (1960, s. 26–27) pojednává o registrech na bezplatném seznamu a v uvolňování paměti.
  5. ^ McCarthy, John; Abrahams, Paul W .; Edwards, Daniel J .; Hart, Timothy P .; Levin, Michael I. (1985), Příručka programátora LISP 1.5 (druhé vydání), Cambridge, Massachusetts: MIT Press, ISBN  978-0-262-13011-0, strana 36, ​​popisuje buňky cons jako slova s ​​15bitovými poli „address“ a „decrement“.
  6. ^ Fortran zkompilovaný jazyk pro zpracování seznamu
  7. ^ Fortran zkompilovaný jazyk pro zpracování seznamu; Přepis HTML
  8. ^ A b Části z NILS 'LISP PAGES- http://t3x.dyndns.org/LISP/QA/carcdr.html
  9. ^ A b MIT AI Lab Memo 6 ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf
  10. ^ A b KÓDOVÁNÍ PRO POČÍTAČ MIT-IBM 704 ftp://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf
Poznámky