4 ms·

Adapton: Programming Language Abstractions for Incremental Computation

106 points by jxub 8y ago

amelius 8y ago
I know there has been some research in this area over the decades, but I'm wondering: how practical is this approach nowadays?
- ishitatsuyuki 8y ago
  Adapton's idea is based on self-adjusting computation [1], which is considered pretty mature [2]. In the field there are also approaches like incremental lambda calculus [3] and differential dataflow [4]. Both of them focuses on propagating differences (changes) instead of invalidating dirty nodes in a dependency graph. [1] https://www.semanticscholar.org/paper/Self-adjusting-computation%3A-(an-overview)-Acar/be94c5051438209816397be214ee8c1bdda94165 https://www.semanticscholar.org/paper/Self-adjusting-computa... [2] https://web.archive.org/web/20170628103354/lambda-the-ultimate.org/node/5115 https://web.archive.org/web/20170628103354/lambda-the-ultima... [3] https://www.semanticscholar.org/paper/A-theory-of-changes-for-higher-order-languages%3A-by-Cai-Giarrusso/2b844dfb491ad5b7e3eba6d81f0eda2de2bc118c https://www.semanticscholar.org/paper/A-theory-of-changes-fo... [4] https://www.semanticscholar.org/paper/Differential-Dataflow-McSherry-Murray/f5df61effe8047eb9ea1702cfcc268dbba678567 https://www.semanticscholar.org/paper/Differential-Dataflow-...
- chubot 8y ago
  From what I can tell, incremental computation is starting to be used in practice: Jane St has an OCaml library called Incremental: "Data Driven UIs, Incrementally" by Yaron Minsky at Strange Loop 2018: https://www.youtube.com/watch?v=R3xX37RGJKE https://www.youtube.com/watch?v=R3xX37RGJKE This talk has a pretty impressive live JS table demo! It looks faster and nicer than most JS UIs I've seen. ----- And the Skip language was developed Facebook. Apparently they started to use it for some production stuff, but somehow they decided against it and spun it out: http://skiplang.com/ http://skiplang.com/ https://news.ycombinator.com/item?id=18077612 https://news.ycombinator.com/item?id=18077612 Julien Verlaguet - Reflex: Reactive Programming at Facebook -- https://www.youtube.com/watch?v=AGkSHE15BSs https://www.youtube.com/watch?v=AGkSHE15BSs Reflex was an earlier name or earlier incarnation of Skip.
- bcherny 8y ago
  I’m not sure how practical this kind of generalized approach is, but notice how incremental computation is already all around you: in your build system, in the way React recomputes its tree and your browser recomputes layout, in any pull-based protocol where the server keeps state.
  - EvilTerran 8y ago
    In spreadsheets, too!
- thelastbender12 8y ago
  Didn't yet go through the work posted, though at multiple investment banks the pricing/risk engines make use of _compute graphs_ which have a similar execution style. Only recompute nodes that get invalidated on change in input data and propagate till the output.
nixpulvis 8y ago
I've been aware of this kind of thing before, but never really looked into it. This is pretty interesting, and the Rust docs are pretty good at stepping through it. Rust specifically can have difficulty with cyclic data, and it seems this could help with that, though it's bypassing the lifetime analysis of the type system. Two thoughts of the top of my head (I haven't yet read any of the literature): 1) how is/could rust's lifetime analysis be applied to these ideas productively. 2) I wonder if you could map some predefined _names_, or something inside the system to physical caches or hardware structures.
nurettin 8y ago
How is this any different than plain old memoization?
- gnulinux 8y ago
  Memoization is one specific strategy to implement an incremental algorithm. E.g. ML style on input 1 train and predict, on input N only predict wouldn't be memoization, but it'd be incremental (in most cases, i.e. when training is more computationally intensive than prediction). In other words, memoization is a subset of incremental computation.
kibwen 8y ago
Neat, I didn't know that the new reference implementation was in Rust. It's interesting because the Rust compiler developers are themselves writing a framework for incremental computation, inspired by Adapton, for use in the compiler itself: https://github.com/nikomatsakis/salsa https://github.com/nikomatsakis/salsa (note: WIP)
aldanor 8y ago
Somewhat related and also Rust - I’ve recently put together a crate for frp-like computation (in terms of streams and all that, but the use case is somewhat close to adapton, although simpler), for my own use but then figured I’d share it because why not - https://github.com/aldanor/reactive-rs https://github.com/aldanor/reactive-rs

