clojure: no cons cells

Question

i heard that clojure does not have cons cells as of most lisp languages.

does that mean a clojure list does not end with an empty list?

could anyone explain what that exactly means?

Answer 1

Lisp provides a primitive cons data structure and a notation for it.

See John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, 1960, Chapter 3, Recursive Functions of Symbolic Expressions.

That chapter introduces:

• Symbolic expressions made of atoms and pairs of symbolic expressions written using a dot notation: ( a . b )
• a list notation to abbreviate certain symbolic expressions (a b c)
• an atomic symbol nil to terminate lists
• the primitive functions car, cdr, cons, eq and atom
• several other functions: ff, subst, equal, null, cadr, caddr, null, append, among, pair, assoc, sublis, apply, eval, ...

Early on in Lisp, functions to mutate cons cells have been added: rplaca (means replace car) and rplacd (means replace cdr). See the LISP 1.5 Programmer's Manual by John McCarthy et al. from 1962. These functions allow us to write destructive functions and also allow us to create cyclic cons-based data structures like cyclic lists.

Common Lisp

Typically Lisp dialects implement most of this. Common Lisp is no exception and for it this functionality is described in the Common Lisp standard: Conses. Examples using the functions mentioned above:

; pair two lists into a list of cons cells.
; the function pair is called pairlis in Common Lisp.
CL-USER 17 > (pairlis '(john mary eva) '(34 29 40))
((EVA . 40) (MARY . 29) (JOHN . 34))

; find a cons cell in a list of cons cells,
; based on the content of the car of those cons cells
CL-USER 18 > (assoc 'eva (pairlis '(john mary eva)
                                  '(34 29 40)))
(EVA . 40)

; create a tree out of cons cells and atoms
CL-USER 19 > (cons (cons 10 20) (cons 30 40))
((10 . 20) 30 . 40)

; a cons cell is not an atom
CL-USER 20 > (atom (cons 1 2))
NIL

; a cons cell is not nil
CL-USER 21 > (null (cons 1 2))
NIL

; substitute an item with a new one in a tree
CL-USER 22 > (subst 30                          ; new
                    'bar                        ; old
                    '((10 . 20) . (bar . 40)))  ; tree
((10 . 20) 30 . 40)   ; also written as  ((10 . 20) . (30 . 40))

; substitute several items in a tree, using an assoc list
; to describe the substitutions
CL-USER 23 > (sublis '((a . 10) (d . 40))      ; substitutions
                     '((a . b) . (c . d)))     ; tree
((10 . B) C . 40)

Lists are then a special case of symbolic expressions. They are typically written without dots:

CL-USER 24 > '(a . (b . nil))
(A B)

Common Lisp also supports the mutating operations rplaca and rplacd of Lisp 1.5:

CL-USER 25 > (let ((c (cons 0 1)))              ; create a cons
               (print c)                        ; print it
               (print (rplaca c 'foo))          ; replace the car
               (print (rplacd c 'bar))          ; replace the cdr
               (print (eq c (rplaca c 'baz)))   ; identical ?
               (values))
(0 . 1)      ; the cons cell
(FOO . 1)    ; car replaced
(FOO . BAR)  ; cdr replaced
T            ; still the same object

Emacs Lisp

Emacs Lisp also implements the above functionality:

ELISP> (sublis '((a . 10) (d . 40))                                             
               '((a . b) . (c . d)))
((10 . b) c . 40)

Clojure

Clojure does not support these symbolic expressions as described by John McCarthy. It has no cons cells, no dot notation and does not provide the above interface. For example atom means something completely different in Clojure. cons does not create a cons cell. Lists are not made of cons cells.

In Clojure a dot is just another symbol:

user=> (count '(1 . 2))
3

There is a primitive function to construct lists:

user=> (list 1 2 3)
(1 2 3)

The result should be a list:

user=> (list? (list 1 2 3))
true

There is a function called cons:

user=> (cons 0 (list 1 2 3))
(0 1 2 3)

Somehow this is not a list:

user=> (list? (cons 0 (list 1 2 3)))
false

Basically Clojure does use different data structures (-> sequences, logical lists) with its own naming and semantics. Even if names are similar to Lisp names, don't expect that they do the same.

Scheme

The programming language Scheme also provides cons cells similar to above. It lacks some of the functions, but they can be easily implemented. For example sublis might be implemented like this in Scheme (see initdr.scm):

(define (sublis alist tree)
  (if (pair? tree)
      (cons (sublis alist (car tree))
            (sublis alist (cdr tree)))
      (if (assv tree alist)
          (cdr (assv tree alist))
          tree)))