Computation expressions

ITT8060 Advanced Programming · Autumn 2026

Tallinn University of Technology

Full prose version with runnable examples: notes.html

ITT8060

Introduction

Lecture 7 chained validation checks with Result.bind. Lecture 8 passed continuations by hand. Lecture 10 wrote generators with gen { … }.

Each time: a type M<'T>, a bind that chains a step onto a value of that type, a return that wraps a plain value. A chain written by hand became nested callbacks: fun x -> … fun y -> ….

A computation expression is F#'s notation for such a chain. let! is a bind, return is a return; the compiler rewrites the body into calls of the methods of a "builder" object.

The builder decides what the chain means: no result, an error, a continuation, a sequence.

ITT8060

1 · One shape, four times

ITT8060

Four signatures

Option.bind : ('a -> 'b option)      -> 'a option      -> 'b option
Result.bind : ('a -> Result<'b, 'e>) -> Result<'a, 'e> -> Result<'b, 'e>
Gen.bind    : ('a -> Gen<'b>)        -> Gen<'a>        -> Gen<'b>

a continuation step (Lecture 8), with
c : ('a -> 'r) -> 'r  and  f : 'a -> ('b -> 'r) -> 'r
fun k -> c (fun x -> f x k)          : ('b -> 'r) -> 'r

What do these four have in common?

A type M<'T>: 'T option, Result<'T, 'e>, Gen<'T>, ('T -> 'r) -> 'r.

A bind that takes an M<'a> and a step 'a -> M<'b> and gives an M<'b>.

A return that wraps a plain value: Some, Ok, Gen.constant, fun k -> k x.

The library functions take the step first (they fit after |>); the continuation step and a builder's Bind take the value first.

ITT8060
let tryParse (s: string) =
  match System.Int32.TryParse s with
  | true, n -> Some n
  | _ -> None

let tryDivide (n: int) =
  if n = 0 then None else Some (100 / n)

let tryRoot (n: int) =
  if n < 0 then None else Some (sqrt (float n))

The staircase

Three steps on a string, chained by hand:

let staircase (s: string) =
  tryParse s
  |> Option.bind (fun n ->
    tryDivide n
    |> Option.bind (fun q ->
      tryRoot q
      |> Option.bind (fun r ->
        Some (n, q, r))))

staircase "4" is Some (4, 25, 5.0); staircase "four" is None.

Lecture 8's sizeK l <| fun sl -> sizeK r <| fun sr -> … is the same staircase with continuations.

ITT8060

The name

A type constructor with these two operations is called a monad.

The name is all the theory this lecture needs.

Why it matters: every later concept is this shape with a different M<'T>, and the notation removes the staircase from all of them at once.

ITT8060

2 · The notation and its translation

ITT8060

The form and the rules

b { body }: b is an ordinary value, the "builder". The compiler rewrites ("desugars") the body into calls of its methods.

Written in the body

Translated to

let! x = e followed by rest

b.Bind (e, fun x -> rest)

return v

b.Return v

return! e

b.ReturnFrom e

do! e followed by rest

let! () = e, that is b.Bind (e, fun () -> rest)

plain let, do, match

unchanged, their bodies translated

the whole body

b.Delay (fun () -> …) when b defines Delay

A let! on the last line is an error: something must follow it.

ITT8060

Two steps, written out

b {
  let! x = e1
  let! y = e2
  return x + y
}
b.Bind (e1, fun x ->
  b.Bind (e2, fun y ->
    b.Return (x + y)))

The translated form is the staircase of concept 1: the notation hides the nesting, the compiler puts it back.

ITT8060

Lecture 10's generator, by hand

let ordPairGen =
  gen {
    let! j = Gen.choose (1, 100)
    let! i = Gen.choose (0, j - 1)
    return (i, j)
  }
let ordPairGen'' =
  gen.Delay (fun () ->
    gen.Bind (Gen.choose (1, 100), fun j ->
      gen.BindReturn (
        Gen.choose (0, j - 1), fun i -> (i, j))))

On the right, what the compiler makes of the left: gen is a builder value; Delay wraps the body in a function, let! is Bind, and the final let! … return pair is one BindReturn call.

ITT8060

Where the full rules are

use!, while, try and custom operations have rules of their own: the computation-expression section of the F# language specification (fsharp.github.io/fslang-spec).

Why it matters: let! is not magic; it is a method call you can write out, and the builder is where its meaning lives.

ITT8060

3 · Writing a builder

ITT8060
type OptionBuilder () =
  member _.Bind (o, f) = Option.bind f o
  member _.Return x = Some x

let option = OptionBuilder ()

An option builder

The methods take the value first, so Bind flips the arguments of Option.bind.

What does this evaluate to?

option {
  let! x = (None: int option)
  return x + 1
}

None: Bind (None, f) is Option.bind f None, which never calls f.

ITT8060
type 'a Logging = Logging of 'a * string list

type LoggingBuilder () =
  member _.Bind (Logging (x, msgs1), f) =
    let (Logging (y, msgs2)) = f x
    Logging (y, msgs1 @ msgs2)
  member _.Return x = Logging (x, [])

A logging builder

A value paired with the messages produced on the way to it.

Bind runs the step and appends its messages after the ones already collected.

Return wraps a value with no messages.

ITT8060
let parse (s: string) =
  Logging (int s, [$"parsed {s}"])

let loggingTest =
  logging {
    do! log "starting"
    let! n = parse "42"
    do! log "doubling"
    return n * 2
  }

The worked program

do! for the logging steps, let! for the value.

loggingTest is Logging (84, ["starting"; "parsed 42"; "doubling"]): the messages are in the order the steps ran.

Why it matters: a builder is the type's bind and return given the names the compiler looks for, and the compiler tells you which further name it needs.

ITT8060

4 · Continuations as a computation expression

ITT8060
type 'a BinTree =
  | Empty
  | Node of 'a BinTree * 'a * 'a BinTree

let leaf x = Node (Empty, x, Empty)

let t = Node (Node (leaf 2, 7, Empty),
              9,
              Node (leaf 13, 21, leaf 25))

Lecture 8's tree

let rec size t =
  match t with
  | Empty -> 0
  | Node (l, _, r) -> size l + 1 + size r

size t is 6. Lecture 8 made size tail recursive by passing a continuation: sizeK t k.

ITT8060
type CPSBuilder () =
  member _.Bind (c, f) =
    fun k -> c (fun x -> f x k)
  member _.Return x = fun k -> k x

let cps = CPSBuilder ()

let runCPS c = c id

The continuation builder

M<'T> is here the function type ('T -> 'r) -> 'r: a computation that takes the continuation k and calls it with the result.

Bind runs the first computation with a continuation that runs the step; Return calls k on the value.

runCPS supplies id, as sizeK t id did.

ITT8060
let rec sizeC t =
  cps {
    match t with
    | Empty -> return 0
    | Node (l, _, r) ->
        let! sl = sizeC l
        let! sr = sizeC r
        return sl + 1 + sr
  }

Size with let!

The staircase of sizeK replaced by two let! lines; a match inside the expression, a return in each branch.

What is runCPS (sizeC t)?

6, equal to size t.

ITT8060

What Delay would change

deep, Lecture 8's million-node left spine: sizeK deep id gave 1000000.

> let c = sizeC deep;;
Stack overflow.
Repeated 13709 times:
--------------------------------
   at FSI_0001.sizeC[...](BinTree`1<Int32>)

(captured on SDK 10.0.302)

The overflow happens while the computation is constructed: cps.Bind (sizeC l, …) evaluates sizeC l when the expression is built, before runCPS is reached.

A builder with Delay receives the body as a function and can postpone it until the continuation arrives: exercise 2.

Why it matters: the builder decides when the work happens, not only what it means.

ITT8060

5 · Sequence expressions are computation expressions

ITT8060

The notional SeqBuilder

The language specification describes seq as if it had this builder (its For line corrected):

type SeqBuilder () =
  member x.Yield v = Seq.singleton v
  member x.YieldFrom (s: seq<_>) = s
  member x.Return (() : unit) = Seq.empty
  member x.Combine (xs1, xs2) = Seq.append xs1 xs2
  member x.For (xs, f) = Seq.collect f xs
  member x.While (guard, body) = …
  member x.TryFinally (xs, compensation) = …
  member x.Using (resource, xs) = …

Combine is Seq.append, For is Seq.collect (Lecture 4's List.collect on sequences), Yield is Seq.singleton.

ITT8060
type MySeqBuilder () =
  member _.For (xs: 'a seq, f: 'a -> 'b seq) =
    Seq.collect f xs
  member _.Yield x = Seq.singleton x

let myseq = MySeqBuilder ()

A two-method builder

The opener with myseq in place of seq gives the same list: openerSame is true.

Two yields one after the other, myseq { yield 1; yield 2 }: which method will the compiler ask for?

error FS0708: This control construct may
only be used if the computation expression
builder defines a 'Combine' method

With Combine added, it asks for Delay next. Completing the builder is exercise 3.

ITT8060
let mutable evaluated = 0

let squares =
  seq {
    for i in 1 .. 3 do
      evaluated <- evaluated + 1
      yield i * i
  }

Has the body run?

squares is defined. What is evaluated now?

0: nothing has run.

Seq.toList squares is [1; 4; 9], and evaluated is then 3: once per element, when the list asked for them.

The counter counts every enumeration.

ITT8060
let rec from n =
  seq {
    yield n
    yield! from (n + 1)
  }

An infinite sequence

from 10 |> Seq.take 5 |> Seq.toList is [10; 11; 12; 13; 14].

Seq.take enumerates as much as is asked for; the recursion never runs ahead of it.

Why it matters: the same translation, with Delay, is what makes sequences lazy; seq { } is not a special loop, it is a builder.

ITT8060

6 · Beyond let!

ITT8060
type ValidationBuilder () =
  member _.Bind (r, f) = Result.bind f r
  member _.Return x = Ok x
  member _.MergeSources (a, b) =
    match a, b with
    | Ok x, Ok y -> Ok (x, y)
    | Error e1, Error e2 -> Error (e1 @ e2)
    | Error e, _ | _, Error e -> Error e

let validation = ValidationBuilder ()

All errors at once

Lecture 7 asked how to report all errors, not just the first.

and! binds two computations that do not depend on each other; MergeSources says how to combine them. With errors as lists, two errors are appended.

ITT8060
let later =
  async { printfn "running (async)"; return 1 }
printfn "defined (async)"
let ran = Async.RunSynchronously later
printfn "ran (async): %d" ran

let now =
  task { printfn "running (task)"; return 1 }
printfn "defined (task)"
printfn "ran (task): %d" now.Result

Delay in the built-in builders

In what order do the six lines print?

defined (async)
running (async)
ran (async): 1
running (task)
defined (task)
ran (task): 1

async has a Delay: the body runs when the computation is started. task starts its body at once. Both: Lecture 12.

ITT8060

match!, use!, try

match! e with … is let! followed by a match on the result: Bind.

use! x = e is a let! whose value is disposed at the end: Using.

try … with and try … finally inside a computation expression: TryWith and TryFinally, with the body delayed.

ITT8060
type SelectSeqBuilder () =
  member _.For (xs: 'a seq, f: 'a -> 'b seq) =
    Seq.collect f xs
  member _.Yield x = Seq.singleton x
  [<CustomOperation("select")>]
  member _.Select (xs: 'a seq, f: 'a -> 'b) =
    Seq.map f xs

let selseq = SelectSeqBuilder ()

Custom operations

A builder may define its own keywords; the compiler passes the sequence built so far.

selseq { for i in 1 .. 10 do select (fun i -> i + 100) } gives [101; 102; …; 110].

query { } is a library builder made of custom operations. Projection and variable space: worked example C in the notes.

ITT8060

The method table

The methods this lecture's builders define or its translations call:

Bind          let!, do!
Return        return
ReturnFrom    return!
Zero          an if without else; a body without a result
Combine       one part followed by another
Delay         the body as a function
For           for … do
Yield         yield
YieldFrom     yield!
MergeSources  and!

The full table, with signatures: the notes and the F# language reference.

Why it matters: the keywords you will meet in async, task, seq and query all map to this one table.

ITT8060

Summary

  1. A computation expression is translated into calls of a builder's methods.
  2. let! is Bind and return is Return.
  3. The builder decides what the chain means: no result, an error, a continuation, a sequence.
  4. The compiler names the method a construct needs.
  5. Sequence expressions are the same mechanism and are lazy.
ITT8060

Homework, reading and next week

Homework 8 is out this week.

Reading:

Next week: events and asynchronous computations.

ITT8060

Appendix: computation expressions as DSLs

ITT8060
let fortyTwoFn =
  il {
    ldc_i4 6
    ldc_i4_0
    ldc_i4 7
    add
    mul
    ret
  }

(From Keith Battocchi)

An IL DSL

A computation expression that reads like .NET intermediate-language assembly. Each line is a custom operation of the builder il.

fortyTwoFn () is 42: the body was compiled to a dynamic method and wrapped as an F# function.

The stack is typed: an add on a stack with one integer does not compile.

ITT8060

An IL DSL: the builder

type 'a Stack = Stack of (ILGenerator -> unit)
type 'a Completed = Completed of (ILGenerator -> unit)

type ILBuilder () =
  member _.Yield (() : unit) : unit Stack = Stack (fun _ -> ())
  [<CustomOperation("ldc_i4")>]
  member _.Ldc_i4 (Stack f : 'r Stack, n: int) : (int * 'r) Stack =
    Stack (fun ilg -> f ilg; ilg.Emit (OpCodes.Ldc_I4, n))
  // stack transition: int :: int :: rest -> int :: rest
  [<CustomOperation("add")>]
  member _.Add (Stack f : (int * (int * 'r)) Stack) : (int * 'r) Stack =
    Stack (fun ilg -> f ilg; ilg.Emit OpCodes.Add)

A computation is a function that emits instructions; its type parameter is the shape of the evaluation stack. A body that starts with a custom operation starts from Yield (), the empty stack. ldc_i4_0 and mul have the same shape (notes).

ITT8060

An IL DSL: running it

  [<CustomOperation("ret")>]
  member _.Ret (Stack f : ('a * unit) Stack) : 'a Completed =
    Completed (fun ilg -> f ilg; ilg.Emit OpCodes.Ret)
  member _.Run (Completed f : 'a Completed) : unit -> 'a =
    let dm = DynamicMethod ("", typeof<'a>, [||])
    dm.GetILGenerator () |> f
    let d = dm.CreateDelegate typeof<System.Func<'a>> :?> System.Func<'a>
    fun () -> d.Invoke ()

ret accepts only a stack with exactly one value. Run is called by the compiler on the whole translated body: it compiles the emitted instructions into a dynamic method and wraps it as an F# function.

ITT8060

DSLs you will meet

query { for student in db.Student do where (student.ID = 1); select student }: where, select, sortBy, join are custom operations, translated for a database by LINQ.

FsToolkit.ErrorHandling: result { }, option { }, validation { } with and!, asyncResult { }: this lecture's builders as a library.

Saturn (web): application { use_router webApp; url "http://0.0.0.0:8085/" }, router { get "/" (text "hello") }.

Farmer (Azure deployments): arm { location Location.NorthEurope; add_resource webApp }.

Expecto (tests): test "name" { Expect.equal (f 2) 4 "f 2" }.

ITT8060