From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 36B24BC69 for ; Sat, 14 Oct 2006 21:57:14 +0200 (CEST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id k9EJvDXj011682 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Sat, 14 Oct 2006 21:57:14 +0200 Received: from courriel.upmc.fr (courriel3.reseau.jussieu.fr [134.157.0.194]) by shiva.jussieu.fr (8.13.7/jtpda-5.4) with ESMTP id k9EJusri092679 ; Sat, 14 Oct 2006 21:56:54 +0200 (CEST) X-Ids: 164 Received: from etu.upmc.fr (localhost [127.0.0.1]) by courriel.upmc.fr (8.13.6/jtpda-5.4) with ESMTP id k9EJurVC036816 ; Sat, 14 Oct 2006 21:56:54 +0200 (CEST) Received: from out-of.ilog.fr (out-of.ilog.fr [81.80.159.49]) by webmail.etu.upmc.fr (Horde MIME library) with HTTP; Sat, 14 Oct 2006 21:56:53 +0200 Message-ID: <20061014215653.by7emka3kgscccsc@webmail.etu.upmc.fr> Date: Sat, 14 Oct 2006 21:56:53 +0200 From: Diego Olivier FERNANDEZ PONS To: Pietro Abate Cc: caml-list@inria.fr Subject: Reordering continuations (was :Type inference inside exceptions ?) References: <20061006201647.1a88vj0tkockc4k8@webmail.etu.upmc.fr> <452D753E.1020607@glondu.net> <20061013142317.z70cu8q30g40gckc@webmail.etu.upmc.fr> <20061013124223.GA30832@pulp.rsise.anu.edu.au> In-Reply-To: <20061013124223.GA30832@pulp.rsise.anu.edu.au> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; DelSp="Yes"; format="flowed" Content-Disposition: inline Content-Transfer-Encoding: quoted-printable User-Agent: Internet Messaging Program (IMP) H3 (4.1.3) X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-2.0.2 (shiva.jussieu.fr [134.157.0.164]); Sat, 14 Oct 2006 21:56:54 +0200 (CEST) X-Virus-Scanned: ClamAV 0.88.2/2031/Sat Oct 14 15:21:16 2006 on shiva.jussieu.fr X-Virus-Status: Clean X-Miltered: at discorde with ID 45314119.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 45314106.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; pons:01 pons:01 reordering:01 inference:01 reordering:01 defines:01 node:01 stack:01 discrepancy:01 pointer:01 delimited:01 computed:01 enumeration:01 debugging:01 delimited:01 Quoting Pietro Abate : >> 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 =3D 2 and you want to go back to a previous state where x !=3D 2 because : - not knowing the value of x, you did the hypothesis x =3D 2 and now want to try its negation [implicit enumeration algorithms] - the data of you program changed and now x =3D 3 [self adjusting algorithms] - any other reason (e.g. debugging) In combinatorial optimization, we call this REVERSIBILITY (talk about =20 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 =3D=3D 2 search forall v in x, try (x =3D=3D 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 =3D=3D 0, x2 =3D=3D 3, y3 =3D=3D 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 =20 > failures and backtrack ? I would not call that lookahead but rather using statistical =20 correlation between the data and the position in the tree of the =20 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 i= s 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