Some Details on F# Computation Expressions

One of the things we added to F# in version 1.9.2 is a syntax for computation expressions. These are a generalization of the  sequence expressions added in F# 1.9.1.  In this post I'll drill down on some more technical details on sequence expressions and computation expressions, as a preliminary for later posts showing their use. If you're new to F# don't worry too much about the details of this post: it's mostly for people interested in "looking under the hood".

As a reminder, here is a very simple sequence expression:

seq { for i in 0 .. 3 -> (i,i*i) }

This evaluates to an on-demand sequence

seq [ (0,0); (1,1); (2,4); (3,9) ]

This syntax can also be used to specify lists and arrays:

    [ for i in 0 .. 3 -> (i,i*i) ]

    [| for i in 0 .. 3 -> (i,i*i) |]

The outer expression forms are:

expr =

| ...

| seq { cexpr } Generated sequence (IEnumerable<_>)

| [ cexpr ] Generated list

| [| cexpr |] Generated array

The constructs that can be used inside sequence expressions are not limited to "for" - you can bind variables, use conditionals and use iterative constructs such as "while" loops and imperative constructs such as "do" statements that have a side effect. Using side effects, "use" bindings and "while" loops inside seqeuence expressions will be unfamiliar to some. However, it is very useful. For example, here is a sequence expression that opens a file for reading and then iterates the file line by line, yielding one line on each iteration:

 

let reader =

seq { use reader = StreamReader(File.OpenRead("test.txt"))

while not reader.EndOfStream do

yield reader.ReadLine() }

I now find myself using sequence expressions very frequently in my F# coding. They are also used as the core syntactic form for queries that are executed on a database via LINQ.

 

When we look at the constructs that can be used in sequence expressions we see that each syntactic element corresponds to an operator in the F# Sequence library, Some of the corresponding constructs are listed below.

    for pat in expr do cexpr looping (Seq.map_concat)

 

    use pat = expr in cexpr Local resource binding (Seq.using)

 

    while expr do cexpr Iterative generation (Seq.generated)

 

    cexpr1 Append (Seq.append)

    cexpr2

 

    yield expr Yield one (Seq.singleton)

 

Now,F# computation expressions generalize sqeuence expressions in interesting ways. A computation expression has the form

    expr =

        | ...

        | ident { cexpr } Computation expression

Here "ident" should be an object that supports particular methods needed to interpret the syntax inside "cexpr". The identifier out the front of a computation expression is called a "builder" object.

Computation expressions give us a way of representing important kinds of programs in a succinct and natural way, reusing the basic elements of the F# syntax to write programs which have quite a different behaviour in practice. For example, let's consider functions of the following type, which we could call "option generating functions": These can also be thought of as functions where the notion of failure (or exceptions) has been made explicit:

type Attempt<'a> = (unit -> 'a option)

As with sequence expressions, elements of the syntax are translated away. For example, the sequence expression

 

attempt { let! n1 = f inp1

let! n2 = failIfBig inp2

let sum = n1 + n2

return sum };;

becomes:

 

attempt.Delay(fun () ->

attempt.Bind(f inp1,(fun n1 ->

           attempt.Bind(f inp2,(fun n2 ->

              attempt.Let(n1 + n2,(fun sum ->

                  attempt.Return(sum))))))))

 

In this case, we're assuming that "attempt" has type

type AttemptBuilder =

member Bind : Attempt<'a> * ('a -> Attempt<'b>) -> Attempt<'b>

