Representing Closures in C

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;
};


struct app {
struct exp *exp1;
struct exp *exp2;
};


enum type {
LAM,
VAR,
APP,
LIT
};


struct exp {
enum type type;
union {
struct lam *lam;
char *var;
struct app *app;
int lit;
} form;
};


Now I'm about to write my eval function which looks something like
this:




int eval(struct exp *exp)
{
switch(exp->type) {
case LIT:
return exp->form.lit;
break;
/* more cases */
}
}


When evaluating a function application I need to somehow bind the value
of the evaluated argument to the variable in the lambda abstraction.
This example will hopefully explain what I need to achieve:


((\x. x) 1)


When evaluating this call to the identity function the whole expression
should evaluate to one. I need a way to bind the value 1 to the
variable x so x can later be looked up in the body of the lambda
abstraction.


I'm aware that I have more (and probably more difficult) problems
ahead such as dealing with tail recursion, etc. but it would be nice if
I could get something up and running before improving upon it.


I imaging that I'll need:
* a way of representing the environment in which an expression should
    be evaluated
* a way of representing closures
Perhaps that's the same thing?


Any good articles or papers out there? What I'm looking for is a
hands-on description of how it can be done 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]

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