22 Managing Effects🔗

Effects are things programs do besides return values. Examples of effects are: mutable state, reading and writing from a file or the network, non-determinism, probabilistic behavior, printing to the screen, non-termination, etc. We program with effects all the time, and most programming languages let us freely mix programs that have effects with programs that are effect free (also known as pure). The consequence of freely mixing effectful with pure programs that a programmer can never be sure if a function they call is performing some effect, which significantly harms modularity of reasoning (for example, it may not be safe to reorder two seemingly unrelated function calls if they both perform affects that make them depend on each other).

Consequently, modern programming language design has increasingly been exploring ways of cleanly separating effectful code from pure code. Here we will briefly explore the two most popular approaches to this: effect handlers and monads.

At the highest-level, effect handlers deal with effects by introducing a new control scheme that "jumps to the handler" when an effect is encountered. Monads deal with effects by "sequencing computations." We will briefly see each of these ideas in turn.

22.1 Monads🔗

We saw last lecture that we broke down TinyPPL into two components: a pure component that didn’t have any probabililstic effects, and a effectful component that consolidated all the probabilistic effects. Monads are a programming design pattern that codifies this separation between pure and effectful programs at the type level.

22.1.1 Handling Errors: The Maybe Monad🔗

Monadic syntax separates pure and effectful (also sometimes called "computational") programs into two separate syntactic categories. The monadic fragment of the language always has the following interface:

• A function called pure (also often called return) that "injects" or "lifts" a pure value into the monad.

• A function called bind (also often written >>=) that sequences together monadic computations.

• Effectful terms that manipulate effects.

We will see some examples of implementing interpreters in monadic style. Then, we will see how the programming language Haskell uses monads to handle effects.

(define-type PureCalcLang

(addE [e1 : PureCalcLang] [e2 : PureCalcLang])

(identE [x : Symbol])

(numE [n : Number]))

(define-type MaybeCalcLang

(pureE [e : PureCalcLang])

(bindE [x : Symbol] [e1 : MaybeCalcLang] [e2 : MaybeCalcLang])

(divE [e1 : PureCalcLang] [e2 : PureCalcLang]))

