[mononcqc]

even cons, car and cdr can be done with lambda, which adds to the mind bending.

    > (define (cons a b) (lambda (f) (f a b)))
    > (define (car c) (c (lambda (a b) a)))
    > (define (cdr c) (c (lambda (a b) b)))
    > (car (cdr (cons 1 (cons 2 (cons 3 '())))))
    2

[eru]

And of course, even lambda is unnecessary. Using two combinators, customarily called s and k suffices:

  k x y = x
  s x y z = x z (y z)

This system is called the SKI-calculus (http://en.wikipedia.org/wiki/SKI_combinator_calculus). The I in SKI stands for the identity, and can be expressed in terms of s and k.

As an example, here is the y-combinator:

  y = s s k (s (k (s s (s (s s k)))) k)