← back

Closures and Objects (draft)

4 March 2015

One of the things I find the most magical about Scheme1 is how different programming paradigms can be built using nothing more than closures and lambdas.

Here, we will use lexical closures and first-class functions to build a simple, Java-like class based object system using the most basic Scheme constructs.

This is mostly rehashing a medley of (similar) approaches scattered in various papers and articles on the subject. I've distilled them into a step-by-step construction, and I hope my presentation is simple enough to convey the essence of what it means to be "object oriented".

The examples also illustrate lexical scoping cleanly. Whenever I explain Java's scoping rules and object system to beginners, I usually start with closures in Scheme then show how they map to Java. I've found that this approach is way more effective.

(aside) Basic Scheme

Functions

What is the simplest program we can write? Well, it’ll probably be something mathematical.

Identity: \(f(x) = x\)

Plus one: \(g(x) = x + 1\)

\(f(42) \Rightarrow 42\)

\(g(42) \Rightarrow 43\)

If we examine these two functions, we can identify the building blocks of the simplest programming language possible.

We have:

(In fact, we can get rid of constants and function names…)

In Scheme, we write

(define f
  (lambda (x) x))

(define (g x)
  (+ x 1))

(define answer 42)

; evaluate =>

> (f 100)
100
> (g 100)
101
> answer
42

(lambda (a1 a2 ... an)...) creates a function that takes in n parameters. That is, we abstract the notion of a function and separate it from the action of naming things. We can write a function explicitly as a lambda, or use the syntax for function definition. I’ll explicitly write lambdas to make things clear.

In general, to evaluate a function f with n arguments, you call (f arg1 arg2...). Constants like answer evaluate without parens.

Local variables

In math, we write2

let \(c = 3 \times 10^8\) in \(e = mc^2\) or

\(e = mc^2\) where \(c = 3 \times 10^8\).

In Scheme, we write

(define e
  (lambda (m)
    (let ((c 300000000))
      (* m (* c c)))))

Capturing a variable in this matter creates a closure.

That’s all we need3. Now you’re probably thinking, how the heck can we build objects out of this? We don’t have access modifiers! We don’t have this! We don’t have special syntax for constructors! Relax, and prepare to be amazed.

(Don’t worry, I’ll introduce more syntax as we need it).

Closures as Objects

To see how to build objects, we first need to define exactly what an object is. If you know Java, you'd probably be listing all the boilerplate: we need a class, subclasses, interfaces, constructors, there are static variables, instance variables, ....

None of that! Those are simply implementation details (which coincidentally happens to be shared amongst most OO languages). The plainest definition is that objects are a collection of functions and variables.

Well, we have functions and we have variables! Let's make some objects.

A singleton object with an anonymous method

Here is a Hello World singleton object, with one method that when called, prints "Hello World".

(define hello
  (lambda ()
    (displayln "Hello World")))

That's simplifying it a bit, but we can add some boilerplate to make it more uniform with the rest of our objects.

But this is the simplest building block.

A constructor

Here is Hello World as a class.

(define hello-class
  (lambda ()
     (lambda ()
       (displayln "Hello World"))))

What?! That's just a lambda returning lambda!

(aside) Lambda over Lambda

In Scheme there is no distinction between functions and values, which means that functions can be returned by other functions and be taken as input by other functions.

That's whats happening here: the first lambda, when called, gives you a lambda as result. When you call the result, then you evaluate the "method".

Why do it like this?

