This is to record some ideas from the 60’s that were used to implement Algol 60 compilers, especially the Burroughs 5500 and its descendants. The particular issue was how to compile nested procedure definitions when the body of the code referred to variables declared at several levels of the nest. Some Algol compilers provided only global and local variables but this did not comply with the official language definition.

I will repeat here an anecdote which I think is roughly correct. I heard this from John McCarthy, who was on the committee that defined the language. Near the end of the deliberations, they were tacking down the precise meaning of invoking a subroutine. It was proposed that the body of the text of the routine definition could be placed at the call site, replacing the routine parameters in the routine’s body with the corresponding arguments at the call site, without changing the meaning of the program. There were details to be filled in but this seemed to be an attractive and fundamentally simple proposal. It had already been decided that procedures could be defined in inner blocks, (like gcc and unlike C) and these combined decisions had consequences that McCarthy suspects some other committee members did not appreciate. McCarthy says he had an idea of how to compile such programs. I don’t know whether the following is McCarthy’s idea but here is what some conforming compilers did. At this time the stack idea was not widely known but I suspect that the committee members were all aware of it. Hardware lacked direct support for a stack, but then again it lacked direct support for just about any particular pattern.

When a call site is compiled, code to transfer to the routine is produced. A conventional register locates the first unallocated stack space and another register locates the caller’s frame for use upon return. The prelude (code) of the routine allocates a new stack frame, and saves the caller’s frame address therein. The frame is also made to locate the older frame that was produced when the static block holding the routine definition was entered. That older frame holds values of variables declared in that outer block. Following this chain to older frames leads to one frame for each level of lexical scope. Some shortcuts are possible but this is the general case. A procedure value was implemented with a double pointer: to the compiled routine body and to the stack frame holding the values of variables declared in the scope immediately containing the routine definition.

This talks about the display which optimized this a bit. Just now I do not see that the display idea works.

Indefinite Extent

Just as the storage is deallocated for local variables when a routine returns, so too does the viability of functions defined therein end. Some languages have syntax to support capturing the address of a variable in a stack frame beyond the life of the frame; they also allow capturing references to routines defined therein. Programs that try to use this are in error and there is typically no feasible checking. Languages with indefinite extent closures are required to ‘do the right thing’ which may involve retaining whatever storage remains accessible via the retained references. This precludes simple stack protocol for a routine X that defines other routine Y references to which may outlive an invocation of X. The local variables of X remain accessible via Y.