Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Self-adjusting computation seems to be related to all of the other topics, but I would like to get a clearer sense of how they all relate. For example, do any of them subsume or obsolete any of the others?
One might also throw Incremental Computing into the mix, of which Self-adjusting computation is presumably a special case.
Speaking only to the relationship between FRP and SAC:
My froc library (see http://jaked.github.com/froc) implements a form of FRP directly on top of SAC; froc behaviors are exactly SAC changeables, and froc events are SAC changeables which take on "instantaneous" values (i.e. for only one SAC update cycle). More details on how this works at http://ambassadortothecomputers.blogspot.com/2010/05/how-froc-works.html.
Froc's programming model is identical to that provided by the FrTime / Flapjax thread of FRP work, which can be implemented by pushing changes through a dependency graph. Haskell-based FRP systems (Fran et al.) are for the most part pull-based, but provide a somewhat more expressive programming model which allows free use of recursion.
I essentially agree with Dave's comment: these are lots of different things (and I only feel remotely competent to talk about three of them).
However, from the perspective of a consumer of functional programming research, the three things I know something about probably feel related, because they all are ways of making functional programs deal with inputs that change over time. For instance:
[Update] In practice, the challenges associated with each of these three things are different: it doesn't necessarily make sense to talk about any of them as special cases of the others. However, as Jake points out below, there are (slightly restricted) libraries of functional reactive programming that are implemented on top of self-adjusting computation primitives. Similarly, it might be possible to effectively implement something like partial evaluation on top of self-adjusting computation, since SAC makes the very few a priori assumptions about its input data.
I definitely agree with the decision tree laid out by Rob Simmons above; I also agree with his conclusion: they are all different, and probably not in some subsumption hierarchy.
[Disclaimer: I have very little knowledge of automatic differentiation. I have some passing knowledge of partial evaluation and FRP, but haven't used or researched either directly. I'm very familiar with self-adjusting computation; I do research in that area.]
Let me try to extend the description of SAC given above: Self-adjusting computation is a paradigm where computational decisions depend on data, which is assumed to change over time. The computation itself produces more data, which may be consumed by other (self-adjusting) computation. When any input data is changed, the technique provides a general-purpose mechanism by which the computation is updated to reflect the changes. (When I say "computation", I mean a dynamic structure, like an execution trace, that reflects the operational steps used to produce the output from the input.) By updating the computation, the update mechanism also updates the output of the computation.
As with FRP, SAC enjoys nice compositional reasoning: one can compose two functions and get the composition of their (self-adjusting or reactive) behavior. There may be a subsumption relationship there, where some flavor of SAC perhaps subsumes some flavor of FRP, but that's a topic of future research. It's certainly not obvious that this relationship exists between current approaches of SAC and FRP.
SAC compared with partial evaluation: As Rob Simmons says above, dependencies in SAC need not be separated a priori into two categories (static and dynamic); moreover, even in the case that all data has the potential to change, assuming that the changes to this data are incremental (and that the underlying program enjoys "stability" across such changes), the SAC approach can still deliver significant time savings.
This is because SAC is largely a dynamic technique, unlike partial evaluation, which is largely a static (compilation-time) technique. Because of these phasing differences, I do not think that it's useful to think of one subsuming the other. They are just different (mostly orthogonal?) approaches.
If I had to make them comparable, I might say something like "PE statically specializes programs based on a fixed part of the input, and SAC dynamically specializes a computation based on the prior input".
The important thing to note about SAC specializing a computation is that, after a change occurs, the computation itself is updated to reflect this (via a mechanism I mentioned above, called "change propagation"). This is in contrast to PE, where the specialization only occurs once, up front. Hence, SAC is more "dynamic"/"online" (like FRP), whereas PE is (usually?) more of a offline process. (Perhaps someone that knows more about run-time specialization of code can extend this comparison to PE when it occurs at run-time.)
