If you haven't heard

There seem to be more readers of my posts than there used to be, so I wanted to mention a project I've been slowly working on.

I've been porting MIT Scheme to the .NET CLR. MIT Scheme has two major components: the ‘microcode’ which provides the memory model and the primitives, and the ‘runtime’ which is the Scheme code and libraries that come with the system. Once upon a time, the ‘microcode’ really was microcode. The Scheme-81 Chip (sorry, I can't find the text on line) was a microcoded VLSI processor that interpreted the SCode representation of Scheme. Sometime around 1982, the microcode was translated to 68000 assembly code and used to run Scheme on the HP 9836 Chipmunk. Sometime around 1983 or so, Jim Miller wrote an SCode interpreter in C that replaced the microcode layer. My version is a new SCode interpreter in C#. The source code is available at http://code.google.com/p/jrm-code-project/.

I'm doing this for fun and to try out different ideas I've had about interpreter implementation. The interpreter basically works, but it is missing a lot of primitive procedures and I haven't hooked up the error handler yet. It is, of course, a lot slower than the standard version of MIT Scheme (which is mostly compiled), but it is in the ballpark of MIT Scheme on interpreted code.

So why am I bringing this up? Lately I've been posting about first-class environments. MIT Scheme has first-class environments, and it uses them to provide different ‘packages’ for the Scheme code (a package is separate namespace in which you can run REPL). MIT Scheme also has a compiler that can produce very efficient code in the right circumstances. There is a caveat, though. If you make use of first-class environments, the compiler is forced to create environment structures that are compatible with the interpreter's representation. This is because there may be a need to call in to the interpreter to eval an arbitrary expression in such an environment. In these circumstances, the compiler can perform essentially minor optimizations that do very little to speed up the code. MIT-Scheme only uses first-class environments — actually, I'm going to call them ‘interpreter compatible environments’ because that's more accurate — to construct the runtime packages. There are on the order of 50 of them. The rest of the code doesn't use them at all.

As I have mentioned in earlier posts, the two things that an interpreter does most is variable lookup and continuation management. These things are critical to interpreter performance. I managed to get two academic papers published on how to get the underlying system to manage continuations efficiently, yet still be able to reify them to support first-class continuations. Right now I'm working on improving variable lookup.

