I am building a simple interpreter for untyped lambda calculus, currently trying to implement alpha-reduction.
According to this document on LC:
Alpha-reduction is used to modify expressions of the form "λx.M". It renames all the occurrences of x that are free in M to some other variable z that does not occur in M (and then λx is changed to λz).
It appears that I need to collect the information about the scope (free/bound) of variables prior to alpha-reducing the expression.
How should one go about this? My initial idea was to traverse the AST and produce something similar to a symbol table.