Reordering continuations (was :Type inference inside exceptions ?)

[Diego Olivier FERNANDEZ PONS <diego.fernandez_pons@etu.upmc.fr>]

Quoting Pietro Abate <Pietro.Abate@anu.edu.au>:

>> Reordering the continuations to continue the computation in an other
>> branch than the deepest try ... fail is a classical technique in
>> combinatorial optimization. The way you order your continuations
>> defines a "node ordering strategy", most usual being :
>> - stack -> depth first search
>> - queue -> limited discrepancy search
>> - priority queue -> best first search
>
> Can you give some pointer about this technique ... I guess I've already
> seen/used it, but maybe in disguise... is this related with delimited
> continuations and some kind of lookahead technique to detect failures
> and backtrack ?

This topic is shared by a lot of domains including combinatorial
optimization [linear (integer) programming, constraint programming,
dedicated algorithms], automatic theorem proving [SAT and related],
incremental computation [self-adjusting algorithms], functional
programming, data structures, etc.

I will divide my answer in several parts :
1. Relation with (limited) continuations
2. Reordering continuations
3. Implementing reversibility : copying vs trailing


1. Relation with (limited) continuations

Basically, you did a computation (e.g. computed some shortest path),
where you used the fact that x = 2 and you want to go back to a previous
state where x != 2 because :
- not knowing the value of x, you did the hypothesis x = 2 and now
want to try its negation [implicit enumeration algorithms]
- the data of you program changed and now x = 3 [self adjusting
algorithms]
- any other reason (e.g. debugging)

In combinatorial optimization, we call this REVERSIBILITY (talk about  
its links with persistence later).

Unlike (delimited) continuations, you don't need to go back to any
possible previous state but only to specific points. These points are
named CHOICE POINTS and can only be placed on some "events" which is
the minimum granularity of your backtracking algorithm.

This is similar to the Caml debugger (events and jumps).

Programming languages for combinatorial optimization integrate some
facilities to declare choice points (in other words continuation
"holes") and provide a set of possible events on
DECISION VARIABLES (typically when the domain of the variable changes).
All this is then translated by the underlying algorithm to a low-level
implementation that can use several techniques (call/cc, exceptions,
persistence, reified continuations, etc.)

Example: OPL (The Optimization Programming Language, Pascal van Hentenryck
MIT Press 1996) introduces two constructions [dvar] and [try] that
allows you to write (simplified syntax)

dvar x [0..3]  // possible events
dvar y [0..3]  // possible events

subject to

     x + y == 2

search

     forall v in x, try (x == v) // continuation holes

Compare this with a much more complex continuation framework
integrated to a general purpose language like

R. Kent Dybvig, Simon Peyton Jones, and Amr Sabry:
A Monadic Framework for Delimited Continuations

I can now answer to the first question

> is this related with delimited continuations

Yes but I would say that we use these techniques (continuations,
persistent data structures, backtracking monads, exceptions) more
than contribute to their study.

2. Reordering continuations

In an implicit enumeration algorithm, all the possible continuations
have to be visited (that is the "enumeration" part of the name) but
some orders may be better than others because one accumulates
information while visiting the continuations and this allow the
algorithm to prove that visiting some continuations is useless (that
is the "implicit" part of the name).

Usually you have for an optimization problem:
- a global lower and upper bound (that improves while the algorithm
runs)
- local lower and upper bounds (that depend on your position in the
tree, in other words the sequence of decision that have been take to
arrive to that point e.g. x1 == 0, x2 == 3, y3 == 0, all other
unknown).

If you are minimizing, and the local lower bound is already higher
than the global upper bound, you can prune all the branch. All those
continuations won't be visited.

There are tons of search strategies according to the type of problem
you are solving. They all combine
- a variable ordering (this gives the shape to the tree)
- a node ordering (this says how the nodes are visited)

As I said before, the most usual node orderings are depth first,
limited discrepancy and best-first. You will find a good entering
point with the original LDS paper (on the web)

William D. Harvey, Matthew L. Ginsberg
Limited Discrepancy Search (IJCAI 1995)

> Is this related to [...] some kind of lookahead technique to detect  
> failures and backtrack ?

I would not call that lookahead but rather using statistical  
correlation between the data and the position in the tree of the  
optimal solution to find it soon.

3. Implementing reversibility

There are two classical ways to implement reversibility in
combinatorial optimization engines : copy and trailing

A copy engine just maintains a copy of the decision variables for all
opened nodes. When you jump from a node to another, you just have to
select the correct version.

In functional languages, the simplest implementation is combining
recursive calls (and exceptions) with persistent data structures.

Example : Alain Frish's sudoku solver

But some engines written in imperative languages also work that way

Example : Gecode in C++ (Alice is its SML frontend).

In the trailing technique, there is a single state (current state)
that has to be synchronized every time the "focus" is moved in the
search tree. Usually this leads to stamped version arrays data
structures, that save all the local differences in a TRAIL.

Within trailing engines, the state your program would have in another node is
distributed in the central memory. To jump to another node you have to
"replay" the paths in the search tree: you physically undo the
modifications until the lowest common ancestor between the current
node and the desired node and you do again all the "forward" decisions
needed to reach the node.

An example of trailing engine in a functional language is FaCiLe
(Pascal Brisset et Nicolas Barnier, Caml).

An example of trailing for self-adjusting algorithms is given by

Umut A. Acar, Guy E. Blelloch, Matthias Blume, Kanat Tangwongsan.
An Experimental Analysis of Self-Adjusting Computation (PLDI 2006)

The original LDS paper is written supposing that the underlying engine
uses trailing to implement reversibility.

There is also something named "semantic backtracking". To keep it
short, instead of physically restoring the state, you restore it
logically, in other words you change your current state in order to be
semantically equivalent to the state you want to reach.
Imagine a fixed-size queue implemented by an array with a first and
last pointer. Then any "translated" array is semantically equivalent,
so instead of physically restoring the queue you had, you can put the
elements back in a "forward" way.

Pascal Van Hentenryck and Viswanath Ramachandran
Backtracking without trailing in CLP (R) (TOPLAS 1995)

         Diego Olivier