[plt-scheme] determine free variables

On Mon, Mar 24, 2008 at 7:55 PM, YC <yinso.chen at gmail.com> wrote:
> Hi all -
>
> What's the best approach to determine free variables at source level?
>
> What i am trying to accomplish is to take a scheme expression from a file,
> say
>
> (+ foo bar)
>
> and transform
>
> (lambda (foo bar)
>   (+ foo bar))
>
> for arbitrary scheme expressions.
>
> Are there procedures that would allow me to determine whether a symbol has a
> binding?  Given scheme identifier can be bound to different values, it seems
> like this would require some sort of runtime environment inspection - is
> that true?

No, runtime checks are not required because Scheme is lexically
scoped. You can determine all the free variables an expression needs
after parsing. The process of determining free variables, however, is
not just an excercise in syntatic analysis.

The program transformation technique known as lambda lifting computes
the free variables needed by each function in order to make all
functions global. That is, lambda lifting eliminates nested functions
by making them global. The free variables of each function need to be
known in order to add them as parmeters to the lifted functions. In a
paper by Johnsson (1985) the term lambda lifted was coined and the
paper describes an O(n^3) algorithm to compute free variables (and
perform optimal lambda lifting). In 2004, Danvy and Schultz developed
an O(n^2) graph-based algorithm, but it is only an approximation of
optimal lambda lifting (i.e. to many variables may be unnecessarily
indentified as free). In 2005, Morazan and Mucha developed an O(n^3)
graph-based optimal lambda lifting algorithm. In 2007, Morazan and
Schultz developed an O(n^2) graph-based optimal lambda lifting
algorithm.

You can read the 2007 article in the draft proceedings of IFL 2007,
you can wait until the LNCS version is in print, or you can privately
request I send you a copy if you are interested.

I hope this points you in the right direction for some algorithms.

Marco