free variables in lambda terms ?

Konst Sushenko konsu@microsoft.com
Thu, 25 Apr 2002 20:07:01 -0700


hi, would someone please help me with the question below? i tried asking
on comp.lang.functional list but noone responded...


"konsu" <konsu@hotmail.com> wrote in message
news:<ATOx8.42722$t65.9246@nwrddc02.gnilink.net>...
> hello,
>=20
> as an exercise, i am trying to implement a pure lambda calculus
interpreter.
> i am using normal order reduction with textual substitution of terms.
>=20
> a program that my interpreter accepts is a list of name/term
declarations:
>=20
> <name 1> =3D <lambda term 1>
> ...
> <name N> =3D < lambda term N>
>=20
> each declaration defines a global name and binds a term to it, and the
> interpreter starts evaluation with the term named 'main'.
>=20
>=20
> i implemented all the functions necessary to evaluate a closed lambda
term,
> and now i got to the point where i need to handle free variables in a
term.
> my assumption is that free variables denote terms declared as above.
>=20
> my question is when should i expand free variables? i also would
appreciate
> any references to literature, etc. where this is discussed.
>=20
> so far i believe the way to do it is to reduce a term to its normal
form
> without handling free variables, and then, if it has free variables,
look up
> their definitions in the environment and replace them with their
bodies,
> evaluate the resulting term to its normal form again, and keep
repeating
> this process until no free variables are found.
>=20
> is this the right way to do it? or should i check for free variables
when i
> compute the WHNF, etc.? any advice from the experts?
>=20
> thanks
> konst
>=20
>=20