07Jul

Lisp In Small Pieces, Coffeescript Edition, Chapter 3, Part 1

Posted by Elf Sternberg as Uncategorized

I’ve been working my way through a Lisp textbook, Lisp In Small Pieces, by Christian Quinnec. It was originally written in French and is not that well known among English-speaking Lisperati, not in comparison to the Wizard book or Paul Graham’s On Lisp, but what caught my attention was how it really was in small pieces. Each chapter ended with an interpreter described, sometimes in code, sometimes in text; if you were smart enough, you could actually piece the whole thing together and see how it worked.

I decided to make things hard for myself. Since I’m not a Lisperati (although I may well and truly be seduced by Hy), I decided to make things hard for myself by writing the interpreter in Coffeescript. Most Lisp books assume you have a Lisp handy, and Quinnec’s examples are fine and dandy on many variants of Scheme, but for a fun time I decided to write it in something else. Raganwald claims Javascript “is a Lisp,” and if that’s so it ought to be good enough to write a Lisp in it.

I mean, it’s obviously been done before. I tried once before but got lost. LiSP does me the favor of keeping me on track.

You can see all my sourcecode at Github: Lisp In Small Pieces.

Chapter 1 contains the base interpreter. It also contains a hand-written Lisp reader, and refers to another project I have on GitHub, cons-lists, which is exactly what it sounds like, a singly-linked list implementation in Javascript, using nested Javascript arrays as the base. The base interpreter is very primitive– you can’t even create new variable names in the global namespace! Although you can shadow them using lambdas, so it’s pretty much bog standard Lambda Calculus.

Chapter “Lambda 1” contains a continuation-passing variant of the interpreter from Chapter 1. It’s basically a facile reading of Lisperator’s λ-language intepreter, with my own parser front-end and some CPS style. It passes all the tests, but it’s a distraction.

Chapter 3 contains the same interpreter, only using the architecture Quinnec describes in Chapter 3 of his book.

Chapter 2 describes a number of different methodologies for binding, scoping, and namespaces. The material is interesting but I didn’t pursue writing the various interpreters. I “got” what Quinnec was saying, and if I’m ever interested in writing something with scoping rules outside of the lexical scopes with which I’m familiar, I might revisit the material.

The next step will be to add functions to the Chapter 3 interpreter to do the various continuation management games, like call/cc, throw/catch, and so forth. Because those, I feel I need to understand.

How far will I take this project?  I’m not sure.  Chapter 4 is “Assignment and Side Effects,” so I’ll do that.  Chapter 5 is theory, and 6 implementation, of a “fast interpreter” of the kind French programming language guys apparently love to study.  I’ll read them, but I’m not sure what code I’ll generate out of that.  Chapter 7, “Compilation,” is interesting in that he starts by defining a VM that on top of which our bytecode will run, and implement both the VM and the compiler in Scheme.  I think I want to do that chapter, and then re-write the compiler to create LLVM-compatible code instead, just to learn LLVM.  Chapter 8 implements EVAL, chapter 9 has Macros, and chapter 10 has Object-Oriented Lisp.  So I’ll probably do those as well.

And then… we’ll see.  I surprised myself by doing Chapter 3 in less than two weeks.

Comment Form

Subscribe to Feed

Categories

Calendar

July 2015
M T W T F S S
« May   Aug »
 12345
6789101112
13141516171819
20212223242526
2728293031