Taking Computation Expressions one step further

In this article, I will present an extension to the F# compiler (I used November 2010 CTP from the F# PowerPack site). I was inspired by two things. The first was an old attempt to create a computation builder for XML/HTML objects, which wasn’t very successful because of the lack of options in computation expressions (not saying anything bad, still many more options than Haskell monads). The second was Tomas Petricek’s article about joinads. My extension is more generic than the joinads, so even though joinads implementations are less nicely formed, you can do much more than just joinads. I still like to use Tomas’ joinads extension because it really does look better.

My extension basically allows you to use keywords other than let! and do! for the same operations and the builder object can know which keyword was used. The original keywords are kept unchanged for support. Any “ident! pat = e in ce” is first redirected to Ident(e, fun pat –> ce) and if Ident doesn’t exist it is redirected to CustomBinding(“Ident”, e, fun pat –> ce). Any “ident@! e in ce” is first redirected to Ident(e, fun () –> ce) and if Ident doesn’t exist it is redirected to CustomDo(“Ident”, c, fun () –> ce).

I felt obligated to show not only the extended power of the extension (look at the HTML example later on), but also show that it can do almost anything joinads can (so I implemented the Maybe and Future joinads). If the only thing you need from here is joinads, you should really consider simply using Tomas’ extension which gives better looking joinads and few more features.

Here is a simple HTML object:

~~"ul" {
    yield ~~"li" { yield a "http://websharper.com/" "WebSharper" }
    yield ~~"li" { yield a "http://tryfsharp.org/" "TryF#" }
|> printfn "%A"

Looks like regular computation expression, but let’s look at the function “a”:

let a href text =
    ~~"a" {
        href@! href
        target@! "_blank"
        return text
The important part is the two lines with href@! and target@!. This is quite simple. The CustomDo method looks like this:
member this.CustomDo (n : string, v, f) =
    elem.SetAttributeValue(XName.Get (n.ToLower()), v)

In the case of the href@! line, the call is: builder.CustomDo(“Href”, href, …).

Now let’s look at my implementation of the Maybe joinad. First, let’s compare to Tomas’ code:

/// Logical 'or' operator for ternary (Kleene) logic
let kleeneOr a b = maybe {
    match! a, b with
    | !true, _ -> return true
    | _, !true -> return true
    | !a, !b -> return a || b }

// Print truth table for the ternary operator
for a in [Some true; None; Some false] do
    for b in [Some true; None; Some false] do
        printfn "%A or %A = %A" a b (kleeneOr a b)

It tried to match the 2 bool options, if it succeeds it binds the result to a Some, if it fails it returns a None. Mine is a bit uglier, but follows the same logic:

let kleeneOr a b = maybeJ {
    match@! [a; b]
    with@! fun [Some true; _] -> true
    with@! fun [_; Some true] -> true
    with@! fun [Some a; Some b] -> a || b
    ignore () }

Not sweet sugar, but keeps the same logic. If you need to match a list of values not of the same type, you have to box everything before the match, unbox after it and create active patterns which accept obj and imitate the native patterns (e.g. ( |True|_| ) for match (box true) and ( |Zero|_| ) for matching (box 0)).

Notice that we still match a set of arguments, we match them to cases which might and might not work and return a value. The operation is so similar, that you can write a simple pre-processor which will translate it automatically.

Let’s move on to my implementation of the Future joinad. With the joinads:

future {
    match! after 100 true, after 1000 false with
    | !true, _ -> return true
    | _, !true -> return true
    | !a, !b -> return a || b }
And my implementation sticks to the same logic:
future {
    match@! [after 100 true; after 1000 true]
    with@! fun [Some true; _] -> true
    with@! fun [_; Some true] -> true
    with@! fun [Some a; Some b] -> a || b
    ignore ()

And again the logic is kept, while (some of) the sugar is removed.

I think that this demonstrates the potential of the extended computations expressions (or e-monads). The greatest disadvantage of both the joinads extension and the e-monads extension is that even though you can tell Visual Studio to use the updated tools, IntelliSense still uses the same tools. Hopefully, in a future version of Visual Studio there will be an option to change IntelliSense’s F# tools.

  • Tomas Petricek’s article about joinads (including compiled tools and his sources code).
  • The full example (including the implementations) can be downloaded from here.
  • The compiled tool for e-monads can be downloaded from here.

This entry was posted on Saturday, April 2nd, 2011 at 12:35 PM and is filed under Default. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

3 Responses to “Taking Computation Expressions one step further”

  1. MBR Says:

    I think this sort of capibility is needed in F# – the ability to express DSL’s in the language.
    But when you go this far past computation you’re no longer using a functional paradigm, but just emulating a macro system, with the restriction that you must over-load existing keywords – this seems like the worst of both worlds. We should just have a user-definable sub-grammar inside of {}’s, and real macros that when run take the expression tree as input, and output another one which is compiled. (Template-matching using the user-defined grammar would also be a plus.)

  2. MBR Says:

    Arg – that was only half my response…
    Anyway, good work getting in there and extending the compiler…

  3. Ramon Snir Says:

    @MBR: I am a big fan of DSLs, so I felt it is really missing from F#. If you want to keep inside the functional paradigm, you should also be careful with regular computation expressions (e.g. Tomas Petricek’s imperative monad).

    I think that the e-monads are a good place to start when designing a DSL – you got a good basis, but you are still limited to F# logic.

Leave a Reply