F Sharp Programming/Computation Expressions

F# : Computation Expressions

Computation expressions are easily the most difficult, yet most powerful language constructs to understand in F#.

Monad Primer

Computation expressions are inspired by Haskell monads, which in turn are inspired by the mathematical concept of monads in category theory. To avoid all of the abstract technical and mathematical theory underlying monads, a "monad" is, in very simple terms, a scary sounding word which means execute this function and pass its return value to this other function.

Note: The designers of F# use the term "computation expression" and "workflow" because it's less obscure and daunting than the word "monad", and because monad and computation expression, while similar, are not precisely the same thing. The author of this book prefers "monad" to emphasize the parallel between the F# and Haskell (and, strictly as an aside, it's just a neat sounding five-dollar word).

Monads in Haskell

Haskell is interesting because it's a functional programming language where all statements are executed lazily, meaning Haskell doesn’t compute values until they are actually needed. While this gives Haskell some unique features such as the capacity to define "infinite" data structures, it also makes it hard to reason about the execution of programs since you can't guarantee that lines of code will be executed in any particular order (if at all).

Consequently, it's quite a challenge to do things which need to be executed in a sequence, which includes any form of I/O, acquiring locks objects in multithreaded code, reading/writing to sockets, and any conceivable action which has a side-effect on any memory elsewhere in our application. Haskell manages sequential operations using something called a monad, which can be used to simulate state in an immutable environment.

Visualizing Monads with F#

To visualize monads, let's take some everyday F# code written in imperative style:

let read_line() = System.Console.ReadLine()
let print_string(s) = printf "%s" s

print_string "What's your name? "
let name = read_line()
print_string ("Hello, " + name)

We can re-write the read_line and print_string functions to take an extra parameter, namely a function to execute once our computation completes. We’d end up with something that looks more like this:

let read_line(f) = f(System.Console.ReadLine())
let print_string(s, f) = f(printf "%s" s)

print_string("What's your name? ", fun () ->
    read_line(fun name ->
        print_string("Hello, " + name, fun () -> () ) ) )

If you can understand this much, then you can understand any monad.

Of course, it is perfectly reasonable to say what masochistic reason would anyone have for writing code like that? All it does it print out "Hello, Steve" to the console! After all, C#, Java, C++, or other languages we know and love execute code in exactly the order specified—in other words, monads solve a problem in Haskell which simply doesn't exist in imperative languages. Consequently, the monad design pattern is virtually unknown in imperative languages.

However, monads are occasionally useful for modeling computations which are difficult to capture in an imperative style.

The Maybe Monad

A well-known monad, the Maybe monad, represents a short-circuited computation which should "bail out" if any part of the computation fails. Using a simple example, let’s say we wanted to write a function which asks the user for 3 integer inputs between 0 and 100 (inclusive) -- if at any point, the user enters an input which is non-numeric or falls out of our range, the entire computation should be aborted. Traditionally, we might represent this kind of program using the following:

let addThreeNumbers() =
    let getNum msg =
        printf "%s" msg
        // NOTE: return values from .Net methods that accept 'out' parameters are exposed to F# as tuples. 
        match System.Int32.TryParse(System.Console.ReadLine()) with
        | (true, n) when n >= 0 && n <= 100 -> Some(n)
        | _ -> None
    
    match getNum "#1: " with
    | Some(x) ->
        match getNum "#2: " with
        | Some(y) ->
            match getNum "#3: " with
            | Some(z) -> Some(x + y + z)
            | None -> None
        | None -> None
    | None -> None

Note: Admittedly, the simplicity of this program -- grabbing a few integers -- is ridiculous, and there are many more concise ways to write this code by grabbing all of the values up front. However, it might help to imagine that getNum was a relatively expensive operation (maybe it executes a query against a database, sends and receives data over a network, initializes a complex data structure), and the most efficient way to write this program requires us to bail out as soon as we encounter the first invalid value.

This code is very ugly and redundant. However, we can simplify this code by converting it to monadic style:

