In Scheme, car, cdr, and cons are the most important functions. The cons function is used to construct pairs and pairs are used to construct the lists. The car and cdr are used to access data and return accordingly first and second element from a pair.
The name of the cons function is an abbreviation of the word construct. The origins of the names for car and cdr are a little bit historical and comes from the IBM 704. car is an acronym from the phrase Contents of the Address part of the Register; and cdr is an acronym from the phrase Contents of the Decrement part of the Register. These phrases refer to specific pieces of hardware on the very early computer on which the Lisp language was developed. Nowadays the more appropriate names for these functions would be firs and rest .
The cons function accepts any two values, not just a list for the second argument. The two values joined with cons are printed between parentheses, with a dot, because Lisp interpreters uses a . to visually separate the elements in the pair. For example:
> (cons 1 2)(1 . 2)
Lists are built on top of pairs. For example, the list ‘(a b c) is constructed by evaluating the following expression:
> (cons ‘a (cons ‘b (cons ‘c ‘())))(a b c)
The list procedure provides a shortcut for creating lists:
> (list ‘a ‘b c)(a b c)
The same can be achieved by ‘(a b c) .
Appending value to the list can be done in the following way:
> (cons 1 ‘(2 3 4))(1 2 3 4)
We can play more with the cons function. Notice that the expression (cons ‘(a b c) ()) creates a pair whose first element is a list. So it evaluates to:
((a b c))
The () stands for null, so the result is a pair (value, null) . Notice the double braces in the returned expression. Let?s consider more examples:
> (cons ‘(a b c) ‘(d))((a b c) d)
Above result is a list with two elements ? a list as the first and d as the second. It is equivalent to [[a, b, c], d] .
Whether a given pair is a list depends on what is stored in the cdr field. A proper list is defined in the recursive way as and empty list () or a pair which second element is a proper list. A chain of pairs that doesn?t end in the empty list is called an improper list.
Car
As mentioned earlier the car of a pair is its first item. And in case of lists it?s the head of the list. Thus the car of the list (a b c d) is a and the car of the pair (a . b) is also a.
car is non-destructive which means it doesn?t mutate the pair by removing the first item from it, it only echoes what it is. After car has been applied to a list, the list is still the same as it was.
Cdr
The cdr function returns the second element of the pair which in case of lists is the list?s tail. So applying the cdr function to the examples above we will get:
> (cdr ‘(a b c d))(b c d)> (cdr ‘(a . b))b
Like car, cdr does not remove any elements form the list.
Setters
The functions set-car! and set-cdr! are used to set accordingly the first and the second element of the pair. And contrarily to the car and cdr they actually mutate the pair. Applying them to the lists we will get following results:
> (define x ‘(a b c d))
First we defined new list x and notation above stands for x = [a, b, c, d] .
> (set-car! x ‘z)> x(z b c d)> (set-cdr! x ‘(y x))> x(z y x)
If we set car of the list as any possible value it remains a list but if we will try to set cdr of the list as a non-list value we?ll got a pair in return.
> (set-cdr! x ‘a)(z . a)
