Zipper File System: Delimited continuations in operating systems
        Oleg Kiselyov and Chung-chieh Shan

     In programming languages, delimited continuations are the
meanings of delimited evaluation contexts. In operating systems,
delimited continuations manifest as the context of a user process or
thread, a co-routine, an event handler, or a process snapshot. In this
presentation we draw attention to a less known manifestation of
delimited continuations in operating systems: data structure
traversals and file systems, especially transactional file systems.

    We have built the Zipper File System as a working prototype that
explicitly uses delimited continuations as a uniform framework to
implement all file system operations as well as multiprocessing and
exception handling. The prototype also illustrates how a mature
language with an advanced type system, such as the high-level
general-purpose language Haskell, makes delimited continuations easier
and more reliable to use. Haskell has been used both to prototype
microkernels (Secure L4) and to implement complete operating systems
(House).

      The Zipper File System is a file server running on a host
operating system such as Unix. The file server lets multiple remote
clients concurrently traverse, view, and manipulate what looks like a
Unix file system. In our current prototype, all file system data
reside in virtual memory; we thus rely on VM or snapshot facilities of
the host OS for disk operations.

    Our server offers the typical operations of creating and removing
files and directories, listing and traversing directories, reading and
writing files, creating and following links. Atypically, we also
support
  - transactional semantics, with undo and snapshots;
  - the strongest isolation mode for clients, repeatable read;
  - pervasive copy-on-write for files and directories;
  - intrinsic depth-first traversal; and
  - cyclic directory references.
Currently, the clients access our server via a simple TCP protocol,
designed for ease of demonstration.  It is straightforward to add
support for NFS, 9P, or another distributed file system protocol.

     Our server is multi-tasking but single-threaded. The type system
ensures that our tasks cannot mutate any global state or cause any
concurrency problems. Therefore, the tasks can safely be run in
parallel on any available processor (core). Thus delimited
continuations let us statically isolate side effects even though the
program as a whole performs lots of IO operations.

     We use the zipper, a delimited continuation of a traversal, to
navigate within any data structure.  If the data structure in question
is a map whose keys are strings and whose values are either strings or
other maps, then the zipper-based file system looks like an ordinary
hierarchical file system. We can traverse richer data structures than
mere maps with string keys, so our file system can support arbitrary
file and directory attributes. In short, we implement file system
operations as debugging checkpoints during an arbitrary
traversal. This technique already supports hierarchies created on the
fly, such as those in Semantic File System or Logic File System.

     The Zipper File System consists of only about 1000 lines of code,
about half of which implements delimited continuations and
zippers. More information, including `screenshots' and complete
source code, is available online at
	https://okmij.org/ftp/Computation/Continuations.html#zipper-fs

     We conclude that explicitly recognizing these uses of delimited
continuations helps us design a system of concurrent, isolated
transactions where desirable features such as snapshots, undo,
copy-on-write, reconciliation, and interposition fall out by
default. It also lets us take advantage of efficient implementation
techniques from programming-language research.