Type inference inside exceptions ?
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20061014 (19:57) 
From:  Diego Olivier FERNANDEZ PONS <diego.fernandez_pons@e...> 
Subject:  Reordering continuations (was :Type inference inside exceptions ?) 
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 [selfadjusting 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 lowlevel 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 bestfirst. 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 selfadjusting algorithms is given by Umut A. Acar, Guy E. Blelloch, Matthias Blume, Kanat Tangwongsan. An Experimental Analysis of SelfAdjusting 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 fixedsize 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