The lesser of two evals

(With apologies to Manuel Simoni)

I gave this talk at MPI-SWS in Saarbrücken yesterday. My original plan was to upload the video that our support people recorded, so I could include the audience discussion. (Yeah, there was some. Fuck you.) That turned out to be a grainy picture of me talking, a grainy picture of my slides, and a grainy picture of a bunch of people staring blankly at a videocast to Kaiserslautern. Squished nicely together into a grainy composite image with crap audio. Given the amount of taxpayer-funded videotech we have here, it’s odd verging on disturbing that we couldn’t do better.

So instead, here’s a version of the talk I recorded on Sunday. (If you watched my last video: although the title is the same, there isn’t much overlap in content.)

A recurring theme is comparing computation. Any differencing scheme for a datatype T has three components. First we need an indexing scheme for identifying, or “aligning”, nodes in the T’s being compared. (With string differencing, the most common indexing scheme identifies maximal subsequences common to the two strings.) Second, we need a data type of T-deltas. A T-delta might be an imperative sequence of traversal and editing steps that transforms the source into the target, as in string or tree differencing, or something more declarative: with set differencing for example we need only pick out the “new” elements, which occur in the target but not in the source, and the “deleted” elements, which occur in the source but not in the target. (To instead use an imperative script which added and removed elements individually would, for set differencing, be an over-specification.) Finally, we need an algorithm that applies the indexing scheme and uses the resulting alignment information to compute a T-delta from two T’s.

When the set of operations allows arbitrary moves — e.g. sequence differencing that allows elements to be transposed or tree differencing that allow siblings to be reordered — then the hardest part by far is coming up with the indexing scheme, i.e. deciding when two nodes “align”. Indeed, sequence differencing with transposition is NP-hard, and since tree differencing with sibling-transposition can clearly encode it, so is tree-differencing. To make this kind of problem more tractable, people usually resort to eliminating moves from the set of permissible operations, or exploiting other information to decide how to align nodes. For example with execution indexing, steps in a computation are identified using a variety of tricks, including counting the invocations of a particular statement, matching the execution context against a context-free grammar, and address normalisation to unify non-deterministic allocations.

Differential computation-slicing

In my LambdaCalc prototype, deltas are pervasive. They come up in two ways. The first way is rather trivial from a differencing point of view, since it involves comparing two slices of the same evaluation. This is discussed in the second part of the talk above, and is also the subject of this paper. Slices are syntactic approximants of the original execution; they have the same structure as the original execution modulo some sub-computations which have been discarded, which we call “holes”. (See The Lattice of Flow Diagrams by Dana Scott for some similar concepts.) Because their structure differs only with respect to holes, two slices of the same execution always have a trivial alignment function, and the set of edit operations can be reduced to just subgraph insertion and deletion. (In a LambdaCalc visualisation, you are always looking at only one half of a symmetric delta: it’s as though of the two evals, one is always the lesser. You can see the other half of the delta by moving forward in time and looking back.)

This kind of execution-differencing allows the user to interactively focus on parts of the computation “upstream” (via backward slicing) and “downstream” (via forward slicing) of some sub-value or sub-expression of whatever they are currently looking at. It’s discussed in detail in both the talk and the paper. It’s a kind of interactive parallel decomposition of the execution, allowing you to pick out a thread of execution and see it flowing forwards or backwards. Bret Victor‘s typically amazing nano-demo in this recent Alan Kay presentation (about 20 minutes in) shows something similar: Kay mouses over the output of a pipelined, parallel graphics computation, and you see the corresponding part of the input being highlighted at each stage of the pipeline. I’m looking forward to reading their paper on this.

Differential execution

The other kind of delta in LambdaCalc is when the computation updates in response to an edit. (The first kind of delta is in fact just an important special case of this more general form of update; so I think I want to say that program slicing is just a special case of incremental computation. But that’s another story.) The general case is less straightforward, because the structure of the computation can differ in arbitrary ways. In particular the indexing scheme which aligns nodes across the two states is no longer just a simultaneous traveral of the two DAGs. Instead we must determine how nodes correspond not only in the presence of node creation and deletion but also in the presence of arbitrary shuffling around. (Just consider if the user permutes the elements in a list to which a function is being mapped, for example. There was an example of this in my first video.)

