First-class environments

In the previous posts I discussed the advantages of procedural abstraction, showed various ways to poke holes in the abstraction, and discussed the consequences of doing so. In this post, I'm going to talk about first-class environments.

I really liked first-class environments when I was first exposed to them. It was cool to be able to reflect the underlying interpreter data structures to user space. At one point I attempted to port Gary Drescher's Object Lisp to Scheme. In order to handle the dynamic object scope, I used first-class environments and injected the object bindings into the lexical environment when the object was in use. (There are a lot of reasons why this doesn't work.) Over time, however, I came to realise that there was more difficulty and less power with first-class environments than I had originally thought. At this point I believe that first-class environments are useless at best, and dangerous at worst.

Before I get too far, I need to precisely describe what a first-class environment is. In Scheme, all variables are associated with a unique binding. The variable is either ‘free’, in which case it is a reference to a ‘top-level’ or ‘global’ binding, or it is ‘lexical’ in which case there is an enclosing lambda expression that is lexically superior to the reference names it as an argument. A lexical variable becomes ‘bound’ when the (closure containing the) lambda expression is applied. The binding exists as long as any code within the body of the lambda expression could refer to the variable. The ‘environment’ is the collection of bindings necessary to evaluate a given piece of code. (You should all be familiar with this.)

No doubt you are familiar with the ‘chained environment model’. In this model, a closure is made over the current environment every time a lambda expression is evaluated. When the closure is applied, the environment at the time of closing is used as a base, and a new ‘frame’ is created with the new bindings. When a variable is to be evaluated, the frames are searched from most-recent to least-recent to discover the binding. We're already in a little bit of trouble. While this model accurately describes how to determine the correct binding of a variable, it is just a model. The implementation is allowed to do whatever it wants provided that it always returns the same answer as the model would. There are several different implementations of this model. The usual implementation in a toy interpreter is to represent the environment as a simple association list. Bindings are pushed on to the list at application time and the list is searched on each reference. A more sophisticated interpreter may keep a linked list of vector-like ‘frame’ objects. It is simple to keep track of the ‘lexical address’ of a variable. This consists of the count of the number of frames back and the position in the frame where the binding is stored. When the variable is evaluated, no search is necessary. The environment chain is followed until the correct frame is found, and then the binding is at a known offset. Some implementations take advantage of the fact that most environments can be temporarily allocated on the stack in a contiguous region. These implementations can simply compute a static index back from the current stack pointer in a number of cases. Some implementations use a ‘flat’ environment. A flat environment is a vector of the addresses of the bindings needed by the lambda body. When the lambda is closed over, the bindings are copied. Finally, some implementations carefully analyze the body of the lambda expression and decide among one of several environment representations that might work best for the particular body.

The model does not specify what happens to those bindings that are not used within the body of the lambda. For example, in this code:

(let ((greeting "Hello!"))
  (display greeting)
  (for-each (lambda (e) (display e) (newline)) (list "How" "are" "you?")))

The binding for greeting could be used by the lambda expression passed to for-each, but it isn't. The model tells us that display and newline refer to the top-level definitions, and that e is immediately bound by the lambda, but it does not tell us what happens to the binding of greeting after the greeting is displayed. Some implementations retain the binding, others drop it, still others do one or the other at different times.

Returning to the question of what a ‘first-class environments’ is, there is the question of whether you should be able to extract one from an arbitrary closure. There are three potential answers:

1. Yes, you should always be allowed to extract the environment from any closure.
2. No, you must indicate beforehand which environments are to be first-class. (The the-environment form in early Scheme implementations and in MIT Scheme is an example.)
3. Maybe, it depends on the implementation.

The second question is whether the returned environment contains all lexically visible bindings, or whether it contains only those bindings that are used at the point of capture, or whether you enumerate exactly which ones you want captured.

1. All bindings, in use or not, are captured.
2. Only the bindings in use are captured, the others may not be.
3. Only the bindings explicitly listed by the user are captured.
4. All, some, or none are captured depending on the implementation.

The third question is whether the returned environment contains a snapshot of the bindings (a static copy of the values at the time of capture), a live copy of the bindings (a copy that changes as the values change), a mutable live copy (modifications to the copy affect the running of the code that refers to the bindings), or a user-specified list of the above.

1. The actual bindings (mutable and live) are returned.
2. A read-only reference to the bindings are returned. Values may be seen to change over time, but they cannot be modified via this interface.
3. A snapshot to the bindings are returned. Changes to the actual bindings are not seen.
4. The user specifies which variables are live, mutable, or snapshot.
5. Implementation dependent.

Finally, there is a question of what happens if we evaluate a define expression in the returned environment.

1. Evaluating a define establishes a new, shadowing binding if a previous binding did not exist. It acts like an assignment if a previous binding did exist.
2. define is not to be used. It is an error to try it. (Optionally an error is signalled, etc.)
3. Implementation dependent.

I'm pretty sure these options cover the design space. The current state of affairs is that all options are implementation dependent. Any standardization of first-class environments will have to change at least one of these options away from implementation dependent. So let me now discuss the problems.

When someone suggests ‘first-class environments’, I assume they want options 1, 1, 1, and 1, that is, they can grab any environment at any time, all lexical bindings are present, used or not, the bindings are live and mutable, and you can insert new, shadowing bindings. Many people have told me not to make that assumption, so I'll talk about the other variations as well. In this variation, though, the user simply cannot reason about his code. There are no abstraction barriers because any piece of code can, at any time, crack open a closure and change the meaning of any variable whatsoever. Something as simple as (lambda (x) (+ x 1)) cannot be assumed to do addition if someone injects a shadowing binding for +. Obviously you cannot compile this to an add instruction if you don't assume it will still be addition at runtime.

Thomas Lord suggested “When you write your code, avoid capturing environments and then you are all set.”

He is apparently suggesting option 2 for the first question: explicit marking of environments you wish to capture. This is a considerably weaker proposal because allows the user to statically analyze any code that doesn't use a first-class environment, and it allows the implementation freedom in choosing environment representations in any code that doesn't use first-class environments. I have few objections to that, but let's examine question 2 under this proposal.

The second question is whether all bindings are visible, or only those bindings that the user explicitly specifies. The latter would take a form something like this: (the-environment foo bar <more variables here> ...). I have a small objection to this. It is poor practice to expose the internal names of your variables (see previous posts). I don't think it useful for Scheme standardization because it is trivially implemented as a macro. (The third option of some bindings being available, some not, is not worth considering. It would be impossible to write portable code that used them because there are no guarantees they exist.)

So allow me to summarize my objection to first-class environments:

• If first-class environments can be arbitrarily extracted from any closure, you can no longer depend on lexical scoping. You throw the baby out in favor of the bathwater.
• If first-class environments can only be obtained through use of an explicit special form, and you explicitly enumerate the variables captured, you don't need a change to the standard, you need a SRFI with a macro.
• If first-class environments can only be obtained through use of an explicit special form, but all visible variables captured, you still don't need a change to the standard, you need a SRFI with a more complicated macro.

---

It isn't clear to me how hygienic macros would work with first-class environments. Recall that if a hygienic macro introduces bindings, the appropriate renaming is performed during transcription to avoid accidental capture. But if we wish to capture one of these bindings, we'll need to be able to refer to it in some way. Code outside the macro would be unhygienic if it could refer to the variable, so that's a problem. Code inside the macro would work fine (it would be renamed appropriately to keep a hold of the reference), but then you don't need a change in the standard to put code inside your macros.