blob: a15d3f9ab00dd28ead79d546971ff4e7b7a4bc6c (
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
37
38
39
40
41
42
43
44
|
module Minilang.Lambda.Eval where
import Data.Text (Text, unpack)
import Debug.Trace (trace)
data Term
= Var Text
| Lam Text Term
| App Term Term
deriving (Show, Read, Eq)
type Env = [(Text, Value)]
data Value
= V Text
| Abs Text Term Env
| Ap Value Value
deriving (Show, Read, Eq)
-- call-by-value evaluator
eval :: Term -> Env -> Value
eval (Var x) env = case lookup x env of
Just v -> v -- we do not need to eval v again
Nothing -> V x -- x is not bound in env
eval (Lam x body) env = Abs x body env
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
Abs x body env' -> eval body ((x, a') : env')
f' -> Ap f' a'
evalNeed :: Term -> Env -> Value
evalNeed (Var x) env = case lookup x env of
Just v -> v
Nothing -> V x
evalNeed (Lam x body) env = Abs x body env
evalNeed (App f a) env =
let a' = eval a env
in case evalNeed f env of
Abs x body env' -> evalNeed body ((x, a') : env')
f' -> Ap f' a'
|
