RCA et CDR

En programmation informatique , CAR ( car) / k ɑːr / ( écouter ) et CDR ( cdr) ( / ˈ k ʌ d ər / ( écouter ) ou / ˈ k ʊ d ər / ( écouter ) ) sont des opérations primitives sur les contre cellules (ou ” expressions S non atomiques “) introduites dans le langage de programmation Lisp . Une cellule cons est composée de deux pointeurs; l’ opération car extrait le premier pointeur et l’ opération cdr extrait le second.

Ainsi, l’expression vaut , et vaut .(car (cons x y ))x(cdr (cons x y ))y

Lorsque les cellules cons sont utilisées pour implémenter des listes à liens simples (plutôt que des arbres et d’autres structures plus compliquées ), l’ opération car renvoie le premier élément de la liste, tandis que cdr renvoie le reste de la liste. Pour cette raison, les opérations portent parfois les noms first and rest ou head and tail .

Étymologie

Lisp a été initialement implémenté sur l’ ordinateur IBM 704 , à la fin des années 1950.

L’explication populaire selon laquelle CAR et CDR signifient “Contents of the Address Register” et “Contents of the Decrement Register” ^[1] ne correspond pas tout à fait à l’architecture IBM 704 ; l’IBM 704 n’a pas de registre d’adresse accessible par le programmeur et les trois registres de modification d’adresse sont appelés «registres d’index» par IBM.

Le 704 et ses successeurs ont une longueur de mot de 36 bits et un espace d’adressage de 15 bits . Ces ordinateurs avaient deux formats d’ instructions , dont l’un, le type A, avait un préfixe de code d’opération court de 3 bits et deux champs de 15 bits séparés par une balise de 3 bits. Le premier champ de 15 bits était l’adresse de l’opérande et le second contenait un décrément ou un comptage. La balise spécifiait l’un des trois registres d’index . L’indexation était un processus soustractif sur le 704, d’où la valeur à charger dans un registre d’index s’appelait un “décrément”. ^{[2] : p. 8} Le matériel 704 avait des instructions spéciales pour accéder aux champs d’adresse et de décrémentation en un mot. ^{[2]: p. 26} En conséquence, il était efficace d’utiliser ces deux champs pour stocker dans un seul mot les deux pointeurs nécessaires à une liste. ^{[3] : Introduction.}

Ainsi, “CAR” est “Contenu de la partie adresse du registre”. Le terme “registre” dans ce contexte fait référence à “l’emplacement de la mémoire”. ^{[4] [5]}

Les précurseurs ^{[6] [7]} de Lisp incluaient des fonctions :

• car(“contenu de la partie adresse du numéro de registre”),
• cdr(“contenu de la partie de décrémentation du numéro de registre”),
• cpr(“contenu de la partie préfixe du numéro de registre”), et
• ctr(“contenu de la partie étiquette du numéro de registre”),

chacun prenant une adresse machine comme argument, chargeant le mot correspondant de la mémoire et extrayant les bits appropriés.

704 macros

La macro assembleur 704 pour carétait : ^{[8] [9] [10]}

LXD JLOC 4 # C( Décrémentation de JLOC ) → C( C ) # Charge la décrémentation de l’emplacement JLOC dans le registre d’index C CLA 0 , 4 # C( 0 – C( C ) ) → C( AC ) # Le registre AC reçoit l’adresse de début de la liste PAX 0 , 4 # C( Adresse de AC ) → C( C ) # Charge l’adresse de AC dans le registre d’index C PXD 0 , 4 # C( C ) → C ( Décrémentation de AC ) # Efface AC et charge le registre d’index C dans le décrément de AC

La macro assembleur 704 pour cdrétait : ^{[8] [9] [10]}

LXD JLOC 4 # C( Décrémentation de JLOC ) → C( C ) # Charge la décrémentation de l’emplacement JLOC dans le registre d’index C CLA 0 , 4 # C( 0 – C( C ) ) → C( AC ) # Le registre AC reçoit l’adresse de début de la liste PDX 0 , 4 # C( Décrémentation de AC ) → C( C ) # Charge la décrémentation de AC dans le registre d’index C PXD 0 , 4 # C( C ) → C( Décrémentation de AC ) # Efface AC et charge le registre d’index C dans le décrément de AC

