17Aug

Finished Chapters 4 and 5 of Lisp In Small Pieces

Posted by Elf Sternberg as Uncategorized

Chapter 4 of Lisp In Small Pieces introduces side effects. It also introduces a (excruciatingly simplified) taste of what managing memory feels like, with a monotonically increasing integer representing memory we’ve requested, and a corresponding identity in the environment.

More interesting is the abandonment of the Object-Oriented approach in Chapter 3 for a completely functional approach in Chapter 4. Everything is a function with enclosure. When you want a number, you have to send the message (number sValue) to extract it. You can get typing information with (object sType). The “sValue” and “sNumber” are, in my code, simple Javascript objects of type Symbol, around which I’m trying to formalize symbols and quotations, so that going forward it’s easy to distinguish a Symbol as a unique type– doing so may remove an entire class of difficulty in the read() function.

Chapter 4 was supposed to also teach about memory management and variable “boxing,” but in fact it only contains a very cheap pair of stacks: one for the environment, the key of which is a name and the value of which is a number, and one for memory, the key of which is the number, and the value of which is the object: a symbol, a number, a boolean function or an arbitrary function. It makes a strong correspondence between this Lisp and the λ-calculus, and even shows how, with a few small extensions, the λ-calculus can accommodate assignments and similar side effects, although not necessarily externalities, like I/O. Extending this to a real memory management system is, I hope, not entirely left up to the reader as an exercise.

I’m still trying to figure out how to write this monoidically, such that I can “lift” (see: The Elevated World) all of my functions out of the “standard Lisp lists and things” world to the “lisp lists and things encapsulated with metadata about compilation,” which would enable me to add debugging, source code, and sourcemap information to the resultant product. Maybe I need to do a few more monoid/monad tutorials, the more hands-on ones, to wrap my head around lifting.

The source code for Chapter 4 of Lisp In Small Pieces, Coffeescript Edition is, as always, available on Github.

Chapter 5 basically reiterates Chapter 4, only it does so entirely in Greek. I’m only half-kidding; it’s mostly an attempt to formally described the interpreter covered in Chapter 4 using the formal language of an extended λ-calculus. It doesn’t have an interpreter of its own, except in a purely theoretical, head-in-the-clouds description of a λ-calculus-derived language written mostly in Greek symbols.  So there’s not going to be any source code associated with it.

Comment Form

Subscribe to Feed

Categories

Calendar

August 2015
M T W T F S S
« Jul   Sep »
 12
3456789
10111213141516
17181920212223
24252627282930
31