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.
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.
constants, e.g. \(42\)
variables, e.g. \(x\)
function definition, e.g. \(g(x) = x + 1\)
function application, e.g. \(f(42)\).
(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
n arguments, you call
(f arg1 arg2...). Constants like
answer evaluate without parens.
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).
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.
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.
Here is Hello World as a class.
(define hello-class (lambda () (lambda () (displayln "Hello World"))))
What?! That's just a lambda returning 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
lambda creates a closure, which is like a box containing everything inside the
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 . 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
hi2 point to are the same. (
eq? basically does pointer comparison)
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
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.
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.
(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 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
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?
The classic SICP  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:
(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.
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
(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
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
(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
Suppose we wanted to use a counter in a clock object.
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]
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.
I haven't read all of this, but anything I've written here has to have been done before...
 SICP Chapter 3: Modularity, Objects, and State. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-19.html#%_chap_3
 Object Oriented Style, D. P. Friedman. http://www.cs.indiana.edu/~dfried/ooo.pdf
 Scheme with Classes, Mixins, and Traits, M. Flatt, et al. http://www.cs.utah.edu/plt/publications/aplas06-fff.pdf
 Scheming with objects. ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/swob.txt
 Objects are a poor man’s closures. http://okmij.org/ftp/Scheme/oop-in-fp.txt
 Purely-functional Object-Oriented System in Scheme. http://pobox.com/~oleg/ftp/Scheme/pure-oo-system.scm
 Let over Lambda, Chapter 2: Closures. http://letoverlambda.com/index.cl/guest/chap2.html
 Paul Graham on using closures instead of objects. http://paulgraham.com/pfaq.html
This is (nearly) valid Haskell...↩
Yes, just this slightly sugared version of the lambda calculus is enough.↩
((counter3 'up)) -- the inner parens is the selector,
counter3->up; outer corresponds to method invocation,