Difference between CDR, CAR and REST, FIRST and possible implementation?

Question

I'm learning a little bit about functional programming in LISP and here's what I've bumped into: LISP uses CAR, CDR functions as well as FIRST and REST functions. Both related to lists.

From what I've learned so far, there's a difference between these two, but I don't quite see what the difference is.

Could anyone sum this up for me? And how do I eventually implement FIRST/REST using CDR, CAR?

---

Edit: Since accepted answer mentions documentation, but does not link, here is the link for the documentation for CAR/CDR, here then for FIRST/REST.

In addition - important note - that linked documentation is "just implementation notes" for CLISP, which is a commonly used environment. Generally it is almost impossible to find "official documentations" for languages such is this one.

Fireworks

None of these functions is a predicate. – Data

@RainerJoswig Alright thanks, my bad, it is now fixed in the post. – Fireworks

@Fireworks Note that there's a third pair of elements in the set: CONS and LIST*. LIST* will do a bit more that CONS, in that it can take multiple arguments, but when it's called with just two, it does exactly the same thing as CONS, but is much more suggestive of the list-oriented intent. – Pandanus

What makes the language specification "just implementation notes"? You won't find a more official documentation for Common Lisp. Or maybe you write "CLISP" to shorten "Common Lisp" and think Common Lisp is an implementation of some abstract "LISP"? If you want to broaden the scope, Scheme users define "first", etc manually (en.wikibooks.org/wiki/Scheme_Programming/List_Operations) and Racket's first functions are only valid for non-empty lists (see docs.racket-lang.org/reference/pairs.html). But when it comes to Common Lisp, as your tags indicate, the specification is clear. – Protozoan

Answer 1

In terms of what they do, car and cdr are equivalent to first and rest. This is quite clear in the documentation. The HyperSpec says on the entry for first, second, &c:

The functions first, second, third, fourth, fifth, sixth, seventh, eighth, ninth, and tenth access the first, second, third, fourth, fifth, sixth, seventh, eighth, ninth, and tenth elements of list, respectively. Specifically,

(first list)    ==   (car list)
(second list)   ==   (car (cdr list))
(third list)    ==   (car (cddr list))

…

Notes:

first is functionally equivalent to car, second is functionally equivalent to cadr, third is functionally equivalent to caddr, and fourth is functionally equivalent to cadddr.

Now, there is a difference, not in functionality, but in style, when you're using these functions. This is actually called out in the HyperSpec as well, e.g., in the entry on rest:

Notes:

rest is often preferred stylistically over cdr when the argument is to being subjectively viewed as a list rather than as a cons.

For instance, consider two ways of mapping over structures built from cons cells. In the first, we're mapping over a tree of cons cells, calling some function with each leaf (i.e., non-cons) of the tree. We check whether something is a cons with consp, and if it is, we recurse onto its car and cdr. We combine the results into a new cons cell by calling cons.

(defun map-over-cons (function tree)
  (if (not (consp tree))
      (funcall function tree)
      (cons (map-over-cons function (car tree))
            (map-over-cons function (cdr tree)))))

