Jon,
In ML there has been work on self adjusting computations (check the work of
Amut Acar and unfold recursively).
Dynamic graphs are in a sense an optimization of self-adjusting
computations in the same way logical persistence is an optimization of
physical persistence
Lets say I have an backtracking algorithm that uses a set data structure. I
have two implementation possibilities
- physical persistence : restore the data structure to its (physical)
previous states
- logical persistence : store changes and restore them when I am
backtracking (the sets will be represented by a different physical tree)
(* Physical persistence *)
let rec subsetsum = fun target candidates ->
match target with
| 0 -> Some []
| n when n > 0 ->
if IntSet.is_empty candidates then None
else
(
let value = IntSet.choose candidates in
let remaining_candidates = IntSet.remove value candidates in
match subsetsum (target - value) (IntSet.filter (fun x -> x <= target -
value) remaining_candidates)
with
| None -> subsetsum target remaining_candidates
| Some list -> Some (value :: list)
)
| _ -> failwith "incorrect argument : negative target"
(* Logical persistence *)
let add_list = List.fold_left (fun s v -> IntSet.add v s)
let rec subsetsum = fun target candidates ->
match target with
| 0 -> Some []
| n when n < 0 || IntSet.is_empty candidates -> None
| _ ->
let value = IntSet.choose candidates in
let removed = IntSet.elements (IntSet.filter (fun x -> x > target -
value) candidates) in
let candidates = IntSet.remove value (IntSet.filter (fun x -> x <=
target - value) candidates) in
match subsetsum (target - value) candidates
with
| None -> subsetsum target (add_list (IntSet.add value candidates) removed)
| Some list -> Some (value :: list)
In self-adjusting systems, whenever a data changes, the sequence of
computations is replayed from the last common node (like the inner match in
the loop of a backtracking algorithm). In dynamic algorithms for problem
XXX there is an algorithm that restores an equivalent state (typically an
invariant).
Diego Olivier
--
Caml-list mailing list. Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
