Thursday, November 10, 2011

C Style Haskell

The other day I found this blog post on using GADTs to write more usable C style Haskell with effects, references and loops.  I couldn't get the example to typecheck without unsafe code, so I decided to write my own version.  I wanted the behavior of expressions and operators to be similar to that of C.  This is what I came up with:

swap(r1, r2) = function $ do
{
    z <- auto undefined;
    z =: r1;
    r1 =: r2;
    r2 =: z;
};

factorial = function $ do
{
    a <- auto 0;
    n <- auto 1;
    for ( a =: prim 1 , a <. prim 11 , a +=: prim 1 ) $ do
    {
       n *=: a;
       iff ( a <. prim 7) $ do
       {
           continue;
       };

       iff ( a >. prim 5) $ do
       {
            break;
       };
    };

    swap( ref n , ref a);
    returnF n;
};

In order to make expression operators behave similarly to that of C, I added a new value type as a wrapper for computations in this monad, so as to allow seamless composition of effectfull expressions on the right hand side.  "callCC" was used to achieve C style "break", "continue" and "return".  The reader monad was used to hide the extra arguments required for callCC.

Here is the full code.

4 comments:

  1. Hi! Thanks for this code, this is what I dream about to optimize low-level Haskell functions.
    I got a compilation error:
    Couldn't match type `a0' with `a'
    `a0' is untouchable
    inside the constraints (b ~ Comp)
    bound at a pattern with constructor
    C :: forall r a b. MIO r (V b r a) -> V Comp r a,
    in a case alternative
    `a' is a rigid type variable bound by
    the type signature for val :: V b r a -> MIO r a
    at /home/named/Downloads/raw.hs:69:8
    Expected type: V b0 r0 a0 -> ReaderT (Control r) (ContT r IO) a
    Actual type: V b0 r0 a0 -> MIO r0 a0
    In the pattern: C m
    In a case alternative: C m -> val' =<< m
    In the expression:
    case val of {
    R r -> liftIO $ readIORef r
    L v -> return v
    C m -> val' =<< m }

    Couldn't match type `b0' with `b1'
    because type variable `b1' would escape its scope
    This (rigid, skolem) type variable is bound by
    a pattern with constructor
    C :: forall r a b. MIO r (V b r a) -> V Comp r a,
    in a case alternative
    The following variables have types that mention b0
    val' :: V b0 r0 a0 -> MIO r0 a0
    (bound at /home/named/Downloads/raw.hs:74:1)
    Expected type: ReaderT (Control r) (ContT r IO) (V b0 r0 a0)
    Actual type: MIO r (V b1 r a)
    In the pattern: C m
    In a case alternative: C m -> val' =<< m
    In the expression:
    case val of {
    R r -> liftIO $ readIORef r
    L v -> return v
    C m -> val' =<< m }

    Did you test your code with ghc-7.6?

    ReplyDelete
  2. I haven't tested with GHC-7.6 yet. Does ImperativeHaskell work?https://github.com/mmirman/ImperativeHaskell

    ReplyDelete
    Replies
    1. Imperative Haskell does work. Thank you, now I feel safe. I can write C-style if I do need performance.

      Delete
    2. I wouldn't count on it for performance. Run tests. Monad transformer stacks aren't the fastest.

      Delete

1. Do be civil.
2. Reasonable criticisms are welcome, but personal opinions are not.
3. These posts are not for evangelizing languages, but for contemplating interesting properties.