Mad Schemes : Learning Lisp via SICP

Originally published on: Fri, 3 Sep 2010. Last updated Mon, 6 Sep 2010.

Several years ago, I read Paul Graham's famous essay Beating the Averages. I re-read the essay regularly.

In the essay, pg draws attention to the fact that Lisp was the secret weapon that he and Robert T. Morris used to build and update Viaweb much more quickly than the competition could do with their own attempts at Internet storefronts.

I chose to believe that any dynamic language could have been used in place of Lisp in the hands of a competent programmer. Occasionally, I wonder if I'm wrong.

I read other essays by other people who seem to be rather on-the-ball who state that learning Lisp can change the way one approaches solutions to problems ... whether you build those solutions in Lisp or not. They all cite the tome formerly used at MIT as an introductory programming course : Structure and Interpretation of Computer Programs ( i.e. "SICP" ).

I recently purchased the book and decided to write out the student exercises in each chapter as I read it. I'm effectively back in school.

I downloaded the recommended MIT GNU Scheme compiler, but I favored a different one ... Scheme48. I suspect that I may run into behavioral anomalies as the course material introduces more complex concepts. I'll cross those bridges when I get there.

I have seen many others write journals to chronicle their efforts to learn Lisp through this book. I am going to do the same.

Rather than writing separate blog-posts for each entry, I will simply append new material with a new date heading to this post. A lot of what I write will essentially be just stream-of-conscious ramblings.

3 Sep 2010

I hadn't realized it until I read through the early portions of the book, but this course served as an introduction to computer programming for both Computer Science majors and Electrical Engineering majors.

I keyed onto the fact that the rules of Scheme can be conveyed in about an hour, much like explaining the rules of chess. The idea is that while the rules can be explained in a short amount of time, practice is required to properly learn how to apply the rules.

At this point in the reading, I wonder if I could device a web-programming curriculum around an implementation of scheme. My idea is to apply a language-agnostic approach to the basics of web-application development so that time exhausted in learning language detairs. I'll keep that idea in mind as I progress through the book.

One of the things I've noticed early in the chapter is how the authors tie the syntax of the English language to the syntax of a programming language. They refer to variables as "pronouns" to help the reader.

Early in the book, special forms are discussed. I had understood special forms to be mutations in the standard s-expression syntax. I was wrong.

The authors describe the if special form by its different behavior. The if looks like a run-of-the-mill Scheme expression, but it does not evaluate all of its arguments in the standard manner, so it is considered to have a special behavior. The cond special form also exhibits special behaviors related to logic and flow-control.

The importance of these particular examples were lost on me until I had reached exercise 1.6 where a hypothetical Scheme programmer, Alyssa P. Hacker, tries to create her own if using cond ( another special form).

When my computer locked up for a few moments and then indicated that it had run out of stack space, I knew that something had recursed far too deeply ... I just didn't know what or why.

I took some time away from the book to read more about Scheme48. I needed to know what function could write a specified block of text to the console. Rather than calling up a debugger, I just wanted to insert some diagnostic code into the function that I suspected as being the problem. Perhaps this was the incorrect way to approach it, but I was able to better diagnose the problem. I just didn't figure out why it was happening until I had consulted the blog pages of others who have worked through the material.

So far, the student has been made responsible to tinker with a group of functions that calculate square-roots via successive approximation. The introduction of a single bug left me rather clueless about how to properly fix it ( other than rewriting it differently ). I wonder what's in store for me when I reach the more complex examples?

6 Sep 2010

Going back through the manual notes I'm taking, I'm reminded that I was surprised that and and or are considered special forms. After explanation, the fact that not all operands may be evaluated was obvious.

I find it interesting that one can defined named procedures locally inside a given procedure definition. I've only seen something like this before in Pascal. In C we used to apply the static modifier to a function's name to keep the identifer's scope local to the source file.

The authors go on to demonstrate lexical scoping an interesting concept where local procedures can share the access to parameters passed in to the governing procedure.

In footnote number twenty-nine, the iterative factorial procedure that they present does not use a local counter variable as I would have tried to do.

They are beginning to formally address recursion as a looping technique. In fact, I laughed out loud when they referred to the looping constructs of languages more in my repertoire as "defects".

I was happy to see the coin-counting problem as it is a favorite of mine. The discussion on the redundant reiterations of calls to procedures with the same operands was interesting. They referred to the measure of this phenomenon as Orders of Growth.

I am reminded of web page requests and rules for idempotency. I believe that I had read somewhere that there were in existence implementations of functional programming languages that cache the values returned for a given set of input parameters so that recalculation does not occur. I am now wondering how one might implement that feature conditionally, so that only certain procedures could leverage it without marring the syntax of a language. I'm now wondering when I'm going to be smart enough to write a mechanism to do just that in Scheme so that I can selectively empower a procedure to be cacheable.

Unless otherwise noted, all code and text entries are Copyright Š2010 by James K. Lawless

Save to del.icio.us
Save to StumbleUpon
Digg it
Save to Reddit
Share on Facebook
Share on Twitter
More bookmarks