(define (interp-calc-pure env e)

(type-case PureCalcLang e

[(addE e1 e2) (+ (interp-calc-pure env e1)

(interp-calc-pure env e2))]

[(identE x)

(type-case (Optionof Number) (hash-ref env x)

[(some v) v]

[(none) (error 'runtime "unbound identifier")])]

[(numE n) n]))

(interp-calc-eff : ((Hashof Symbol Number) MaybeCalcLang -> (Optionof Number)))

(define (interp-calc-eff env e)

(type-case MaybeCalcLang e

[(pureE p) (some (interp-calc-pure env p))]

[(bindE x e1 e2)

(type-case (Optionof Number) (interp-calc-eff env e1)

[(some e1-v)

(interp-calc-eff (hash-set env x e1-v) e2)]

[(none) (none)])]

[(divE e1 e2)

(let [(v1 (interp-calc-pure env e1))

(v2 (interp-calc-pure env e2))]

(if (equal? v2 0)

(none)

(some (/ v1 v2))))]))

(define mt-env (hash '()))

(test (interp-calc-eff mt-env (divE (numE 10) (numE 0))) (none))

(test (interp-calc-eff mt-env (bindE 'x (divE (numE 10) (numE 0))

(pureE (addE (identE 'x) (numE 10)))))

(none))

22.1.2 The Continuation Monad🔗

Control effects are also nicely handled by monads via the continuation monad.

(define-type PureCalcLang

(addE [e1 : PureCalcLang] [e2 : PureCalcLang])

(identE [x : Symbol])

(numE [n : Number]))

(define-type MaybeCalcLang

(pureE [e : PureCalcLang])

(bindE [x : Symbol] [e1 : MaybeCalcLang] [e2 : MaybeCalcLang])

(returnE [e : PureCalcLang]))

(define (interp-calc-pure env e)

(type-case PureCalcLang e

[(addE e1 e2) (+ (interp-calc-pure env e1)

(interp-calc-pure env e2))]

[(identE x)

(type-case (Optionof Number) (hash-ref env x)

[(some v) v]

[(none) (error 'runtime "unbound identifier")])]

[(numE n) n]))

;; (interp-calc-eff : ((Hashof Symbol Number) RetLang -> Number))

(define (interp-calc-eff env k e)

(type-case MaybeCalcLang e

[(pureE p) (k (interp-calc-pure env p))]

[(returnE p)

(interp-calc-pure env p)]

[(bindE x e1 e2)

(interp-calc-eff env

(λ (e1-v)

(interp-calc-eff (hash-set env x e1-v) k e2))

e1)]))

(define mt-env (hash '()))

(test (interp-calc-eff mt-env (λ (x) x)

(bindE 'x (returnE (numE 20))

(pureE (numE 10))))

20)

22.1.3 Programming with Monads🔗

Similar to how we can have continuation-passing interpreters and also use continuations in our programs by using continuation-passing style, we can also make use of monads in our programming languages by writing our programs in monadic style. A program written in monadic style separates effectful computations from pure computations using a type system. This requires a fairly sophisticated type system, more sophisticated than Plait’s, in order to accomplish it. The Haskell programming language makes use of monads in order to handle effects; let’s briefly see how this looks.

We saw earlier that we can handle possibly failing computation by using the "maybe monad". Let’s briefly see what it looks like to program in the maybe monad in Haskell.

First, we can define a "safe division" function that, similar to our calculator example before, outputs none if a division by 0 is attempted:

The above syntax is in Haskell and is obviously quite foreign. The first line is a type signature: it says that the safe_div name is a function that takes two doubles as an argument and returns a Maybe Double. The next line defines the function itself: the two arguments x and y are both type Double, and the body of the function first checks if y is 0; if it is, then it returns Nothing; otherwise it returns Just (x / y), which is the Haskell syntax for some.

Now we can do some computations with our safe division function. Let’s use bind to sequence together a chain of computations that may fail:

Again this syntax is quite foreign. The bind operator >>= is acting as an infix function call: its first artgument is on the left and its second argument is on the right. The syntax \x -> e is Haskell’s syntax for lambda. pure is the usual pure function. We can call this function in various ways:

Chaining together sequences of binds is very common in Haskell, so there is some nice syntactic sugar for this using so-called do-notation. The following function definition is equivalent to the sequence of binds above and much nicer to read:

Haskell lets you define your own monads and use the nice do-syntax! Here is a little fragment that shows how to add a probabilistic programming language into Haskell by implementing the distribution monad we saw last lecture:

This lets us make essentially all of Haskell into a probabilistic programming language!

22.2 Effect Handlers🔗

One of the main challenges of programming with monads is that they do not compose well. If you want to write a program that has multiple different kinds of effects at the same time in a language like Haskell you need to make use of infrastructure for combining monads (so-called "monad transformers"). It becomes rather messy. But, the upshot is that the type system tells you what kinds of effects your programs can have! This is quite nice.

Monads, however, are not the only kind of way of handling effects in languages. An alternative approach that is becoming ever more popular are effect handlers. At a high level, effect handlers look very similar to resumable exceptions.

#lang racket

(require effect-racket)

(effect flip (prob))

(define (process r prob b)

(match r

[#t prob]

[#f 0]

[r (if b (* r prob) (* (- 1 prob) r))]))

(define (prob-service)

(handler

[(flip prob)

(define r1 (continue #t))

(define r2 (continue #f))

(define p1 (process r1 prob #t))

(define p2 (process r2 prob #f))

(+ p1 p2)]))

(with ((prob-service))

(define a (flip 1/3))

(define b (flip 1/2))

(and a b))

22.2.1 Programming Languages with Effect Handlers🔗

If you’re interested in learning more about effect handlers there are a variety of languages today that support them:

• Koka is an experimental functional programming language that effect handlers. Effect handlers are deeply built in to the language and are quite elegant to use in this language.

• OCaml recently added effect handlers