CW 2011 Tutorial:
Introduction to Programming with Shift and Reset

September 23, 2011

1 Goal of the tutorial

The concept of continuations arises naturally in programming: a conditional branch selects a continuation from the two possible futures; raising an exception discards a part of the continuation; a tail-call or `goto' continues with the continuation. Although continuations are implicitly manipulated in every language, manipulating them explicitly as first-class objects is rarely used because of the perceived difficulty.

This tutorial aims to give a gentle introduction to continuations and a taste of programming with first-class delimited continuations using the control operators shift and reset. Assuming no prior knowledge on continuations, the tutorial helps participants write simple co-routines and non-deterministic searches. The tutorial should make it easier to understand and appreciate the talks at CW11.

We assume basic familiarity with functional programming languages, such as OCaml, Standard ML, and Scheme. No prior knowledge of continuations is needed. Participants are encouraged to bring their laptops and program along.

2 Practical Information

3 Necessary Software

PLEASE install OchaCaml before the tutorial. We will use it in the tutorial.

OchaCaml

The compilation/installation instruction is found here. Your installation is successful if you can launch OchaCaml and obtain 41 by typing the following program

1 + reset (fun () -> 2 * shift (fun k -> k (k 10))) ;;

followed by return. (To exit OchaCaml, type

quit () ;;

followed by return, or just ctrl-D.) If you have any problems compiling/installing OchaCaml, send an e-mail to: asai (at) is.ocha.ac.jp.

Editor

Use your favorite editor that can copy and paste a program into OchaCaml. If you are using Emacs, tuareg-mode (for OCaml) works for OchaCaml, too.

Other Languages

Optionally, install OCaml, Haskell, or Racket (a variant of Scheme), if you want to try shift and reset in these languages, too. See the appendix for more details.

4 Tutorial Notes and Code

Tutorial note (English/Japanese), program
Tutorial note on Haskell (English only), program
Slides

Appendix

A How to use `shift`/`reset` in OCaml

Install Delimcc library.
For each answe type, declare a prompt by:
```
let p = Delimcc.new_prompt ()
```
reset (fun ()-> M) is written as: Delimcc.push_prompt p (fun () -> M)
shift (fun k -> M) is written as: Delimcc.shift p (fun k -> M)

B How to use `shift`/`reset` in Haskell

See ContExample.hs for how to define and use shift/reset in the standard Haskell (using the mtl package).
For shift/reset with answer-type modification, one needs parameterized monad. See here for details.

C How to use `shift`/`reset` in Racket

Choose the module language.
Write (require racket/control) at the beginning.
Syntax: (reset M), (shift k M).

This document was translated from L^AT_EX by H^EV^EA.

CW 2011 Tutorial: Introduction to Programming with Shift and Reset