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

Mon Aug 31 15:50:06 CEST 2009

Constraint Programming

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][>>][..]