Each nesting of let or lambda creates a closure, which is like a box containing everything inside the let or lambda. (It's evident in the structure of the parentheses, and you can draw a literal box around it for visual aid --- those are called contour diagrams.) Inner closures have access to outer closures, but not vice versa.

Each created closure is distinct. If I have a lambda-lambda and I call it twice, I get back two different closures. Closures capture the lexical environment for the variables inside it, which allows us to . This is the basis for the environment model [1]. This is what allows us to "instantiate objects" (read on).

That's basically how Java does it as well. In Lisp, every function is a "function object" --- think a pointer to some code in the text area. Of course, you can return function pointers.

(define hi1 (hello-class))
(define hi2 (hello-class))

> (hi1)
Hello World
> (hi2)
Hello World

> (eq? hi1 hi2)
#t

Note that the functions hi1 and hi2 point to are the same. (eq? basically does pointer comparison)

Instance variables

Here's a singleton counter object that counts up.

(define counter-up-object
  (let ((count 0))
     (lambda ()
       (set! count (add1 count)) ; mutate the count variable
       count)))   ; show the count

Here's the same thing as a counter class.

(define counter-up
  (lambda ()
    (let ((count 0))
       (lambda ()
         (set! count (add1 count))
         count))))  ; show the count

(define counter1 (counter-up))
(define counter2 (counter-up))

> (eq? counter1 counter2)
#f

Why are counter1 and counter2 not equal?

Now look what happens!

> (counter1)
1
> (counter1)
2
> (counter1)
3
> (counter2)
1
> (counter2)
2
> (counter2)
3

In Java, the this keyword is generated at compile-time by inserting an implicit parameter into each method, then passing a reference of the calling object at run-time. Here, we don't need it because the instance variables are captured in the closure.

Method dispatch

Objects aren't useful if they only have a single function. Let's see how we can add multiple methods to a closure, making the counter go up and down.

Anonymously

(define counter
  (lambda ()
    (let ((count 0))
      (lambda (method)
        (case method
          ('up (lambda ()
                 (set! count (add1 count))
                 count))  ; show the count
          ('down (lambda ()
                   (set! count (sub1 count))
                   count))
          (else (error "undefined")))))))

(define counter3 (counter))
(define counter4 (counter))

Now we've rigged it so that instead of returning the function to be called, we return a selector function that expects the method name, then returns the method we were looking for.

Note that we haven't named any of the methods, only mapped them to unique symbols.

And in general, because we can create anonymous closures and functions, we can create anonymous singletons, classes... etc. The use of explicit lambdas is to emphasize this point: if you remove the (define ...) then you get an anonymous thing.

