20170620
Information about propagators and propagator accessories
This document is not intended as an introduction to propagators. Rather it's a collection of resources. As a minimal introduction: a propagator is a monotone function between join-semilattices. We intend to build networks of cells which contain values drawn from join-semilattices, connected by propagators, which read from and write to some cells. These networks have very useful properties for concurrent and distributed programming, among many other things.
Talks by Edward Kmett are probably the most up-to-date information available on propagators.
Note that these two are very similar, but each has some info or explanations that the other hasn't:
- Lambda Jam 2016: https://www.youtube.com/watch?v=acZkF6Q2XKs
- YOW West 2016: https://www.youtube.com/watch?v=ctT425sPAm4
This talk can be considered the "hard mode" version of the above two:
- Boston Haskell 2016: https://www.youtube.com/watch?v=DyPzPeOPgUE
As far as I know, these repos each contain tricks and tools related to propagators, but none of them are the final form of Ed's ideas.
- https://github.com/ekmett/propagators
- https://github.com/ekmett/concurrent
- https://github.com/ekmett/models
Alexey Radul and Gerald Sussman at MIT did earlier work on propagators. The Scheme programming language was used.
- Paper "The Art of the Propagator": http://web.mit.edu/~axch/www/art.pdf
- Radul's PhD thesis: http://web.mit.edu/~axch/www/phd-thesis.pdf
There does not exist a book on propagators. This book is considered by Ed to be a good introduction to lattices:
- Introduction to Lattices and Order: https://www.amazon.com/Introduction-Lattices-Order-B-Davey/dp/0521784514/
Datalog looks like a propagator network. In the propagator vocabulary, Datalog rules are propagators and Datalog tables are cells. This similarity is not just skin-deep. We should steal lots of stuff from Datalog. In particular, when looking for a scheduling algorithm for our propagators, we want to use something like semi-naive evaluation of Datalog. This involves creating a topological ordering. Since we want to be able to create and remove propagators from the network dynamically, we will need to figure out how to efficiently maintain a topological ordering. Datalog's stratified negation feature can be adapted to propagators. Effectively this means we can have propagators which write non-monotonically, so long as they do not participate in any cycles. There are other conditions which allow us to relax our constraints in other ways.
- CRDTs
- CALM Conjecture
- Berkeley Orders of Magnitude (BOOM): http://boom.cs.berkeley.edu/
- Assumption-based Truth-management systems