patternMinor

Simple evaluator of Scheme-like expressions in Haskell

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

schemesimpleevaluatorexpressionslikehaskell

Problem

This is my first nontrivial Haskell program:

```
module Main where
import qualified Data.Map as Map

type Env = Map.Map String Expression

data Expression =
Constant Integer
| Variable String
| Add Expression Expression
| Multiply Expression Expression
| Let [(String, Expression)] Expression
| Lambda String Expression
| Call String Expression
| Closure Env String Expression
deriving Show

evaluate :: Env -> Expression -> Expression

evaluate env constant@(Constant _) = constant

evaluate env (Variable name) =
case Map.lookup name env of
Just expr -> expr
_ -> error ("No such variable " ++ name ++ " in Variable expression")

evaluate env (Add aExpr bExpr) =
let
aValue = evaluate env aExpr
bValue = evaluate env bExpr
in
case (aValue, bValue) of
(Constant aInt, Constant bInt) -> Constant (aInt + bInt)
_ -> error ("Add applied to non-integer")

evaluate env (Multiply aExpr bExpr) =
let
aValue = evaluate env aExpr
bValue = evaluate env bExpr
in
case (aValue, bValue) of
(Constant aInt, Constant bInt) -> Constant (aInt * bInt)
_ -> error ("Multiply applied to non-integer")

evaluate env (Let bindings body) =
let
addBindingsToEnv acc [] = acc
addBindingsToEnv acc (x : xs) =
let acc' = Map.insert (fst x) (evaluate env (snd x)) acc
in addBindingsToEnv acc' xs
in evaluate (addBindingsToEnv env bindings) body

evaluate env (Lambda param body) = Closure env param body

evaluate env (Call name arg) =
let
evaluateClosure (Closure capturedEnv param body) =
let
argValue = evaluate env arg
closureEnv = Map.insert param argValue capturedEnv
in
evaluate closureEnv body
in
case Map.lookup name env of
Just x@(Closure _ _ _) -> evaluateClosure x
Just x -> error ("Variable " ++ name ++ " is not closure in Call expression")
_ -> error ("No such variable " ++ name ++ " in Call expression")

main :: IO ()
main = do
let

Solution

I would change the type of evaluate to return Either String Expression. This also leads to using the Monad to structure the functions.

As an example:

evaluate :: Env -> Expression -> Either String Expression
evaluate env (Add aExpr bExpr) = do
    aValue  Right $ Constant (aInt + bInt)
      _ -> Left "Add applied to non-integer"

This way you can catch and handle the Left cases. error is typically not used in live code.

Personally, I would break the Number expressions out into a separate Math/Num Expression
which would allow for focused optimizations, sub processing, etc.

data MathExpression = Add Expression Expression
                    | Multiply Expression Expression
  deriving (Show)

data Expression = Constant Integer
                | Variable String
                | MathExpression
                | Let [(String, Expression)] Expression
                | Lambda String Expression
                | Call String Expression
                | Closure Env String Expression
  deriving Show

I find the stacked let style really hard to follow and in most cases you do no need them. This is especially true once evaluate returns an Either.

evaluate env (Call name arg) =
    case Map.lookup name env of
      Just (Closure capturedEnv param body) -> do
        argValue  Left ("Variable " ++ name ++ " is not closure in Call expression")
      _ -> Left ("No such variable " ++ name ++ " in Call expression")

-- move this out to facilitate unit testing
evaluateClosure :: String -> Env -> Expression -> Expression -> Either String Expression
evaluateClosure param capturedEnv body closure =
  let closureEnv = Map.insert param closure capturedEnv
   in evaluate closureEnv body

Code Snippets

evaluate :: Env -> Expression -> Either String Expression
evaluate env (Add aExpr bExpr) = do
    aValue <- evaluate env aExpr  -- if either of these two evaluates fail this call
    bValue <- evaluate env bExpr  -- to evaluate will stop and return the failure 
    case (aValue, bValue) of
      (Constant aInt, Constant bInt) -> Right $ Constant (aInt + bInt)
      _ -> Left "Add applied to non-integer"

data MathExpression = Add Expression Expression
                    | Multiply Expression Expression
  deriving (Show)

data Expression = Constant Integer
                | Variable String
                | MathExpression
                | Let [(String, Expression)] Expression
                | Lambda String Expression
                | Call String Expression
                | Closure Env String Expression
  deriving Show

evaluate env (Call name arg) =
    case Map.lookup name env of
      Just (Closure capturedEnv param body) -> do
        argValue <- evaluate env arg
        evaluateClosure param capturedEnv body argValue
      Just x -> Left ("Variable " ++ name ++ " is not closure in Call expression")
      _ -> Left ("No such variable " ++ name ++ " in Call expression")

-- move this out to facilitate unit testing
evaluateClosure :: String -> Env -> Expression -> Expression -> Either String Expression
evaluateClosure param capturedEnv body closure =
  let closureEnv = Map.insert param closure capturedEnv
   in evaluate closureEnv body

Context

StackExchange Code Review Q#69459, answer score: 3

Revisions (0)

No revisions yet.