Roots of Lisp
The first time I read Paul Graham's article The Roots of Lisp was a couple of years ago. I remember thinking that it's cool that Lisp can be defined in itself using only seven functions (quote, atom, eq, cons, car, cdr and cond) but it's even more interesting to think about what kind of boiler-plate code would be required to support such an implementation. I mean, it's not like McCarthy and the others had a high-level language available when they wrote the first Lisp interpreter.
Yesterday I stumbled on the Software Preservation Group's History of Lisp-page. It contains a lot of information about those first steps in Lisp history. One of many interesting things to read about is Pascal Bourguignon's work on getting the first Lisp compiler (written in 1962) running on an IBM 7090 emulator.
Whilst Pascal's project is indeed impressive work and interesting in many ways it would be even more interesting to do something similar using GCC in order to get a minimal Lisp interpreter. And I mean really minimal. For instance, complicated things to parse such as (foo bar baz) won't be supported, a minimal parser would require you to write (foo . (bar . (baz . ()))). But since that's just the first layer in the implementation we could write a new reader using our minimal Lisp. One that would support, among other things, parsing lists as we'd usually write them.
I wonder if the same seven functions will be sufficient to pull that off or if it turns out to require more things. Unfortunately I haven't got the time to find out. I'll just keep reading the available historical material and keep hoping for someone else to step up for this experiment ;-)
Labels:
Lisp,
Programming
3 kommentarer:
Writing a LISP parser isn't that hard. S-expression syntax is straight forward to parse. Making it efficient is another story. I spent a lot of time hand tuning the parser in Jamocha to lower memory usage and increase throughput. To me, it's harder to parse a language like JRules or drl, since they allow java like syntax. I'm clearly bias for LISP syntax.
Hi Peter,
yeah, I know. I actually wrote a toy lisp interpreter in Java a few years ago. I wrote a custom parser for it and it still didn't get out of hand as most other parsers quickly do ;-)
I know what you mean about "getting out of hand". On a related note, the main branch of jamocha went through 3 different revisions of parsers. The first version used JJTree from the clips manual, which produced a slow parser and a ton of supporting classes. The second version improved on it, but was still slow according to the students at Aachen university. The third version is much simpler and considerably faster than the first two. Sometimes following a strict AST results in a complex parser that is slow :)
Skicka en kommentar