Cons

• In Lisp, cons is a core builtin function that links two values together by creating a memory object for the first value consisting of a car (content of address register) and cdr (content of decrement register):
  • the car contains the actual value of the list item
  • the cdr contains a pointer to a cons object containing the second value being linked
  • the cons object containing the second value likewise consists of a car (the value) and a cdr (pointer to the next cons), or nil, which terminates the singly linked list
• Ordered pairs:
  • cons can be notated (cons 1 2) (creates objects for 1 and 2 and links them, terminating with nil)
  • cons can alternatively be notated with a dot: (1 . 2)
    • this is known as a “dotted pair” or a “cons pair”
• Lists:

  • The list function within Lisp uses cons internally

    (list 5 10 15)
    

    …is the same as…

    (cons 5 (cons 10 (cons 15 nil)))
    

  • this also means that cons can be used to “shift” (front-append) an element onto the front of a list

• Trees:

  • in truth, all singly linked lists are binary trees

  • thus, binary trees can be implemented with cons rather easily

    (cons (cons 1 2) (cons 3 4))
    

    ((1 . 2) . (3 . 4))