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
Anonymous
October 02, 2007
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". ]Anonymous
October 10, 2007
F# 1.9.2.9 includes a pre-release of new F# functionality called asynchronous workflows . In this blogAnonymous
January 15, 2008
I have written a library for using software transactional memory in F#. The library exposes memory transactions...Anonymous
January 17, 2008
Greg Neverov (of active patterns fame) has placed an implementation of Software Transactional MemoryAnonymous
November 04, 2008
I have have been playing around with F# and I decided to create a state monad. This worked out reallyAnonymous
December 26, 2008
Pre nešto više od pet godina sa nekoliko drugara otvorio sam školu računara i oo tada se vikendom u njojAnonymous
February 23, 2009
These pages document F# as a research project. You can find out all about the latest happenings with