Saturday, July 21, 2007

Cute idiom from Haskell

I discovered this fun idiom while implementing an operational semantics in Haskell. The monadic syntax allows you to express monadic binding in either of two directions:
x <- expr;
or
expr -> x;
Combine that with a custom operator definition:
infix 4 |-
and now you can write interpreters whose syntax looks like a big-step evaluation judgment:
(|-) :: Env -> Expr -> Eval Value
env |- Lit n = return (Number n)
env |- Var x = case lookup x env of
Just v -> return v
Nothing -> throwError $ "free variable " ++ x
env |- Abs x e = return (Closure env x e)
env |- App e1 e2 =
do env |- e1 -> v1;
env |- e2 -> v2;
case v1 of
Closure env' x e ->
do (x,v2):env' |- e -> v;
return v;
Number n -> throwError $ "apply " ++ (show n)