---
title: You Could Invent Object-Oriented Programming
teaser: In which we recreate OO using lambdas and closures.
tags: closure,lisp,oop
author: Mike Burns
published_on: 2014-12-18
---

Object-oriented programming was established in the Smalltalk programming
language by Dr. Alan Kay in the early 1980s, with heavy inspiration from Simula
and LISP. Dr. Kay describes,

<blockquote cite="http://www.purl.org/stefan_ram/pub/doc_kay_oop_en">
OOP to me means only messaging, local retention and protection and  hiding of
state-process, and extreme late-binding of all things. It can be done in
Smalltalk and in LISP.
<footer><cite><a href="http://www.purl.org/stefan_ram/pub/doc_kay_oop_en">Re:
Clarification of "object-oriented"</a></cite></footer>
</blockquote>

Let's create an object from scratch to see what's going on underneath.

This blog post is going to use a subset of the Scheme programming language.
Scheme is a LISP with some properties that will prove useful:

* Block syntax for introducing lexical scoping (`let`).
* Procedure objects that close over a surrounding environment (`lambda`).
* Latent, dynamic typing.

## One Minute Intro to Scheme

To create a symbol, use a single quote in front:

```scheme
'hello
```

To assign a name for a value, use the `define` form:

```scheme
(define x 8)
```

To apply a function to values, use a prefix notation:

```scheme
(+ 4 5 10 (- 20 3 10))
```

To create a procedure object, use the `lambda` form:

```scheme
(lambda (x) (display x))
```

To create a lexical block, use the `let` form:

```scheme
(let ((x 8)
      (y 10)
      (add100 (lambda (n) (+ n 100))))
 (* x y (add100 30)))
```

To mutate a value, use the `set!` form:

```scheme
(define m 20)
(set! m (* m 2))
```

Here are example functions:

```scheme
;; make-user : String Number -> (list-of any)
;; Create a user record with a given name and age.
(define make-user
   (lambda (name age)
     (cons 'user (cons name (cons age null)))))

;; display-name : (list-of any) -> String
;; Print the name of the user. Raises the error 'not-a-user if passed
;; something besides a user record.
(define display-name
  (lambda (user)
    (cond
      ((eq? (first user) 'user)
       (display (first (rest user))))
      (else
        (error 'not-a-user)))))
```

Great, you're now a Scheme expert.

## Inverting It

Let's see if we can get rid of that `cond` that checks the type.

We'll start with changing `make-user`. This is how we used it:

```scheme
(define mark (make-user "Mark" 18))

(display-name mark)
;; Mark
```

We'll start with one small change:

```scheme
(define mark (make-user "Mark" 18))

(display-name (mark))
;; Mark
```

That is, the `make-user` function now produces a function instead of a list.
This function takes no arguments but when called it produces the desired list.
Functions like `mark` are called thunks (as in, the past tense of "to think").

```scheme
;; make-user : String Number -> (-> list-of any)
;; Create a user record with a given name and age.
(define make-user
  (lambda (name age)
    (lambda ()
      (cons 'user (cons name (cons age null))))))
```

For our next trick, we can pass an argument to `mark`, our prior thunk:

```scheme
(define mark (make-user "Mark" 18))

(mark 'display-name)
;; Mark
```

This treats `mark` as an object that responds to messages, in this case the
`'display-name` message.

```scheme
;; make-user : String Number -> (Symbol -> any)
;; Create a user object with a given name and age. This object responds to
;; 'display-name. Raises the error 'message-not-understood for all other
;; messages.
(define make-user
  (lambda (name age)
    (lambda (message)
      (cond
        ((eq? message 'display-name)
         (display name))
        (else
          (error 'message-not-understood))))))
```

We're going to walk through this function before moving on.

`make-user` is a function that takes `name` and `age`. This function produces
another function, which we called `mark` above.

`mark` is a function that takes a `message` and dispatches based on it. So far
it only knows one message: `'display-name`. When given that message it displays
the `name`; for everything else it raises an error.

This is `mark`, with one thing missing:

