Re: Add nested-function support in a language the based on a stack-machine

On 2018-03-06, John Levine <johnl@taugh.com> wrote:
>>>>>This is because displays were found to be more costly for Algol-like
>>>>>languages ...
>>>
>>>>> IIRC the additional cost is in updating the display on calls
>>>>>and returns.
>
> I get the impression that displays describe two different things.
>
> One is a static array that has one entry for each level of lexical
> scoping. In a routine declared N levels (zero based) down, its prolog
> saves the Nth entry in the display and replaces it with a pointer to
> the current stack frame, and the epilog restores it. It can assume
> that higher level routines have correctly set entries 0:N-1. That
> seems pretty efficient. Assuming the saved pointer is at a known
> location in each stack frame you can do a longjmp and unwind stacks
> without too much pain.
>
> The other is the same array, but with a copy of the current display in
> each routine's stack frame. This is slower at call time but probably
> faster to use on machines like S/360 without direct addressing
> since the display on the stack is addressable from the frame pointer,
> but static data needs to load a pointer from a constant pool. A
> longjmp doesn't need anything special since stacked displays go away
> when the stack frames go away.


This is precisely what I happen to be working on at the moment: a
virtual machine for a Lisp dialect in which I plan to have displays
copied into the local stack frame. I expect it to be a performance
advantage that there is nothing special to do when the stack frame goes
away.


If we had to take some unconditional action, we would have to set up
a catch frame. That means doing a setjmp-like operation that saves
a whole vector of stuff similar to a jmp_buf. Not just machine
registers, but the signal mask (or a virtualized representation of it,
for efficiency), and other stuff. This vector is larger than a display
display containing a significant number of environment levels!


If the scope binds dynamically scoped variables, those have to be
undone. However, that requires no special action. The dynamic
environment is a chain rooted at a global pointer called dyn_env. Long
ago, I made the simplifying design decision to include this dyn_env
pointer in the jmp_buf-like context that is saved at every catch frame,
and so there is no need for a scope to set up a handler for the sake of
restoring dynamically scoped bindings. The normal return case has to
restore dyn_env, which is simple.

Return to the comp.compilers page.
Search the comp.compilers archives again.