[<<][staapl][>>][..]Mon Aug 31 15:50:06 CEST 2009

Exploration ----------- In good in-house tradition, I'm going to try to re-invent it before I look up the implementation again in SICP[?] or Steele's Thesis[?]. The idea is the following: constraint networks are multi-way functions built up from primitive constraints. You can do the following: * compose networks * assert inputs / receive satisfiability errors * query outputs / receive un-asserted errors The tricky part is going to be to stage the control flow into a predictable real-time C-program, but first let's write a dynamic version and see where local algorithms fail. Start with 2 primitive constraints (possibly the only ones I will need). a + b + c = 0 a * b * c = 1 To make constraint satisfaction into a local algorithm, a rule needs to be an active element: when receiving an assertion it needs to: - propagate it if possible - store it if no propagation is possible - raise an error if there is a conflict In general, a rule is an ordered / named list of nodes, and a governor that implements the behaviour above. Nodes in a rule can be asserted or floating. Let's represent asserted nodes by a number and non-asserted ones by #f. A rule -> node link needs to be bidirectional to propagate values through the network. For this a `slot' structure can be used, referring to a rule and an index (all rules have position-encoded nodes). Control Flow ------------ - a node is asserted, propagating a signal to its associated rules. - a rule is asserted: - underdetermined: stop - determined: propagate - overdetermined: error Remarks ------- Q: Find out why this can't solve sets of equations. (or can it? what's the relation with triangulation?) A: One answer is that it's possible to have N inputs and M equations, which will give a propagation when there are N-M inputs defined. OK. Control flow seems to work. Now, what can we actually do with this? * Adding linear functionals is a trivial extension. Adding general M x N systems requires some more code-gen magic to turn the equations into directed equations, but doesn't add any significant other difficulties. * In general, adding a particular N nodes, M<N equations feature is straightforward as long as ``directionalizing'' the equations into functions is possible. * If the inputs and outputs are known, it reduces to a static I->O DFL program. So, I wonder.. What value does this add? - it abstracts control flow (directionalizing equations + sequencing) What about the following form: - set of equalities - set of inequalities + actions Abstract Interpretation ----------------------- Let's try to capture the static part using abstract interpretation. Essentially, turn the current implementation into a staged macro implementation. An interesting point: can you stage `amb'? An interesting property of directional constraints is that you don't need to make choices before you do tests. In discrete constraint satisfaction problems you do need to do that. Maybe I can make a combination of both? Continuous and discrete constraints, and use a staged `amb' to compile it. So what you do in the abstract evaluation is working with the _availability_ of parameters. Then you can serialize the control flow and cast it in stone, leaving the _values_ of the parameters unspecified. This means that DFL probably becomes a special case of constraint programming. Let's call it ``staged constraint programming''. Or ``staged prolog''. So.. What is the abstract version of a constraint? It's really simple: a constraint propagator. So, in the staged/ae version there are really only 2 problems: - constraint propagation based on availability, resulting in a sequential program. - constraint -> function conversion based on the sequencing (constraint directionalization) This pattern is quite neat: starting with an exotic control flow paradigm, fixing control flow through staging, which then allows binding optimizations (storage) and compile-time evaluation.

[Reply][About]

[<<][staapl][>>][..]