# F Sharp Programming/Computation Expressions

 F# : Computation Expressions

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

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).

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.

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 ("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 () ->
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.

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.
| (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`.

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

bind( (fun () -> printMsg "Creating webclient..."; new System.Net.WebClient()), fun webclient ->
bind( (fun () -> printMsg "Extracting urls..."; Regex.Matches(html, @"http://\S+") ), fun matches ->
printMsg ("Found " + matches.Count.ToString() + " links")
)
)
)

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

>
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 = 11, Url = http://www.peta.org, Extracting urls...
ThreadID = 5, Url = http://microsoft.com/, Extracting urls...
ThreadID = 13, Url = http://www.wordpress.com/, Extracting urls...
```

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` rather than `int option`. 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()`
`cexpr1cexpr2` `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.