Self-explaining computation

Behind every value lies a computation struggling to get out. That’s the idea behind what I call the explodable user interface. (Forget wearable. Explodable.) By “explodable” what I have in mind is the ability to pick any part of an application’s GUI that you happen to be interested in and interactively “unpack” it into a story that explains how it was computed. It should be as though code lurks behind everything you can see, all the way back to the data sources your application works with. In Lisp you can explode an atom into its constituent characters, but the relationship between a Lisp atom and its characters has no computational content to speak of. In a typical application, the relationship between a value and its parts is non-trivial. If it were otherwise, you wouldn’t call it an “application”: you’d call it “a bunch of data”. Whenever this non-trivial structure is present, you should be able to browse into it in order to understand it or change it.

One of the steps towards turning this idea into a reality involves making the sharing structure of a pure computation explicit. I discuss this and related ideas in the following video. (The video is a segment of a talk I’ll be giving in a few weeks here at MPI-SWSJames Cheney came up with “self-explaining computation” as the title of a paper we submitted to POPL 2010. The paper wasn’t accepted, and eventually mutated into this ICFP paper, but I still like the old name! It’s a nod to self-adjusting computation, which is itself an allusion to self-adjusting binary trees. Ho hum.)

Visualising sharing by sharing visualisation

I already need to represent a LambdaCalc computation as a DAG, with explicit sharing, so that I can capture re-use across computations as the partial inclusion of the previous state into the new state. But sharing also happens within a single state. Computations share whenever when you invoke the same closure with an identical value (think memoisation, only with pointers) but, more importantly, values are shared all over the place. This kind of structural re-use is a familiar implementation technique from languages like ML and Haskell. Functional programmers often think about the way values are shared, even if technically it’s not part of the observable behaviour of their program.

There are two kinds of value-sharing within a computation. The first is analogous to the tail-call optimisation. Consider the call graph for eval as it interprets a program. Some of these calls are tail calls. (In terms of big-step semantics: whenever you have an evaluation rule which returns v, where v is the value computed by the rightmost premise of the rule, you have a tail call.) For example a case analysis just returns the value of the selected branch; a function call just returns the value computed by the executed function body. Maximal chains of these tail calls in the interpreter can be visualised as single computation-cells in LambdaCalc, returning the value computed by the terminal computation in the chain. (And this observation now suggests an obvious improvement to the current LambdaCalc UI: make the linear control-flow within one of these computation-chains more explicit, by just showing the path selected in the tree of conditionals, rather than the whole tree.) The structural/visual re-use here is that many steps in the computation share a single value-cell.

The second kind of visual sharing is more akin to memoisation. With memoisation, you avoid redundant computations by retrieving the cached value whenever you “match” a previously executed function call. In LambdaCalc, computation “is” the visualised structure. So memoisation is spatial: when you find yourself trying the construct a visualisation that’s already been built, you can reuse the cached version instead. This gives rise to explicit sharing in the UI itself. The sharing can be visualised using links (as shown the video above) or by other visual cues that make it clear that two bits of UI are “the same”. For example you could transclude the memoised view, but have it so that selecting the transcluded view selects all occurrences of that view. You could even clone the mouse pointer when over a shared view.

Exploding the user interface

I’m only scratching the surface of this idea in the video above. I show how you can collapse a computation all the way back to a value, and conversely expand a value out into an explanation of how it was computed. There’s a sizeable gap between this basic facility and explodable user interfaces proper, of course. Some prerequisites are straightforward UI improvements, in the form of more control-flow-symmetric visualisation: flattening conditional structure within a linear chain, as mentioned above; allowing “leading” context as well as “trailing” context to be collapsed into an ellipsis; and showing bindings for the pattern-variables that occur in a case analysis, as mentioned in the video. These are all relatively straightfoward regularisations that will significantly improve the scalability and incremental explorability of the UI.

Beyond making the UI more symmetric and scalable, a more fundamental requirement is GUI-level integration between the meta-language – the host environment that provides LambdaCalc with a GUI, namely Haskell – and the object language, LambdaCalc itself. In particular, when the programmer writes GUI code (code that computes values of type “GUI”) in LambdaCalc, the computed GUI values must be visualised as GUI objects inline with the visualisation of the execution of the GUI program itself. This means being able to reflect a value of type “GUI” up to the meta-language so that it can be directly rendered in the host GUI. I’m guessing that this is the kind of thing that goes on in reflective GUIs like Squeak, but I haven’t actually looked at how they work.

I already have the raw components of this, a pair of functions called reflect and reify that coerce values between Haskell and LambdaCalc. This is how I’ve implemented some of the GUI for LambdaCalc itself. However, the integration is ad hoc and requires more work. When that’s in place, collapsing a computation back to a value will turn it back into the application’s GUI. At that point the application and its programming environment become one and the same beast.

