module Minilang.Lambda.Eval where

import Data.Text (Text)

data Term
  = Var Text
  | Lam Text Term
  | App Term Term
  deriving (Show, Read, 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