Truly mind boggling ..

written by admin 2157 days ago. Last update at 2013-04-02 16:29:26. Categories Lisp.

Inspired by listening to a Podcast about Lisp and since there is quite some hype now around functional programming, I started again to read some Lisp classics, especially The Seasoned Schemer, a truly marvelous book.

Now, every Lisp dialect I know contains at least three fundamental procedures, namely cons, car and cdr. And so does Scheme, a main Lisp dialect. In the spirit of The Seasoned Schemer, we can describe what cons, car and cdr do, namely

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

So far there is nothing mind boggling, admitted. Assume now that there is no car, cdr and no cons. All we have is lambda and define where lambda allows us to express a anonymous procedure and where define allows us to give something a name. Just charged with this, can we still implement cons, car and cdr?

The boggling thing is, yes we can. Here we go:

(define cons (lambda (a b) (lambda (m) (m a b))))
(define car  (lambda (z)    (z (lambda (x y) x))))
(define cdr  (lambda (z)    (z (lambda (x y) y))))

Let’s see whether this works as expected:

;; declare a variable z to contain a tuple (1,2)
(define z (cons 1 2))
;; try car and cdr
(car z)
=> 1
(cdr z)
=> 2

It works. It’s mind boggling, isn’t it?

So how does it work anyway? The result of (cons ..) is just a procedure which happens to remember the arguments passed. That procedure is a value like any other. However, that procedure value can also be called with one argument which is expected to be a procedure again. Let’s assume that we have a procedure foo somewhere, then we can do something like ((cons 1 2) foo) and we end up in (foo 1 2), as by the definition of cons above.

So if we want to express car, then foo must be (lambda (x y) x) while in the case of cdr, foo becomes (lambda (x y) y). All what is left is to define car as procedure with one argument and calling that argument with foo, i.e.

(car z) =>
(car (cons 1 2)) =>
((cons 1 2) (lambda (x y) x)) =>
(lambda (1 2) 1) =>