> (counter3 'up)
#<procedure:...om/_site/oop.rkt:53:28>

Oops! We got back a function of no arguments --- to call it, we need to do the equivalent of Java's counter3.up();.

counter3.up is a compile-time error in Java because it hides the actual dispatch mechanism (the symbol and implementation name are the same) --- you can only call methods.

> ((counter3 'up))
1
> ((counter3 'up))
2
> ((counter3 'up))
3
> ((counter3 'down))
2
> ((counter3 'down))
1

> ((counter4 'up))
1
> ((counter4 'down))
0
> ((counter4 'down))
-1
> ((counter4 'up))
0
> ((counter4 'down))
-1

Questions4

If you were to implement this in C using structs and function pointers, what operation does each pair of parens in ((counter3 'up)) correspond to?

What about (counter)? (counter3 'up)?

Named functions

The classic SICP [1] way.

(define counter
  (lambda ()
    (let ((count 0))

      (define up
        (lambda ()
          (set! count (add1 count))
          count))

      (define down
        (lambda ()
          (set! count (sub1 count))
          count))

      (lambda (method)
        (case method
          ('up up)
          ('down down)
          (else (error "undefined"))))
)))

Questions How would you make a method private?

We can also do it without a dispatch function:

Hash table

(define counter-3
  (lambda ()
    (let ((count 0))
      (make-hash
       `((up .
             ,(lambda ()
                (set! count (add1 count))
                count))

         (down .
               ,(lambda ()
                  (set! count (sub1 count))
                  count)))))))

(hash-ref (counter-3) 'up)

So, what exactly is an object? A closure where you can index into specific elements.

Static variables

What if we want a variable to be shared across all instances of a class? That's easy enough, we just need to move the lexical scope of the let.

(define global-state
  (let* ((global 1000)
         (set-global (lambda (x)
                        (set! global x)
                        global))
         (get-global (lambda () global)))

    (lambda ()
      (lambda (sel)
        (case sel
          ('set set-global)
          ('get get-global)
          (else (error "undefined")))))))

(define glo1 (global-state))
(define glo2 (global-state))

> ((glo1 'set) 42)
42
> ((glo2 'get))
42

Questions

Does it matter what scope we define our functions in?

What is the equivalent definition of the global-state class in Java?

What happens if we move the let above the definition of global-state?

Putting it all together

(define global-local-state
  (let* ((global 1000)
         (set-global (lambda (x)
                       (set! global x)
                       global))
         (get-global (lambda () global)))

    (lambda ()

      (let* ((local 9000)
             (set-local (lambda (x)
                           (set! local x)
                           local))
             (get-local (lambda () local)))

        (lambda (sel)
          (case sel
            ('setGlobal set-global)
            ('getGlobal get-global)
            ('setLocal set-local)
            ('getLocal get-local)
            (else (error "undefined"))))
))))

(define gls1 (global-local-state))
(define gls2 (global-local-state))


> ((gls1 'getGlobal))
1000
> ((gls2 'getGlobal))
1000
> ((gls2 'setGlobal) 56)
56
> ((gls1 'getGlobal))
56
> ((gls2 'getGlobal))
56

> ((gls1 'getLocal))
9000
> ((gls1 'setLocal) 'hello)
'hello
> ((gls2 'getLocal))
9000

;;; TODO TODO TODO TODO

Composition

Suppose we wanted to use a counter in a clock object.

Inheritance

Wrapping it up with macros

Now we'd want to abstract all that boilerplate, and instead write this:

(class Shape                    ; does not extend any class
                                ; no constructor/default vars
  (method pub show (num)
    (displayln num))
)

(class Square extends Shape
   (ctor '((slen . 10)))        ; default modifiable instance variables as assoc list
   (var pri sides 4)            ; other instance variables
   (method pub area ()
     (* sides slen))
)

(define sq1 (Square '((slen . 15))))
(sq1 'area ())                  ; call a method
(sq1 'show (4))                 ; call inherited method

All the code [oop.rkt][]

Afterward

It seems that if we constrain ourselves to a very specific style and structure of Scheme, we recover not only class-based objects, but basically the essence of Java.

Now that you've seen how OOP can be built from a more general language, would you like to learn about the other things it can do?

Thanks to Bryan Garza for reading early drafts and identifying poor exposition, as well as for conversations on Lisp programming in general.

Further reading

I haven't read all of this, but anything I've written here has to have been done before...

[1] SICP Chapter 3: Modularity, Objects, and State. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-19.html#%_chap_3

[2] Object Oriented Style, D. P. Friedman. http://www.cs.indiana.edu/~dfried/ooo.pdf

[3] Scheme with Classes, Mixins, and Traits, M. Flatt, et al. http://www.cs.utah.edu/plt/publications/aplas06-fff.pdf

[4] Scheming with objects. ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/swob.txt

[5] Objects are a poor man’s closures. http://okmij.org/ftp/Scheme/oop-in-fp.txt

[6] Purely-functional Object-Oriented System in Scheme. http://pobox.com/~oleg/ftp/Scheme/pure-oo-system.scm

[7] http://c2.com/cgi/wiki?ClosuresAndObjectsAreEquivalent

[8] Let over Lambda, Chapter 2: Closures. http://letoverlambda.com/index.cl/guest/chap2.html

[9] Paul Graham on using closures instead of objects. http://paulgraham.com/pfaq.html


  1. Here I use Scheme to mean Scheme-like Lisps. I use Racket.

  2. This is (nearly) valid Haskell...

  3. Yes, just this slightly sugared version of the lambda calculus is enough.

  4. ((counter3 'up)) -- the inner parens is the selector, counter3.up or counter3->up; outer corresponds to method invocation, counter3.up()