I have an efficient and easy-to-implement indexing scheme, which is the computationally hard part for most differencing problems. The usual difficulty is that the differencing problem starts with no prior knowledge of how the nodes in the structure might correspond. The emphasis of the problem is on discovering a “good” (efficient) set of correspondences. In LambdaCalc, these correspondences are computed during execution with a constant-factor overhead. This is easy because the input to the interpreter is a program where every sub-expression has already been assigned a unique index. Evaluation then deterministically creates new indices for computation nodes and computed values, using the indices in the source expression as the source of “raw identity”. So in our setting, the hard bit is not computing the deltas, but rather one of computing the target state from the source state in such a way that the time taken to obtain the target state asymptotically coincides with the size of the resulting delta. This is a quite different problem, one of incremental computation. And one I haven’t yet tackled.

Having a simpler alignment problem means we can have richer set of possible deltas. In particular, we can support arbitrary moves, because we don’t have to compute the move information, but merely harvest the move information provided by the programmer in the form of the original edit operation. This contrasts interactive programming with, for example, self-adjusting computation, where the computation is a tree and the computation can only be updated via subtree insertion and deletion. This is too simplistic for interactive programming, as it doesn’t support common edits, such as transposing elements of a list or arguments to a function. Any interactive programming system must support these familiar edits efficiently. Non-monotonic self-adjusting computation does allow re-ordering of trace nodes, although reordering is non-deterministic: an implementation may choose to re-use nodes out-of-order, but does not have to. And more importantly, the way computation nodes are reused non-monotonically does not have to correspond in any way to how the input changed. In LambdaCalc, identification of nodes is deterministic, not a choice made by the implementation, and this means that every computation delta can be causally attributed to a delta made by the programmer.

The point of the more general form of differential execution is not just about incremental performance, though. It’s about being able to observe the impact of changes to the program on the structure of the execution. I discuss this briefly in the last part of the talk. The split example I give works in a rather neat way, although only part of that is actually visible in the demo. The behaviour shown when you insert new elements into the input is pretty intuitive, but what happens when the broken implementation is fixed is less so. This is because the output cells shuffle around in a way that unfortunately isn’t visible with the current LambdaCalc UI. There are “pointers” (only observable at the meta-level, not at the level of the user’s program) which connect the list cells together; these all change during the update, but as these pointers have no real visualisation, they don’t appear in blue, like other changed things. This can be improved. Animation will certainly be part of it eventually.

DSLs, ADTs, and other abstractions

Something that came up in separate conversations with Scott and Derek is how abstract data types and other abstractions fit into this take on things. Interactive programming exposes a very intensional view of the computation, by design. Doing so has the potential to violate encapsulation or abstraction. For example, suppose a module with a Set interface and an implementation of it based on lists. We want the user to be able to “debug into” this module, if it helps them, but perhaps without having to expose the implementation detail. For example, the user should be able to select an element in the output of set union and see the corresponding occurrence(s) of that value selected in the arguments to set union, without being able to see the intermediate processing that “explains” this connection. So, maybe this is a situation where we can still expose the fine-grained relationship between input and output, without exposing the implementation. (It also reminds me of dependency-tracking at the level of ADTs in self-adjusting computation.)

Related to this is the observation that you might want to expose a computation to end users, but at a more user-friendly level of abstraction than the implementation code. In other words, computational explanations should be couched in the domain language that users have in mind when using your application. We should take this requirement seriously, for sure. The direction I would like to move in here is towards taking the user-level domain model and making it explicit and executable. After all, this is the business model that the application’s designers and business analysts would like to program directly. Why hand-off to a team of “developers” for implementation if you can capture a business process directly as an executable model? And then it’s the execution of these models that can be exposed to end-users, to provide “online explanations” that make actual sense to them. So there is potential here for transparent, self-explaining computation to be a “killer app” for DSLs.

Comments are closed.