member Delay : (unit -> Attempt<'a>) -> Attempt<'a>

member Let : a * ('a -> Attempt<'a>) -> Attempt<'a>

member Return : 'a -> Attempt<'a>

We can define the builder object "attempt" as follows:

let succeed x = (fun () -> Some(x))

let fail = (fun () -> None)

let runAttempt (a:Attempt<'a>) = a()

let bind p rest = match runAttempt p with None -> fail | Some r -> (rest r)

let delay f = (fun () -> runAttempt (f ()))

type AttemptBuilder() =

/// Wraps an ordinary value into an Attempt value.

/// Used to de-sugar uses of 'return' inside computation expressions.

member b.Return(x) = succeed x

/// Composes two attempt values. If the first returns Some(x) then the result

/// is the result of running rest(x).

/// Used to de-sugar uses of 'let!' inside computation expressions.

member b.Bind(p,rest) = bind p rest

/// Sequences two attempts. If the first returns Some(x) then the result

/// is the result of running rest(x).

/// Used to de-sugar computation expressions.

member b.Delay(f) = delay f

/// Used to de-sugar uses of 'let' inside computation expressions.

member b.Let(p,rest) : Attempt<'a> = rest p

let attempt = new AttemptBuilder()

Now that's done we can can use the "attempt" builder in conjunction with some computation expressions, for example:

let failIfBig n = attempt { if n > 1000 then return! fail else return n };;

val failIfBig: int -> Attempt<int>

> runAttempt (failIfBig 999);;

val it : int option = Some(999)

> runAttempt (failIfBig 1001);;

val it : int option = None

Now, those familiar with LINQ and Haskell may see where this is heading: the de-dugared form of computation expressions is similar to the desugared form of the query notation of LINQ, though there are some technical differences. Likewise the kinds of operations used under the hood are much like the operations used in both LINQ and Haskell monads. Indeed, computation expressions can be seen as a general monadic syntax for F#.

One of the important things about computation expressions is that they lead you toward a compositional approach to programming. For example, you can build new "attempt" computations out of old ones.

let sumIfBothSmall (inp1,inp2) =

attempt { let! n1 = failIfBig inp1

let! n2 = failIfBig inp2

let sum = n1 + n2

return sum };;

The key to understanding any kind of computation expression is to understand the meaning ot the "let!" operator. In the sample above the first line takes an Attempt<int> computation and runs it, binding the result to "n1" if it succeeds. Likewise the second line attempts to run a similar Attempt<_> and bind the result to n2.

In F#, computation expressions can use quite a number of constructs, just as for sequence expressions. We'll see many uses of these in later blog posts. Hwere are some of the constructs that can be used (we've omitted some such as try/finally):

    let! pat = expr in cexpr b.Bind(expr,(fun pat -> «cexpr»))

   

    let pat = expr in cexpr b.Let(expr,(fun pat -> «cexpr»))

   

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

   

    do expr in cexpr b.Let(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 v.Combine(«cexpr1», b.Delay(fun () -> «cexpr2»))

   

    return expr b.Return(expr)

    return! expr expr

Here are some of the expected signatures for members of the builder object for a computation type M<_>. Not all members are required - you only need those members needed by the actual syntactic elements used in the computation expression body.

member Bind : M<'a> * ('a -> M<'b>) -> M<'b>

member Return : 'a -> M<'a>

member Let : 'a * ('a -> M<'b>) -> M<'b> .

member Delay : (unit -> M<'a>) -> M<'a>

member For : seq<'a> * ('a -> M<'b>) -> M<'b>

member While : (unit -> bool) * M<'a> -> M<'a>

member Using : 'a * ('a -> M<'a>) -> M<'a> when 'a :> IDisposable

member Combine : M<'a> * M<'a> -> M<'a>

member Zero : unit -> M<'a>

Sequence and computation expressions are related to constructs found in other programming languages, e.g.:

  • they play a similar role to the "list comprehensions" and "do" notations in Haskell
  • they are used to simulate the "query" notation in C# 3.0 annd VB 9 (though without all the features of LINQ)
  • as we have seen above, sequence expressions can be used as "imperative sequence generators", giving them much of the expressive power of "iterators" from C# 2.0, Icon and Python

Over time we expect to increase the range of constructs that can be used within computation expressions even further.

In future blog posts I'll show more examples of sequence expressions and computation expressions in action.