Type inference inside exceptions ?

Type inference inside exceptions ?

[Diego Olivier FERNANDEZ PONS]

     Bonjour,

I would like the type-checker to infer the type inside exceptions (or  
at least to help me in the "guess a type and test" loop).

More specifically, here is my problem:

I have a program that computes the optimal solution of the minimal  
cardinality subset-sum problem with multiplicities. In simple words it  
gives the minimum number of coins you need to reach a given amount of  
money.

val smc : int -> int list -> int list list * int = <fun>
# smc 226 [198; 122; 90; 75; 64; 54; 53; 10; 5; 1];;
- : int list list * int =
([[75; 75; 75; 1]; [122; 64; 10; 10; 10; 10]; [198; 10; 10; 5; 1; 1; 1]],
  198105)

The programs gives all the solutions it found, the last one being the  
optimal (with the total number of backtracks). The best solution is  
kept by side-effects on a global variable.

type environment = {
     mutable solutions : int list list;
     mutable backtracks : int;
     mutable card : int
   }

exception Fail

let rec min_card env = fun to_reach chosen candidates ->
   if (to_reach = 0) then
     match compare env.card (List.length chosen) with
       | n when n <= 0 ->
	  env.backtracks <- env.backtracks + 1;
	  raise Fail
       | _ ->
	  env.solutions <- chosen :: env.solutions;
	  env.card <- List.length chosen;
	  raise Fail
   else
     match candidates with
       | [] ->
	  env.backtracks <- env.backtracks + 1;
	  raise Fail
       | x :: tail when x > to_reach -> min_card env to_reach chosen tail
       | x :: tail ->
	  try
	    min_card env (to_reach - x) (x :: chosen) candidates
	  with Fail ->
	    min_card env to_reach chosen tail

let rec smc = fun to_reach list ->
   let env = { solutions = []; backtracks = 0; card = max_int } in
     try
       min_card env to_reach [] (List.sort (fun x y -> compare y x) list)
   with Fail -> (List.map List.rev env.solutions, env.backtracks)

Now I want the program not to return all the solutions but only the  
first solution it found and a list of continuations that I can launch  
again if a better solution is required.

Therefore I add a second exception
type continuation = ...
exception Solution of int * continuation list

And I collect the continuations from the try ... catch when the left  
tree happens to contain a solution

try
    explore left subtree
with
   | Fail -> explore right subtree
   | Solution (s, cont) ->
     let c = function () -> explore right subtree in
       raise Solution (s, c :: cont)

Not knowing the type of the continuation, I just tried unit -> int

Here is the detailed code

type continuation = unit -> int
exception Solution of int * continuation list

let rec min_card env = fun to_reach chosen candidates ->
   if (to_reach = 0) then
     match compare env.card (List.length chosen) with
       | n when n <= 0 ->
	  env.backtracks <- env.backtracks + 1;
	  raise Fail
       | _ ->
	  env.solutions <- chosen :: env.solutions;
	  env.card <- List.length chosen;
	  raise (Solution (List.length chosen, []))
   else
     match candidates with
       | [] ->
	  env.backtracks <- env.backtracks + 1;
	  raise Fail
       | x :: tail when x > to_reach -> min_card env to_reach chosen tail
       | x :: tail ->
	  try
	    min_card env (to_reach - x) (x :: chosen) candidates
	  with
	    | Fail -> min_card env to_reach chosen tail
	    | Solution (s, continuation) ->
		let c = fun () -> min_card env to_reach chosen tail in
		  raise (Solution (s, (c :: continuation)))

I first wrap without catching the exceptions and test

let smc = fun to_reach list ->
   let env = { solutions = []; backtracks = 0; card = max_int } in
       min_card env to_reach [] list