When an interpreter compatible environment is used, there is little choice but to represent the environment as a linked list of frames. Each frame can use a vector representation for the variables that are bound by lambda application, but each frame also needs the ability to incrementally add bindings should the user evaluate a ‘define’ expression or invoke load from one of these environments. When evaluating a variable, the interpreter walks the environment chain and scans each frame until it finds the closest binding with the correct name (this is called a ‘deep search’). Needless to say this can cause serious performance degradation. A number of ways have been devised to avoid this problem. One that is of interest is the idea of computing a fixed lexical address for a variable. In most circumstances, the environment chain always has the same shape and the variable always appears at a fixed location. It is faster to dereference the chain until the correct frame is found and then pull the value of the variable from the vector. Unfortunately, it can be incorrect to do so. If an intervening frame is interpreter compatible, the user might load a file or define a variable that shadows the lexical binding. If this happens, the shadowing variable should be used rather than the former one at the fixed location. In Free variables and first-class environments, Miller (see above) and Rozas describe how MIT Scheme deals with shadowed variables. In essence, when you introduce a shadowing binding, you walk the rest of the environment chain and mark the shadowed variables. The interpreter uses the fast lookup method, but checks for the mark. If the mark is absent, the correct variable was found. If the mark is present, the interpreter does a deep search to find the variable. It sounds a lot simpler than it is. Because the lexical environment structure forms a tree, it is possible to have variables that are shadowed along one branch, but unshadowed on the other. It is possible to have variables that are shadowed at different depths on different paths. These are not often encountered (in the mid 80's, long after they thought they had covered every possible case of shadowing, Rozas discovered a new way to fool the variable lookup mechanism into fetching the wrong variable). If it did happen, the error message “Broken Compiled Variable -- get a wizard” would appear and Scheme would halt.

In my attempted port of Object Lisp, I would get this all the time. The idea was to inject the object bindings into the lexical environment when invoking an object method. This, of course, caused shadowing. But upon leaving the object method, I would remove the shadowing bindings. Upon invoking a method on a different object, a different set of bindings would be injected. The variable lookup mechanism would get confused because it would find the shadowing mark and try to locate the actual binding, but the next time it tried it would find a shadowing binding, but for a different variable. At this point I realized what a mess this was and decided that my approach wasn't going to work.

When the Scheme compiler became stable enough that the majority of code is expected to be run in compiled mode, it was considered too much of a burden to try to maintain the shadowed variable tracking mechanism and it was removed. MIT Scheme now has a slower, but far simpler interpreter. If you want fast, use the compiler.

Ok, back to my version of MIT-Scheme. For interpreter compatible environments, there is little choice but to deep search on every variable reference. But MIT Scheme only has about 50 or so of these and the vast majority of the code does not need to implement environments in this way. If we assume that incremental definition can only occur in the special interpreter compatible frames, then we can change the environment representation to make variable lookup faster. One popular mechanism is the ‘flat environment’ representation. In this representation a closure does not contain a pointer to a parent environment, but rather it contains a flat vector of pointers to the appropriate value cells for the lexical variables it uses. This makes a tradeoff. When creating a lexical closure, we have to copy a potentially large set of pointers to the lexical bindings, but when we look up a lexical variable, we only need to index into the lexical vector and dereference the pointer we find. Empirically, it seems that the tradeoff is largely worth it.

So I've changed my version of MIT Scheme to use flat environments rather than linked frames for the case where first-class environments are not used. It has been rather tricky, though, and I have a lot of scaffolding in place to double check everything. I'm now carefully removing the scaffolding and cleaning up the code to see if I have a net improvement in performance.

Needed for a debugger?

Pascal Costanza writes:
I always find the argument that some language construct is supposedly “dangerous” a bit weird. It's too fuzzy to make such a statement, in my humble opinion. What's more important, I think, is this: Do you want to be able to implement portable runtime debuggers or not? If you want this, you need first-class environments.

Argh! I did use the word “dangerous” and I was determined not to. You are correct that it is too vague a term. What I really mean in this case is this: if the language specification requires that all variable bindings be exposable and mutable to arbitrary code (that is one possible definition of `first-class environment'), then `lexical scoping' can no longer be guaranteed by the implementation, and that this drastically changes the character of the language in a particularly undesirable way, to wit, all reasoning about the code must take into account the entire body of code, not simply the lexically enclosing contexts. (Wow, that was a long sentence.)

I disagree that you need first-class environments in order to write a portable runtime debugger. That's a complex assertion, so I'll need to make a few assumptions about what you mean (and please correct me if I'm wrong).

First, it seems to me that a debugger is not usually a portable program. It will have to depend upon how the implementation works. A Scheme->C compiler would need to have some facility to debug the code generated by the C compiler. A Scheme implementation hand written in assembly code would need special assembly routines to decode the binary layout of data structures. A Scheme implementation in C# would naturally have debugging information stored as .NET metadata in the image. Then there are implementation details. Some Scheme systems alpha-rename the variables. Others discard the variable names and use De Bruijn indexes for variables. Some Scheme systems perform CPS conversion, others perform A-normal conversion. Some Scheme systems implement the interpreter as a finite state machine with a push-down stack, others use a ‘threaded’ interpreter, still others use a ‘lambda combinatorical’ approach. It seems to me that each variation will need its own means of debugging that cannot be easily shared with other variations.

Second, it seems to me that the information the debugger presents to the user is also implementation dependent. Suppose an implementation had an extension that allowed you to declare runtime constants, and that this implementation would inline the constants where they were used. Would you still expect `bindings' for these constants to be visible on the stack?

If the debugger is completely, transparently portable, and it were used on the same piece of code in two different implementations, I assume that it would present exactly the same information in exactly the same way (by my definition of ‘complete and transparent’). It seems to me that this would impose a particular evaluation model on the code. I can see two ways to achieve this:

1. Impose a canonical evaluation model that all implementations must follow. This would specify a particular environment model that must be used and maintained by the implementation.
2. Write a portable meta-circular evaluator that is designed to work with the portable debugger.

Option 2 solves the problem without the need to standardize on first-class environments.

---

Let me take a moment to describe what MIT Scheme does.

In MIT Scheme, you can run code in one of three modes. The first mode is plain interpreted code. The code is input as text then lightly processed to expand the macros and build an abstract syntax tree which is then walked by the interpreter.

The second mode is ‘syntaxed’. A program called ‘SF’ is run on the text. An abstract syntax tree is built, but then it is more heavily processed. In addition to expanding the macros, SF will ‘inline’ a number of primitive procedures and runtime constants and will simplify the code. The resulting AST is dumped to a file in binary mode. This processed code loads much more quickly and runs a fair amount faster than the original code.

The final mode is compiled code. The compiler uses SF as a preprocessor. The compiler can either produce C code that is then fed into a C compiler, or it can produce native x86 code. This code can be made to run very quickly.

Each of these modes has potentially different semantics. Before you panic too much at that, let me note that this is completely under the control of the user. The default action is to preserve the semantics of the interpreted code in all cases. When you choose the default action (or rather, fail to choose a non-default), SF will only expand the macros in the code. No inlining of any kind is performed. The compiler only open-codes those procedures inlined by SF, so no compiler optimization will be perfomed either. Therefore, simply running SF and compiling will not change the semantics of the code.

Simply running SF and compiling will not change the performance of the code, either. Given that the compiler can infer nothing about the code, all it can do is ‘inline’ the interpreter. All function calls are out-of-line and must go through an interpreter-compatible stack frame. (The compiler will transparently cache the values of some variables, but there is little performance to be gained through this.)

These semantics are very flexible. If you change the definition of CAR and CDR, the compiled code will use the new definition. However, in “real-life” circumstances, you never need this sort of flexibility. It is there, and it is the default, but for nearly any production purpose you'd like to tell the compiler that the standard definitions of the standard primitives can be assumed to be unchanging. To get a lot of bang for your buck, you simply add a declaration to the source code: (declare (usual-integrations))

When usual-integrations are declared, some fifty or so primitive procedures will be inlined by SF. These include things like CAR, CDR, VECTOR-REF, VECTOR-SET, +, etc. In addition, users can declare certain procedures of their own to be inlined. These inlining operations can have a dramatic impact on the performance of the code, but they come at a price. Because these are now inlined, redefinition of these functions will have no effect this code. Furthermore, the inlining is visible if you pretty-print the code. Inlining can introduce new lexical variables and eliminate the need for others. The lexical environment as defined in the source code may not reflect the actual set of bindings.

Most users find this a reasonably low price to pay. Few want to redefine the standard primitives (and you can specify exceptions if you really do want to redefine one or two particular ones), and while the environment may change, it isn't so different that it is unrecognizable. (There is a caveat here. We assume that the debugger will reflect the environment, but that user code is not reaching in to that reflected environment in order to perform some function necessary for the program. That is, the code isn't sneaking around using the debugger to do an ‘end-run’ around the scoping rules.)

With certain primitives inlined by SF, the compiler can now do a much better job of generating code. Instead of calling out to the procedure VECTOR-REF every time it needs to look at a vector, it can use an indexed offset load instruction. This can easily be hundreds of times faster.

Using the compiler also comes at a price. The compiler is free to put variables in machine registers, duplicate variables (provided the duplication has no semantic effect), or eliminate variables that are not necessary. The compiled code cannot be interrupted at arbitrary points. Between these points, the compiler may generate code that does not preserve the consistency of the Scheme memory model. Of course it must restore consistency before checking for interrupts. The end result is that the compiled code may be so different from the original code that it is unrecognizable. It will, however, compute the same value.

Needless to say, the debugger would have a hard time with this. There is no environment data structure. The contents of the registers is known only to the compiler. Variable names have long since gone away, and wouldn't matter because some variables are aliased and others don't even exist. So what is a user to do?

The compiler does something rather sophisticated. It keeps track of which points in the source code correspond to possible interrupt checks. Since it knows that a debugger can only gain control at an interrupt, it can annotate each interrupt poll with meta-information that tells the debugger what part of the source code is running at that point. It is an approximation, but a fairly good and useful one. In addition to this, the compiler emits a variable map that gives the debugger some information about where variables might be located. This allows the debugger to present a fairly good picture of where in the source code you are, and what the variables are bound to, if they exist at all. The debugger includes a simple meta-circular evaluator that can evaluate forms as if they were executed in the context of the debugged stack frame. Not every form can be evaluated, and assignments don't work, but enough code works to present a good illusion.

---

So what is the point of describing this? I think this is a nice engineering compromise between performance and debugging. However, it requires some assumptions. First, it is the case that you cannot get at the environment of an arbitrary compiled procedure. It may or may not exist, and you need the debugging meta-information to parse it, and it may have all, some, none, or extra bindings. It cannot be used programmatically, it can only be presented to the user as an aid to debugging. Second, MIT Scheme allows for first-class environments. When you call (the-environment) you will get an interpreter compatible environment with all that entails. This disables all optimizations done by SF or the compiler because any optimizations could change the expected contents. On the other hand, if you don't use the full environment, you can simply close over the variables that you do use, and the compiler will be sure to preserve the semantics of your closure while it optimizes the code. Third, it assumes that any introspection can be subordinated by the user. That is, I can write code and instruct the compiler to assume that introspection is unnecessary. With this assumption, the compiler can generate much better code. However, that also means that if you want introspection into my compiled code, you are likely to be out of luck.

In conclusion, I have these objections to your assertion that you a standardized first-class environment API to write a portable debugger:

1. If you write a portable meta-circular evaluator to go with your debugger, you can define your own environment structures independent of the underlying implementation.
2. A standardized first-class environment API would unduly restrict implementations to following a particular evaluation model.
3. A first-class environment model that allowed the underlying system to add or remove bindings as it deemed necessary is by definition not portable because no binding or lack thereof could be assumed.
4. Debugging is outside the milieu of the language specification. Each implementation can supply its own debugger or many debuggers or none at all.
5. Not specifying a first-class environment model does not mean that a sophisticated debugger cannot be built.

I personally like the ability to use introspection when I am developing code. But I also like the ability to ‘seal’ the code against introspection in order to make the known working code run fast and to guarantee stability of that code.

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.

Closing in

In the previous posts I showed some problems that occur when you poke holes in the abstraction you get from procedures. By default, lexical scoping is opaque and you have to write extra code to poke through the holes. But is there any advantage to procedural abstraction and lexical scoping beyond the fact that it is a reasonable default?

The big advantage is that procedural abstraction allows you to separate use from implementation. We don't need to know how a procedure accomplishes what it does, we just need to know what the result should be. On the other side of the barrier, we don't need to know how where the arguments came from, or what the result is used for, we just need to compute it. Presumably, the more efficiently the better. Now let's return to Louis Reasoner. He's just written a sorting routine:

(define (lib-sort list <)
  (cond ((pair? list)
         (let ((first (car list)))
           (do ((before '() (cons (car after) before))
                (after (lib-sort (cdr list) <) (cdr after)))
               ((or (null? after) (< first (car after)))
                (append (reverse before)
                        (cons first after))))))
        ((null? list) '())
        (else (error "foo"))))

It occurs to him that maybe that call to reverse could be a bottleneck, so he instruments it with the code from the last post:

(define lib-sort
  (let ((reverse-counter 0))
    (register-counter! reverse-counter)
    (lambda (list <)
      (cond ((pair? list)
             (let ((first (car list)))
               (do ((before '() (cons (car after) before))
                    (after (lib-sort (cdr list) <) (cdr after)))
                   ((or (null? after) (< first (car after)))
                    (set! reverse-counter (+ reverse-counter 1))
                    (append (reverse before)
                            (cons first after))))))
            ((null? list) '())
            (else (error "foo"))))))
;Value: lib-sort

(lib-sort '(3 1 4 1 5 9 2 6 5 3 5) <)
;Value 20: (1 1 2 3 3 4 5 5 5 6 9)

((cadr (assq 'reverse-counter *counters*)))
;Value: 11

But Louis is called away before he can go much further down this path. He gives the rest of his tasks to his intern.

The intern has to write a program that, given a list, sorts it and returns a pair where the car is the sorted list, and the cdr is the length of the sorted list. That's trivial:

(define (sort-and-length list <)
  (let ((s (lib-sort list <)))
    (cons s (length s))))

But it occurs to him that this is less efficient than it could be. The call to length has to traverse the entire list, and presumably the call to lib-sort must as well. In order to cut down on the number of list traversals, the intern takes a look at the code for lib-sort. It is rather baffling to him (he is an intern), but he figures out that since reverse is called on every recursive call, the number of calls to reverse has to equal the length of the list. So he codes up this monstrosity:

(define (sort-and-length list <)
  (let* ((c (assq 'reverse-counter *counters*))
         (start ((cadr c)))
         (s (lib-sort list <)))
      (cons s (- ((cadr c)) start))))

Time passes...

It turns out a customer is complaining that the code is too slow. A quick test shows that he is trying to sort a list of ten thousand elements and it is spending all its time in lib-sort.

“What idiot wrote this?!” asks Cy D. Fect. “There is an FFI to qsort.” Cy replaces the sort routine:

(define (lib-sort list predicate)
  (vector->list (ffi-qsort (list->vector list) predicate)))

Of course he removed the code that tracks calls to reverse because qsort doesn't use it. When he checks in the code, lib-sort is much, much faster, but for some reason all the menus in the GUI now only contain a single entry. Cy calls in Ben Bitdiddle for help. Ben notices that the GUI calls sort-and-length for each menu, and sort-and-length is reporting that each menu has zero entries. He fixes sort-and-length to do the obvious thing and everything is off and running again. Ben shakes his head and sighs.

---

One of the most important points of procedural abstraction is that it allows you to change the implementation of the procedure at will without having to analyze the entire code base. We saw before that if we allow the internal variable names to escape (by using them as keys), then we can no longer change the names. In this case, we're going further. We want to eliminate the name altogether because we're changing the entire algorithm. The variable `reverse-counter' won't even exist anymore in this code. By exposing it in this way, we made it possible for an unplanned dependency to be added.

In this example, the unplanned dependency was rather idiotic. That's not the point. I have run into this sort of bug many, many times where an abstraction is not fully documented (or not well documented) and a programmer misunderstands the API and uses some internal function for the wrong purpose. Things work fine until the implementation changes, then very weird unrelated things start to break. Sometimes the code is so tangled that you have to emulate the effect of the old implementation just to keep from having to rewrite huge swaths of the unrelated code.

Move, Down the road I go

Louis Reasoner doesn't care for all the work he had to do just to make it possible to read and clear the counter. He decides to write a macro to help. It's pretty simple:

(define-syntax register-counter!
  (syntax-rules ()
    ((register-counter! variable)
     (add-counter! (quote variable)
                   (lambda () variable) ;; reader function
                   (lambda () (set! variable 0)) ;; clear function
                   ;; maybe more functions here some day
                   ))))

(define lib-mapcar 
  (let ((calls-to-f 0))
    (register-counter! calls-to-f)
    (lambda (f list)
      (cond ((pair? list)
             (let ((h (car list)))
               (cons (begin
                      (set! calls-to-f (+ calls-to-f 1))
                      (f h))
                     (lib-mapcar f (cdr list)))))
            ((null? list) '())
            (else (error "improper list"))))))

This works nicely.

Management is insisting that the Lisp system support ‘constant ref arguments’. They are a bit unclear as to what the advantages are, but they say that they are absolutely necessary in order to assure investors that modern software techniques are supported. In disgust, Alyssa P. Hacker writes these macros and then takes a vacation:

(define-syntax ref
  (syntax-rules ()
    ((ref var) (lambda () var))))

(define-syntax deref
  (syntax-rules ()
    ((deref var) (var))))

Louis Reasoner takes a look at the code, thinks for a long while, then comes up with a test case:

(define (fib x)
  (if (< (deref x) 2)
      (deref x)
      (let ((x1 (- (deref x) 1))
            (x2 (- (deref x) 2)))
        (+ (fib (ref x1)) (fib (ref x2))))))

(let ((arg 7)) (fib (ref arg)))
=> 13

But Louis sees a problem: suppose we have a function that takes several ref arguments. It's such a pain to write something like this:

(foo (ref x) (ref y) (ref z) (ref a) b c)

So he writes his own macro:

(define-syntax lref
  (syntax-rules ()
    ((lref var ...)
     (list 
       (cons (quote var) (lambda () var)) ...))))

For those unfamiliar with the ... notation, the idea is that it causes pattern repetition. lref will be an n-ary macro. Each var that is passed in will be turned into an entry in an alist.

Now it is much easier to write code like this:

  (foo (lref x y z a) b c) 

With all the references passed in as an alist. Foo will have to be tweaked:

(define (foo ref-args b c)
  (let-syntax ((deref (syntax-rules () 
                        ((deref var) ((cdr (assq 'var ref-args)))))))
    ;; example body for foo
    (display (+ (deref x) (deref y) c))))

(let ((x 3)
      (y 2)
      (z 1))
  (foo (lref x y z) 2 5))
=> 10

The boilerplate syntax at the beginning of foo is a pain, but Louis is sure that some kind of macro can take care of that as well.

---

There is a looming problem here, which I hope is fairly obvious given the last couple of posts. Spoiler below....

I want to be clear on something, though. In any sort of example like this, where there is a problem that is not immediately obvious, you have to write a fair amount of code to get to the heart of the issue. You have the option of using real-world code, but there is often so much going on in the code it is hard to see the specifics. You have the alternative of writing a toy example (like this one), but then you get the objection “no one would ever write such bad code”, so your example, while potentially a problem, is so convoluted that it would never occur in practice.

So here's the big looming problem: the callee needs to know the names of the arguments that the caller assigned. Stupid macros, passing an alist, and so-called constant references are just there for a good story. The problem is that if we wish to change the name of something in foo, we have to locate every possible caller and change the name there as well. The register-counter! has the same problem: if you change the name of the counter variable, you have to find any code that examines the counters and be sure it isn't looking for the old name.

Just use grep? What if they wrote some code over at Larry Liverless Labs that uses the old name? A big advantage of lexical scoping is that interior names are local. You can change them, add them, or remove them without examining the entire code base. The macros that Louis wrote fail because they expose the internal names to code outside the function.

Tomorrow, the advantages of hiding the code...

And nows the time, the time is now

In my previous post I showed one way of breaking procedural abstraction. Dynamic binding allows the details of the implementation to be visible to unrelated code, and this causes unpredictable consequences (if it is used pervasively).

Let's give Louis Reasoner another tricky task. He's going to port the code to Scheme and he is to remove the logging from lib-mapcar and instead instrument the code with a counter that will be used by the statistics package. Recall that the code currently looks like this:

(defun lib-mapcar (f list)
  (cond ((consp list)
         (let ((h (car list)))
           (log "Calling " f " on " h)
           (cons (funcall f h) 
                 (lib-mapcar f (cdr list)))))
        ((null list) '())
        (t (error "improper list"))))

The port to Scheme is easy:

(define lib-mapcar 
  (lambda (f list)
    (cond ((pair? list)
           (let ((h (car list)))
             (cons (f h) 
                   (lib-mapcar f (cdr list)))))
          ((null? list) '())
          (else (error "improper list")))))

And Louis adds a counter:

(define lib-mapcar 
  (let ((calls-to-f 0))
    (lambda (f list)
      (cond ((pair? list)
             (let ((h (car list)))
               (cons (begin
                       (set! calls-to-f (+ calls-to-f 1))
                       (f h))
                     (lib-mapcar f (cdr list)))))
            ((null? list) '())
            (else (error "improper list"))))))

But at this point he is stuck. He wants to be able to get at the value of the counter in order to read the count, but he can't because of the lexical scoping. There is an easy trick. We use another closure that closes over the same variable:

(define *counters* '())

(define (add-counter! name reader)
  (set! *counters* (cons (cons name reader) *counters*)))

(define lib-mapcar 
  (let ((calls-to-f 0))
    (add-counter! 'calls-to-f (lambda () calls-to-f))
    (lambda (f list)
      (cond ((pair? list)
             (let ((h (car list)))
               (cons (begin
                      (set! calls-to-f (+ calls-to-f 1))
                      (f h))
                     (lib-mapcar f (cdr list)))))
            ((null? list) '())
            (else (error "improper list"))))))

And here it is in action:

(lib-mapcar (lambda (x) (* x 2)) '(3 1 4 1 5 9 2 6 5 3 5))
=> (6 2 8 2 10 18 4 12 10 6 10)

((cdr (assq 'calls-to-f *counters*)))
=> 11

Using an alist to hold the counters and just invoking the reader procedure is a little crude (we could make some nice abstractions here), but that isn't the point. The point is that by closing over calls-to-f and exporting that closure we have poked a very tiny hole in our abstraction barrier. The hole is just big enough that some external code that is not under our control can read the value of our counter, but that is it. There is no way for the external code to modify the value. But there is one other thing we hid. The name of the variable that holds the counter is also hidden from the external code. If we want, we can change the code like this:

(define lib-mapcar 
  (let ((the-counter 0))
    (add-counter! 'calls-to-f (lambda () the-counter))
    (lambda (f list)
      (cond ((pair? list)
             (let ((h (car list)))
               (cons (begin
                       (set! the-counter (+ the-counter 1))
                       (f h))
                     (lib-mapcar f (cdr list)))))
            ((null? list) '())
            (else (error "improper list"))))))

I have renamed the variable and all the places that the variable is used. This makes no difference to any other code. And because the scope is lexical, I know that all the code that could possibly care about the variable name is right there. I don't need to sift through the entire rest of the code base or obtain a list of variables from my customers. Nor do I have to tell them I changed the name. Now this is pretty cool.

You should find it easy to imagine how we could allow the external code to reset the counter to zero in addition to reading it, but not allow it to set the counter to an arbitrary value.

Yet more rambling

I hope I'm preaching to the choir when I say that procedural abstraction is the greatest thing since sliced bread. If you're still a skeptic, let me point you at these:

• Lambda: The Ultimate Imperative
• LAMBDA: The Ultimate Declarative
• Debunking the 'Expensive Procedure Call' Myth, or,
  Procedure Call Implementations Considered Harmful, or,
  Lambda: The Ultimate GOTO

Now of course there are a huge number of other worthy abstractions, but since procedural abstraction is universal, you can model them with procedures. (Yes, there are other universal models you could use. No, I'm not suggesting we discard the other abstractions and implement them with procedures.) I'm simply pointing out that procedures are a very nice, powerful, and universal abstraction.

Let's break them.

Why would I want to break abstraction? Isn't that a bad thing? Well, yes, it is. I think it is a complete disaster, and I hope you do, too. But I've noticed a few people that seem to think that maybe a little bending — maybe a tiny bit of tweaking — might be ok if you were able to get something for it at the end of the day. They are wrong.

One reason that procedures make for good abstraction barriers is that they are opaque. As a caller, you cannot see how the procedure is written or how it performs its work. You get to supply the arguments, it gets to return an answer and that's it. The barrier works the other way, too. The procedure you call cannot get its hands on the guts of the caller, either. This wasn't always the case. Some early Lisp dialects were dynamically scoped (but Lisp 1.5 had static binding!). The bindings of the caller were visible in the callee. There were several people that pointed out that this was not a good thing. Suppose you have this code:

;; In a library somewhere:

(defun lib-mapcar (f list)
  (if (null list)
      '()
      (cons (funcall f (car list))
            (lib-mapcar f (cdr list)))))

But later we get a bug report:

(lib-mapcar #'(lambda (x) (+ x 1)) (cons 1 2))
;; This crashes!

Obviously you shoudn't call lib-mapcar on an improper list, but crashing is less desirable than an informative error message, so Louis Reasoner is tasked with fixing lib-mapcar. It takes him a while, but he comes up with this:

(defun lib-mapcar (f list)
  (cond ((consp list)
         (cons (funcall f (car list)) 
               (lib-mapcar f (cdr list))))
        ((null list) '())
        (t (error "improper list"))))

In the code review, Alyssa P. Hacker suggests logging the calls to f, so Louis does this:

(defun lib-mapcar (f list)
  (cond ((consp list)
         (let ((h (car list)))
           (log "Calling " f " on " h)
           (cons (funcall f h) 
                 (lib-mapcar f (cdr list)))))
        ((null list) '())
        (t (error "improper list"))))

The code passes the regression tests and they ship it.

Two days later, a frantic call comes in from Larry Liverless Labs. Their physics package has mysteriously stopped working. They describe the bug:

(let ((h 6)  ;; approx. Planck's constant
      (c 3)) ;; approx. C
  (lib-mapcar
     #'(lambda (lam) (/ (* h c) lam))
    '(3 1 4 1 6)))
;; Expected answer:  (6 18 4 18 3)
=> (3 9 2 9 1)

The problem, obviously, is that the variable h that Louis introduced is shadowing the variable h in the physics package.

“I'll just change it, then. Can I get a list of all the variables used by all our customers so I know which ones to avoid? Oh, and we should document all the variables we declare so that future customers won't accidentally use one.”

The solution is to use lexical scoping because it hides the details of the implementation.

Now I'm not saying that dynamic scoping is bad or wrong, I'm saying that it is the wrong default. Suppose there is a dynamic variable that controls the logging level:

         ...
         (let ((h (car list)))
           (log logging-level "Calling " f " on " h)
         ...

If there are only a handful of these, we could document them all. Or we could invent a naming convention that makes it obvious that we expect it to be dynamic (add asterisks around it, for example), or we could add special forms for establishing and referring to dynamic variables (like fluid-let or parameter-value). But we really want it to be the case that when we send a junior programmer like Louis Reasoner in to look at the code, he can assume that local changes have local effect and that as long as he computes the correct value, he'll be ok.

to be continued...

More rambling

I'm going somewhere with this, I swear.

Primitive ontological abstraction gives us some objects we can play with, but it would be nice to be able to talk about them. Nominal abstraction allows us to assign a name to an object and to use the name to refer to the object. It's such a natural thing to do that you hardly notice it being done, but it is a tremendous source of power as well as confusion. I'm not going to explore this further right now.

So we have objects and names, and at this point we can construct a primitive programming language about on the level of assembly code. It isn't much, but it's better than toggle switches and hex codes. We need a few more abstractions. We'll need relational abstractions of some sort. I don't mean something as formal and heavyweight as a database relation, I mean some means of talking about two objects and how they relate to each other. An example would be a number and an array, and I might want to `put the number in the array'. And we'll want a way to refer to a quality that might be shared among several objects.

Now there are several ways we could go from here, but I was doing a bunch of thinking about procedural abstraction. (I was trying to figure out what sort of abstractions you needed in order to even make sense of procedural abstraction and I came up with the ones I just mentioned.) Procedural abstraction in some sense gives you the verbs you need in order to accomplish something with the objects. You don't strictly need them — very early computers didn't support subroutines, and there are a handful of computer languages that don't have the notion of a procedure. But the large majority of computer languages have a way of creating procedures (or methods, subroutines, functions, whatever you want to name them). Why is this?

One reason is that a function is a very well developed mathematical construct. Hundreds of years of thought have gone into formalizing what a function is. Another reason is that every theory of computability has ended up with modeling programs as the set of partial recursive functions. The final reason is that functions and procedures make extremely good abstraction barriers. A mathematical function is a perfect ‘black box’. It is characterized purely by the pairing up of what goes in and what comes out. Two mathematical functions are different if and only if there is an input-output pair for one that doesn't exist on the other. To a large extent, two computer programs are different if and only if there exists an input that produces different outcomes depending on the program. (There are caveats. Bubble sort and merge sort produce identical results, but whether we considered them the ‘same’ would depend on whether performance and resource use were taken into account.)

Semi-coherent rambling

I need to post more frequently, and if I wait for my thoughts to become coherent it may be quite some time.

I wanted to say something about abstraction, so I was thinking about some of the fundamental abstractions computer scientists use. What's really happening (for some sense of ‘real’) in the computer is some very complex electromagnetic field interactions. But no computer hacker I know sits down at the terminal and starts programming from Maxwell's equations. There are better ways to think about what a computer does.

Maybe the most basic abstraction is what I'll call primitive ontological abstraction. We'll take a fairly stable pattern of currents and we'll call that a ‘number’ or a ‘byte’ or some such thing. A circuit that can maintain the pattern we'll call a ‘register’, so we can talk about ‘register EAX’ holding ‘the value 27’ or somesuch thing. Here we abstracting away the idea of patterns of current flowing through the computer to simple objects. I call it primitive ontological abstraction because we're not dealing with ‘Big-O Object-Oriented’ ideas, but rather with the notion that there are ‘things’ in the computer like bits, bytes, characters, text strings, code chunks, etc. that are the basic ‘stuff’ we're going to compute with.

Without primitive ontological abstraction, our interaction with computer is going to be very limited. We could fiddle around with the electrical signals going in to the processor and maybe cause the computer to halt or generate a non-maskable interrupt, but it's hard to program the computer when you have no notion of ‘instructions’. But primitive ontological abstraction only lifts us up to the machine-code level where we are putting different byte values in sequential memory and then telling the computer to load the ‘program counter’ with a particular start address. At this point we need the next abstraction: naming.

---

Ok, my bus ride is over. We'll leave naming to the next post.

Which Schemes?

What's the point of a Scheme standard? I can think of a number of uses.

• A guideline for new Scheme implementations.
• A touchstone to distinguish a “real” implementation from a wanna-be.
• A reference point for academic papers so they don't need to devote an appendix to describing the semantics of their language.
• A “weighty tome” that adds gravitas to one's bookshelf.
• The reference for nitpicking language lawyers.
• A wishlist of features that would be nice to have.

But I think the most important thing for a Scheme standard to be is this:

• An agreement between language implementors and programmers that specifies the minimum functionality that an implementor is expected to provide and the maximum functionality that a programmer can assume is available from any system that claims to meet the standard.

Naturally, any implementation can provide more functionality than is prescribed, and no one expects any particular program to use all possible functionality.

Additional functionality is the way the language has evolved. The different implementations would add extra features for various reasons. Since these features were developed independently, there were often incompatible. Some of the differences were simply idiosyncratic, others, however, were caused by deliberate decisions about design. When a feature proved its utility, the programmers would put pressure on the implementations to add the feature. When a useful feature was incompatible between different implementations, an effort was made to reconcile the incompatibilities. In the early days, this could be accomplished by getting all the implementors in the same room and letting them argue. This isn't practical anymore.

The reason I put together my spreadsheet of Scheme implementations was not so that I could argue that any one is better than another. My purpose was altogether different. I wanted to get an idea of what subset of Scheme implementations are likely to affect or be affected by a new standard. Most of these Scheme implementations are at least R5RS compatible, and all of them extend the language in various ways. Some of these extensions are quite common across a large number of implementations.

If every Scheme implementation implemented an extension to the language in the same way with the same semantics, I can hardly there being much opposition to declaring this to be a standard feature. It would be a de-facto standard and it would require zero effort on the part of implementors if it became a de jure standard. On the other hand, if no Scheme implementation implemented a particular extension (say, for example, SRFI-49), there shouldn't be an enormous outcry if the feature were omitted from the standard. The issue becomes more complicated when a feature is available in only a subset of the implementations.

Let's take a particular example: SRFI-8 (special form receive for multiple values), is available in 21 implementations. The SRFI is trivially implemented with an R5RS syntax-rules macro. It seems to me that this would be a prime candidate for inclusion in an upcoming standard. It would require very little work on the part of implementors (unless, of course, they did not support multiple values at all or did not have syntax-rules), and the aesthetic issue (introducing a trivial special form) is fairly minor.

SRFI-36, on the other hand, is only available in three implementations. It defines a hierarchy of I/O exceptions. It would be non-trivial to add this to an implementation that had no exception hierarchies, or to one that had incompatible exceptions. It would be a poor candidate for inclusion.

What about something like SRFI-23? Here's where things get tricky. There are only seventeen implementations that support SRFI-23, but included in those seventeen are PLT Scheme, MIT Scheme, Gambit, Gauche, Chicken, SCM, SISC, and Scheme48. It's not universal, but it is very widespread. Or what about SRFI-48? It is available in Larceny, Scheme48, partly in Kawa, STKlos, PLT Scheme, Iron Scheme, and S7. If you use MIT Scheme, Gambit, Gauche, Chicken, SCM or SISC, you're out of luck.

The tiers that I had published previously were not there because of my preferences. They were there as a rough guide to determine how much support is needed or given for a particular feature set. Your new special form may be the niftiest hack since McCarthy's amb, but if you can't get buy-in from PLT, MIT, Gauche, Guile, Gambit, Chicken, Scheme48, and SCM, it just cannot be called a standard. Alternatively, if the “Top Ten” buy into your ideas (whatever the “Top Ten” might be), then it will probably be one of the less supported implementations that will have to admit that they do not adhere to the standard.

So which Schemes are the leaders of the pack?