Monday, September 10, 2007

Got Closures ? Have OO

In the classical object oriented model, an object encapsulates local state (instance variables) and contains a pointer to the shared procedures. These procedures are the methods, which operate on the encapsulated state, that forms the environment of the object. Each method can declare local variables as well as look up for additional state information from the shared environment based on lexical scoping rules. So we have the object as the combination of the environment and the set of methods that operate on the environment. Class based languages like Java and C++ provide another abstraction - the class, which instantiates objects by initializing the environment and setting up appropriate pointers to the shared procedures.

But what if my programming language is classless ? One of the best examples of this is the Javascript language. It is based on prototypes, without the class structure and supports higher order functions and lexical closures. How do I implement object-orientation in Javascript ? Javascript is a prototypal language without any built in support for classes. This post attempts to look into OO through a different looking glass, a quite unnatural source, a quite different language and a very much different programming paradigm. In the absence of first class support for the classical OO paradigm, this post looks at alternative means of implementing encapsulation and object-orientation while designing real world abstractions. The language used is Scheme, popularly referred to as a functional language, and the implementation addresses all issues faced by the other numerous classless languages mentioned above.

The basic theme of the following discussion is from SICP, a true classic of Computer Science in the domain of programming languages. In case you have any doubt regarding the credibility of SICP, please go through the first two customer reviews of this book in Amazon.

Object Orientation - the Scheme way !

Let us look at the following abstraction of a bank account in Scheme ..

