Home

The Art of the Propagator

The Art of the Propagator, Alexey Radul and Gerald Jay Sussman.

We develop a programming model built on the idea that the basic computational elements are autonomous machines interconnected by shared cells through which they communicate. Each machine continuously examines the cells it is interested in, and adds information to some based on deductions it can make from information from the others. This model makes it easy to smoothly combine expression-oriented and constraint-based programming; it also easily accommodates implicit incremental distributed search in ordinary programs. This work builds on the original research of Guy Lewis Steele Jr. and was developed more recently with the help of Chris Hanson.

I just ran across this tech report. I haven't read it yet, but the subject is particularly well-timed for me, since I just finished a correctness proof for a simple FRP system implemented via imperative dataflow graphs, and so constraint propagation has been much on my mind recently. It's pretty clear that constraint propagation can do things that FRP doesn't, but it's not so clear to me whether this is a case of "more expressiveness" or "more fragile abstractions".

By neelk at 2009-03-24 23:47 | DSL | Implementation | Paradigms | other blogs | 22662 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Looks very interesting! (And

Looks very interesting!

(And to help socialization, here's a riddle: What does the title allude to? Please, if the answer is totally obvious refrain from answering!)

By Ehud Lamm at Tue, 2009-03-24 23:54 | login or register to post comments

Reference to

A certain book, but not the one about delusion ;)

By vladsharp at Wed, 2009-03-25 00:44 | login or register to post comments

Hmm...

I'd say it's totally obvious, but I wonder if we're thinking of the same thing? ;)

By Matt Hellige at Wed, 2009-03-25 01:43 | login or register to post comments

AIM-453?

I'd guess it's AIM-453. Although Vlad's comment has me wondering if there's something else I'm missing.

By Allan McInnes at Wed, 2009-03-25 01:57 | login or register to post comments

Given the authors I think

Given the authors (and the name mentioned in the abstract) I think you are correct. Though, I get a whiff of that book in there as well, but that may be accidental (keep in mind that I only read the abstract).

By Ehud Lamm at Wed, 2009-03-25 05:36 | login or register to post comments

link

For reference: AIM-453

By Dave Herman at Wed, 2009-03-25 12:33 | login or register to post comments

Where is the constraint community?

This paper is very strange. It overlooks almost three decades of work by the constraint community. This work goes far beyond the original work by Steele in 1980. Constraint systems with good properties have been developed for many domains using many sophisticated algorithms for the propagators. Concurrency for propagators is well-understood, as is confluence, two properties that are not tackled at all by this paper.

By Peter Van Roy at Wed, 2009-03-25 12:00 | login or register to post comments

Can you recommend a good survey paper?

Could you recommend a good survey paper that's more modern, then? I'm particularly interested in implementation techniques.

By neelk at Wed, 2009-03-25 14:52 | login or register to post comments

Confluence?

What's confluence? Is it when two propagators feed into the same node, and have to provide the same value? Because Radul did address that when he presented the paper at ILC09. However, unless I missed something (quite possible), he didn't seem to provide much detail on how to address it efficiently—I think he just talked about having the source nodes guess, and keep track of what guesses failed.

By John Stracke at Fri, 2009-03-27 19:54 | login or register to post comments

Confluence

A term rewriting system is confluent if the order of rewrites doesn't affect the final result. The Church-Rosser theorem of the lambda calculus is the LTU-relevant version of confluence. The analagous property of these propagation systems is obviously interesting: do you always get the same answer regardless of the order in which fire the various propagators? (Obviously it depends on the details of what sort of propagation you allow.)

By Tom Duff at Fri, 2009-03-27 20:35 | login or register to post comments

Got it, thanks.

Got it, thanks.

By John Stracke at Mon, 2009-03-30 17:42 | login or register to post comments

Relationship with the community.

I asked one of the authors of the paper to comment on this objection. It is true that Sussman and company are not that good at keeping up with related work. However, I don't think they are blindly replicating what other people have done. They have a very different focus than much of what I have seen in the constraint programming community -- they are language designers first and foremost, so they are investigating the idea of propagators as a foundation for language design. Most people investigating constraint systems seem to envision them subordinate to the language -- their software ends up as libraries used by other languages.

Or, as one of the authors said: this paper is meant to follow the path blazed by of "The Art of the Interpreter." When that paper was written, it wasn't as if people hadn't researched and built plenty of interpreters already. They were hardly claiming they had "discovered" the idea of an interpreter. But they were trying to take all the other work that people had done and discover in it its essence, to boil down the essential "art" behind all the other designs.

It is also key to note that this is "art of the propagator," not "art of the constraint system." They are starting with the idea "we want to program with propagators," and asking "so what happens next?" The answer might be "you get a constraint system," and so they investigate constraint systems, and touch on related work from the constraint programming community. But unlike that community, they don't see constraints as their principle object of study. Their focus is different.

By rfrankel at Mon, 2009-04-06 13:11 | login or register to post comments

The MIT technical report which proceeds the thesis

touches upon previous work. It is a well-written document, which comes with exemplary source code. Even though I am still slowly digesting it, I can already highly recommend it: MIT CSAIL Technical Report 2009-053.

By namin at Sat, 2010-10-23 07:17 | login or register to post comments

Revised Report

Alexey Radul and Gerry Sussman did some more work since his thesis,
producing an actually usable experimental platform. Look in:

http://groups.csail.mit.edu/mac/users/gjs/propagators/

for documentation.

The complete system is available in

http://groups.csail.mit.edu/mac/users/gjs/propagators/propagator.tar

By namin at Mon, 2010-10-25 06:59 | login or register to post comments

Constraint Propagation: Models, Techniques, Implementation

The best survey I know of is the recent Ph.D. dissertation of Guido Tack, which explains both theory and implementation and gives many insights: Constraint Propagation: Models, Techniques, Implementation (Jan. 2009). It explains the issues around concurrency and confluence and much more. It gives the foundation of the state-of-the-art Gecode constraint solving library. There are other good books, by Marriott and Stuckey (1998) and Krzysztof Apt (2003) in particular, but they are less up-to-date.

By Peter Van Roy at Wed, 2009-03-25 19:10 | login or register to post comments

Thanks

Excellent, I've been looking for something like this as well.

By Neil Toronto at Fri, 2009-03-27 19:28 | login or register to post comments

Yes, thanks!

Thanks for the link.

By neelk at Fri, 2009-03-27 19:37 | login or register to post comments