Wiz - A Scheme interpreter implemented in Haskell

A Program is a collection of Form:

data Program = Program [Form]

A Form can be either a Definition or an Expression:

data Form = FDef Definition | FExpr Expression
  deriving (Show)

A Definition binds a Symbol (represented as a String) to an Expression.

data Definition = Definition String Expression
  deriving (Show)

Expression are more complex and have many faces:

data Expression = Number Integer
                | Boolean Bool
                | Operator Char
                | Symbol String
                | Quote Expression
                | If Expression Expression Expression
                | Lambda Formals Expression
                | List [Expression]
                  deriving (Eq)

In order to perform something useful we must be able to evaluate a Form. Evaluation happens in an Environment, which is a mapping from Symbol to Expression.

data Environment = Environment (Map.Map String Expression)
                   deriving (Eq)

In other words, the Environment tells us what Expression we need to evaluate to know the value of a Symbol (notice the recursive nature of this notion).

eval is the only function exported by the Wiz.EvalApply module. It takes an Environment and a Form, and returns a pair composed by a possibly new Environment and an Expression representing the return value of the Form.

eval :: Form -> Environment -> (Environment, Maybe Expression)
eval form env =
  case form of
    FDef def   -> (evalDefinition def env, Nothing)
    FExpr expr -> (env, Just $ evalExpr env expr)

Evaluating a Definition adds a new mapping in the Environment. It's the only thing that produces a side-ezffect, namely a variation in the Environment in which we'll evaluate future forms.

evalDefinition :: Definition -> Environment -> Environment
evalDefinition (Definition symbol expr) (Environment env) =
  Environment (Map.insert symbol expr env)

Evaluating an Expression yields another simpler Expression, until we reach an atomic value (so far they are Number, Boolean and procedures) that we are able to display.

evalExpr :: Environment -> Expression -> Expression

A special case is evaluating a procedure application (e.g. (fact 10)). Assuming fact refers (in the current Environment) to a procedure, we invoke apply.

apply :: Environment -> Expression -> [Expression] -> Expression

To apply (or invoke) a procedure we must evaluate its body in a new fabricated enviroment based on the original one but extended with new symbols. These symbols are the formals parameters of the procedure, their values are given by the expressions passed as arguments in the procedure call.

apply env (Lambda (Formals formals) body) arguments =
  evalExpr env' body
  where env' = extendEnvironment env (zip formals evaledArguments)
        extendEnvironment (Environment env) newElems =
          Environment (Map.union (Map.fromList newElems) env)
        evaledArguments = map (evalExpr env) arguments

After reading some Scheme code in init.scm to initialize the environment, we enter the main loop (I'm in love with this idea of building basic language utilities expressed in the language itself).

The main loop is relatively simple. It receives a new form from user input (I used Haskeline to implement the commandline), it parses it to obtain an internal representation tree, and it eval it. And so on.