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:

  1. Anonymous1:52 PM

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

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

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

    ReplyDelete
  4. 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.

    ReplyDelete
  5. 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.

    ReplyDelete