ITT8060 Advanced Programming · Autumn 2026
Tallinn University of Technology
Full prose version with runnable examples: notes.html
ITT8060Lecture 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
ITT8060Option.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.
ITT8060let 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))
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.
ITT8060A 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
ITT8060b { 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 |
|---|---|
|
|
|
|
|
|
|
|
plain |
unchanged, their bodies translated |
the whole body |
|
A let! on the last line is an error: something must follow it.
ITT8060b {
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.
ITT8060let 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.
ITT8060use!, 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
ITT8060type OptionBuilder () =
member _.Bind (o, f) = Option.bind f o
member _.Return x = Some x
let option = OptionBuilder ()
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.
ITT8060type OptionBuilder () =
member _.Bind (o, f) = Option.bind f o
member _.Return x = Some x
let option = OptionBuilder ()
let squareRoot x =
if x >= 0.0 then Some (sqrt x) else None
let rootOfFive =
option {
let! five = Some 5.0
let! root = squareRoot five
return root
}
rootOfFive is Some 2.236067977.
Starting from Some -5.0: squareRoot gives None, and the chain
ends there. rootOfMinusFive is None.
Starting from None: the first let! ends the chain.
rootAfterNone is None.
ITT8060type Request =
{ userId: UserId; name: string; email: string }
let nameNotBlank (r: Request) =
if r.name = "" then Error "Name must not be blank"
else Ok r
type ResultBuilder () =
member _.Bind (r, f) = Result.bind f r
member _.Return x = Ok x
let result = ResultBuilder ()
Lecture 7's chain as let! lines:
let validateRequest' (r: Request) =
result {
let! r1 = nameNotBlank r
let! r2 = name50 r1
let! r3 = emailNotBlank r2
let! r4 = emailHasAt r3
return r4
}
The other three checks have the same shape as nameNotBlank.
validateRequest' request = validateRequest request is true; the
notes compare a failing request as well.
ITT8060type '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 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.
ITT8060A body that ends in a unit expression (log, then do something):
let logging = LoggingBuilder ()
let log msg = Logging ((), [msg])
let write (s: string) =
logging {
do! log ("writing: " + s)
printfn "%s" s
}
Which method will the compiler ask for?
error FS0708: This control construct may only be used if the
computation expression builder defines a 'Zero' method
(captured on SDK 10.0.302)
A body without return ends in b.Zero (). Add
member _.Zero () = Logging ((), []); write "hello" is then
Logging ((), ["writing: hello"]).
ITT8060let parse (s: string) =
Logging (int s, [$"parsed {s}"])
let loggingTest =
logging {
do! log "starting"
let! n = parse "42"
do! log "doubling"
return n * 2
}
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
ITT8060type '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))
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.
ITT8060type 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
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.
ITT8060let 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
}
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.
ITT8060Delay would changedeep, 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
ITT8060seq { for i in 0 .. 3 -> (i, i * i) }
|> Seq.toList gives [(0, 0); (1, 1); (2, 4); (3, 9)].
Inside seq { }: for … do, yield (for … -> v is for … do yield v),
yield!, if … then yield (an if with no else). Their translation:
Written in the body |
Translated to |
|---|---|
|
|
|
|
|
|
one part followed by another |
|
|
|
ITT8060SeqBuilderThe 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.
ITT8060type MySeqBuilder () =
member _.For (xs: 'a seq, f: 'a -> 'b seq) =
Seq.collect f xs
member _.Yield x = Seq.singleton x
let myseq = MySeqBuilder ()
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.
ITT8060let mutable evaluated = 0
let squares =
seq {
for i in 1 .. 3 do
evaluated <- evaluated + 1
yield i * i
}
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.
ITT8060let rec from n =
seq {
yield n
yield! from (n + 1)
}
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.
ITT8060let!
ITT8060type 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 ()
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.
ITT8060let checkName (r: Request) =
if r.name = "" then
Error ["Name must not be blank"]
else Ok r.name
let checkEmail (r: Request) =
if r.email.Contains '@' then Ok r.email
else Error [$"Email {r.email} is not valid"]
and!let validate (r: Request) =
validation {
let! name = checkName r
and! email = checkEmail r
return (name, email)
}
let badRequest =
{ request with name = ""; email = "nobody" }
What is validate badRequest?
Error ["Name must not be blank"; "Email nobody is not valid"]
For Lecture 7's request itself: Ok ("Kati Karu", " Kati.Karu@TalTech.ee ").
ITT8060let 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 buildersIn 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.
ITT8060match!, use!, trymatch! 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.
ITT8060type 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 ()
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.
ITT8060The 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.
ITT8060let! is Bind and return is Return.
ITT8060Homework 8 is out this week.
Reading:
Next week: events and asynchronous computations.
ITT8060
ITT8060let fortyTwoFn =
il {
ldc_i4 6
ldc_i4_0
ldc_i4 7
add
mul
ret
}
(From Keith Battocchi)
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.
ITT8060type '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 [<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.
ITT8060query { 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