dynamic aspects

My research project is called interactive programming. The central concepts are (1) reification, where a big-step semantics is taken to characterise a data type, and evaluation to produce instances of this data type; (2) reactivity, the interpretation of a program as a transition system whose states are such instances; and (3) persistence, a means for sharing state across transitions so that common substructure is not duplicated. Since none of these ideas is particularly novel, I need to be careful in my treatment of related work.

Reified evaluation arises, in a restricted form, in Umut Acar‘s self-adjusting computation, as well as in debuggers that record execution traces or similar structures. Reactivity is central to visual programming, spreadsheet languages, functional reactive programming (FRP), and again, self-adjusting computation. Persistence also arises in self-adjusting computation, as a form of memoisation. Self-adjusting computation is therefore of special importance: it is the only prior work which combines all three concepts. What I want to do here is compare Acar’s (mature, well-worked out) system with what I’m hoping to do.

Before I start, I should point the reader to this interim technical report. My report has a number of problems, which I won’t attempt to enumerate, and unfortunately it doesn’t use the term “reification”. (That was Tom Harke’s idea.) It should shed some light on what I mean by a persistent evaluation graph, which is essentially Acar’s notion of a “trace”. My notation is intentionally similar to Acar’s.

Self-adjusting computation

Self-adjusting computation is a language and runtime system for incremental computation. After an initial evaluation, the inputs of a program can be repeatedly modified, and the resulting changes to the output observed. During the initial evaluation, the runtime records a trace identifying how parts of the computation depend on other parts. When an input is modified, the output is re-calculated by a change propagation algorithm, which exploits the information in the trace to perform the update efficiently.

Early formulations required the programmer to deal explicitly with much of the technical machinery involved in making a computation self-adjusting. Although the resulting programs were still much easier to write than hand-coded dynamic algorithms, the approach was difficult and error-prone.

The most recent version, a self-adjusting extension of Standard ML called ΔML, provides more direct language support. This brings it closer in concept to interactive programming. Nevertheless it differs in several important respects, thanks to its focus on incremental performance. The following discussion is organised around the common features of reification, reactivity and persistence. The figure show some typical ΔML code.

structure ModList =
struct
  datatype 'a cell = NIL | CONS of 'a * 'a modlist
  withtype 'a modlist = 'a cell box
  type 'a t = 'a modlist

  afun lengthLessThan (l: 'a modlist) : bool box =
  let putM = mkPut $ ()
      afun len (i,l) =
        if i >= n then false
        else case get $ l of
               NIL => true
             | CONS(h,t) => len $ (i+1,t)
  in putM $ (NONE, len $ (0,l)) end

  afun map (f: 'a -> 'b) (l: 'a modlist) : 'b modlist =
  let val putM = mkPut $ ()
      mfun m l =
        case get $ l of
          NIL => NIL
        | CONS(h,t) => CONS (f h, putM $ (SOME h, m t))
  in putM $ (NONE, m l) end
end

Reification

In both systems, the initial evaluation is reified into a data structure capturing the dependencies between parts of the computation.

The key difference seems to be in whether the reification is “full”, or only “partial”. In self-adjusting computing, the trace only captures the aspects of evaluation relevant to efficient incremental update. In interactive programming, the entire evaluation is reified.

Reactivity

In both systems, data can be modified after the initial evaluation, causing the output to be updated. Synchronisation updates the trace as well as the output, producing a result consistent with an initial evaluation, and leaving the system ready to respond to another input change. Both implementations are imperative, to allow state to be reused across transitions.

The differences seem to follow from the different treatment of traces: partial reification means that self-adjusting computation has an (efficient, but potentially problematic) hybrid execution model.

Persistence

In both systems, sub-computations are shared across states by a generalised memoisation facility which stores not just computed values but associated traces.

Here, the differences arise because interactive programming makes the identities of evaluation nodes part of the observable structure. This shifts memoisation from a performance trick, to playing an essential role in the treatment of evaluation graphs as purely functional data structures.

The $64,000 question is: can full reification ever be done efficiently?