# val smc : int -> int list -> int = <fun>
# smc 226 [198; 122; 90; 75; 64; 54; 53; 10; 5; 1];;
Exception: Solution (7, [<fun>; <fun>; <fun>; <fun>; <fun>; <fun>; <fun>]

Seems correct.

Now I try to extract the integer

let smc = fun to_reach list ->
   try
     let env = { solutions = []; backtracks = 0; card = max_int } in
       min_card env to_reach [] list
   with Solution (c, l) -> c

# val smc : int -> int list -> int = <fun>
# smc 226 [198; 122; 90; 75; 64; 54; 53; 10; 5; 1];;
- : int = 7

Correct.

Now I try to extract the continuation list

let smc = fun to_reach list ->
   let env = { solutions = []; backtracks = 0; card = max_int } in
     try
       min_card env to_reach [] list
     with Solution (c, l) -> l

This expression has type continuation list but is here used with type int

Ok. I have to correct the type of continuation by hand

lets try [type continuation = unit -> (unit -> int)]

This expression has type continuation list but is here used with type
   unit -> int

lets try [type continuation = Cont of (unit -> continuation)]
and [let c = Cont (fun () -> ... ) in raise Solution (s, c :: cont)]

This expression has type continuation list but is here used with type
   continuation

lets try [type continuation = Cont of (unit -> continuation list)]

# val smc : int -> int list -> continuation list = <fun>
# smc 226 [198; 122; 90; 75; 64; 54; 53; 10; 5; 1];;
- : continuation list =
[Cont <fun>; Cont <fun>; Cont <fun>; Cont <fun>; Cont <fun>; Cont <fun>;
  Cont <fun>]

Great ! Now I want the solution, its cardinality and the continuation list

lets try ...

          Diego Olivier

Re: [Caml-list] Type inference inside exceptions ?

[ketty .]

[-- Attachment #1: Type: text/plain, Size: 278 bytes --]

On 10/6/06, Diego Olivier FERNANDEZ PONS <diego.fernandez_pons@etu.upmc.fr>
wrote:

> I would like the type-checker to infer the type inside exceptions (or
> at least to help me in the "guess a type and test" loop).



I'd like it to infer the types of record-fields as well :)

[-- Attachment #2: Type: text/html, Size: 604 bytes --]

Re: [Caml-list] Type inference inside exceptions ?

[Diego Olivier FERNANDEZ PONS]

Quoting "ketty ." <kattlachan@gmail.com>:

>> I would like the type-checker to infer the type inside exceptions (or
>> at least to help me in the "guess a type and test" loop).
>
> I'd like it to infer the types of record-fields as well :)

WISH GRANTED.

type ('a, 'b, 'c) environment = {
     mutable solutions : 'a;
     mutable backtracks : 'b;
     mutable objective : 'c
}

let min_card = fun env ... -> ...

# val min_card :
   (int list list, int, int) environment ->
   int -> int list -> int list -> int list * int list continuation list =
   <fun>

The typechecker inferred the type of your record-fields.

Polymorphic exceptions are forbidden because they could break the type  
system, leading to a ['a -> 'b] type. That is why I asked for "type  
inference" or any kind of useful help and not for "polymorphic  
exceptions". I would accept the compiler to deny the use of the  
exception if it is not monomorphic.

         Diego Olivier

Re: [Caml-list] Type inference inside exceptions ?

[Stéphane Glondu]

Diego Olivier FERNANDEZ PONS a écrit :
> Now I want the program not to return all the solutions but only the
> first solution it found and a list of continuations that I can launch
> again if a better solution is required.

I don't really understand what you are doing: why do you generate a list
of continuations instead of a single one? Don't you want a kind of lazy
list?

> Here is the detailed code
> [...]
> Great ! Now I want the solution, its cardinality and the continuation list

Does this code really do what you expect? Did you take into
consideration multiple executions of your continuations? I am rather
unconfident with your single mutable variable...

> lets try ...

Is this the end of your mail?

-- 
Stephane Glondu

Re: [Caml-list] Type inference inside exceptions ?

[Diego Olivier FERNANDEZ PONS]

     Bonjour,

Quoting Stéphane Glondu <steph@glondu.net>:
> I don't really understand what you are doing: why do you generate a list
> of continuations instead of a single one?

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

> Don't you want a kind of lazy list?

I first wrote a code that solves the problem completely.
Then I modified the code to handle continuations of the form (unit ->  
somthing)
Then I replaced (unit -> something) with a lazy list
Finally I kept the list of continuations but send it back by function  
return instead of an exception [And type inference DOES work in that  
case !]

I am "complaining" because the compile DOES infer types within  
exceptions but does not allow you to let him fix the type the way he  
needs. It only says "It is not what I was expecting, so your function  
won't compile, sorry".

As far as I understand the reason is to avoid polymorphic exceptions  
but this could have been done just forbidding the final result to be  
polymorphic or typechecking and not compiling, or giving me a way to  
just typecheck without creating the value.

> Does this code really do what you expect?

Reasonably

>> lets try ...
>
> Is this the end of your mail?

Unless you want a complete log of everything I tried when developping  
that code...

         Diego Olivier

Re: [Caml-list] Type inference inside exceptions ?

[Pietro Abate]

On Fri, Oct 13, 2006 at 02:23:17PM +0200, Diego Olivier FERNANDEZ PONS wrote:
> Quoting St??phane Glondu <steph@glondu.net>:
> >I don't really understand what you are doing: why do you generate a list
> >of continuations instead of a single one?
> 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 ?

thanks!
:)
p

-- 
++ Blog: http://blog.rsise.anu.edu.au/?q=pietro
++ 
++ "All great truths begin as blasphemies." -George Bernard Shaw
++ Please avoid sending me Word or PowerPoint attachments.
   See http://www.fsf.org/philosophy/no-word-attachments.html

Reordering continuations (was :Type inference inside exceptions ?)

[Diego Olivier FERNANDEZ PONS]

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

Re: [Caml-list] Reordering continuations (was :Type inference inside exceptions ?)

[Diego Olivier FERNANDEZ PONS]

     Bonjour,

Here is some code that shows the effect of reordering continuations in  
a combinatorial problem. The first one is the minimum cardinality  
subset-sum problem, the second returns the order in which the leaves  
of the search tree are visited.

Each time a solution is found, the number of failures is printed. This  
gives an idea of how much time was spent to find the solution.

(* subsetsum in depth first search *)
# let p = smc 47 [39;32;20;19;16;9;1] in solve p (new stack);;
0 fails : 39 1 1 1 1 1 1 1 1
8 fails : 32 9 1 1 1 1 1 1
47 fails : 20 16 9 1 1
61 fails : 20 9 9 9
118 fails : 19 19 9
- : int list list * int =
([[39; 1; 1; 1; 1; 1; 1; 1; 1]; [32; 9; 1; 1; 1; 1; 1; 1]; [20; 16; 9; 1; 1];
   [20; 9; 9; 9]; [19; 19; 9]],
  457)

(* subset sum in limited discrepancy search *)
# let p = smc 47 [39;32;20;19;16;9;1] in solve p (new queue);;
0 fails : 39 1 1 1 1 1 1 1 1
0 fails : 32 9 1 1 1 1 1 1
16 fails : 19 19 9
- : int list list * int =
([[39; 1; 1; 1; 1; 1; 1; 1; 1]; [32; 9; 1; 1; 1; 1; 1; 1]; [19; 19; 9]], 459

The second example builds a tree which leaves are labelled from 0 to  
2^n - 1 from left to right. The order in which the leaves are visited  
is returned.

# let p = label 4 in solve p (new stack);;
- : int list * int =
([0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15], 0)

# let p = label 4 in solve p (new queue);;
- : int list * int =
([0; 8; 4; 2; 1; 12; 10; 9; 6; 5; 3; 14; 13; 11; 7; 15], 0)

Here is the complete code

class type ['a] continuationQueue =
   object
     method push : 'a -> unit
     method pop : 'a
     method is_empty : bool
     method length : int
   end

class ['a] queue =
   (object
     val contents = (Queue.create () : 'a Queue.t)
     method push = fun x -> Queue.push x contents
     method pop = Queue.pop contents
     method is_empty = Queue.is_empty contents
     method length = Queue.length contents
   end : ['a] continuationQueue)

class ['a] stack =
   (object
     val contents = (Stack.create () : 'a Stack.t)
     method push = fun x -> Stack.push x contents
     method pop = Stack.pop contents
     method is_empty = Stack.is_empty contents
     method length = Stack.length contents
   end : ['a] continuationQueue)

type 'a environment = {
     mutable backtracks : int;
     mutable objective : int;
     mutable queue : 'a queue
  }

exception Fail

type 'a continuation = Cont of (unit -> 'a)

let rec print_list = function
   | [] -> print_newline()
   | x :: tail -> print_int x; print_string " "; print_list tail

let rec min_card env = fun to_reach chosen candidates ->
   if (to_reach = 0) then
     match compare env.objective (List.length chosen) with
     | n when n <= 0 ->
	env.backtracks <- env.backtracks + 1;
	raise Fail
     | _ ->
	env.objective <- List.length chosen;
	print_int env.backtracks;
	print_string " fails : ";
	print_list (List.rev chosen);
	(List.rev chosen)
   else
     match candidates with
     | [] ->
	env.backtracks <- env.backtracks + 1;
	raise Fail
     | x :: tail when x > to_reach -> min_card env to_reach chosen tail
     | x :: tail ->
	let c = Cont (fun () -> min_card env to_reach chosen tail) in
	env.queue#push c;
	min_card env (to_reach - x) (x :: chosen) candidates

let smc = fun to_reach list ->
   function env ->
     let c = Cont (function () -> min_card env to_reach [] list) in
     env.queue#push c; env

let rec label_nodes env = fun count remaining_depth ->
   match remaining_depth with
     | 0 -> count
     | n ->
	let c = Cont (fun () -> label_nodes env (2 * count + 1) (n - 1)) in
	  env.queue#push c;
	  label_nodes env (2 * count) (n - 1)

let label = function depth ->
   function env ->
     let c = Cont (fun () -> label_nodes env 0 depth) in
       env.queue#push c; env

let rec solve_rec = function env ->
   if env.queue#is_empty then []
   else
     let Cont c = env.queue#pop in
     try
       let s = c () in
       s :: solve_rec env
     with Fail -> solve_rec env

let solve = fun f queue ->
   let env = { backtracks = 0; objective = max_int; queue = queue } in
   let solutions = solve_rec (f env) in
   (solutions, env.backtracks)

         Diego Olivier

Re: [Caml-list] Reordering continuations (was :Type inference inside exceptions ?)

[Diego Olivier FERNANDEZ PONS]

     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 écrit]
> It is also the technique to find alternative recognition hypotheses  
> in most speech recognizers (hypothesis graph search with dynamical  
> 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 automaton
(e.g. an LR grammar with conflicts, an ambiguous grammar) to an
exception based implicit enumeration algorithm (i.e. a recursive  
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 = LR, pessimistic -> breath first search = 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  
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  
> 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] == 2
   min cardinality subsetsum 15 [17;15;13;12;11;7;5;2;1] == 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

Looking for references to usage of ocaml in data mining, knowleadge discovery, etc

[Dr. Axel Poigné]

Hello

I look for references to usage of ocaml in Data Mining, Knowleadge  
Discovery. Inductive Logic Programming, Vector support Machines and  
related topics. I have browsed the net but entries are sparse.

I would like to try using Ocaml in these areas and want to avoid  
double work.

Axel


------------------------------------------------------------------------ 
-------------------------
Dr.rer.nat. Dipl.Ing.Axel Poigné

Fraunhofer Institut Intelligente Analyse- und Informationssysteme - IAIS
Department Knowledge Discovery
Schloss Birlinghoven
D-53754 Sankt Augustin

Tel.: +49 (0) 2241 14 - 2440
Fax: +49 (0) 2241 14 - 42440
e-Mail: axel.poigne@ais.fraunhofer.de
web:  http://www.ais.fraunhofer.de/~ap
------------------------------------------------------------------------ 
------------------------

Re: [Caml-list] Looking for references to usage of ocaml in data mining, knowleadge discovery, etc

[Markus Mottl]

[-- Attachment #1: Type: text/plain, Size: 1303 bytes --]

On 10/19/06, Dr. Axel Poigné <axel.poigne@iais.fraunhofer.de> wrote:
>
> I look for references to usage of ocaml in Data Mining, Knowleadge
> Discovery. Inductive Logic Programming, Vector support Machines and
> related topics. I have browsed the net but entries are sparse.
>
> I would like to try using Ocaml in these areas and want to avoid
> double work.
>

You may have already found AIFAD (Automated Induction of Functions over
Algebraic Datatypes), a symbolic machine learning program, which generalizes
induction of decision trees to structured values, and is pretty efficient
even on large amounts of data.  You can find the sources and documentation
here:

  http://www.ocaml.info/aifad

It's also available as a Godi-package, which makes it easier to install,
because it depends on other libraries.

We use Lacaml, a fairly complete and convenient binding to BLAS/LAPACK, here
at Jane Street Capital for implementing numeric algorithms to analyse very
substantial amounts of financial data.  I unfortunately cannot give you
details about this work.  You can get Lacaml through Godi or download it
here:

  http://www.ocaml.info/home/ocaml_sources.html#LACAML

Best regards,
Markus

-- 
Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com

[-- Attachment #2: Type: text/html, Size: 1909 bytes --]