This kind of destructuring interweaving of visualisation of execution and visualisation of output has been lacking so far in the live programming systems I’ve seen. The standard setup is to have a static program in one window, and the output in the other. The execution itself is hidden, and a fortiori the relationship between steps in the execution and elements of the output. As you hack the program, the output updates, but there’s no way to browse into the execution and see the value similarly broken down and distributed over the bits of the computation that contribute to it.

10 comments

  1. Johnicholas says:

    Do you think this is relevant to Mike Thyer’s Lazy Specialization? http://thyer.name/

    • Roly Perera says:

      I’m not sure. There’s nothing like specialisation going on. No work gets done with the body of a function until the application is fully saturated. Thanks for the pointer though, certainly something to think about.

  2. Roly, my friend, when I hear of “explodable user interface” I think of destroyable terrains and a physics-inspired UI, or perhaps of Mission Impossible messages. Surely we can find a better descriptor for your meaning? Perhaps “whitebox” or “transparent”. “Self-explaining” also works.

    I agree with the vision of providing user’s easy access to explanations for a computation, though my approach to the problem is different. One goal of mine has always been zoomable user interface (ZUI), and the basic rule for ZUI is that computation costs be roughly proportional to pixels on screen. In LambdaCalc, this would correspond to computing only the parts of the visualization that are actively being visualized (typically the result and a couple intermediate frames) as opposed to computing an entire structure of computation then displaying just a few parts.

    To support progressive disclosure and ZUIs, I’ve focused my efforts on supporting multiple views – treating computation as a view or composition of views. A view of active source would then just be one possible view to compute, and would only be computed when actively viewed.

    One technique I’ve found useful is to provide descriptors of the view into the computation – i.e. instead of computing the whole structure then trimming it, provide sort of a query-value indicating which parts of the structure are currently observed, and focus on the stability problem (a small shift in query should not result in a big shift in results) by appropriate use of layers, etc.

    Stability, BTW, is a problem for disclosure of dynamic-structured computations, such as recursive lambda calculus. How do we describe a stable path and stable view of a computation that’s bouncing around like a madman on a pogo stick?

    Well, there are ways to do so. Graphs are a nice way to show where something is, recursive contributions, and where it has been recently. It’s an interesting problem to tackle. But I think you’ll want to expand on the notion of `visualization`. Drill down with ellipses is really providing very little useful information per pixel (and is too interactive, requires too many clicks on screen).

    • Roly Perera says:

      I agree that computing the whole thing and then visualising doesn’t really make sense. The view should induce demand on the computation, and that should determine the amount of work done. But I worry about your (Euclidean-esque) ZUI principle that computation costs should be roughly proportional to pixels on screen. Is that even possible? I presume you’re not talking about computing some kind of coarse-grained abstraction of the computation that fits in fewer pixels and therefore costs less to compute? That might work for computations with a certain kind of homogenous or self-similar structure, like particle-based physics for a game, but I don’t see how it could be general.

      Either way, I definitely intend to move to a demand-driven model. What I plan to do is related to the work described in this paper, and may bear some similarity to your idea of view descriptors. In the paper we show that you can compute “forward” under CBV to obtain a value v, and then use a copy of v with some bits missing to compute “backwards”, obtaining a slice of the original program. This partial copy of v describes the demand being placed on v by some client system, perhaps a user or perhaps an attached computation. The “demand pattern” induces further demand patterns on sub-computations and ultimately determines a slice of the original program. What I plan to do is dump the CBV aspect of this work and just compute directly with demand patterns. It’s something like a generalisation of lazy evaluation: instead of computing to head-normal form, which always computes the output to a fixed depth (the root constructor), you compute to some level of strictness determined by a partial value specifying the demand on the output to an arbitrary depth. The user can drill into a partial value to induce more demand and cause more computation to take place.

      I’m also not sure about the stability issue. In the ICFP paper we don’t consider computations with changing structure. Maybe having explicit identity on nodes helps, since the demand placed on a sub-component of the output then has the potential to persist across disruptive reorganisations of the computation.

      • It is possible to structure computations in a manner that enforce the ZUI principle. However, there would be a severe cost in expressiveness, and a tighter coupling between a particular “canonical” view and computation than is preferable.

        I think it better to focus on design that encourage and support the ZUI principle, such that it can be achieved on a path-of-low-resistance. I keep views precise from end-to-end, and manage queryable resources (e.g. sensors, databases) based on the current demand. I eventually found parameterized demand a powerful, uniform basis for control of all things (sensors, databases, actuators, UI, etc.) which led to Reactive Demand Programming.

        Anyhow, what ZUI would mean for LambdaCalc would be: (a) instead of opening a value (“expanding” it into the UI), you zoom in; (b) you provide the illusion that the sub-structure is always open; (c) you don’t actually provide the sub-structure for stuff that would only consume a few pixels on the screen. ZUI is achievable if you structure your display models to support spatial analysis (without doing the detail computation) and progressive disclosure.

        Maybe having explicit identity on nodes helps, since the demand placed on a sub-component of the output then has the potential to persist across disruptive reorganisations of the computation.

        It does help. It’s a technique I use. But many computations are unstable, and even with stable explicit identity we might use different identities (from abstract infinite spaces of identities… plenty to choose from) at different instants. Providing a little history, graphs, temporal abstraction is a useful way to support users in dealing with instability when we can’t avoid it.

        • I would note: the instability issue becomes much more important when you have changes not caused by a single user. I.e. concurrent users, sensors, shared databases.

          • Roly Perera says:

            Agreed. I use a deterministic policy for assigning indices to computation nodes, so I don’t run into the issue of choice, but certain kinds of algorithm (e.g. sorting) that generate lots of intermediate nodes typically lose so much information about the relationship between input and output that the identity of all the output nodes can be destabilised by introducing a single new element into the input.

            There may be lots of ways of addressing these sorts of issues, including using more bidirectional (less lossy) languages, encapsulating unstable algorithms in stable wrappers (which I’ve experimented with successfully in LambdaCalc), and using heuristics to establish correspondences between nodes which have been assigned difference indices. Re. your idea of presenting history or temporal information to the user, maybe they could also be allowed to establish (manually populate) identity links between past and present, so they provide their own continuity when the system is unable to do it for them.

  3. Every value comes along with the computation history that generated it. This history aids in incremental (self-adjusting) computation because when part of an input changes, we only have to recompute the parts of the computation history that are affected by this change. Further, having the computation history around aids the programmer because she can check to see how any value came to be. It’s like always having a stack trace that can be pulled up.

    This gets to be very helpful when we want to investigate the *provenance* of a value. Sussman talks about this idea in [Building Remote Systems](http://groups.csail.mit.edu/mac/users/gjs/6.945/readings/robust-systems.pdf).

    Years ago I was building a system like this towards an application which is still relevant (probably even more relevant nowadays) that you may want to look into. The idea was to program large, tangled queries on multiple, distributed, constantly updating data sources. For example, you would pull some rows from one database; you’d map a function to these; that function would require pulling other data out of other data sets, etc. And as data changed (rows added or removed), your live query would incrementally update as necessary. Queries were full-featured pure functions which would generate HTML which would update live in the browser. [Meteor](http://meteor.com/) and other JS frameworks are now doing something similar, though they haven’t connected the reactive system all the way up to recursive database queries. CouchDB views do something similar but you can’t compose them (i.e. have views generate data which then triggers other views). Datomic seems to be doing something similar, along with trying to get transactions right. The user’s actions on the mouse/keyboard can also be thought of as streaming data sources as in traditional FRP so the model is pretty comprehensive.

    You can think of these as just “queries”, or you can think of this as an entire knowledge inference system. The query is pulling information but also synthesizing information, and when you chain a bunch of these inferencers, it’s important to keep track of the provenance of the inferences. Might be “killer app” for lambdacalc.

    I like the idea of multiple mouse cursors when showing multiple views of a transclusion. Might get wacky.

    • Roly Perera says:

      It’s interesting that you mention provenance and incremental update. As you say, these are the two main advantages of having the computation history around, other than being able to use it for interactive debugging and program comprehension. Of course provenance and incremental update are closely related: to work out whether a computed value is affected by an incoming delta, you need to know whether it ultimately consumes that particular change.

      Your old provenance project sounds interesting (and thanks for the pointers to those other projects). As it happens, LambdaCalc has some provenance features implemented which I haven’t yet had time to show. They’re discussed in this paper, which I’ll be presenting at ICFP in September.

      I think you’re spot on with your point about these systems built out of tangled queries from disparate data sources on the web. These systems aren’t just queries. Non-trivial computation is taking place too. Similar issues come up in scientific computing, where there is “synthesis” of data as well as just importing of data. I think we’ll also see federated wikis facing this challenge, because they’re going to be pulling data from all over the place and visualising it out of its original context. When we have computational and GUI models where every bit of content is equipped with an audit trail, it’ll be easier to trust your data sources.

      Thanks for the feedback!

  4. […] programs as clay until they’re ready to be fired in the kiln. Roly Perera’s work on self-explaning computation interests me a lot as does Chris Granger’s work on Light Table. Rapid feedback loops are […]