Re: Representing Closures in C

> > [There's certainly been a lot of work on this. Seems to me you basically
> > want to carry a symbol table along with each expression. -John]


I threw together a crude and probably incorrect interpreter tonight. I
store bound variables in a linked list that's carried along with the
closure.


struct env {
                char *id;
                struct value val;
                struct env *next;
};


struct closure {
struct env *env; /* free variables */
struct exp *exp; /* body to be evaluated */
char *id; /* the variable to bind when evaluated */
};


This is probably not very efficient (if you know of a better way
please tell me) but it also allows expressions to share the "tail" of
the environment. (Imagine a tree turned upside down.) It might be
better to store top level functions (which I have not implemented yet)
in a hashtable so they can be looked up more efficiently.


The source code is available here, it is quite short.
http://www.itstud.chalmers.se/~larssont/interpreter/


It is neither garbage collected nor tail recursive at the moment.


Tommy Thorn wrote:
> Do yourself a favor and read Simon Peyton Jones' "The Implementation
> of Functional Programming Languages" (available for free here:
> http://research.microsoft.com/~simonpj/papers/slpj-book-1987/index.htm)
> or even more to the point, Implementing functional languages: a
> tutorial
> (http://research.microsoft.com/Users/simonpj/Papers/pj-lester-book).


I've read parts of Simon Peyton Jones's book but I'm unsure about how
much overlap there is between writing an interpreter for non-strict and
strict languages. In particular, do I need graph reduction?


> There's a range of choices in the implementation. John's suggestion
> is one option. Another one is to implement beta substitutions
> literally (called "template expansion"); that is, to evaluate
>
> ((\x.e1) e2)
>
> by deep copying(*) e1, replacing instances of variable x by the
> argument (e1[e2/x]). That will work in the framework you sketched
> above.


Interesting approach, I've never actually thought about performing
beta-substitution in that way.


> Pretty much all the remaining alternatives require some amount of
> transformation on the original expression (~ compilation). Fx.
> eliminating the dynamic variable lookup in the scheme suggested by
> John, you'd replace variables with their de Bruin index and use it to
> access the value of that variable in the closure.


I did quick search for "de Bruin index" but it came back empty. What is
a "de Bruin index"? Also, I'm not opposed to doing some
transformations, I'll probably do both closure conversion and CPS
transformation as suggested here:
http://www.iro.umontreal.ca/%7Eboucherd/mslug/meetings/20041020/minutes-en.html


> Have fun,
> Tommy


Thanks.


> (*) Be careful to handle names correctly, eg. ((\x.\x.e1) e2) = \x.e1,
> not \x.(e1[e2/x])


I think my interpreter handles this correctly. Is this a problem with
both strict and non-strict interpreters?

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