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.

Assignment Considered Harmful

One of the things I got myself for Christmas was Chris Reade's Elements of Functional Programming. Despite being nowhere near done with some other books I'm working through, I cracked it open today.  Page three has the following gem: "From this point of view, it is argued that the assignment statement is considered harmful in high-level languages, just as the 'goto' statement was considered harmful for structured programming in the sixties (Dijkstra, 1968).  Note that it is the use of assignments that takes most of the blame for not allowing separation of concerns when programming."

That's a pretty bold statement, no?  However, Chris Reade is somewhat less widely read than E. Dijkstra; googling for either "assignment considered harmful" (or variants) shows no front page hits that trace back to Reade.  Much as I am inclined to agree with that statement, I recognize that my opinion is rooted in many years' experience with the complexities involved in programming with traditional assignment semantics, and have not had nearly as much opportunity to see the downside of purely functional programming. 

So what did I find when I googled for "assignment considered harmful?"  Well, not much that was actually on topic.  The functional programming outlook was represented by this blog post.  From a different viewpoint, there was this paper, which looks at four different semantics for "x=y", none of which involves immutable data, and concludes that traditional assignment semantics are the worst of the four options!

The Type of []

That should be "The Type of []", but it seems that blogger won't let you change the font on the heading. 

Anyway, so the section of Learn You A Haskell where it introduces value constructors says this: "Value constructors are actually functions that ultimately return a value of a data type."  (For example, Just is function that takes an argument of type a and returns a value of type Maybe a).  That seemed pretty straightforward and I think I internalized it well on the first pass.  

The LYAH section on type constructors also mentions the fact that type constructors are functions.  So I kind of knew that fact but didn't really know it until I got unto the Functor section and the explanation that fmap is just a generalization of map.   Because the type of fmap is (Functor f) => (a->b) -> f a -> f b.  My brain began to rewind a bit, trying to figure out how [Int] fit the type signature f a with a bound to Int.  Then it hit me that [] is just syntactic sugar for a type constructor, which is just a function that creates a type. I'm just so used to that class of objects being builtin language keywords that this took more than a bit of adjustment.

In other languages, list<int> myList is just a set of keywords you say to make the compiler give you a list of integers; a compiler feature or even a compiler-level function if you will.  Haskell gives you the list type constructor as an actual function.  EDIT: The function is evaluated at compile time, but it is nonetheless a function. 

The Haskell Road . . .

Time for another quick book report.  The Haskell Road to Logic, Maths, and Programming advertises itself as a from-the-bootstraps guide to, well, logic, math, and programming.  I've finished the first 4 chapters, a little more than a third of the book.  What do I think so far?

It's a very good guide to the foundations of mathematics.  Though I have a math degree, this is something that never really clicked for me before.  The ad copy states the only knowledge the book presumes is secondary school mathematics. I don't have that perspective, but I think the book does a good job of explaining the foundations of mathematics without assuming any more knowledge than that.  I'm not so sure it's as successful on the programming side -- I think there are several places where a reader with no programming experience would be quite confused about the example programs.

It seems to me that the book's real target audience is programmers who want to learn some Haskell and learn the fundamentals of logic and math and how to use formal methods in Haskell.  So far, it accomplishes those goals fabulously.