Wednesday, May 07, 2008

Motivations for Little Interpreters

We're continuing a series about writing little interpreters. Although it is fun and cool, so are isolated guitar licks for about the first five minutes; long-term you probably will want to play whole songs if you want to have listeners. Similarly, you need an application, killer or not, for an interpreter or it will lie around collecting bit dust and require "maintenance" (right, Dijkstra?).

I suppose you could say I'm talking about an interpreter for a Domain Specific Language here, but really all I mean is that if you care enough to write an interpreter, you may as well take the opportunity to build into it something you can use, and for this post I'll address the area of a useful domain.

Specifically, if you care about an interpreter it means it will support a domain you care about: photos, 3D graphics, matrices.

In the implementation language of the interpreter, you will want to define
1. Data structures
2. Ways to construct and operate on them

and you'll make provisions for these in your language. Thinking these through carefully, and probably writing them into a runtime library complete with unit tests, is a respectable way to approach things before sticking an interpreter front end onto the data and code of your domain of interest.

Let me give you one simple example of an interpreter I wrote for personal productivity. In 1995 I wrote "Joel's Calculator" to help me write status reports for my manager, and also to do some basic statistical analysis. (No, I didn't have Excel; I was working with an HP-UX workstation.) Our embedded systems group had gotten a rare opportunity for a complete product rewrite, and we needed to track our time and estimates carefully. We had to track time spent on particular modules and count overhead, and in our weekly status report submit an account of time on our various modules, with overhead (anything not in a particular module) evenly divided among our projects. I would keep a log of time spent that looked something like this:

Tue May 7
0840-0920 Email
0920-1135 Serial driver
1250-1300 Ovr
1300-1400 Phase 2 mtg
1400-1600 Serial driver testing
1600-1715 Code review
It was an easy way to keep track, in a text editor. Then at the end of the week, I would sum the "billable hours" for modules like Serial driver. What I ended up wanting was a way to do "time arithmetic":

serial = 11:35-9:20 + 16:00-14:00
ovr = 9:20-8:40+0:10+14:00-12:50+17:15-16:00
This worked very well for me as a workflow. I could write simple expressions like this, assign them to variables, combine the results gradually, and so on. This was really a desk calculator, but I was pleased with the effect that I could enter times textually in a very natural way, use simple infix arithmetic notation, and have it just work.

In this case my chief domain of interest was pretty simple, a pair of hour and minutes, and the operations on the domain were also fairly simple, but a little challenging to get right.

Of course, you may be coming at this from the perspective that the goal and the domain are already well defined. For example, you're working with a library of interest and you'd like to play with it interactively; you can envision making Scheme bindings and writing abstractions to make it do something useful. Or you even have a very powerful system written in an existing but limited language, but you need to bust out of the limits. Using a lightweight Lisp/Scheme interpreter that you can modify to script some macros to generate code in another language may solve some scaling problems for you.

So, if you want to start a little interpreter project, which I'd like to encourage, before you get started, pick a goal, pick a domain, and refine the domain as the first step.

No comments: