CAR and CDR

CAR and CDR

Introduced in the Lisp programming language, car (pronEng|ˈkɑr, just like the English word "car") and cdr (IPA|/ˈkʌdər/ or IPA|/ˈkʊdər/) are primitive operations upon linked lists composed of cons cells. A cons cell is composed of two pointers; the "car" operation extracts the first pointer, and the "cdr" operation extracts the second.

Thus, the expression (car (cons "x" "y")) evaluates to "x", and (cdr (cons "x" "y")) evaluates to "y".

When cons cells are used to implement singly-linked lists (rather than trees and other more complicated structures), the "car" operation returns the "first" element of the list, while "cdr" returns the "rest" of the list. For this reason, the operations are sometimes given the names "first" and "rest" or "head" and "tail".

Origin of the names car and cdr

Lisp was originally implemented on the IBM 704 computer, in the late 1950s. The 704 hardware had special support for splitting a 36-bit machine word into four parts, an "address part" and "decrement part" of 15 bits each and a "prefix part" and "tag part" of three bits each. Precursors to Lisp included functions "car" (short for "Contents of the Address part of Register number"), "cdr" ("Contents of the Decrement part of Register number"), "cpr" and "ctr", each of which took a machine address as an argument, loaded the corresponding word from memory, and extracted the appropriate bits. The 704 assembler macro for cdr was

:LXD JLOC,4:CLA 0,4:PDX 0,4:PXD 0,4Portions from NILS' LISP PAGES- [http://t3x.dyndns.org/LISP/QA/carcdr.html http://t3x.dyndns.org/LISP/QA/carcdr.html] ]

A machine word could be reassembled by "cons", which took four arguments ("a","d","p","t"). The prefix and tag parts were dropped in the early stages of Lisp's design, leaving CAR, CDR, and a two-argument CONS. [cite web
last = McCarthy | first = John | authorlink = John McCarthy (computer scientist)
date = 1979-02-12
title = History of Lisp
url = http://www-formal.stanford.edu/jmc/history/lisp/lisp.html
]

The alternate names first and rest, which date back at least to 1959, [McCarthy, J., Erratum to Memo 8, " [ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-008.pdf Recursive Functions of Symbolic Expressions and Their Computation By Machine] ", dated March 13, 1959, retrieved September 19, 2008.] are sometimes preferred to car and cdrdue to their greater clarityFact|date=September 2008. However, car and cdr have the advantage that short compositions of the functions can be given short and more or less pronounceable names of the same form. In Lisp, (cadr '(1 2 3)) is the equivalent of (car (cdr '(1 2 3))); its value is 2 (the "first" item of the "rest" of (1 2 3)). Similarly, (caar '((1 2) (3 4))) is the same as (car (car '((1 2) (3 4)))); its value is 1. Most Lisps set a limit on the number of composed forms they support; Common Lisp and Scheme both provide forms with up to four repetitions of the "a" and "d".

Other languages

ML and Haskell are also functional languages which use the singly-linked list as a basic data structure. ML has functions "List.hd" and "List.tl"; and Haskell has functions "head" and "tail", which are analogous to "car" and "cdr", respectively. However, they are seldom used; instead, parts of the list are usually de-constructed using pattern matching.

References


*Russel, S. (undated, c. late 1950s) Writing and Debugging Programs. MIT Artificial Intelligence Laboratory Memo 6.
* cite web
last = Faase | first = Frans
date = 2006-01-10
title = The origin of CAR and CDR in LISP
url = http://www.iwriteiam.nl/HaCAR_CDR.html

* cite book
last = Graham | first = Paul | authorlink = Paul Graham
title = ANSI Common Lisp
publisher = Prentice Hall
year = 1996
id = ISBN 0-13-370875-6


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • CDR — may refer to: Computer science *Contents of Decrement Register in the programming language Lisp Technology *CD R, a recordable compact disc format *.cdr, the file extension for the CorelDRAW drawing file, and for the Raw Audio CD data file *.cdr …   Wikipedia

  • Car (disambiguation) — A car is a type of vehicle, most often in American English an automobile.Car may also refer to:TransportationVehicles* Railroad car, a vehicle on a train that is not a locomotive * Archaic for: ** Chariot ** Carriage ** Cart * The cab of an… …   Wikipedia

  • List of accidents and incidents involving military aircraft, pre-1950 — This is a list of notable accidents and incidents involving military aircraft grouped by the year in which the accident or incident occurred. For more exhaustive lists, see the [http://www.baaa acro.com/ Aircraft Crash Record Office] or the [http …   Wikipedia

  • Lisp (programming language) — Infobox programming language name = Lisp paradigm = multi paradigm: functional, procedural, reflective generation = 3GL year = 1958 designer = John McCarthy developer = Steve Russell, Timothy P. Hart, and Mike Levin latest release version =… …   Wikipedia

  • Cons — In computer programming, cons (pronEng|ˈkɒnz or IPA|/ˈkɒns/) is a fundamental function in all dialects of the Lisp programming language. cons constructs (hence the name) memory objects which hold two values or pointers to values. These objects… …   Wikipedia

  • cons — This article is about the Lisp programming function. For other uses, see Cons (disambiguation). In computer programming, cons (  /ˈkɒ …   Wikipedia

  • SECD machine — The SECD machine is a highly influential virtual machine intended as a target for functional programming language compilers. The letters stand for Stack, Environment, Code, Dump, the internal registers of the machine. These registers point to… …   Wikipedia

  • Linked list — In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the… …   Wikipedia

  • Common Lisp — Paradigm(s) Multi paradigm: procedural, functional, object oriented, meta, reflective, generic Appeared in 1984, 1994 for ANSI Common Lisp Developer ANSI X3J13 committee Typing discipline …   Wikipedia

  • Null Object pattern — Null object redirects here. For the concept in category theory, see Initial object. In object oriented computer programming, a Null Object is an object with defined neutral ( null ) behavior. The Null Object design pattern describes the uses of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”