Implementation of untyped lambda calculus in Haskell using only functions available from the standard prelude.
The design is layered, with each layer building on the previous. The layers are described below.
The base layer contains lambda expressions along with certain key functions related to α and β conversion. Lambda Expressions are represented as a Haskell data type:
data Λ = V Var | A Λ Λ | Λ Var Λ -- constructors for (1) terms (2) applications (3) abstractionsLambda expressions are anonymous - there is no concept of a named expression. This means that an expression can only be re-used by literally copying it in its entirety (since it can't be referred to by name). This limitation is remedied by Named Expressions.
Lambda expressions are implemented in Terms.hs
A named expression is similar to a lambda expression except that it has a name and its body may itself contain references to other named expressions. This allows complex expressions to be defined conveniently by re-using earlier definitions, but it's really no more than syntactic sugar because all references are translated into raw anonymous lambda expressions before evaluation. (This translation is particularly interesting when simple or mutual recursion is involved)
Named expressions live inside an environment. References are translated into lambda expressions by looking them up in the environment. An environment is an ordered structure insofar as expressions can only refer to named expressions added earlier. In addition named expressions may be private, meaning that only some expressions may refer to them.
Named expressions and environments are implemented in Env.hs
A simple parser allows named expressions to be created from scripts that resemble a primitive programming language. The parser is implemented using the approach described by Erik Meijer in his Haskell course.
The parser is implemented in Parse.hs.
The final layer is a REPL which allows a user to interactively define and evaluate expressions. These can be typed directly into the repl or loaded from scripts files.
The REPL is implemented in Repl.hs