let addThreeNumbers() =
    let bind(input, rest) =
        match System.Int32.TryParse(input()) with
        | (true, n) when n >= 0 && n <= 100 -> rest(n)
        | _ -> None
        
    let createMsg msg = fun () -> printf "%s" msg; System.Console.ReadLine()
    
    bind(createMsg "#1: ", fun x ->
        bind(createMsg "#2: ", fun y ->
            bind(createMsg "#3: ", fun z -> Some(x + y + z) ) ) )

The magic is in the bind method. We extract the return value from our function input and pass it (or bind it) as the first parameter to rest.

Why use monads?

The code above is still quite extravagant and verbose for practical use, however monads are especially useful for modeling calculations which are difficult to capture sequentially. Multithreaded code, for example, is notoriously resistant to efforts to write in an imperative style; however it becomes remarkably concise and easy to write in monadic style. Let's modify our bind method above as follows:

open System.Threading
let bind(input, rest) =
    ThreadPool.QueueUserWorkItem(new WaitCallback( fun _ -> rest(input()) )) |> ignore

Now our bind method will execute a function in its own thread. Using monads, we can write multithreaded code in a safe, imperative style. Here's an example in fsi demonstrating this technique:

> open System.Threading
open System.Text.RegularExpressions

let bind(input, rest) =
    ThreadPool.QueueUserWorkItem(new WaitCallback( fun _ -> rest(input()) )) |> ignore
    
let downloadAsync (url : string) =
    let printMsg msg = printfn "ThreadID = %i, Url = %s, %s" (Thread.CurrentThread.ManagedThreadId) url msg
    bind( (fun () -> printMsg "Creating webclient..."; new System.Net.WebClient()), fun webclient ->
        bind( (fun () -> printMsg "Downloading url..."; webclient.DownloadString(url)), fun html ->
            bind( (fun () -> printMsg "Extracting urls..."; Regex.Matches(html, @"http://\S+") ), fun matches ->
                    printMsg ("Found " + matches.Count.ToString() + " links")
                )
            )
        )
        
["http://www.google.com/"; "http://microsoft.com/"; "http://www.wordpress.com/"; "http://www.peta.org"] |> Seq.iter downloadAsync;;

val bind : (unit -> 'a) * ('a -> unit) -> unit
val downloadAsync : string -> unit

>
ThreadID = 5, Url = http://www.google.com/, Creating webclient...
ThreadID = 11, Url = http://microsoft.com/, Creating webclient...
ThreadID = 5, Url = http://www.peta.org, Creating webclient...
ThreadID = 11, Url = http://www.wordpress.com/, Creating webclient...
ThreadID = 5, Url = http://microsoft.com/, Downloading url...
ThreadID = 11, Url = http://www.google.com/, Downloading url...
ThreadID = 11, Url = http://www.peta.org, Downloading url...
ThreadID = 13, Url = http://www.wordpress.com/, Downloading url...
ThreadID = 11, Url = http://www.google.com/, Extracting urls...
ThreadID = 11, Url = http://www.google.com/, Found 21 links
ThreadID = 11, Url = http://www.peta.org, Extracting urls...
ThreadID = 11, Url = http://www.peta.org, Found 111 links
ThreadID = 5, Url = http://microsoft.com/, Extracting urls...
ThreadID = 5, Url = http://microsoft.com/, Found 1 links
ThreadID = 13, Url = http://www.wordpress.com/, Extracting urls...
ThreadID = 13, Url = http://www.wordpress.com/, Found 132 links

Its interesting to notice that Google starts downloading on thread 5 and finishes on thread 11. Additionally, thread 11 is shared between Microsoft, Peta, and Google at some point. Each time we call bind, we pull a thread out of .NET's threadpool, when the function returns the thread is released back to the threadpool where another thread might pick it up again—its wholly possible for async functions to hop between any number of threads throughout their lifetime.

This technique is so powerful that it's baked into F# library in the form of the async workflow.

Defining Computation Expressions

