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)
“It is a fundamental characteristic of civilization that man most profoundly mistrusts those living outside his own milieu, so that not only does the Teuton regard the Jew as an incomprehensible and inferior being, but the football player likewise so regards the piano player.”
—Robert Musil (1880–1942)