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.


 


 

Comments (7)

  1. rog says:

    this is interesting, and i think understand a reasonable portion of what’s going on in the “de-sugarisation” process. i’m confused, however, by the difference between let and bind (let vs. let! ?) and between return and return!. return! and let! seem like keywords to me, but don’t seem to be mentioned in the F# manual page.

    any pointers to a reference or a blog entry talking about these things?

    the point at which i stumble in the example is at:

       let! n2 = failIfBig inp2

       let sum = n1 + n2

    that is, i can’t work out how the addition

    can be valid if n2 is the

    result of calling failIfBig, hence of type

    Attempt<int>, i.e. (unit -> int option)

    and there’s no addition operator specified in terms of  that type.

    [ Don says: the “let!” strips of the Attempt<_> from the Attempt<int> through the process of calling Bind in the de-sugared version. That’s what bind is for. So n1 has type “int”. ]

     

  2. F# 1.9.2.9 includes a pre-release of new F# functionality called asynchronous workflows . In this blog

  3. I have written a library for using software transactional memory in F#. The library exposes memory transactions…

  4. Greg Neverov (of active patterns fame) has placed an implementation of Software Transactional Memory

  5. I have have been playing around with F# and I decided to create a state monad. This worked out really

  6. sUpER pOke says:

    Pre nešto više od pet godina sa nekoliko drugara otvorio sam školu računara i oo tada se vikendom u njoj

  7. These pages document F# as a research project. You can find out all about the latest happenings with