papers on adaptive computations?

[fradav]

Hi,

It is a very intersting paradigm. Any bibliographic references on this type of computation (for example versus FRP) ?

Regards,

[fradav]

Found it.

@article{acar2006adaptive,
  title={Adaptive functional programming},
  author={Acar, Umut A and Blelloch, Guy E and Harper, Robert},
  journal={ACM Transactions on Programming Languages and Systems (TOPLAS)},
  volume={28},
  number={6},
  pages={990--1034},
  year={2006},
  publisher={ACM New York, NY, USA}
}

[haraldsteinlechner]

There is much more. Incremental computation as such has a long history. There is a overview in A categorized bibliography on incremental computation. Acar et al. 's Adaptive Functional Programming spawned a new stream of research, they later called self-adjusting-computation. As shown by Acar et al. self-adjusting-computation can be implemented as a library based on combinators. While the combinators track dependencies, a change-propagation mechanism takes care of making all outputs consistent given modified inputs (as a batch operation). Carlsson's paper Monads for incremental computing showed a lightweight DSL for adaptive computation and is similar to adaptive computation expression builders in FSharp.Data.Adaptive.

FSharp.Data.Adaptive had an earlier life in the context of the aardvark rendering engine. Incremental optimization techniques such as Lazy Incremental Compuation for Efficient Scene Graph Rendering used Hudson's lazy graph update algorithm which utilizes an explicit marking phase, which is different from Acar's push based change propagation algorithm. Eager out-of-date marking paired with lazy re-compuation turned out to be very useful for rendering applications (e.g. here). Interestingly and luckily Hammer et al. took this path from computer languages side in Adapton which also has lazy semantics and showed manifold uses, for example also incremental spreadsheets with support for sharing, swapping and switching computations.

By far this is not all, important related work from FRP side is missing here. Maybe others can comment on this as well.

[dsyme]

@haraldsteinlechner if it's ok I'll include that section you've written in the documentation.

[haraldsteinlechner]

Sure. Just updated the text a bit. I will come back to this issue when new papers pop up in that field.