mental / deltared

DeltaRed is a multi-way constraint solving library for Ruby based on the
the DeltaBlue algorithm presented in "Multi-way versus One-way Constraints
in User Interfaces: Experience with the DeltaBlue Algorithm"
by Sannella et al.  (available http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.2131 )

== So What Does It Do?

Constraint solvers, generally, are good for solving problems which fit the
description of "when this value changes, update these other values."  Think
Rake, but for your program's data instead of files.  Rake is actually
a constraint solver itself: when a file is updated, it knows which other
files to update and the how to update them.  Similarly, when a DeltaRed
"variable" changes, DeltaRed knows which other variables to update and
how to update them.

 a, b = DeltaRed.variables(0, 0)
 a.constraint!(b) { |v| v * 2 }

 b.value = 3
 p a.value # => 6
 b.value = 2
 p a.value # => 4

The above constraint is like a Rake rule: it declares that <tt>a.value</tt>
depends on <tt>b.value</tt>.  When <tt>b.value</tt> is set to some value,
DeltaRed knows to update <tt>a.value</tt>, and like Rake, the block attached
to the rule tells it how to do that (in this case, <tt>a.value</tt> is obtained
by multiplying <tt>b.value</tt> -- which DeltaRed helpfully passed to the
block -- by 2).

The same constraint (since it only contains a single formula) can also be
expressed in a more verbose fashion:

 a, b = DeltaRed.variables(0, 0)
 DeltaRed.constraint! do |c|
   c.formula(b => a) { |v| v * 2 }
 end

