As revealed last time, my university training was focused on a business degree with a programming minor, the point of which was to prepare me for being a dark programmer in some basement of a bank or other financial institution. There was an actual track for this at my university. As such, my instructors told me not to worry too much about data structures; I didn't need to know about trees, linked lists, and deques.
I thought, since I'd done the exercise, that I was done with A Language In 20 Minutes, but this morning I had an inspiration and so, on the commute into work, I hacked out a new version that's available on Github. It's more "functional," as I said, for some definition of functional.
But what I did add was a Lisp-like list class that behaves more or less like a Lisp cons list: A linked list of two cells, the second of which points to the next cell. Like so:
[(data:C), (next)] -> [(data:B), (next)] ->
These lists start out with just the 'A' entry; when you cons an entry, it looks like: cons(D, list), and it would add a 'D' entry to the "head" of the list. The amazing thing about this structure is that you only have access to the head, but through it you have access to the whole list.
When you're describing the scope of an operation for an interpreter, you still need a traversible, ordered collection of scopes that go all the way from your deepest scope to your root in order to ensure along the way that every variable is defined, and add new variables to your current scope as needed. When you create a new scope in your interpreter, you do it in a given function call that will interpret expressions within that scope. When you leave that function, you need to expunge the memory allocated for your scope. So let's say that the D object mentioned above is a dictionary for resolving variables in the current scope; by consing it onto your list, you can now traverse the scope, checking all the dictionaries down to the root automatically.
And when you leave the scope, the D object and its list reference get reaped. You get memory management for free.
The dirty secret inside Coglan's example (see the first commit to my github) is that his Scope object is a cons list; it's just a very informally defined one, using the parent field to point to the next cell, all the way down to the "TopScope."