Data Is Code
Code is just smart data, and data is just dumb code.
- Structure and Interpretation of Computer Programs
I’m going to try to convince you that data is code. Strap yourselves in!
A cons cell is a way of representing a pair, and it has two operations,
cdr, to access the first and second elements of the pair respectively. In Python, we could construct and access cons cells as follows:
cons = lambda a: lambda b: (a, b) car = lambda cell: cell cdr = lambda cell: cell
Let’s create a pair and get the second element:
>>> p = cons(1)(cons(2)(())) >>> car(cdr(p)) 2
It turns out that cons cells are all you need to implement singly linked lists. For example, lists in Lisp are implemented as a series of nested cons cells. A list is either empty (represented above by
()) or a cons cell where the first element of the pair is the head of the list and the second element of the pair is the rest of the list. Using our above definitions in Python, the list
[0, 1, 2, 3] would be represented as (0, (1, (2, (3, ())))). In code, this would be:
One way of visualising the above list is as follows:
cons / \ 0 cons / \ 1 cons / \ 2 cons / \ 3 ()
Suppose we wanted to access the second element of this list. We could express this as the
car of the
cdr of this list. In code:
>>> example = cons(0)(cons(1)(cons(2)(cons(3)(())))) >>> car(cdr(example)) 1
So far we’ve defined functions that wrap Python’s tuples, and we’re still in data land, working with those tuples. But it doesn’t have to be this way.
You may have noticed that my definitions above were all functions of one argument. This was not entirely coincidental: cons cells as described above are very similar to Church pairs, which are a way of representing pairs in the lambda calculus. Let’s make a minor change to the above definitions:
pair = lambda a: lambda b: lambda f: f(a)(b) fst = lambda p: p(lambda a: lambda b: a) snd = lambda p: p(lambda a: lambda b: b) nil = lambda a: a
We can recreate the pair above:
>>> p = pair(1)(pair(2)(nil)) >>> fst(snd(p)) 2
p is now a function, but it is representing the same data as above.
As an aside, the functions we use in
snd are Church booleans that encode
false in the lambda calculus. We can rewrite our definitions with this new knowledge:
true = lambda a: lambda b: a false = lambda a: lambda b: b fst = lambda p: p(true) snd = lambda p: p(false)
We can perform the same operations as before to get the second element of our list:
>>> example = pair(0)(pair(1)(pair(2)(pair(3)(nil)))) >>> fst(snd(example)) 1
Now we’ve moved to function land, and there are no tuples in sight. All we need are functions of one argument, which is convenient because this is all that lambda calculus gives us. Fortunately, lambda calculus is Turing complete and therefore enough.
Our code is represented as bits in memory i.e. data, but our data can be represented as functions i.e. code. You might say that bits and bytes are the lowest level representation and therefore somehow more fundamental than code, but even our data is just an undistinguished pattern of 1s and 0s without some code to make sense of it. It really is turtles all the way down.