(define make-account
  (lambda (account-no account-name balance)

    ;; accessors
    (define (get-account-no) account-no)
    (define (get-name) account-name)
    (define (get-balance) balance)

    ;; mutators
    (define (set-account-name! new-account-name)
      (set! account-name new-account-name)

    ;; deposit money into account
    (define (deposit! amount)
      (set! balance (+ balance amount))

    ;; withdraw money
    (define (withdraw! amount)
      (if (>= balance amount)
          (begin (set! balance (- balance amount))
          "Insufficient funds"))

    ;; the dispatcher
    (define (self message)
      (case message
        ((no)         get-account-no)
        ((nm)         get-name)
        ((balance)    get-balance)
        ((set-nm!)    set_account-name!)
        ((withdraw!)  withdraw!)
        ((deposit!)   deposit!)
        (else (error "unknown selector" message))))

Every time we call make-account, we get back a dispatch function, every instance of which shares the same code, but operates on the different set of data supplied to it, which forms the execution environment.

;; creates an account a1
(define a1 (make-account 100 "abc" 0))

;; creates an account a2
(define a2 (make-account 200 "xyz" 0))

;; fetches the account-no of a1 -> 100
((a1 'no))

;; sets the account-name of a1 to "pqr"
((a1 'set-nm!) "pqr")

That is, we have two separate objects for the account abstraction and a bunch of shared methods to operate on each of them. A clean separation of code and data, a nice encapsulation of state. The arguments passed to the make-account invocation, account-no, account-name and balance are completely encapsulated within the abstraction and can only be accessed through the shared procedures.

The Secret Sauce

Lexical closures! In the above code snippet, all free variables within the methods are looked up from the environment of execution based on the lexical scoping principles of Scheme. This is exactly similar to the classical OO model that we discussed in the beginning. In the model with first class objects, we have

  • the environment formed by the instance variables, encapsulating local state per object and

  • the methods, which are shared across objects.

These two orchestrate the mechanism through which behaviors are implemented in abstractions. OTOH in languages like Scheme and Javascript, the corresponding roles are played by

  • the execution context, where the procedures look up for free variables and

  • the procedures themselves.

Hence closures play the same role in the Scheme based implementation that objects play in a classical one with Java or C++. Here is what wikipedia has to say :

a closure is a function that is evaluated in an environment containing one or more bound variables. When called, the function can access these variables. The explicit use of closures is associated with functional programming and with languages such as ML and Lisp. Constructs such as objects in other languages can also be modeled with closures.

What about Inheritance ?

We can implement inheritance in the above abstraction by using the delegation model. This is an object based implementation, similar to what we do in classless languages like Javascript. Simply incorporate the specialized behaviors in a new abstraction and delegate the common behaviors to the base abstraction. The following example implements a minimum-balance-checking-account, which has an additional restriction on the withdraw method in the form of a minimum balance check. It delegates all common behavior to the earlier abstraction make-account, while itself implements only the specialized functionality within the withdraw method.

(define make-min-balance-account
  (lambda (account-no account-name balance)
    (let ((account (make-account account-no account-name balance)))

      ;; implement only the specialized behavior
      ;; delegate others to the base abstraction
      (define (withdraw! amount)
        (let ((bal ((account 'balance))))
          (if (>= (- bal amount) 1000)
              (begin ((account 'withdraw!) amount)
                     ((account 'balance)))
              "Min balance check failed")))

      (define (self message)
        (case message
          ((withdraw!)    withdraw!)
          (else (account message))))

But Scheme is a Functional Language

Programming without assignments is functional programming, where procedures can be viewed as computing mathematical functions, without any change in the local state. Scheme is a multi-paradigm language and the above implementation uses assignments to mutate the local states of the abstraction. The set! operation used in the above implementation helps us model local states of objects. However, it is absolutely possible to provide a completely functional-OO system implementing polymorphism using Scheme that does not have a single assignment or mutator operation. See here for a sample implementation.

Are Closures equivalent to Objects ?

This is a very interesting topic and has been extensively discussed in various forums in the theory of programming languages. While objects are often referred to as "poor man's closures", the converse has also been shown to be true. Instead of trying to mess around with this tension between opposites, let me point you to a fascinating note on this topic in one of the forums of discussion.


Anonymous said...

I found this post via, and you just blew my mind. What a great observation! Really insightful.

There seems to be a small typo in the first code segment:

((set-nm!) set_account-name!)

... should be set-account.

Thanks for a great post.

Unknown said...

LOVED the Koan.
Anyhow, I don't see the point on using a functional language for OO programming :) feels as akward as trying to use a typical OO language for functional programming (or like C for OO programming). It can be done, but why? :-D
They're different paradigms, I think we should use the language that supports the paradigm we're using. OO has the advantage of having a solid Analysis and Design methodology behind it, though.

Unknown said...

@Gabriel: Absolutely! Can't agree more. OO languages offer great modularity in analyzing large systems. Things become a bit fuzzy for multiparadigm languages like Scheme. Though the very fact that you can implement objects in Scheme using the circuitous syntax proves that closures are poor man's objects. And, of course try to implement closures in C++ or Java. You will realize that objects are poor man's closures. The KOAN!

Justin said...

If you are interested in this stuff, check out "The Art of the Metaobject Protocol." It's all about how a complete object oriented system was implemented in Lisp. Very interesting read.

Anonymous said...

I appreciate the attempt, but what you have produced are not objects, and certainly they're not the protos you find in prototype languages like JavaScript. Instead they are commonly known as "structs" or "records" or "modules", that is, objects minus inheritance. Sometimes OO-- languages along these lines are called "Object-Based" languages. The last one I can recall: HyperTalk.

Your attempt isn't new: both Paul Graham and Peter Norvig have noted the identical relationship between closures and what they (somewhat embarassingly) mistook for OO. But inheritance creates some ugly wrinkles which are not elegantly solved with simple lexical closures.

That being said, you can certainly create elegant prototype-style languages in Lisp in tiny amounts of code, and maybe one day the linked example will be ported to Scheme if Scheme advances to the point of allowing structures with custom print properties.

Unknown said...

This post has been picked up by reddit .. enjoy the spice here.

Maxim Ananyev said...

Great posting!

Could you please tell what widget do you use for that syntax coloring and scrollbars?