Structured objects from lexical closures
2021-07-15

One of the most interesting ideas I’ve come across so far by reading SICP is how to implement objects “from scratch”. For instance, the venerable cons cell from Lisp can be constructed as follows:

(define (cons x y)
  (lambda (f) (f x y)))

(define (car z)
  (z (lambda (x y) x)))

(define (cdr z)
  (z (lambda (x y) y)))

If you can’t stand parenthesis, here’s some equivalent Python code:

def pair(x, y):
    return lambda f: f(x, y)

def first(z):
    return z(lambda x, y: x)

def second(z):
    return z(lambda x, y: y)

p = pair(4, 2)
second(p)
# => 2

Here I’ve defined a pair as a function that, given a function f as input, applies f to the two elements of the pair. These remain accessible to the function returned by cons/pair thanks to lexical scoping.

We can also have multiple fields:

(define (make-user name phone address)
  (lambda (n)
    (case n
      ((0) name)
      ((1) phone)
      ((2) address))))

(define (user-name u) (u 0))
(define (user-phone u) (u 1))
(define (user-address u) (u 2))

Example usage:

(define pippo (make-user "Pippo" "12467620823" "Via Roma"))
(user-name pippo)
;; => "Pippo"

The technique employed here is a bit different (and maybe conceptually simpler): the object is a function that takes a number as an input and returns the value of the corresponding field.

So far we’ve created simple immutable structures, but what if we want more?

(define (make-account)
  (define balance 0)

  (lambda (msg)
    (case msg
      ((balance) balance)

      ((deposit)
       (lambda (amount)
         (set! balance (+ balance amount))))

      ((withdraw)
       (lambda (amount)
         (if (> amount balance)
           (error "insufficient balance")
           (set! balance (- balance amount)))))

      (else (error "undefined property or method" msg)))))

Now the result of (make-acount) is a procedure that takes a symbol as input and returns either the account’s balance or a method on the account itself. This method is another procedure that modifies the value of the property balance, which as before is stored in a lexical closure.

(define acc (make-account))

(acc 'balance)
;; => 0

((acc 'deposit) 100)
(acc 'balance)
;; => 100

This technique is known as message passing, as we interact with the object by sending messages (in our case, symbols) and observing the result.

We can define some sugar for accessing properties and methods like this:

(define (account-balance account)
  (account 'balance))

(define (account-deposit account amount)
  ((account 'deposit) amount))

(define (account-withdraw account amount)
  ((account 'withdraw) amount))

(account-withdraw acc 25)
(account-balance acc)
;; => 75

It’s really fascinating how much you can do by simply passing around functions and little more!