blob: 68b01be914980611232e9de8e961ddc4756afb4f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
module Minilang.Lambda.Eval where
import Data.Text (Text)
data Term
= Var Text
| Lam Text Term
| App Term Term
deriving (Show, Eq)
type Env = [(Text, Term)]
-- call-by-value evaluator
eval :: Term -> Env -> Term
eval (Var x) env = case lookup x env of
Just v -> v -- we do not need to eval v again
Nothing -> Var x
eval (Lam x body) _env = Lam x body
eval (App f a) env =
-- we need to force evaluation of the argument
-- because haskell's default semantics is non-strict
-- so if a' is never used, it will not be evaluated!
let a' = eval a env
in seq a' $ case eval f env of
Lam x body -> eval body ((x, a') : env)
f' -> App f' a'
evalNeed :: Term -> Env -> Term
evalNeed (Var x) env = case lookup x env of
Just v -> evalNeed v env -- we need to eval v because it might be a redex
Nothing -> Var x
evalNeed (Lam x body) _env = Lam x body
evalNeed (App f a) env =
case evalNeed f env of
Lam x body -> evalNeed body ((x, a) : env)
f' -> App f' a
|
