Simple OO Inheritance in Scheme (SICP Redux)

Over on the reddit thread for my last blog post, there were a few requests for a more full-featured object oriented implementation.  I've been looking for a good excuse to brush up on my Lisp, so I've implemented a couple of examples.

There's no Haskell content here, so only follow the cut if you're interested in following up on the last post. 

Reason #23 you should read Abelson & Sussman

I'd forgotten just how great The Structure and Interpretation of Computer Programs is. I'm working my way through my ancient copy of the first edition. As their example of object-oriented programming in Lisp, you might expect that they would use CLOS, or maybe Symbolics Common Lisp with its nifty mixins*. No, they go for the throat:

(define (make-account balance)
  (define (withdraw amount)
     (if (>= balance amount)
         (sequence (set! balance (- balance amount))
                   balance)
          "Insufficient Funds"))
  (define (deposit amount)
     (set! balance (+ balance amount))
     balance)
  (define (dispatch msg)
     (cond ((eq? msg 'withdraw) withdraw)
           ((eq? msg 'deposit) deposit)
           (else (error "Unknown request"
                        msg))))
  dispatch)


==> (define acc (make-account 100))

==> ((acc 'withdraw) 50)
50

==> ((acc 'withdraw) 60)
Insufficient Funds

The beauty of this example is that it is the object-oriented programming model distilled right down to its essence.  It is succint and to the point.  No need to explain about how the compiler is providing syntactic sugar, it's just straight to the bare metal: an object is a collection of functions and data tied together -- a collection of related closures, really. 

Additionally, their discussion of the OO paradigm doesn't start with talk of "objects" and "messages", it starts with a well-grounded discussion of the programming model and its implications for the structure of your code.  I like that, because that's what Object-oreinted programming is.  All that business about objects, messages, and domain models -- that's how we choose to explain object-oriented programming.   

There's other great stuff in the book, of course.  This is just the bit that I'm loving right now. 

For the Lisp-challenged, here's how the code works:  make-account is a function that returns an anonymous function, let's call it mike.  In the code above, mike is given a name by being bound to acc.  The purpose of  mike is to dispatch calls to withdraw or deposit.  When you call mike, you will pass in either 'withdraw or 'deposit.  Based on which of those you pass in, mike will then return one of the mike-local functions  withdraw or deposit.  This returned function takes a number and returns a number, as shown in the last couple of interpreter commands above.  

Coming soon:  a couple of more blogs posts inspired by SICP.  So why aren't you getting inspired?  Read it already. 


*Well, other that they are using Scheme.   

More on Lambda Calculus

It's disappointing how many Lambda Calculus "tutorials" and "introductions" are really bad about actually being tutorials or introductions.  It reminds me of the book for my undergrad class in partial differential equations.  The book was thin, concise, and to the point.  I'm sure it was readily understandable...to the professor who selected it.  To the students, it was completely dense and incomprehensible.  Too many of the Lambda Calculus tutorials are like that.  Specifically, they too often use symbology and terminology without explaining it.  Hint:  if I understood it, I wouldn't be looking for an introduction to the material. 

Happily the first two links from my last article are well done, even if a bit limited in scope.  For a new student, I would recommend starting with them and then following up with this paper.  It is clearly the most newbie-friendly of any material I have found that treats the subject with any depth (though even that paper is not perfect in this regard).  For the new student, my recommendation would be to read these three pieces, in the order in which they are linked here.

Cliff's Notes squared: Lambda Calculus

I say Cliff's Notes squared, because this is the Cliff's Notes guide to the Cliff's Notes.  

Up til now, I've mostly shied away from anything that had any significant lambda calculus content -- and when I didn't shy away from it, got nothing out of it.  I read one or two "intro" pieces, but they didn't really click for me.  Happily, I've recently found some stuff that works for me.  For a gentle introduction, I can recommend the following. 

This introduction to the lambda calculus is short and sweet.  It doesn't cover a lot of ground but covers it well, and the exercises really work to give you some insight into the fundamentals.  

Another good short intro is here.  It does a great job of explaining why things are done the way they are, including strategies for manipulating lambda expressions.   The exercises are fewer and I found them to less well integrated into the text. I think it's a great companion to the first article -- it provides a bit more explanation where the first article relies a bit more on the reader's intuition.  Given that, if you find yourself stumped by a section in the first article, look here for illumination. 

These class notes are a good follow up to those two articles.  I read them straight through up to page 13, when the S-combinator threw me for a bit of a loop.  I wanted to understand it a bit better before before moving on, so I stopped there and did a bit of further research before continuing.  This was a good thing, as the class notes have introduced Combinatory Logic without letting you know that they have veered from strict Lambda Calculus.

Let me talk about a newbie's view of the formulae in Lambda Calculus and in Combinatory Logic.  The S combinator is defined as S x y z = x z (y z).  This may be a bit confusing at first, it certainly was for me.  Even though I'm pretty handy with higher order functions in practice, and function composition seems as natural as can be, I still get thrown for a loop when I see an equation like this that doesn't make sense unless it's arguments are themselves functions (see the entries on "The Type of []" and "map map and Type-Wrangling"  for similar issues).  Useful exercise: with the definitions on pages 12 and 14 of the class notes, derive the equivalencies for fst and snd on the bottom of page 14. 
 
Maybe soon I can read Edward Yang's blog and get something out of it.