106 points by jxub 8y ago

I know there has been some research in this area over the decades, but I'm wondering: how practical is this approach nowadays?

ishitatsuyuki 8y ago
Adapton's idea is based on self-adjusting computation [1], which is considered pretty mature [2]. In the field there are also approaches like incremental lambda calculus [3] and differential dataflow [4]. Both of them focuses on propagating differences (changes) instead of invalidating dirty nodes in a dependency graph. [1] https://www.semanticscholar.org/paper/Self-adjusting-computation%3A-(an-overview)-Acar/be94c5051438209816397be214ee8c1bdda94165 https://www.semanticscholar.org/paper/Self-adjusting-computa... [2] https://web.archive.org/web/20170628103354/lambda-the-ultimate.org/node/5115 https://web.archive.org/web/20170628103354/lambda-the-ultima... [3] https://www.semanticscholar.org/paper/A-theory-of-changes-for-higher-order-languages%3A-by-Cai-Giarrusso/2b844dfb491ad5b7e3eba6d81f0eda2de2bc118c https://www.semanticscholar.org/paper/A-theory-of-changes-fo... [4] https://www.semanticscholar.org/paper/Differential-Dataflow-McSherry-Murray/f5df61effe8047eb9ea1702cfcc268dbba678567 https://www.semanticscholar.org/paper/Differential-Dataflow-...
chubot 8y ago
From what I can tell, incremental computation is starting to be used in practice: Jane St has an OCaml library called Incremental: "Data Driven UIs, Incrementally" by Yaron Minsky at Strange Loop 2018: https://www.youtube.com/watch?v=R3xX37RGJKE https://www.youtube.com/watch?v=R3xX37RGJKE This talk has a pretty impressive live JS table demo! It looks faster and nicer than most JS UIs I've seen. ----- And the Skip language was developed Facebook. Apparently they started to use it for some production stuff, but somehow they decided against it and spun it out: http://skiplang.com/ http://skiplang.com/ https://news.ycombinator.com/item?id=18077612 https://news.ycombinator.com/item?id=18077612 Julien Verlaguet - Reflex: Reactive Programming at Facebook -- https://www.youtube.com/watch?v=AGkSHE15BSs https://www.youtube.com/watch?v=AGkSHE15BSs Reflex was an earlier name or earlier incarnation of Skip.
bcherny 8y ago
I’m not sure how practical this kind of generalized approach is, but notice how incremental computation is already all around you: in your build system, in the way React recomputes its tree and your browser recomputes layout, in any pull-based protocol where the server keeps state.
- EvilTerran 8y ago
  In spreadsheets, too!
thelastbender12 8y ago
Didn't yet go through the work posted, though at multiple investment banks the pricing/risk engines make use of _compute graphs_ which have a similar execution style. Only recompute nodes that get invalidated on change in input data and propagate till the output.

nixpulvis 8y ago

I've been aware of this kind of thing before, but never really looked into it. This is pretty interesting, and the Rust docs are pretty good at stepping through it. Rust specifically can have difficulty with cyclic data, and it seems this could help with that, though it's bypassing the lifetime analysis of the type system. Two thoughts of the top of my head (I haven't yet read any of the literature): 1) how is/could rust's lifetime analysis be applied to these ideas productively. 2) I wonder if you could map some predefined _names_, or something inside the system to physical caches or hardware structures.

nurettin 8y ago

How is this any different than plain old memoization?

gnulinux 8y ago
Memoization is one specific strategy to implement an incremental algorithm. E.g. ML style on input 1 train and predict, on input N only predict wouldn't be memoization, but it'd be incremental (in most cases, i.e. when training is more computationally intensive than prediction). In other words, memoization is a subset of incremental computation.

kibwen 8y ago

Neat, I didn't know that the new reference implementation was in Rust. It's interesting because the Rust compiler developers are themselves writing a framework for incremental computation, inspired by Adapton, for use in the compiler itself: https://github.com/nikomatsakis/salsa https://github.com/nikomatsakis/salsa (note: WIP)

aldanor 8y ago

Somewhat related and also Rust - I’ve recently put together a crate for frp-like computation (in terms of streams and all that, but the use case is somewhat close to adapton, although simpler), for my own use but then figured I’d share it because why not - https://github.com/aldanor/reactive-rs https://github.com/aldanor/reactive-rs