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:~$

This can give you an idea of how powerful it is to have multiple contexts, and the things we can do given them.

If you look at the tinylisp code, you’ll get a sense of how cons works in terms of contexts.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s