Not Technically Fundamental
Since Lisp has first-class functions, all data structures, including cons cells, are not fundamentally necessary to the language, since all data structures can be implemented using functions. For example, in Scheme:
(define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p))) (define (cdr z) (z (lambda (p q) q)))The above code re-implements the cons, car, and cdr operations, using a function as the "cons cell". This is the usual way of defining data structures in pure lambda calculus, an abstract, theoretical model of computation that is closely related to Scheme.
This implementation, while academically interesting, is impractical because it renders cons cells indistinguishable from any other Scheme procedure, as well as introducing unnecessary computational inefficiencies.
However, the same kind of encoding can be used for more complex algebraic data types with variants, where it may even turn out to be more efficient than other kinds of encoding. This encoding also has the advantage of being implementable in a statically typed language that doesn't have variants, such as Java, using interfaces instead of lambdas.
Read more about this topic: Cons
Famous quotes containing the words technically and/or fundamental:
“When you see something that is technically sweet, you go ahead and do it and you argue about what to do about it only after you have had your technical success. That is the way it was with the atomic bomb.”
—J. Robert Oppenheimer (1904–1967)
“We are told to maintain constitutions because they are constitutions, and what is laid down in those constitutions?... Certain great fundamental ideas of right are common to the world, and ... all laws of man’s making which trample on these ideas, are null and void—wrong to obey, right to disobey. The Constitution of the United States recognizes human slavery; and makes the souls of men articles of purchase and of sale.”
—Anna Elizabeth Dickinson (1842–1932)