## Creating Something (In fact everything) out of nothing, Twice

October 25th 2010 02:39 pm

I am reading through SICP with some of the guys in work and got to a bit that fascinated me and reminded me of my previous life as a mathematician.

The basic data structure in Scheme is the cons cell, essentially representing a ordered pair. So

```> (cons 2 3)
(2 . 3)
```

creates the pair (2 . 3)

Lets call that a,

`> (define a (cons 2 3))`

There are 2 other functions that act on these cons cells, car returns the first, cdr returns the second

```> (car a)
2

> (cdr a)
3```

You can build lists by chaining these cons cells and unpick the contents by using car and cdr

```> (define b (cons 3 a))
> b
(3 2 . 3)

> (car b)
3

> (cdr b)
(2 . 3)

> (cdr (cdr b))
3```

The interesting bit is at p91 of the book where it breaks down the distinction between procedures and data

```(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "arg no 0 or 1" m))))
dispatch)
```

So here cons is a function of x and y as you would expect. The trick is that its return value is a function (internally called dispatch) of one argument that returns x if passed 0 and y if passed 1, otherwise it throws an error.

Now car and cdr can be defined

```(define (car z) (z 0))

(define (cdr z) (z 1))
```

So car takes z as an argument and tries to apply z to 0, while cdr applys it to 1. While car and cdr will accept any function as an argument it makes sense if z is the cons of something as before.

As an example

`(car (cons 1 2))`

car will pass 0 to (cons 1 2)
(cons 1 2) returns 1,
similarly

`(cdr (cons 1 2))`

returns 2 as cdr will pass 1 to (cons 1 2)

This is not how the interpreter actually works, just the introduction to the idea of code as data (as code etc) in Lisp. This is the feature that sets it aside from other languages, in particular code is not parsed, jut loaded up as it is a valid data structure itself and allows for the powerful macro systems usually seen in Lisps.

Now for twice, it reminded me of some Set Theory, in particular forming the Natual Numbers in terms of sets.

We define 0 to be the empty set
$0 = {\emptyset}$.

Then we can define 1 to be
$1 = \{0\} = \{\emptyset\}$
(this has 1 element – we say has cardinality 1)

Then 2 is
$2 = \{0, 1\} = \{\emptyset, \{\emptyset, \{\emptyset\}\}\}$
Notice this has cardinality 2 and is formed as the set containing all the previous numbers.

So we have all positive whole numbers. You can then define arithmetic and number theory in terms of these sets.

See this site for a nice introduction to set theory (it also begins by defining ordered pairs)

Loving SICP, got to do some Induction for the first time in ages last night!

Posted by tom under lisp & SICP | 1 Comment »

### One Response to “Creating Something (In fact everything) out of nothing, Twice”

1. Ankit Jain responded on 24 Sep 2011 at 5:48 am #

I was reading up on the same. Its fascinating.

You could also look up on “Church numerals”. The example from Set Theory mimics the lambda functions used in Church numerals.

Thanks.