Friday, May 02, 2008

Little Lisps: Programming Candy or Spinach?

Last time (StreamTokenizer and Declarative Lexing), I mentioned an idea of presenting language designs in this space as a puzzle to be solved, like a crossword puzzle. I invented the idea there and its been growing on me.

The previous week or so I'd been reading Sam Kamin's "Programming Languages: An Interpreter-Based Approach", so this didn't seem like such a crazy idea as it may sound. In "Programming Languages", Kamin starts with an interpreter for an extremely simple language using Lisp syntax, and procedes with each chapter to show what modifications need to be made to get interpreters for Lisp, Scheme, SASL, APL, Smalltalk, Prolog and others. They all use Lisp syntax, so the code changes are kept quite manageable, and the reader can focus on the essential differences in scoping, evaluation strategies, and the like.

It seems, as a first step, if the Language Design Crossword Puzzle were to be a reality, that making available a standard interpreter source such as Kamin's is a reasonable idea. "Given interpreter0, add macros" would be a puzzle. "Given interpreter0, add object serialization." This is similar in spirit to comments I made earlier about the utility of lambda calculus for studying language features.

But is the Language Design Crossword Puzzle a good idea? What's the point? Arcane Sentiment, a blog I discovered and subscribed to today, introspects on writing little language implementations. He describes certain parts of the exercise as "programming candy", and ironically, they're often the parts written in C, a series of little programming victories. The hard, ill-defined problems to be written in Lisp are the parts that tend to slow him down and demotivate him. (Arcane, I hope I'm fairly characterizing that post. Please correct me if not.)

I had to chuckle in self-recognition, as earlier this week I was watching the first few SICP videos, evaluating the examples in a Scheme-ish interpreter I'd whipped up on Monday and Tuesday, extending it during pauses in dialog while Sussman wrote on the blackboard. Until he hit the pi fraction example and I realized I wasn't at all sure if I wanted to right at that moment be writing code to rationalize denominators and factor fractions or whatever else Scheme might do to support exact rational number (fraction) arithmetic (e.g. (/ 1/2 (+ 1/8 1/3))). That problem at that moment was not interesting for me, and was not well-specified; are rationals always reduced to lowest terms? How is conversion to and from reals handled? I'd have to go study R5RS to learn the expected behavior. Handling the number tower was not my goal going into this project.

Why does Arcane Sentiment dabble in Lispy implementations? Why do I? Why reinvent the wheel? For me, it's a way to learn, to study. Toy implementations are rewarding, as they let you discard parts of a language implementation system that are indeed hard, and focus on particular points of interest. You need to be careful not to oversimplify, if you intend to take your lessons back to a real system. But this approach is something we advise junior programmers all the time: if you're struggling with how a library or language feature is working in the application, try writing a small example program first until you understand how it works.

So, I propose we have the best of both world. Language design problems can be programming candy, as well as programming spinach, that is something good for you. My wife has been making a spinach recipe from her Spain and Portugal cookbook which features raisins and pine nuts. It rocks.

The other question is, is there interest in a "language design puzzle" feature? Before we get to that, let me ask a more relevant question: what aspects of programming language implementation or operation are of interest to you? Macros? Evaluation strategy? Optimizations? Drop me a line to the Google mail account jfkbits and let me know.

Blog challenge: write a post using the phrase "free as in spinach".


grant rettke said...

My vote: "programming fruit".

It is good for you, and once you learn how to appreciate it, it tastes better than *any* candy out there.

JFKBits said...

grant: Good call, and for a similar reason it's why I mentioned the spinach-with-raisins dish :) Not all candy is bad. Just remember what my good friend always says: "Syntactic sugar makes curried functions taste better."