```scheme
(lambda (message)
  (cond
    ((eq? message 'display-name)
     (display name))
    (else
     (error 'message-not-understood))))
```

The missing component is the closure. Note that `name` is a free variable in
the above `lambda` -- it's referenced but undefined. That's because it's
defined in the outer scope (in this case, the `make-user` `lambda`).

## Set It

The rifle on the wall here is `set!`. Let's introduce a `'set-name!` message to
our object, which takes an argument:

```scheme
(define mark (make-user "Mark" 18))

(mark 'display-name)
;; Mark

(mark 'set-name! "Mike")

(mark 'display-name)
;; Mike
```

First, here is another piece of syntax: the `lambda` expression can take any
number of arguments if we separate the final argument with a `.` (period). The
final argument is then passed as a list.

```scheme
(define super-cons
  (lambda (a b . others)
    (cons a (cons b others))))

(super-cons 1 2 3 4 5) ;; => '(1 2 3 4 5)
```

So let's change `mark` to take not just a message but any number of arguments:

```scheme
(lambda (message . args)
  (cond
    ((eq? message 'display-name)
     (display name))
    (else
     (error 'message-not-understood))))
```

And pass the first argument to `set!` when the message `'set-name!` comes in:

```scheme
(lambda (message . args)
  (cond
    ((eq? message 'display-name)
     (display name))
    ((eq? message 'set-name!)
     (set! name (first args)))
    (else
     (error 'message-not-understood))))
```

As before, this is missing its closure:

```scheme
(define make-user
  (lambda (name age)
    (lambda (message . args)
      (cond
        ((eq? message 'display-name)
         (display name))
        ((eq? message 'set-name!)
         (set! name (first args)))
        (else
         (error 'message-not-understood))))))
```

## Playing With Closures

All of these concepts are distinct, small components that can be composed.
Let's make a number incrementer using what we've learned.

First, another piece of syntax. To do multiple things in succession, discarding
all but the final return value, use the `begin` form:

```scheme
(begin
  (display "hello")
  (display "world"))
```

First, a number:

```scheme
(define make-incr 1)

make-incr ;; => 1
```

Wrap it in a `lambda`:

```scheme
(define make-incr (lambda () 1))

(define gimme-an-n! make-incr)

(gimme-an-n!) ;; => 1
(gimme-an-n!) ;; => 1
```

Small refactoring: use a `let` to hold the return value:

```scheme
(define make-incr
  (lambda ()
    (let ((n 1))
     n)))

(define gimme-an-n! make-incr)

(gimme-an-n!) ;; => 1
(gimme-an-n!) ;; => 1
```

Now we can use `set!` to change it each time:

```scheme
(define make-incr
  (lambda ()
    (let ((n 0))
     (begin
       (set! n (+ n 1))
       n))))

(define gimme-an-n! make-incr)

(gimme-an-n!) ;; => 1
(gimme-an-n!) ;; => 1
```

... that's not what we wanted. Let's step through it:

```scheme
(define gimme-an-n! make-inc)
```

`gimme-an-n!` is the result of calling `make-incr`. This is a function. Now we
call it:

```scheme
(gimme-an-n!) ;; => 1
```

When we run this function, it first creates an environment with `n` set to
`0`.  Then, it increments `n` and returns it. When we call this function
again, it does it all over again. However, we only want to create the
environment once.

To fix this, we need our function to close over the environment so that we
re-use the same environment on every function call. Swap the `let` and the
`lambda`:

```scheme
(define make-incr
  (let ((n 0))
    (lambda ()
     (begin
       (set! n (+ n 1))
       n))))

(define gimme-an-n! make-incr)

(gimme-an-n!) ;; => 1
(gimme-an-n!) ;; => 2
```

When we run `make-incr`, first it create an anonymous environment with `n` set
to `0`. Then it returns a function that closes around this environment. This
function is assigned to `gimme-an-n!`. The first time we call it, it increments
the `n` in the environment and returns it. The second time it does the same,
re-using the existing environment. Therefore it increments the environment it
closes around.

Thus we have implemented messaging, local retention and protection of
state-process, and extreme late-binding. This is the core of object oriented
programming: closures and message passing.