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