# This file is meant to be read in presentation mode.
# Convenient function to mark examples.
fun example(m)() { m() }
fun undefined() { error("Undefined: Did you forget to reload the slides?") }
# Composition operators
op h -<- g { fun(m) { h(g(m)) } }
op h -< m { h(m) }
#!
#
# Liberating Effects with Rows and Handlers
#
# Daniel Hillerström and Sam Lindley
# The University of Edinburgh, UK
#
# TyDe'16, Nara, Japan
#
#?
#!
#
# Introduction
#
# Monads are a successful abstraction for effectful programming
# [Moggi, 1991; Wadler, 1992].
#
# Monadic effectful computations do not compose in general.
# [Kammar, Lindley, and Oury, 2013; Kiselyov, Sabry, and Swords 2013].
#
# Algebraic effects [Plotkin and Power, 2001] combined with handlers
# [Plotkin and Pretnar, 2013] provide a modular alternative to monads.
#
# We say [Hillerström and Lindley, 2016]:
# * to be modular an effect type system must support extensible
# effects.
# * the required abstraction to implement extensible effects and
# their handlers is exactly row polymorphism.
#
#?
#!
#
# About this Talk
#
# In this talk:
# * A taster of programming with row-polymorphic algebraic effects and
# handlers in Links.
# * These "slides" are in fact a runnable Links program.
#
# In the paper:
# * Mathematical game Nim as an example of programming with handlers.
# * Implementation based on a generalised CEK machine.
# * Operational semantics and abstract machine semantics.
# * Proof that the two semantics coincide.
#
#?
#!
#
# Links
#
# Links is a functional research web-programming language
# [Cooper, Lindley, Wadler, and Yallop, 2006]:
# * Single source language for multi-tier web-programming.
# * Syntax reminiscent of JavaScript, e.g.
fun uncurriedAdd(x,y) { x + y }
fun curriedAdd(x)(y){ x + y }
# * Statically typed with Hindley-Milner type inference.
# * Comprises three backends:
# - a JavaScript compiler for client-side code,
# - an interpreter for server-side code,
# - and a SQL generator for database code.
# * Effect system used to track whether a computation can run in the
# front-, back-, or database-end.
#
#?
#
#
# Motivation
#
# Many programs comprise an *effectful* component that may
# - raise exceptions,
# - perform input/output,
# - mutate some state,
# - spawn processes,
# - be non-determinism,
# - ... and so forth
#
# In most programming languages effects are dealt with *implicitly*.
#
# Algebraic effects combined with handlers provide a modular
# abstraction for modelling and controlling user-defined computational
# effects such as the aforementioned.
#
#
sig chooseSlide0 : ()
#
#
# Algebraic Effects
#
# An algebraic effect is a collection of abstract operations. For
# example, nondeterminism is an algebraic effect given by single
# nondeterministic choose operation:
{Choose:Bool}
#
-> Bool
fun chooseSlide0() {
#!
#
# Algebraic Effects
#
# An algebraic effect is a collection of abstract operations. For
# example, nondeterminism is given by a single operation `Choose'.
#
# In Links, an abstract operation is invoked using the `do' primitive:
#
do Choose
#?
}
#
#
# Effect Signatures
#
# We can abstract over the invocation of operations by using
# functions. In Links, a function definition begins with the `fun'
# keyword, and we may assign it a type using the `sig' keyword:
sig choose : () {Choose:Bool |e}-> Bool
fun choose() { do Choose }
# Here `e' is a row variable which may be instantiated to contain
# additional operations. This is to say, that `choose' may be used in
# the presence of other effects.
#
#
#!
#
# A Coin Toss [Kammar, Lindley, and Oury, 2013]
#
# We may use `Choose' to model a coin toss, e.g.
typename Toss = [|Heads|Tails|]; # Variant type with two constructors
sig toss : () {Choose:Bool |e}-> Toss
fun toss() {
if (do Choose) Heads
else Tails
}
# The variable `e' is a row variable. Links uses Remy-style row
# polymorphism [Remy, 1993] to implement extensible effect signatures.
# Let us try to evaluate this computation.
var ex1 = toss;
#?
#
#
# Abstract Computations
#
# Evaluation of `toss' throws "Unhandled operation: Choose" right at us.
#
# Thus far we have only considered the *syntax* of effects. We say
# that `toss' is an *abstract computation*.
#
# How can we turn `toss' into a *concrete* computation?
#
#
#
#
# Syntax of effectful computations
#
# Thus far we have only considered the *syntax* of effects.
# Visually, we may depict `toss` as computation tree, e.g.
#
# Choose
# /\
# true / \ false
# / \
# Heads Tails
#
# Internal nodes: Operation names
# Edges: Labelled with return values of the origin operation
# Leaves: Return values of the abstract computation
#
# A handler consists of a collection of clauses, in this case two:
#
# 1) A Return clause which determines how to handle the
# return value `x' of the computation `m',
# 2) and an operation clause `Choose' which determines
# how to handle the said operation in `m'.
#
#!
#
# Effect Handlers
#
# An effect handler is a modular interpreter for computations.
#
# As an example consider a random interpretation of `Choose':
handler randomResult {
case Return(x) -> x
case Choose(resume) -> resume(random() > 0.5)
}
# The operation clause `Choose' expose a function `resume' which is
# the delimited continuation of the operation in the handled
# computation.
#
# Using `randomResult' to interpret `toss':
var ex2 = randomResult(toss);
#?
# I am cheating a bit here.
sig randomResult0 : (() {Choose:Bool |e}~> a) -> () {Choose{_} |e}~> a
handler randomResult0 {
case Return(x) -> x
case Choose(resume) -> resume(random() > 0.5)
}
var ex2 = randomResult0(toss);
#
#
# Instantiation of Abstract Computations
#
# Using `randomResult' we may interpret `toss':
#var ex2 = example( randomResult(toss) );
#
#!
#
# Ascribing Types to Handlers
#
# What might the type of `randomResult' be?
# What should we write in place of `e1' and `e2'?
sig randomResult : (() {Choose:Bool |e}~> a) ->
() {Choose- |e}~> a
handler randomResult {
case Return(x) -> x
case Choose(resume) -> resume(random() > 0.5)
}
#?
#!
#
# An Enumerative Interpretation
#
# The application `randomResult(toss)' yields a computation which
# returns *either* `Heads' or `Tails'.
#
# Alternatively, we can give an interpretation which enumerates the
# possible outcomes of a computation:
sig allChoices : (() {Choose:Bool |e}~> a) ->
() {Choose- |e}~> [a]
handler allChoices {
case Return(x) -> [x]
case Choose(resume) -> resume(true) ++ resume(false)
}
# An example of it in action
var ex3 = allChoices(toss);
#?
# I'm cheating a bit here. Due to absence I'll not be able to evaluate `ex3' after evaluating `ex1'.
sig allChoices0 : (() {Choose:Bool |e}~> a) ->
() {Choose{_} |e}~> [a]
handler allChoices0 {
case Return(x) -> [x]
case Choose(resume) -> resume(true) ++ resume(false)
}
var ex3 = allChoices0(toss);
#!
#
# Exceptions
#
# Let us introduce another abstract operation `Fail':
typename Zero = [||]; # The empty type
sig fail : forall a::Type . () {Fail:Zero |e}-> a
fun fail() {
switch (do Fail) { }
}
# Because `Fail' returns an element of the empty type `Zero', then an
# invocation of `fail' amounts to raising an exception.
#
#?
#!
#
# A Drunk Coin Toss
#
# We can use `toss' and `fail' to model a drunkard tossing a coin:
sig drunkToss : () {Choose:Bool,Fail:Zero |e}-> Toss
fun drunkToss() {
if (do Choose) toss() # Performs `Choose'
else fail() # Performs `Fail'
}
# The two branches of `drunkToss' perform different effects. So, what
# might the effect signature of `drunkToss' be?
#
# Recall
sig toss : () {Choose:Bool |e}-> Toss
# Note: We only mention `Choose' once in `drunkToss'. Alternative
# systems permit multiple occurrences e.g. Koka [Leijen, 2014].
#?
var toss = toss;
#!
#
# Partial Interpretations
#
# With `randomResult' and `allChoices' we may only give a partial
# interpretation of `drunkToss', e.g.
# This one will not succeed:
var ex4 = allChoices(drunkToss);
# Maybe we get lucky:
var ex5 = randomResult(drunkToss);
#?
var ex4 = allChoices0(drunkToss);
var ex5 = randomResult0(drunkToss);
# While we could include a `Fail' clause in `allChoices', a better and
# more modular alternative is to define a separate handler for `Fail'
# and then compose it with a handler for `Choose' in order to fully
# interpret `drunkToss'.
#
#!
#
# Modular Interpretations
#
# We define a handler that models the possibility of failure as a
# Maybe-value:
typename Maybe(a) = [|Just:a|Nothing|]; # Maybe type constructor
sig maybeResult : (() {Fail:Zero |e}~> a) ->
() {Fail- |e}~> Maybe(a)
handler maybeResult {
case Return(x) -> Just(x)
case Fail(_) -> Nothing
}
#?
sig maybeResult0 : (() {Fail:Zero |e}~> a) ->
() {Fail{_} |e}~> Maybe(a)
handler maybeResult0 {
case Return(x) -> Just(x)
case Fail(_) -> Nothing
}
#!
#
# Drunk Coin Tossing
#
# Now, we can fully interpret `drunkToss':
sig ex6 : () {Choose-,Fail- |e}~> [Maybe (Toss)]
fun ex6() { (allChoices -<- maybeResult -< drunkToss)() }
# the opposite composition:
sig ex7 : () {Choose-,Fail- |e}~> Maybe ([Toss])
fun ex7() { (maybeResult -<- allChoices -< drunkToss)() }
# with `randomResult':
sig ex8 : () {Choose-,Fail- |e}~> Maybe (Toss)
fun ex8() { (randomResult -<- maybeResult -< drunkToss)() }
#?
var ex6 = allChoices0 -<- maybeResult0 -< drunkToss;
var ex7 = maybeResult0 -<- allChoices0 -< drunkToss;
var ex7_toss = maybeResult0 -<- allChoices0 -< toss;
var ex8 = randomResult0 -<- maybeResult0 -< drunkToss;
#
#
# Stateful Interpretations (I)
#
# Nondeterminism and failure both comprise a single operation. But,
# algebraic effects may in general consist of more operations.
#
# A canonical example of this is *state* which consists of two
# operations:
# State retrieval
sig get : () {Get:s|_}-> s
fun get() { do Get }
# State update
sig put : (s) {Put:(s) {}-> ()|_}-> ()
fun put(s) { do Put(s) }
# Note: Empty effect signature on `Put', because any effects it may
# have are conferred by its handler.
#
# Replay computation
fun replay(n)(m)() {
if (n <= 0) ()
else { var _ = m(); replay(n-1)(m)() }
}
#
#
# Stateful Interpretations (II)
#
# Say, we want to log the outcomes of `drunkToss'. To achieve this we
# define a stateful post-processing handler:
sig logOutcome : (() {Get:[a],Put:([a]) {}-> () |e}~> a) ->
() {Get:[a],Put:([a]) {}-> () |e}~> ()
handler logOutcome {
case Return(x) -> put(x :: get())
}
#
#
#
# Stateful Interpretations (III)
#
# To thread state through a program, we may use a *parameterised*
# handler, e.g.
#
sig runState : (s) ->
(() {Get:s ,Put:(s) {}-> () |e}~> a) ->
() {Get{_},Put{_} |e}~> (a,s)
handler runState(s) {
case Return(x) -> (x,s)
case Get(resume) -> undefined()
case Put(p,resume) -> undefined()
}
# What should we write in place of `undefined()'?
#
#
#
#
# Stateful Interpretations (IV)
#
# Here is an example which logs the outcomes of `n' drunk tosses:
sig logDrunkToss : (Int) ->
() {Choose:Bool,Fail{_},Get{_},Put{_}|_}~> [Maybe (Toss)]
fun logDrunkToss(n)() {
# var (_, s) = runState([]) # state handler;
# (replay(n) # evaluates a comp. `n' times;
# (logOutcome # logs the outcome of a comp;
# (maybeResult # exception handler.
# (drunkToss))))();
# s
undefined()
}
# According to its effect signature the computation is only partially
# instantiated. We need to pick an interpretation of `Choose'.
#
#
#!
#
# Summary and Future Work
#
# We have briefly seen that
# * Row polymorphism provides a neat abstraction for extensible
# effects.
# * Effectful computations compose smoothly.
# * Handlers provide modular interpretations of effects.
#
# See the paper for
# * The Nim game as another example of programming
# with handlers.
# * Examples with presence polymorphism (c.f. cheat detection).
# * Formalisation: operational semantics, type system, soundness, etc.
# * The implementation details (CEK machine).
#
# Future Work
# * A compiler for server-side Links with effect handlers
# (see my ML talk on Thursday).
# * Type-and-effect directed optimisations of handlers.
# * Extend the effect handlers to the client-side.
#
#?
#!
#
# Thanks / Acknowledgements
#
# Hillerström was supported by EPSRC grant EP/L01503X/1 (The
# University of Edinburgh CDT in Pervasive Parallelism).
#
# Lindley was supported by EPSRC grant EP/K034413/1 (A Basis for
# Concurrency and Distribution).
#
#?
#!
#
# References
#
# Moggi, "Notions of Computations and Monads", IC 1991.
#
# Wadler, "Essence of Functional Programming", POPL 1992.
#
# Rémy, "Type Inference for a Natural Extension of ML", TAOOP 1993.
#
# Plotkin and Power, "Adequacy for Algebraic Effects", FoSSaCS 2001.
#
# Cooper, Lindley, Wadler, and Yallop "Links: Web Programming Without Tiers", FMCO 2006.
#
# Kammar, Lindley, and Oury, "Handlers in Action", ICFP 2013.
#
# Kiselyov, Sabry, and Swords, "Extensible Effects", Haskell 2013.
#
# Plotkin and Pretnar, "Handling Algebraic Effects", LMCS 2013.
#
# Leijen, "Koka: Programming with Row Polymorphic Effect Types", MSFP 2014.
#
# Hillerström and Lindley, "Liberating Effects with Rows and Handlers", TyDe 2016.
#
#?