add minimal evaluator and type inference

1 files changed, 36 insertions, 0 deletions

diff --git a/lambda-calcul/haskell/src/Minilang/Lambda/Eval.hs b/lambda-calcul/haskell/src/Minilang/Lambda/Eval.hs
new file mode 100644
index 0000000..68b01be
--- /dev/null
+++ b/lambda-calcul/haskell/src/Minilang/Lambda/Eval.hs
@@ -0,0 +1,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