Un mot machine pouvait être réassemblé par contre , ce qui prenait quatre arguments ( a , d , p , t ).

Les parties préfixe et balise ont été supprimées au début de la conception de Lisp, laissant CAR, CDR et un CONS à deux arguments. ^[3]

Compositions

Les compositions de caret cdrpeuvent recevoir des noms courts et plus ou moins prononçables de la même forme. En Lisp, (cadr ‘(1 2 3))est l’équivalent de (car (cdr ‘(1 2 3))); sa valeur est 2. De même, (caar ‘((1 2) (3 4)))(prononcé / ˈ k eɪ ɑːr / ) est identique à (car (car ‘((1 2) (3 4)))); sa valeur est 1. La plupart des Lisp, par exemple Common Lisp et Scheme , définissent systématiquement toutes les variations de deux à quatre compositions de caret cdr.

Autres langages informatiques

De nombreux langages (en particulier les langages fonctionnels et les langages influencés par le paradigme fonctionnel ) utilisent une liste chaînée comme structure de données de base et fournissent des primitives ou des fonctions similaires à caret cdr. Ceux-ci sont nommés différemment firstet rest, headet tail, etc. En Lisp, cependant, la cellule cons n’est pas seulement utilisée pour construire des listes chaînées mais aussi pour construire des structures de paires et de paires imbriquées, c’est-à-dire lacdrd’une cellule contre n’a pas besoin d’être une liste. Dans ce cas, la plupart des autres langages fournissent des primitives différentes car ils distinguent généralement les structures de paires des structures de liste, soit par type, soit sémantiquement. En particulier dans les langages typés, les listes, les paires et les arbres auront tous des fonctions d’accès différentes avec des signatures de type différentes : dans Haskell , par exemple, caret cdrdeviennent fstet sndlorsqu’il s’agit d’un type de paire. Les analogues exacts de caret cdrsont donc rares dans d’autres langues. Clojure utilise first au lieu de car et next ou rest au lieu de cdr.

Références

1. ^ Voir, par exemple, Mitchell, John C. (2003), Concepts in Programming Languages ​​, Cambridge University Press, pp. 28–29, ISBN 9781139433488, Section 3.4, Innovations dans la conception de Lisp . La référence identifie l’IBM 704 et explique correctement la partie adresse et décrémentation d’une cellule contre, mais elle omet ensuite la “partie de” dans l’explication de McCarthy.
2. ^ ^{a b} 704 – machine de traitement de données électronique http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf
3. ^ ^{un b} McCarthy, John (1979-02-12). “Histoire de Lisp” .
4. ^ McCarthy (1960 , pp. 26–27)discute des registres sur la liste gratuite et dans la collecte des ordures.erreur harvtxt : pas de cible : CITEREFMcCarthy1960 ( aide )
5. ^ McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1985), Manuel du programmeur LISP 1.5 (deuxième éd.), Cambridge, Massachusetts: MIT Press, ISBN 978-0-262-13011-0, page 36, décrit les cellules contre comme des mots avec des champs “adresse” et “décrémentation” de 15 bits.
6. ^ Un langage de traitement de liste compilé par Fortran
7. ^ Un langage de traitement de liste compilé par Fortran ; Transcription HTML
8. ^ ^{a b} Parties des PAGES LISP de NILS – http://t3x.dyndns.org/LISP/QA/carcdr.html
9. ^ ^{a b} MIT AI Lab Memo 6 https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf
10. ^ ^{a b} CODAGE pour l’ORDINATEUR MIT-IBM 704 http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf

Remarques

• Russel, Steve . “Programmes d’écriture et de débogage” (PDF) . Centre de calcul RLE et MIT. Publications CSAIL et archives numériques (Mémo). Mémo AI , non. 6. Cambridge , Massachusetts : Laboratoire d’intelligence artificielle du MIT . OCLC 35415961 . Archivé de l’original (PDF) le 2017-07-06 . Consulté le 20 juillet 2017 .
• Faase, Frans (2006-01-10). “L’origine de CAR et CDR dans LISP” .
• Graham, Paul (1996). Lisp commun ANSI . Prentice Hall. ISBN 978-0-13-370875-2.
• Barski, Conrad (2010). Land of Lisp : apprenez à programmer en Lisp, un jeu à la fois ! . San Francisco, Californie: No Starch Press, Inc. ISBN 978-1-59327-281-4.