Log in

No account? Create an account
entries friends calendar profile Elf Sternberg's Pendorwright Projects Previous Previous Next Next
Lisp In Small Pieces, Chapter 5: The Storage Story - Elf M. Sternberg
Lisp In Small Pieces, Chapter 5: The Storage Story

One other thing about Lisp in Small Pieces chapter 5 jumps out at me: the storage story.

In the interpreter written for Chapter 5, some things are cons lists (most notably, the expression object you pass into the interpreter), and some things are lists, but they’re not built with car/cdr/cons.

In chapter 3, we built an interpreter that used full-blown objects, in which each object had a field named “other” that pointed to the next object; when looking up a variable or an unwind point, the search was an explict call: starting with the latest object, a search would begin down the chain for a match and, when found, would trigger either a memory retrieval or a continuation, at which point the interpreter would resume with the relevant memory or continuation. Each object had a “failure” root class that would throw an exception.

In chapter 5, it gets even more functional. Chapter 5 tried to define everything in the Lambda Calculus, which allows for closures, but doesn’t by default support objects. But Quiennec really wanted to teach about allocation issues, especially the boxing and unboxing of values, so to make that point, he created two structures: one represents variable names that points to indexes, and one represents an indexed collection of boxes. Lookup represents the Greek equation σ (ρ ν), which is basically that the environment knows the names of thing, and the store knows the location of things.

But in order to be explicitly literal, Quiennec goes full-on. Both environment and store are represented the same. He creates a base environment that looks like this:

ρ.init = (ν) -> "Variable name not found."

and then when we add a new variable name to the stack, we write:

(ρ, ν, σ, κ) -> (ν2) -> if (ν2 == ν) then κ(σ) else ρ(ν2)

. In this case, we call a function that creates a function that, in turn, says “If the name requested matches the name at creation time, return the stored store point (actually, continue with it), else call the next (deeper) environment, all the way down the stack until you find the thing or hit ρ.init”.

It’s a really cheesy ways of emphasizing that you can do Lisp in a full-on Lambda Calculus way, but you probably shouldn’t. It’s also completely dependent upon the parent environment to reap memory when you’ve examined the tip of an expression and have retreated back toward the base of the expression tree to proceed down the next expression.

Lessons here are about the Lambda Calculus, and about memory management. In the latter case, how hard it’s going to be if you want to do it the way the big boys do.  Garbage collection is hard.

Leave a comment