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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id EC5F6BC68 for ; Tue, 17 Oct 2006 14:33:12 +0200 (CEST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k9HCXCXO009809 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Tue, 17 Oct 2006 14:33:12 +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 k9HCXC1K039611 ; Tue, 17 Oct 2006 14:33:12 +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 k9HCX7tW059365 ; Tue, 17 Oct 2006 14:33:12 +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; Tue, 17 Oct 2006 14:33:07 +0200 Message-ID: <20061017143307.iole99sis0ck8s8c@webmail.etu.upmc.fr> Date: Tue, 17 Oct 2006 14:33:07 +0200 From: Diego Olivier FERNANDEZ PONS To: Francisco =?iso-8859-15?b?Sm9z6Q==?= Valverde Albacete Cc: caml-list@inria.fr Subject: Re: [Caml-list] 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> <20061014215653.by7emka3kgscccsc@webmail.etu.upmc.fr> <20061016112515.ircc0o7sgsssowcs@webmail.etu.upmc.fr> In-Reply-To: <20061016112515.ircc0o7sgsssowcs@webmail.etu.upmc.fr> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15; DelSp="Yes"; format="flowed" Content-Disposition: inline Content-Transfer-Encoding: quoted-printable User-Agent: Internet Messaging Program (IMP) H3 (4.1.3) X-Virus-Scanned: ClamAV 0.88.2/2038/Tue Oct 17 00:48:19 2006 on shiva.jussieu.fr X-Virus-Scanned: ClamAV 0.88.4/2038/Tue Oct 17 00:48:19 2006 on courriel3.reseau.jussieu.fr X-Virus-Status: Clean X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-2.0.2 (shiva.jussieu.fr [134.157.0.164]); Tue, 17 Oct 2006 14:33:12 +0200 (CEST) X-Miltered: at concorde with ID 4534CD88.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 4534CD88.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; pons:01 pons:01 reordering:01 inference:01 valverde:01 reordering:01 nodes:01 parsers:01 grammar:01 parsing:01 stack:01 grammar:01 enumeration:01 recursive:01 parser:01 Bonjour, I am not sure I understood all of your comments but I can at least answer to a few of them [Francisco Valverde a =E9crit] > It is also the technique to find alternative recognition hypotheses =20 > in most speech recognizers (hypothesis graph search with dynamical =20 > reordering & pruning of nodes & backtrack, in a nutshell). Parsers and combinatorial optimization engines are equivalent in the sense that for every combinatorial problem you can find a grammar and a string which solutions are the solutions of the combinatorial problem (think of Prolog) and reciprocally under some reasonable hypothesis. This is true for anything that gets close to NP-completeness but in this case both problems are really closely related. Parsing Techniques explain how to compile a non-deterministic stack automato= n (e.g. an LR grammar with conflicts, an ambiguous grammar) to an exception based implicit enumeration algorithm (i.e. a recursive =20 ascent parser implemented with a set of recursive functions). Parsing Techniques - A Practical Guide Dick Grune and Ceriel J.H. Jacobs (1990) on the web A few years ago I put on my web page a few toy LR parser written in that way and an Early parser (in which continuations reified to lists are executed in a breath-first-search way and is some sense memoized). There are working parsers that use this technique, including - Frown, an LALR(k) parser generator for Haskell Ralf Hinze, Ross Paterson - The Essence parser generator for Scheme Mike Sperber (uses partial evaluation instead of code generation) Both come with interesting papers. The general idea is that the definition of the search space (construction of a stack automaton) and its exploration (optimistic -> depth first search =3D LR, pessimistic -> breath first search =3D Earley) are two orthogonal things. The Tomita parsers are a bit more difficult since they are equivalent to a form of memoization inside an implicit enumeration algorithm (or conversely a form of duplication at ambiguous points inside a deterministic algorithm). Speech recognition is a more complicated because of uncertainty but it =20 is the same idea. > Explicit management of the continuation queue/stack/whatever is a > boon I didn't expect, though! If you come up with a library or =20 > modular solution please let me know. It is rather specific to constraint programming but there is a paper that describes a system that allows you to specify in a declarative way the order in which the continuations will be executed. The trick is to lift the combinatorial engine to the search tree: the execution order of the continuations is itself a combinatorial program (I believe they do not bootstrap the solver however but use an ad-hoc mini-solver instead). ToOLS: A Library for Partial and Hybrid Search Methods (2003) Simon de Givry, Laurent Jeannin Proceedings CPAIOR '03 (on Citeseer) It is only applicable when the continuations are restricted enough to carry a clear semantics. If you are looking for more low-level things you should have a look to Oleg's work, and related papers. Native delimited continuations in (byte-code) OCaml http://okmij.org/ftp/Computation/Continuations.html#caml-shift > I'm looking forward to hearing more about your research, as always. Well I can at least explain what I have been trying to do ultimately with continuations and memoization. Pisinger introduced a very fast class of algorithms for knapsack problems which are an hybridisation of implicit enumeration (branch and bound) and dynamic programming. Knapsack Problems Hans Kellerer, Ulrich Pferschy, David Pisinger Springer 2004 [Good overview : New trends in exact algorithms for the 0-1 knapsack problem. EJOR 123 (2000), on the web] I want to automatically derive similar algorithms from any implicit enumeration algorithms thanks to memoization. There is an additional problem related to combinatorial optimization: computing an average solution (50% of the optimum) takes 1s, a good solution (90%) 1 minute, an excellent solution (99%) 1 hour, the optimal solution 1 day, and the optimality proof 1 week. But you usually don't need the optimal solution to a subproblem, only a good enough "lower bound" that enables you either to cut the branch or to decide to dive in it. - From the memoization point of view, one has to generalize the value table to a improving pair of bounds + continuation stack instead of memo : (int -> int) -> int -> int you need memo : (int -> int * continuation queue) -> (int, int) ref * continuation queue if you want the confidence interval [lower bound..upper bound] of a subproblem to be refined, you just execute a few more continuations. - From the implicit enumeration point of view, one has to order the continuations in a "structured stack" where the continuations are indexed by the sub-problems they are solving, and add a cache. You also need to use the relations between the subproblems: the optimal solution of a more constrained problem is an upper bound of the optimal solution of a less contrained problem. For instance: min cardinality subsetsum 15 [17;13;7;5;2] =3D=3D 2 min cardinality subsetsum 15 [17;15;13;12;11;7;5;2;1] =3D=3D 1 This gives you upper and lower bounds form the keys of the table and the cached partial results. I had the idea when reading papers on adaptive functional programming, specially those of U. Acar (http://ttic.uchicago.edu/~umut/papers/index.html= ) Umut A. Acar, Guy E. Blelloch, Matthias Blume, Kanat Tangwongsan. An Experimental Analysis of Self-Adjusting Computation (PLDI 2006) Diego Olivier