Re: Representing Closures in C

"Tommy Thorn" <tommy.thorn@gmail.com>
21 Jul 2006 17:32:51 -0400

          From comp.compilers

Related articles
Representing Closures in C johan.tibell@gmail.com (Johan Tibell) (2006-07-21)
Re: Representing Closures in C haberg@math.su.se (2006-07-21)
Re: Representing Closures in C tommy.thorn@gmail.com (Tommy Thorn) (2006-07-21)
Re: Representing Closures in C johan.tibell@gmail.com (Johan Tibell) (2006-07-22)
Re: Representing Closures in C wyrmwif@tsoft.org (SM Ryan) (2006-07-23)
Re: Representing Closures in C haberg@math.su.se (2006-07-23)
Re: Representing Closures in C tommy.thorn@gmail.com (Tommy Thorn) (2006-07-25)
Re: Representing Closures in C tommy.thorn@gmail.com (Tommy Thorn) (2006-07-25)
Re: Representing Closures in C haberg@math.su.se (2006-07-25)
| List of all articles for this month |

From: "Tommy Thorn" <tommy.thorn@gmail.com>
Newsgroups: comp.compilers
Date: 21 Jul 2006 17:32:51 -0400
Organization: http://groups.google.com
References: 06-07-051
Keywords: functional, storage
Posted-Date: 21 Jul 2006 17:32:51 EDT

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


Post a followup to this message

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