Alternatively, when we map over a list, we typically check for the terminal condition with endp (or null, but endp emphasizes that we're looking for the end of a list, not just looking for nil), and we call the function on the first of the list and recurse into the rest of the list. While it's pretty common to see the result constructed using cons, there's actually list* that will perform the same task when called with two arguments (in general, it can do a bit more) that emphasizes that a list is being constructed:

(defun map-over-list (function list)
  (if (endp list)
      '()
      (list* (funcall function (first list))
             (map-over-list function (rest list)))))

Either of these functions could be written using car, cdr, and cons, or with first, rest, and list*, or any combination of them, but sticking to one or the other helps people that may read the code later (including the original author), and signals the intent of the author.

And how do I eventually implement FIRST/REST using CDR, CAR?

How about:

(defun first (x) (car x))
(defun rest (x) (cdr x))

or possibly even better, if you have symbol-function:

(setf (symbol-function 'first) (symbol-function 'car))
(setf (symbol-function 'rest) (symbol-function 'cdr))

Pandanus

Answer 2

The operations first and rest signals that you are working with a list: a series of pairs ending with the empty list i.e. it is of the form (list x1 ... xn)

The operations car and cdr signals that you are working on a data structure build with pairs, that potentially isn't a list.

That is choose first and rest when you work with lists, to make the code easier for others to read.

Bimetallic

I agree with the statement, but is there justification for this? The intent aspect seems intuitive, but this doesn't state whether there are any technical differences between the corresponding functions (e.g., CAR/FIRST, and CDR/REST, and CONS/LIST*). With some similar functions, there is a difference (e.g., NULL/ATOM/ENDP). – Pandanus

The HyperSpec states that first is equivalent to car. The interpretation is folklore. – Bimetallic

I know that the hyperspec states that they're equivalent. This answer doesn't cite the hyperspec, though. The hyperspec actually mentions the use of REST to signal the intent that the argument is being treated as a list (as opposed to a tree of cons cells). But without references, the answer is just an assertion. – Pandanus

Well, the OP asked for someone to "sum it up", so I made it short. – Bimetallic

Answer 3

Classically, car and cdr have been more machine oriented while first and rest have been more abstract functions. In reality, there is no difference between them. Everyone stuck to car and cdr, so car and cdr prevailed.

If you're having a hard time to finding any differences between car and first, it's because there is none. Look at first as an alias for car.

Definitions?

(defun first (x) (car x))
(defun rest (x) (cdr x))

Seifert

Classically the programmer shows the intent to work with proper lists or with cons cells, Makes reading code a bit easier. – Data

I think the point in this answer is that the names CAR and CDR were originally mnemonics (as discussed in the Wikipedia article, CAR and CDR, but, similar to Rainer's note, that doesn't really discuss at all whether there's a difference between CAR/FIRST, CDR/REST, (and CONS/LIST*). – Pandanus

Answer 4

Firstly, none of these is a predicate (or at least, they aren't what Lisp programmers call "predicates"; in this context, "predicate" means "a function that returns a boolean value").

As to the question, lets hop into a REPL for a minute.

; SLIME 2014-12-23
CL-USER> (describe #'car)
#<FUNCTION CAR>
  [compiled function]

Lambda-list: (LIST)
Declared type: (FUNCTION (LIST) (VALUES T &OPTIONAL))
Documentation:
  Return the 1st object in a list.
Known attributes: foldable, flushable, unsafely-flushable
Source file: SYS:SRC;CODE;LIST.LISP
; No value
CL-USER> (describe #'first)
#<FUNCTION FIRST>
  [compiled function]

Lambda-list: (LIST)
Declared type: (FUNCTION (LIST) (VALUES T &OPTIONAL))
Documentation:
  Return the 1st object in a list or NIL if the list is empty.
Known attributes: foldable, flushable, unsafely-flushable
Source file: SYS:SRC;CODE;LIST.LISP
; No value
CL-USER> (describe #'cdr)
#<FUNCTION CDR>
  [compiled function]

Lambda-list: (LIST)
Declared type: (FUNCTION (LIST) (VALUES T &OPTIONAL))
Documentation:
  Return all but the first object in a list.
Known attributes: foldable, flushable, unsafely-flushable
Source file: SYS:SRC;CODE;LIST.LISP
; No value
CL-USER> (describe #'rest)
#<FUNCTION REST>
  [compiled function]

Lambda-list: (LIST)
Declared type: (FUNCTION (LIST) (VALUES T &OPTIONAL))
Documentation:
  Means the same as the cdr of a list.
Known attributes: foldable, flushable, unsafely-flushable
Source file: SYS:SRC;CODE;LIST.LISP
; No value

So, according to the documentation, and their signatures, car is equivalent to first and cdr is equivalent to rest. Lets test this.

CL-USER> (cons 1 2)
(1 . 2)
CL-USER> (car (cons 1 2))
1
CL-USER> (first (cons 1 2))
1
CL-USER> (cdr (cons 1 2))
2
CL-USER> (rest (cons 1 2))
2
CL-USER> (cons 1 nil)
(1)
CL-USER> (car (cons 1 nil))
1
CL-USER> (first (cons 1 nil))
1
CL-USER> (cdr (cons 1 nil))
NIL
CL-USER> (rest (cons 1 nil))
NIL
CL-USER> nil
NIL
CL-USER> (car nil)
NIL
CL-USER> (first nil)
NIL
CL-USER> (cdr nil)
NIL
CL-USER> (rest nil)
NIL

So, they seem to be the same.

Concentrate

This provides some empirical evidence, but it would be nice to see some actual justification, too. While I know that they do behave identically, this answer doesn't discuss whether there are any possible differences. E.g., could one function do more error or type checking than the other, like with NULL vs ATOM vs ENDP. – Pandanus