Anyway, even if you’ve never heard of Lisp you need to know two things:
- In Lisp, you work very close to your data structures. Everything, including the code that you write, is expressed as lists or variants of lists.
- The most basic data structure is what is known as a cons cell. Simply put, a cons is CONStructed from two arbitrary values, which can be either primitive or a pointers to other cons cells.
Lisp has a function called
cons which takes two arguments and
returns a cons cell. Two other functions, named
historic reasons, takes a cons cell as argument and returns the first
or second value respectively. This doesn’t seem especially exciting
but is cool, since if you have these three functions you can create
linked lists, and all other structures (trees, hash tables, etc.) can
be expressed in terms of lists.
So, in a minimal environment where you don’t even have basic data structures such as arrays, structs or objects with value slots, how exactly do create cons cells? Well, it turns out that as long as you have a facility for defining and applying functions, and a branching mechanism, you can express cons cells in a functional manner:
This idea isn’t mine; it has been around for ages in Lisp and Scheme,
find this construct very simple and beautiful. By calling the
function we create a closure with the variables
b bound to
the supplied arguments.
cons then returns an anonymous function
which is simply a promise to return either
Of course, we could to without the
cdr functions; they are
merely syntactic sugar. Since the value of
c is a function we can just
call it directly:
Finally, this is how we’d go about creating and traversing that linked list:
So, using only functions and branching logic we can derive just about any data structure. I remember learning about this in a CS class where we used a lot of Scheme, and it was mindblowing.
It still is.