Now, one difference between Rake and DeltaRed is that Rake is a
<em>one-way</em> constraint solver.  You can tell it how to make one
file given another, but that's it.  DeltaRed is a <em>multi-way</em>
constraint solver, which means that you can go <em>both ways</em>:
imagine writing a Rake rule that not only defined how to produce
an <tt>.o</tt> file from a <tt>.c</tt> file, but also how to recover
a <tt>.c</tt> file from an existing <tt>.o</tt> file.  (Of course,
it'd still be up to you to write the decompiler...)

Here's an example of a similar kind of thing with DeltaRed, taking
advantage of the ability to define multiple formulas relating the
values of the same variables:

 string, number = DeltaRed.variables("0", 0)
 DeltaRed.constraint! do |c|
   c.formula(number => string) { |n| n.to_s }
   c.formula(string => number) { |s| s.to_i }
 end

 string.value = "23"
 p number.value # => 23
 number.value = 7
 p string.value # => "7"

If <tt>string.value</tt> gets set to a different string, DeltaRed will
know to set <tt>number.value</tt> to its integer equivalent, and if
<tt>number.value</tt> is set to a different integer, DeltaRed will
automatically update <tt>string.value</tt>.

One limitation of DeltaRed is that, while bidirectional loops like this
are permitted within a single constraint, loops involving multiple
constraints aren't really supported.  The following version of the above
won't necessarily work as expected:

 string, number = DeltaRed.variables("0", 0)
 string.constraint!(number) { |n| n.to_s }
 number.constraint!(string) { |s| s.to_i }

== Typical Use

=== Edit Constraints

As in most constraint libraries, variables are updated by adding or
removing (enabling or disabling) constraints.  Even when a variable's
value is set via DeltaRed::Variable#value=, DeltaRed creates a
temporary constraint to force the variable to a specific value.  However,
the temporary constraint created by DeltaRed::Variable#value= doesn't
last.  If you want to hold on to an "edit constraint", you can explicitly
create one via DeltaRed::Variable#edit.

 v = DeltaRed.variables(5)
 c = v.edit(10)

Note that at this point the variable's value is still five, since the
edit constraint has not been enabled.  Although it is slightly more
efficient, this snippet is identical in function to:

 v = DeltaRed.variables(5)
 c = v.constraint { 10 }

Using DeltaRed::Variable#constraint! or DeltaRed::Variable#edit!
would have enabled the constraint along with creating it.  To
enable a constraint after creating it, we can call
DeltaRed::Constraint#enable:

 v.value # => 5
 c.enable
 v.value # => 10

Now the variable's value is ten, and since there are no other constraints
determining its value, it retains that value after the edit constraint is
removed.

 c.disable
 v.value # => 10

=== Stay Constraints

Often, when using multi-way constraints, there can be ambiguities
regarding which variable should be updated.  Stay constraints can help
resolve this ambiguity.

 height, top, bottom = DeltaRed.variables(0, 0, 0)
 DeltaRed.constraint! do |c|
   c.formula([top, bottom] => height) { |t, b| b - t }
   c.formula([top, height] => bottom) { |t, h| t + h }
   c.formula([bottom, height] => top) { |b, h| b - h }
 end

If we change height at this point, should top or bottom change?  We
can use a stay constraint to resolve the ambiguity:

 s = top.stay!
 height.value = 100
 s.disable

So, the stay constraint guarantees that, when we change the height,
the top stays in place and the bottom moves:

 top.value # => 0
 bottom.value # => 100

DeltaRed also provides a slightly more Rubyish way of using temporary
stay constraints:

 top.stay! do
   height.value = 100
 end

=== Plans and Volatile Constraints

Enabling or disabling a constraint may involve updating large portions
of the constraint network, so DeltaRed provides an optimization for
updating variables in response to quickly changing inputs.  A constraint
can be declared as volatile, which means that it will only be evaluated
upon explicit request, as part of an optimized update plan.

For example:

 x_pos, y_pos = DeltaRed.variables(0, 0)
 x_pos.constraint!(:volatile => true) { get_mouse_pos()[0] }
 y_pos.constraint!(:volatile => true) { get_mouse_pos()[1] }

At this point, an optimized update plan can be created for these
constraints:

 plan = DeltaRed.plan(x_pos, y_pos)

(DeltaRed.plan can take a list of either volatile constraints, or variables
directly determined those constraints.)  The DeltaRed::Plan#recompute can
then be used to update variable values in response to input:

 plan.recompute
 x_pos.value # => the current mouse x
 y_pos.value # => the current mouse y

Note that the plan remains valid only as long as no constraints are
enabled or disabled on variables which might influence or be influenced
by the constraints for which the plan was computed.

=== Output Constraints

Output constraints can be used to update things external to the constraint
network when variable values change.  Here's an example which updates an
onscreen rectangle in response to changes to the value of variables
describing the rectangle's dimensions:

 def make_range_subgraph
   min, max, delta = DeltaRed.variables(0, 0, 0)
   DeltaRed.constraint! do |c|
     c.formula([min, max] => delta) { |min_v, max_v| max_v - min_v }
     c.formula([min, delta] => max) { |min_v, d| min + d }
     c.formula([max, delta] => min) { |max_v, d| max_v - d }
   end
   [min, max, delta]
 end

 top, bottom, height = make_range_subgraph
 left, right, width = make_range_subgraph

 DeltaRed.output!(top, left, width, height) do |x, y, w, h|
   # pseudocode
   clear_screen
   draw_rect(x, y, w, h)
 end

== An Overview of the Pieces

=== DeltaRed::Constraint

A constraint which establishes relationships between the values of
constraint variables and optionally external input (in the case of
"volatile" constraints).  Constraints can be enabled and disabled via
DeltaRed::Constraint#enable and DeltaRed::Constraint#disable.  Constraints
are typically created via either DeltaRed.constraint or
DeltaRed::Variable#constraint.

An existing constraint can be used as a template for constructing a
new constraint over different variables by calling
DeltaRed::Constraint#substitute with a hash mapping from the old variables
to the new ones.

=== DeltaRed::Constraint::Group

A group of constraints which may be enabled or disabled together.  Most
often a set of constraints will be enabled during editing, and then disabled
again afterwards; constraint groups exist to make this more convenient.
Constraint groups are normally created via DeltaRed.group, which, when given
a block, captures all of the constraints created within the block into
the constraint group that DeltaRed.group returns.

Similarly to individual constraints, constraint groups may also be used as
templates for creating groups of new constraints, via
DeltaRed::Constraint::Group#substitute.

=== DeltaRed::Variable

A variable which receives its value from constraints.  A variable's
current value is accessible via DeltaRed::Variable#value.  Variables are
most typically created via DeltaRed.variables.

=== DeltaRed::Plan

A plan is an optimized means for recomputing variables when external
inputs (via volatile constraints) change.  A plan for updating a set of
volatile constraints can be constructed via DeltaRed.plan; updates can
then be requested via DeltaRed::Plan#recompute.

== Limitations

While a DeltaRed constraint can contain multiple formulae, each outputting
to a different variable, a formula can only output to a single variable,
and only one formula in a constraint may be active at a time.  Similarly,
while a variable may have multiple constraints which can determine its
value, only one of those constraints may be active at a time; constraints
with higher strengths will take precedence over those with lower strengths.

In the parlance of constraint programming, DeltaRed is a multi-way
local-propagation solver supporting hierarchical constraints but neither
cycles nor multiple outputs.

== What about threads?

DeltaRed is perfectly threadsafe as long as threads don't share variables
or constraints directly or indirectly.  That means you're fine as long as
different threads' variables or constraints don't get connected to each
other by intermediate constraints.  Beyond that, any kind of sharing
will require external synchronization.