The difference between code and data

Today I finished watching SICP 2B video and it was what inspired me to write this post.

Recently I started working on SICP (https://github.com/bor0/sicp) and I also implemented tinylisp (similar to Peter Norvig’s lis.py) in PHP (https://github.com/bor0/tinylisp).

So the 2B video ends with Abelson defining cons in terms of procedures that return other procedures. In this way, one can ask the question “What really is data?”

In almost all of the widely used languages today (JavaScript, PHP, Python), you’ll find that functions are all first-class objects, and this is all thanks to Lisp.

The contract for cons, car, and cdr is as follows:

(car (cons x y)) = x
(cdr (cons x y)) = y

And that’s all really is to data. Any kind of data can be constructed using cons, car, and cdr.
So here is how we can implement cons, car, and cdr in Lisp:

(define (cons a b)
  (lambda (pick)
    (if (= pick 1) a b)))

(define (car a) (a 1))
(define (cdr a) (a 2))

And then ask the evaluator:

> (cons 1 2)
#
> (car (cons 1 2))
1
> (cdr (cons 1 2))
2
>

One needs to take a moment here and think how these are implemented (and possibly try to reduce the examples using the substitution model to get a sense of what really is going on).

For the funs, I implemented this in PHP:

<?php
function cons($x, $y) {
    // context 1
    return function ($a) use ($x, $y) {
        // context 2
        return ($a == 1) ? $x : $y;
    };
}

function car($x) {
    return $x(1);
}

function cdr($x) {
    return $x(2);
}

$x = cons(1, 2);
var_dump($x(1));
var_dump(car($x));
var_dump(cdr($x));
boro@bor0:~$ php test.php
int(1)
int(1)
int(2)
boro@bor0:~$