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)

5 comments:

Anonymous said...

Since when can you write "m -> x" in do notation!? It's not Haskell 98.

Dave Herman said...

I don't know, I just tried it in GHC 6.6.1 and it worked! Google was no help. Who knows?

sigfpe said...

Apparently it's a bug that has now been fixed :-(

Paul Steckler said...

Whoa!

return (Closure env x e)

Any self-respecting Haskeller
would write

return $ Closure env x e

or

(return . Closure) env x e

Or not.

Dave Herman said...

For posterity, here's the trac ticket where they removed the bug/feature:

GHC Bug #1555

Maybe I can still convince someone that this would be useful as an opt-in feature with some compiler flag.