Hang onto your hats! This final part is where the ride gets wild.
Topics covered in the series
Alas, despite having trailed generative programming, I find I don't have any notes from the seminar series covering that topic explicitly (it was not one I was presenting). If I find something, I'll add it in as an extra post.
Continuations
This style of programming originally arose in handling data streams in a fashion using lazy evaluation, and uses closures to represent each step of the program. I/O is made available as a pair of lazy lists, a request list and a response list, and the program is a function which takes a response list to a request list:
For example:
The hidden causality here is that putting the Getq at the head of the request queue causes the Getp c to exist at the head of the response queue (perhaps by reading the keyboard).
In general, the continuation style uses chained closures to construct a complex compound operation from a collection of small basic operations. We introduce the types
Our building blocks will mostly be producers and consumers, and others that are neither:
- Where possible, the continuations are built during the construction phase.
- Each step is provided with the rest of the execution as a continuation building block(s).
- A producer is provided with a consumer which constructs a continuation from the produced data at execution time.
Example -- Console I/O
First we define some primitives:
where we introduce the standard convenience function
to avoid extra parentheses.
We can then define a compound operation, for example:
Example -- The Lexer revisited
The type constructor lexerResult describes the values that the lexer is going to produce. Note that the lexer is going to be a producer continuation.
The type constructor lexerSystem provides us with an I/O abstraction.
Given that the lexer is going to be a producer, we will need a consumer to complete its construction.
To allow for lexical analysis failures, we also have a building block for that.
Note that although it looks like a consumer, in practice we always know the message to use at construction time.
Function lexGetChar builds our most primitive producer continuation.
The consumer (g) constructs a continuation from the character option read from the input.
Similarly, lexPutLexeme builds our most primitive consumer, which writes a lexeme to the output.
In order to make decisions based on our inputs we need to express a conditional branch.
and similarly we want to be able to express repetition.
Thus equipped we can start to write the lexer.
Exercise: Complete the lexer.
Summary
We have used closures as continuations to construct functions which compose using function application to create more complex functions. The end result is a complex closure, which is itself just a function which, when applied to the unit value “()”, is the program we want, with any side effects of the constituent closures. The main problem that we, as programmers, are likely to feel with this approach is that the process of construction is counter-intuitive, due to the back to front construction style, given that each step of the closure takes an argument representing the rest of the program, thus
As Eric Lippert put it (in the context of writing asynchronous code in this style in C#):
Remember what I was saying about the pros and cons of CPS?
- PRO: Arbitrarily complex and interesting control flows can be built out of simple parts – check.
- CON: The reification of control flow via continuations is hard to read and hard to reason about – check.
- CON: The code that represents the mechanisms of control flow completely overwhelms the meaning of the code – check.
- CON: The transformation of ordinary code control flow into CPS is the kind of thing that compilers are good at, and almost no one else is – check.
It is important to note, however, that this is not the only use of continuations. We regularly use continuations as event handlers, and they can also be used to search a set of alternatives, by effectively constructing a set of programs to be tried one after another until one does not fail provides a result, or all of them fail.
Used appropriately, this is a powerful technique.
Monads
Despite the scary name, monads are constructs that arise quite naturally in functional programming; typically as a result of trying to express the OO notion of a separation of concerns, here between individual functions doing localized transformations, and the larger control flow of the program.
A monad is a type the values of which encapsulate a piece of a program in much the same way as a continuation does. There are, however, differences in the way the values work and the way they compose, which fits into the functional programming style more naturally. We will, for the moment, write a monad as a type M t where t is a type which values of the monad produce when “run”, except when the run fails (in which case no value is produced). As with continuation programming, a program is constructed by the composition of monads and functions which produce monads. The basic constructions used are:
Understanding “bind”
The “bind” combinator is often written as the infix operator >>=. This begins to make sense if we use a program layout thus:
We read this as binding value1 to the output(s) of m, using this to produce the monad E1[value1], and then binding value2 to the outputs of that, constructing the monad E2[value2], and so on. A language with monads built in can even provide syntactic sugar for this, such as:
Unfortunately the F# type system is not expressive enough for us to write a general >>= along the lines of
so for the moment we will write >>= but mean the comparable operator specialised to the monad of interest.
Derived combinator cases
A monad type M unit is special (think of it as pure side-effect). With such a type there little point in binding the result values – we know that we will only get ():
A monad which produces a function or functions is also interesting:
Given a function we can construct a function over monads:
Exercise: Prove that Lift f = Apply (Return f)
Given two functions that return monads, we can combine them:
A monad which produces a monad or monads can be flattened (lose a level of monad):
The name join makes sense when the monad involved produces multiple values – the result monad produces all of the values produced by all of the monads produced by mm.
Given a list of monads we can construct a monad of lists:
An example of a monad
We introduced the notion of a monad with the description that it handles things like separation of concerns. One very familiar language construct that we have been using from the very first session can be written in monadic form; a 'a list is just another monad 'a:
Another pure monad construction is Option.
which allows us to chain together a series of operations that might fail, and bypass the calls made after any failure.
Exercise: Construct a pure monad based on trees.
An I/O Monad
These pure monads do not really have a notion of execution. We can use closures again to construct a monad which itself carries out some side-effecting computation and returns a value. As we did for continuations, we will wrap the closures up using a data type (as before this is to highlight the construction and can be elided):
The principal functions for this are:
The construction for bind (>>=) deliberately constructs a wrapped closure. At first sight it looks the same as f(runIO m), which has the same type, but we need to make sure that the sub-term runIO m is evaluated when the result of the bind is run rather than when it is constructed. As all of the other combinators are defined in terms of these three, we won’t need to worry about evaluation order for them. The issue will arise, however, for most special primitives, as we will want side effects to occur at the right time.
To read and write characters we can use:
We can, of course, string a lot of these together using the derived combinators >>= and >>. The result does nothing until run. For example:
We can also define read and write for strings:
Exercise: write PutS.
Computation expressions
F# does provide a form of syntactic sugar that allows us to write monadic code, and continuation passing, in a form that is actually comprehensible to the programmer.
Consider the Option monad. If we introduce a singleton type
where Delay has the effect (as in the >>= operation for our I/O monad) of delaying the execution of the operation until the appropriate point in the sequence, we can write the monadic code using chains of >>=? combinators as a sequence of assignment-like let! expressions.
where f, g, h are functions taking plain values to option values.
The actual compiled form of the let! binding
is in the continuation form
This not only allows us to write monadic code in something close to the syntactic sugar form as alluded to above, but also to express naturally continuation based code (e.g. asynchronous operations) in a sequential style (indeed the async computation builder is a standard part of the library for exactly this purpose).
We can also express the equivalence of the two notations by building a monadic form from a computation expression, such as the async computation builder:
Concluding Remarks
Now, like Wittgenstein's Ladder once you have grokked the content of this course, you should be able to discard the often inefficient implementations used for simplicity (such as avoiding cluttering the example code with reversing cons'd lists), and be confident in using a functional style where complex programs can be built from simple pure elements composed together.
As to the F# language itself, we have barely skimmed the surface -- material like active patterns, quotations (the missing last lecture), the standard collections modules, reactive events and more still remain untouched. But in my experience, once the initial hurdle of the programming style has been crossed, picking those up when you realise you need them is the easy part; whereas before the "Aha!" moment the motivation and need for such features will remain mostly obscure, hidden behind the dilemma of "how do you program when your variables don't?" .
Exercise: Test your understanding by reworking the course material for another language of your choice. Note that for some functional languages, parts will not be applicable as they stand (e.g. neither assignment nor the shared-state queue will be expressible in Erlang); and that for many languages pattern based dispatch and infix notation will not be available.
Posts
