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

On 2018-02-13, Louis Krupp <lkrupp@nospam.pssw.com.invalid> wrote:
> On Mon, 12 Feb 2018 11:25:36 -0800 (PST), dror.openu@gmail.com wrote:
>
>>Suppose I have a simple C-like programming language: ...
>>Like you can see, it supports nested functions.
>
> gcc supports nested functions as an extension to C. Compiling this
> program with -O0 -fdump-tree-all and looking at the generated files
> might give you an idea of one way to do it:
>
> #include <stdio.h>
>
> int main(void)
> {
> int k1 = 1;
> int p1(void)
> {
> int k2 = 2;
> int p2(void)
> {
> int k3 = 3;
> int p3(void)
> {
> return k1 + k2 + k3;
> }
> return p3();
> }
> return p2();
> }
> int n;
>
> n = p1();
> printf("%d\n", n);
>
> return 0;
> }
>
> Apparently, gcc chains stack frames, and accessing uplevel variables,
> as when p3 uses k1 and k2, seems like it would take O(n) time, where n
> is the nesting level.
>
> The alternative, a display vector, seems like it would be easier to


The problem is that these functions can recurse, including mutually.
So that is to say, you can end up with a situation in which you have
a single activation of main with a single k1 variable, but multiple
activations of p2, with multiple k2's all being live at the
same time.


To complicate things, the multiple active p2 functions can be lifted
into function pointers, all of which are simultaneously valid.


Each of those p2 pointers could be called back by some external function.
Those calls have to establish an environment which resolves to the
correct k2, and at the same time to the one and only k1.


That doesn't rule out display vectors, but it seems like each function
activation has to have its own complete display vector.


For instance the p2 level functions need a two-level vector. Under
the same main invocation, they share the vec[0] entry pointing to
the main frame; but each one has a different vec[1] referencing its
own frame.


When a p3 executes it has its own 3 element vec[]. The vec[0] and
vec[1] are copied from the parent p2. If a pointer to a p3 is captured,
then its vec[1] correctly references the particular dynamic p2 instance
in which it is scoped; vec[2] references its own environment.


Under this scheme, we basically we need o(n^2) storage for the vectors,
for n nesting levels in the absence of recursion.


The compiler can determine which functions aren't subject to indirection
and avoid allocating the trampoline space for that.


If functions are downward funargs only (turn to garbage when they go out
of scope), the trampoline space needed to capture a given function
invocation can be part of the activation record of the block in which
that function is declared. When that block terminates, the function is
garbage, and so is its trampoline.


> implement unless you're doing this for a real machine with a real (and
> therefore limited) set of registers.


Hmm. The vectors can be treated like any array, or set of local
variables (v0, v1, ..). We generate abstract AST code to load these and
use them; then that code gets subject to register allocation like
anything else.
[As I recall, you do need a display with a pointer for each lexical scope,
but so long as you don't expect closures to work, you can do it in
constant time with a fixed location where each scope stores its
current frame pointer. If you want closures, then you're into tree
shaped stacks and garbage collected stack frames. -John]

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