Computation expressions are fundamentally the same concept as seen above, although they hide the complexity of monadic syntax behind a thick layer of syntactic sugar. A monad is a special kind of class which must have the following methods: Bind, Delay, and Return.

We can rewrite our Maybe monad described earlier as follows:

type MaybeBuilder() =
    member this.Bind(x, f) =
        match x with
        | Some(x) when x >= 0 && x <= 100 -> f(x)
        | _ -> None
    member this.Delay(f) = f()
    member this.Return(x) = Some x

We can test this class in fsi:

> type MaybeBuilder() =
    member this.Bind(x, f) =
        printfn "this.Bind: %A" x
        match x with
        | Some(x) when x >= 0 && x <= 100 -> f(x)
        | _ -> None
    member this.Delay(f) = f()
    member this.Return(x) = Some x

let maybe = MaybeBuilder();;

type MaybeBuilder =
  class
    new : unit -> MaybeBuilder
    member Bind : x:int option * f:(int -> 'a0 option) -> 'a0 option
    member Delay : f:(unit -> 'a0) -> 'a0
    member Return : x:'a0 -> 'a0 option
  end
val maybe : MaybeBuilder

> maybe.Delay(fun () ->
    let x = 12
    maybe.Bind(Some 11, fun y ->
        maybe.Bind(Some 30, fun z ->
            maybe.Return(x + y + z)
            )
        )
    );;
this.Bind: Some 11
this.Bind: Some 30
val it : int option = Some 53

> maybe.Delay(fun () ->
    let x = 12
    maybe.Bind(Some -50, fun y ->
        maybe.Bind(Some 30, fun z ->
            maybe.Return(x + y + z)
            )
        )
    );;
this.Bind: Some -50
val it : int option = None

Syntax Sugar

Monads are powerful, but beyond two or three variables, the number of nested functions becomes cumbersome to work with. F# provides syntactic sugar which allows us to write the same code in a more readable fashion. Workflows are evaluated using the form builder { comp-expr }. For example, the following pieces of code are equivalent:

Sugared syntax	De-sugared syntax
let maybe = new MaybeBuilder() let sugared = maybe { let x = 12 let! y = Some 11 let! z = Some 30 return x + y + z }	let maybe = new MaybeBuilder() let desugared = maybe.Delay(fun () -> let x = 12 maybe.Bind(Some 11, fun y -> maybe.Bind(Some 30, fun z -> maybe.Return(x + y + z) ) ) )

Note: You probably noticed that the sugared syntax is strikingly similar to the syntax used to declare sequence expressions, seq { expr }. This is not a coincidence. In the F# library, sequences are defined as computation expressions and used as such. The async workflow is another computation expression you'll encounter while learning F#.

The sugared form reads like normal F#. The code let x = 12 behaves as expected, but what is let! doing? Notice that we say let! y = Some 11, but the value y has the type int option rather than int. The construct let! y = ... invokes a function called maybe.Bind(x, f), where the value y is bound to parameter passed into the f function.

Similarly, return ... invokes a function called maybe.Return(x). Several new keywords de-sugar to some other construct, including ones you've already seen in sequence expressions like yield and yield!, as well as new ones like use and use!.

This fsi sample shows how easy it is to use our maybe monad with computation expression syntax:

> type MaybeBuilder() =
    member this.Bind(x, f) =
        printfn "this.Bind: %A" x
        match x with
        | Some(x) when x >= 0 && x <= 100 -> f(x)
        | _ -> None
    member this.Delay(f) = f()
    member this.Return(x) = Some x

let maybe = MaybeBuilder();;

type MaybeBuilder =
  class
    new : unit -> MaybeBuilder
    member Bind : x:int option * f:(int -> 'a0 option) -> 'a0 option
    member Delay : f:(unit -> 'a0) -> 'a0
    member Return : x:'a0 -> 'a0 option
  end
val maybe : MaybeBuilder

> maybe {
    let x = 12
    let! y = Some 11
    let! z = Some 30
    return x + y + z
};;
this.Bind: Some 11
this.Bind: Some 30
val it : int option = Some 53

> maybe {
    let x = 12
    let! y = Some -50
    let! z = Some 30
    return x + y + z
};;
this.Bind: Some -50
val it : int option = None

This code does the same thing as the desugared code, only its much much easier to read.

Dissecting Syntax Sugar

According the F# spec, workflows may be defined with the following members:

Member	Description
member Bind : M<'a> * ('a -> M<'b>) -> M<'b>	Required member. Used to de-sugar let! and do! within computation expressions.
member Return : 'a -> M<'a>	Required member. Used to de-sugar return within computation expressions.
member Delay : (unit -> M<'a>) -> M<'a>	Required member. Used to ensure side effects within a computation expression are performed when expected.
member Yield : 'a -> M<'a>	Optional member. Used to de-sugar yield within computation expressions.
member For : seq<'a> * ('a -> M<'b>) -> M<'b>	Optional member. Used to de-sugar for ... do ... within computation expressions. M<'b> can optionally be M<unit>
member While : (unit -> bool) * M<'a> -> M<'a>	Optional member. Used to de-sugar while ... do ... within computation expressions. M<'b> can optionally be M<unit>
member Using : 'a * ('a -> M<'b>) -> M<'b> when 'a :> IDisposable	Optional member. Used to de-sugar use bindings within computation expressions.
member Combine : M<'a> -> M<'a> -> M<'a>	Optional member. Used to de-sugar sequencing within computation expressions. The first M<'a> can optionally be M<unit>
member Zero : unit -> M<'a>	Optional member. Used to de-sugar empty else branches of if/then within computation expressions.
member TryWith : M<'a> -> M<'a> -> M<'a>	Optional member. Used to de-sugar empty try/with bindings within computation expressions.
member TryFinally : M<'a> -> M<'a> -> M<'a>	Optional member. Used to de-sugar try/finally bindings within computation expressions.

These sugared constructs are de-sugared as follows:

Construct	De-sugared Form
let pat = expr in cexpr	let pat = expr in cexpr
let! pat = expr in cexpr	b.Bind(expr, (fun pat -> cexpr))
return expr	b.Return(expr)
return! expr	b.ReturnFrom(expr)
yield expr	b.Yield(expr)
yield! expr	b.YieldFrom(expr)
use pat = expr in cexpr	b.Using(expr, (fun pat -> cexpr))
use! pat = expr in cexpr	b.Bind(expr, (fun x -> b.Using(x, fun pat -> cexpr))
do! expr in cexpr	b.Bind(expr, (fun () -> cexpr))
for pat in expr do cexpr	b.For(expr, (fun pat -> cexpr))
while expr do cexpr	b.While((fun () -> expr), b.Delay( fun () -> cexpr))
if expr then cexpr1 else cexpr2	if expr then cexpr1 else cexpr2
if expr then cexpr	if expr then cexpr else b.Zero()
cexpr1 cexpr2	b.Combine(cexpr1, b.Delay(fun () -> cexpr2))
try cexpr with patn -> cexprn	b.TryWith(expr, fun v -> match v with (patn:ext) -> cexprn | _ raise exn)
try cexpr finally expr	b.TryFinally(cexpr, (fun () -> expr))

What are Computation Expressions Used For?

F# encourages a programming style called language oriented programming to solve problems. In contrast to general purpose programming style, language oriented programming centers around the programmers identifying problems they want to solve, then writing domain specific mini-languages to tackle the problem, and finally solve problem in the new mini-language.

Computation expressions are one of several tools F# programmers have at their disposal for designing mini-languages.

Its surprising how often computation expressions and monad-like constructs occur in practice. For example, the Haskell User Group has a collection of common and uncommon monads, including those which compute distributions of integers and parse text. Another significant example, an F# implementation of software transactional memory, is introduced on hubFS.

Additional Resources

• Haskell.org: All About Monads - Another collection of monads in Haskell.