7
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ At the risk of missing the point, I'd say that these are four totally different things. Possibly five, if you throw incremental computing into the mix. $\endgroup$ – Dave Clarke Dec 6 '11 at 13:09
  • $\begingroup$ I'd also add staged computation to the mix! $\endgroup$ – CMCDragonkai Jul 26 '16 at 17:34
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good to see you here, Jake! I vaguely remember learning that about froc, but it's good to see a reminder/correction. $\endgroup$ – Rob Simmons Dec 7 '11 at 21:26
9
$\begingroup$

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:

  • Functional reactive programming - consider this when you want to write a program as if you're taking, as input, list of all the user events that's ever happened, but you still want the program to behave reasonably as you feed it inputs over time. An underlying assumption is therefore that the data about past events won't change, and that the only changes to the input will be the addition of new events that happened after all the old events.
  • Partial evaluation - consider this when your program neatly cleaves into two parts, and you want to recompute, over and over, part 2 based on the outcome of part 1. This assumes your code has the property that the difference between "part 1" and "part 2" are known when you write the code, so an underlying assumption is that the data that stays the same (the data part 1 computes with) and the data that changes (the data part 2 computes with) are known in advance.
  • Self-adjusting computation - consider this when your program's execution flow is not neatly divided into parts, but involves a lot of decisions based on data. Self-adjusting computation is designed to react to small changes in inputs by only redoing computation that was based on modified data. Therefore, an underlying assumption is that the particular changes can't be anticipated in advance.

[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.

$\endgroup$
7
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.