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

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 an 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), which 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 a nice example of how the special forms don’t have to be all that special.

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 = {0} = {\emptyset} $$

(this has 1 element - we say has cardinality 1)

Then

$$ 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!