Log in

No account? Create an account
entries friends calendar profile Elf Sternberg's Pendorwright Projects Previous Previous Next Next
Lisp In Small Pieces, Coffeescript Edition, Chapter 3, Part 1 - Elf M. Sternberg
Lisp In Small Pieces, Coffeescript Edition, Chapter 3, Part 1

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.

3 comments or Leave a comment
l33tminion From: l33tminion Date: July 12th, 2015 10:48 pm (UTC) (Link)
What's the argument that JavaScript is a Lisp? It has neither equivalent structure for code and a basic data-structure, nor does it have Lisp-style macros (which make use of that equivalence).
elfs From: elfs Date: July 13th, 2015 04:36 pm (UTC) (Link)
Oddly enough, the definition of Lisp does not have "lisp-style macros" at its core; it has only the equivalent structure for code and data, and macros are a facility built on top of that-- which is why many Lisp textbooks have you writing "Lisp-compliant interpreters" for many, many chapters before they get around to showing you how to implement a macro interpreter.

The equivalence of code and data is a red herring, too; this equivalence is actually true of all programming languages, Lisp being the one in which it is most explicit.

The only thing Javascript is actually missing in order to be "a Lisp" in full is stackless continuations, and we're getting (some of) that in the ES6 implementation. Lexical block scope, dynamic typing, and first-class functions with closures have always been a part of Javascript; recent add-ons include stackless tail call recursion, code/data equivalency, and parser-pass macros. These aren't well-known or widely-used, and your average "just enough jQuery to get by" guy has no idea they exist or even need of them.

Some users do use them unknowingly; if you've ever used react.js, for example, you've used something with a parser-pass macro.
l33tminion From: l33tminion Date: July 21st, 2015 02:54 am (UTC) (Link)
it has only the equivalent structure for code and data, and macros are a facility built on top of that

Yeah, that's why I worded my comment the way I did. It's not that you can't have Lisp-style syntax without Lisp-style macros, it's that Lisp-style macros are a killer app for Lisp-style syntax.

The equivalence of code and data... is actually true of all programming languages

That I know, but the specifics of the syntax can make it quite a bit harder or easier to manipulate code as data.

Most of the stuff I've read before that tried to make some fundamental distinction between "a Lisp" and other modern programming languages that are "not a Lisp" focuses on that aspect instead of some grab-bag of features. Admittedly, it's just one of the features that set Lisp apart originally, but to say that JavaScript is in the same family of languages as e.g. Common Lisp or Scheme seems pretty odd, which is why I was wondering what specific definition Quinnec is using. Maybe I just haven't been reading the right textbooks. My academic CS background contains relatively little Lisp, though I've been programming professionally in Common Lisp for seven years.

(Also, I'm not sure what you mean by "parser-pass" macros specifically. I haven't heard that term before, and a search for "parser-pass macro" turns up no results.)
3 comments or Leave a comment