Re: Representing Closures in C

Johan Tibell wrote:
> I'm writing a small lambda calculus interpreter in C. My abstract
> syntax tree (AST) representation looks like this:
>
> struct exp;
>
> struct lam {
> char *id;
> struct exp *exp;
> };
... snip
> int eval(struct exp *exp) {
> switch(exp->type) {
> case LIT:
> return exp->form.lit;
> break;
...
> [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]


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).


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.


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.


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

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