Representing Closures in C

"Johan Tibell" <johan.tibell@gmail.com>
21 Jul 2006 14:07:52 -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)
[2 later articles]
| List of all articles for this month |

From: "Johan Tibell" <johan.tibell@gmail.com>
Newsgroups: comp.compilers
Date: 21 Jul 2006 14:07:52 -0400
Organization: Compilers Central
Keywords: storage, design, question, comment
Posted-Date: 21 Jul 2006 14:07:52 EDT

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]


Post a followup to this message

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