Cons - Not Technically Fundamental

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 fundamental and/or technically:

    This declared indifference, but as I must think, covert real zeal for the spread of slavery, I can not but hate. I hate it because of the monstrous injustice of slavery itself. I hate it because it deprives our republican example of its just influence in the world ... and especially because it forces so many really good men amongst ourselves into an open war with the very fundamental principles of civil liberty.
    Abraham Lincoln (1809–1865)

    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)