Pairs as lambdas

The SICP video lectures talk about how data is not intrinsic. That is, once you have lambda, you have enough to create all the data structures you want. Of course that is without caring for efficiency.

Here’s some code I was mucking around with the other night:

; Implement pairs (cons, car, cdr) in terms of lambda.

(define cons
  (lambda (a b)
    (lambda (x)
      (cond ((eq? x 'car) a)
            ((eq? x 'cdr) b)
            (else (error "bad dispatch"))))))

(define car
  (lambda (pair) (pair 'car)))

(define cdr
  (lambda (pair) (pair 'cdr)))

; Example to type into the scheme repl.
(define a (cons 3 4))
a                 ; => a procedure
(car a)           ; => 3
(cdr a)           ; => 4
(a 1)             ; error "bad dispatch"

; The following attempts to work out what "error" does. This example will
; probably display "1" and then exit to the repl with "bad dispatch" error.
; It may not as Scheme doesn't define the order of evaluation for arguments to
; a combination.
(+ (display "1\n") (a 99) (display "2\n"))

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: