Variations in F#: Research compiler with Joinads and more!

In this article, I'll write about an experimental extension for F# that I call joinads. If you're following my blog, you may have seen an academic paper [1] that I wrote about it some time ago. Anyway, the motivation for the extension is that there are many useful programming models for reactive, concurrent and parallel programming that would deserve some syntactic support in the programming language.

For example, when programming with futures (the Task<T> type), you may want to implement logical "or" operator for tasks that returns true immediately when the first task completes returning true. When programming with events (the IObservable<T> type), we'd like to wait for the event that happens first. Finally, when programming using agents, we sometimes need to wait only for certain types of messages. All of these problems can be solved, but require the use of (sometimes fairly complicated) functions. Joinads make it possible to solve them directly using the match! syntax. For example, here is the "or" operator for tasks:

1: future {
2:   match! after 100 true, after 1000 false with
3:   | !true, _ -> return true
4:   | _, !true -> return true
5:   | !a, !b -> return a || b }

I'll write more about this example (and the implementation) in a later article. This article focuses on the compiler extension itself. I created a first implementation of the idea above during my internship with Don Syme at MSR Cambridge, but then changed it quite a bit when writing the academic paper mentioned above. However, I never released the source code.

Thanks to the open-source release of F# it is now quite easy to modify the F# compiler and make the modifications available, so I decided I should finally release my F# extensions. I also recently blogged about [3, 4] encoding idioms (also called applicative functors) in C#. I was wondering how to do that in F# and so I also created a simple extension computations based on this abstraction. The support for idioms is just an experiment, but it could be useful, for example, for programming with formlets. You'll find more about it at the end of the article.

You can find the source code on my GitHub (there is also a link compiled binaries at the end of the article). The source code is cloned from an F# Mono repository, which means that it should build on Linux and MacOS too.

Table of contents

• Creating a simple joinad
• Translation of joinads
• Creating a simple idiom
• Translation of idioms
• Summary & downloads

NOTE: This extension is just a research project. As far as I know, there are currently no plans to include it in some future version of the F# compiler. If you like it, download it, play with it and write about it (and send requests to support the idea to the F# team :-)).

Creating a simple joinad 

The version implemented in the prototype is slightly different to the one described in my earlier paper, but the principle is the same. If you want to use the match! construct for working with your computations, you need to extend the computation builder type with a few members. The members have quite straightforward type signature, and so it shouldn't be difficult to implement them.

In this article, I implement a computation builder for working with F# option<'T> type. This is a slightly oversimplified example. We can use match! to write patterns that specify that a monadic value should contain a certain actual value. When working with options, this means the same thing as matching the monadic (option) value against Some. However, the example demonstrates the idea and I'll write about more exciting examples in the future.

Implementing Maybe builder

To implement computation builder that supports the match! construct, we create a usual F# computation builder with the standard members that are used by F# today (you need at least Bind, Return and Delay) and then add three additional members. The additional members are Fail, Choose and Merge. Take a look at the implementation and we'll discuss them later (if you place the mouse pointer over the identifier, you'll see the type, which is quite useful for understanding the operations):

 1: type MaybeBuilder() =
 2:   // Standard monadic 'bind', 'return' and 'zero'
 3:   member x.Bind(v, f) = Option.bind f v
 4:   member x.Return(a) = Some a
 5:   member x.ReturnFrom(o) = o
 6:   member x.Fail() = None
 7: 
 8:   // Combine two options into option of tuple 
 9:   member x.Merge(v1, v2) = 
10:     match v1, v2 with
11:     | Some a, Some b -> Some (a, b)
12:     | _ -> None
13:   // Return first option that contains value
14:   member x.Choose(v1, v2) = 
15:     match v1 with 
16:     | Some(v1) -> Some(v1) 
17:     | _ -> v2
18: 
19:   // Creating & executing delayed computations
20:   member x.Delay(f) = f
21:   member x.Run(f) = f()
22: 
23: // Create an instance of the computation builder
24: let maybe = new MaybeBuilder()

The computation builder implements most of the operations in the usual way. The Delay operation can be implemented in two ways. For computations that can wrap a function unit -> 'T into the computation value M<'T> (without running it), we coudl wrap the function in Delay and don't include Run. I'm using another approach which is to return the function passed to Delay as it is (as a function) and add Run member that runs the function.

The interesting members needed for the match! construct are:

• The Fail operation creates a computation that never produces any value. For options, this is the None value. (This is quite similar to the mzero operation that exists in MonadPlus type class in Haskell)
• The Merge operation has a type M<'T> -> M<'U> -> M<'T * 'U>. It takes two computations and returns a single computation that contains a tuple with the values. If any of the options passed as arguments is None, the result will also be None. If both of the options are Some, then we can get both values and return a tuple wrapped in Some. For some computations including options, this operation can be implemented using Bind and Return. However, this doesn't work for all computation.
• Finally, the Choose operation has a type M<'T> -> M<'T> -> M<'T>. The intuitive explanation of the operation is that it should return the "first available value" and prefer values from the first argument. For options this means that if the first argument is Some, we return its value (wrapped in Some). Otherwise, we return the value of the second argument. The operation returns None only if both of the arguments are None.

Now that we have a computation builder maybe, let's write some interesting computation. We look how the example looks using the match! syntactic sugar and then explain how the translation works...

Implementing three-valued logic

As a simple example, we look how to implement the logical "or" operation for a three-valued logic. As the name suggests, the logic works with three values (true, false and unknown). We can represent values of the three-valued logic using option<bool> and take None to represent the unknown value.

The unknown value means that the value may be either true or false, but we don't know which one. The "or" operator reflects this interpretation - for example, when we write false "or" unknown, the result is unknown (it may be either true or false depending on the second value). The following snippet uses match! to implement the "or" operator as defined in the Kleene logic:

 1: /// Logical 'or' operator for ternary (Kleene) logic
 2: let kleeneOr a b = maybe {
 3:   match! a, b with
 4:   | !true, _ -> return true
 5:   | _, !true -> return true 
 6:   | !a, !b -> return a || b }
 7: 
 8: // Print truth table for the ternary operator
 9: for a in [Some true; None; Some false] do
10:   for b in [Some true; None; Some false] do
11:     printfn "%A or %A = %A" a b (kleeneOr a b)

I believe that the example is quite easy to read. When using match!, the patterns we write in clauses can be of two forms. The form !<pat> (binding pattern) means that the computation must produce a value and the value should match the usual F# pattern <pat>. In case of options, !true essentially means that the value should be Some(true). The form _ (ignore pattern) specifies that we don't care about the value (there may or may not be some value). For options, this means the same thing as underscore (wildcard pattern) used in the standard match construct.

The first two clauses encode the situation when one of the values is true. In that case, we immediately know that the result of the "or" operation is also true. The last case handles the case when both values are known - in that case, we simply use the standard logical or. In all remaining cases that are not covered by any of the patterns, the result is unknown.

When using joinads to work with option values, we don't get any interesting benefits. The true power of the construct is that it can be used for working with other interesting types of computations. This is possible, because match! is just a syntactic sugar that is translated to the primitives of the computation builder...

Translation of joinads 

The desugaring of match! is slightly more sophisticated than the desugaring of let! and other standard constructs. The idea is that we combine all inputs for a clause (horizontally) using the Merge operation. Then we select the first matching clause (vertically) using the Choose operation. A pattern matching failure is represented using the Fail operation. The above example will be translated to the following code:

 1: // Translation of individual clauses - inputs are combined 
 2: // using 'Merge' and body is wrapped using 'Delay'
 3: let cl1 = maybe.Bind(a, function 
 4:   | true -> maybe.Return(maybe.Delay(fun () -> maybe.Return(true)))
 5:   | _ -> maybe.Fail() )
 6: let cl2 = maybe.Bind(b, function 
 7:   | true -> maybe.Return(maybe.Delay(fun () -> maybe.Return(true)))
 8:   | _ -> maybe.Fail() )
 9: let cl3 = maybe.Bind(maybe.Merge(a, b), fun (a, b) -> 
10:   maybe.Return(maybe.Delay(fun () -> maybe.Return(a || b))))
11: 
12: // Clauses are combined using 'Choose' and selected
13: // delayed clause is then evaluated using 'Run'
14: maybe.Bind(maybe.Choose(maybe.Choose(cl1, cl2), cl3), fun r -> 
15:   maybe.Run(r))

When translating joinads, the modified F# compiler works in two steps:

• Every clause is translated into a separate computation of type M<M<'T>> (or M<unit -> M<'T>> when using Delay that returns a function as in this example). The inner computation represents the body to be executed when the clause is selected. To create this computation, the compiler first merges are inputs that appear in binding patterns using Merge. Then it uses Bind to transform the input into either Return (containing a delayed body when the value matches a pattern) or Fail (when the produced value doesn't match).
• After translating the clauses, the compiler constructs an expression that selects the first clause that contains or produces body (the terminology is intentionally vaugue, because the meaning depends on the type of computation). This is done by combining all clauses in the top-to-bottom order using Choose. The result is a computation M<M<'T>> (or M<unit -> M<'T>> for delayed functions), so we need to unwrap the body. This is done by passing the overall result as an argument to Bind. In the continuation, we apply the Run operation, which can unwrap the delayed computation (for computations that are delayed by design, the Run operation isn't required).

The best way to understand how the translation works is to experiment with it. If you're interested in joinads, you can either build the compiler from sources on GitHub (the changes are commented, so you can find more information there too) or you can download binaries at the end of the article.

As mentioned in the introduction, when implementing joinads, I did one additional change in the F# compiler that allows us to use with idioms (applicative functors). The next section presents a basic example.

Creating a simple idiom 

Just like monads (and joinads), idioms (also called applicative functors) are abstract computations that are encoded in terms of several primitive operations. You can find more information about them in the article [2] by Conor McBride and Ross Paterson. Idioms are weaker than monads, which means that every monad is also an idiom. If you have Bind and Return, you can implement operations required by idiom. The opposite is not true - it is not possible to define Bind in terms of operations provided by idioms.

To support writing idioms in the computation expression syntax, we need to take something out. This is opposed to adding new, more powerful, syntax (the match! construct) for joinads. I wrote more about this in my previous articles [3, 4] about idioms in C#. Using idioms, we cannot write computations where binding (e.g. using let!) depends on value of an earlier binding. This essentially means that we have to specify all values bound using let! at once. The binding can then be followed by some computation that eventually returns a value.

The syntactic support that I implemented in computation expressions is quite different to the bracket notation used in the original paper. I think I expect the F# extension to be also used differently. The original paper talks more about function applications with some hidden effects. The F# extension I implemented is more suitable for computations modeled as idioms. A good example of this could be formlets (see the original research paper [5], F# implementation by Mauricio Scheffer or the version in WebSharper). Formlets describe structure of a web page together with code that is executed after the server receives form values back from the client. Here is an example:

1: let registration = formlet {
2:   // Binding that specifies the form components
3:   let! name = Formlets.textbox
4:   and age = Formlets.textbox
5:   and birthday = Formlets.dateSelector
6:   // Calculation with the values
7:   let age = int age
8:   return Person(name, age, birthday) }

The F# extension for idioms allows you to write multiple bindings (at the beginning of a computation) using let! ... and. You can write as many and keywords to specify multiple bindings as you wish. After you finish binding, you're not allowed to use let! again and you need to finish with return.

As I mentioned, this is really just an experiment that I implemented while working on joinads (because it was quite easy). If you find it useful (or not useful) for some interesting purpose, I'd be happy to hear from you. To add some details about how the extension works, let's look at a simplistic example...

Implementing ZipList builder

Perhaps the simplest example of idiom is ZipList. It allows us to apply some operations to elements pulled from lists in parallel. If we have operation f and lists [1;2;3] and [a;b;c], we can use ZipList to get [f (1, a); f (2, b); f (3, c)]. This is not something that you could easily implement using a monad. But when we can bind all lists at once, we can combine them using the zip operation and then iterate over the elements. The following snippet shows the computation builder that defines ZipList idiom:

 1: type ZipList() = 
 2:   // Unit of ZipList idiom is infinite sequence of values
 3:   member x.Return(a) = seq { while true do yield a }
 4:   // Standard projection for sequences
 5:   member x.Select(v, f) = Seq.map f v
 6:   // Zip values from two (possibly infinite) sequences
 7:   member x.Merge(u, v) = Seq.zip u v
 8: 
 9: // Create instance of the computation builder
10: let zip = ZipList()

The Return operation has the same type as the Return operation from monads. The implementation for ZipLists creates an infinite sequence that repeatedly returns the same value. The Select operation implements a projection (look at the type signature). This operation is weaker than Bind for monads. It only allows us to transform values into new values, but we cannot construct and return new M<'T> value inside Select. Finally, the Merge operation is the same Merge that is required for joinads (which is quite interesting!) For the ZipList idiom, the operation zips the two sequences given as arguments.

To demonstrate how the translation works, let's take a look at transposing matrices. The following implementation is quite naive and inefficient, but it is probably the simplest example I could use.

Transposing matrices with idioms

I already explained the matrix transposition algorithm using idioms in my last C# article. If the matrix transposition function gets a matrix with zero rows, it generates an infinite sequence of empty sequences (which can be done using Return). Otherwise, it takes the first row and "zips" it with the transposed sub-matrix that starts from the second row. The zipping can be written using our new let! .. and syntax:

 1: let rec transpose (matrix) = zip {
 2:   if Seq.length matrix = 0 then 
 3:     // Generate infinite sequence of empty lists
 4:     return Seq.empty
 5:   else 
 6:     // Zip elements of the first row with rows of recursively 
 7:     // transposed sub-matrix starting from the second row
 8:     let! xs = Seq.head matrix
 9:     and xss = transpose (Seq.skip 1 matrix)
10:     return Seq.concat [ seq [ xs ]; xss ] }
11: 
12: // Gives: [ [ 1; 4]; [2; 5]; [3; 6] ]
13: transpose [ [ 1; 2; 3]; [ 4; 5; 6 ] ]

I said earlier that an idiom computation needs to start with let! This wasn't quite precise - if we write something like the example above, the compiler will treat it as two separate computations (one in the then branch and the other in the else branch). The first computation is quite simple and calls just return. The second computation is more interesting. It parallelly binds items from the first row and items from the transposed sub-matrix and prepends the elements to the front. (The transposition needs to be lazy, so I'm using seq<'T> which doesn't support nice :: operation).

One thing that's worth mentioning is that the return keyword in the second branch doesn't correspond to the Return operation. You'll see how this is actually compiled in the next section. I'm not sure whether this is a problem or not - if you have any feelings about this, please leave a comment. A possible alternative would be to use the yield keyword in the first case (and define the Yield operation instead).

Translation of idioms 

The interesting part of the translation is when we write some computation that starts with let! .. and and eventually ends with return. In that case, the translator combines all inputs using the Merge operation and transforms the rest of the computation into a function that can be passed as argument to Select:

 1: let rec transpose (matrix) = 
 2:   // Two branches of 'if' are translated separately
 3:   if Seq.length matrix = 0 then 
 4:     zip.Return(Seq.empty)
 5:   else 
 6:     // Combine inputs using 'Merge' and then use 
 7:     // 'Select' to implement projection
 8:     zip.Select
 9:       ( zip.Merge(Seq.head matrix, transpose (Seq.skip 1 matrix)),
10:         fun (xs, xss) -> Seq.concat [ seq [ xs ]; xss ])

As you can see, the two expressions that were used as inputs for let! and and are now combined using Merge. This also demonstrates that the second one cannot depend on the value of the first one. The lambda function passed to Select extracts individual elements of the tuple using pattern that is created from the patterns used in the binding so that the correct variables are in scope.

Summary & Downloads 

This article presents two extensions to F# computation expressions. This is just a research extension and there are currently no plans to include any of this in some future version of F#, but you can download the modified F# compiler and F# interactive below and explore the modified source on GitHub. If you create some interesting computation that uses the extension, please let me know in the comments!

The modified version of F# computation expressions allows you to encode two new types of computations. The first is joinads, which I presented some time ago in a workshop paper at PADL. It adds amatch! construct, which can be used for programming with futures, events and other concurrent & reactive abstractions.

The second extension adds support for idioms. It is used when the computation builder defines Select, Merge and Return. These operations are not expressive enough to support general let! binding, but you can write code using restricted let! .. and syntax that requires specifying all inputs at once. The syntax should be useful for example for writing code based on formlets.

Downloads & Source code

• Download the F# compiler and F# interactive binaries (ZIP) - To use modified fsi.exe in Visual Studio, go to "Options" - "Tools" and specify the path in "F# interactive path" under "F# Tools" (Unfortunately, I don't think there is a way to use the modified version for Visual Studio IntelliSense)
• The source code for the F# extension can be found on GitHub and should compile on Windows, Mac as well as Linux. It should be also possible to use it for MonoDevelop IntelliSense, but I haven't tried that yet.
• The sample joinads and idioms defined in this article are available on my Blog & Documents GitHub. The samples can be executed using the modified F# Interactive.

References

• [1] Joinads: A retargetable control-flow construct for reactive, parallel and concurrent programming - Tomas Petricek, Don Syme
• [2] Applicative programming with effects - Conro McBride, Ross Paterson
• [3] Beyond the Monad fashion (I.): Writing idioms in LINQ - Tomas Petricek's blog
• [4] Beyond the Monad fashion (II.): Creating web forms with LINQ - Tomas Petricek's blog
• [5] The essence of form abstraction - Ezra Cooper, Sam Lindley, Philip Wadler, and Jeremy Yallop