Back to notes


Keywords: lisp, construct, memory, objects, pointers, singly linked lists, higher order functions
  • 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))