From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id pAABD8nF005029 for ; Thu, 10 Nov 2011 12:13:08 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: At0BAIGwu05KfVK2kGdsb2JhbABCqiMIIgEBAQEJCQ0HFAQhgXIBAQEEEgITGQEbHQEDDAYFCzsiAREBBQEcBjWiKwqLYYJjhTg9iHACBQqJdASUKI1FPYNx X-IronPort-AV: E=Sophos;i="4.69,488,1315173600"; d="scan'208";a="129610779" Received: from mail-wy0-f182.google.com ([74.125.82.182]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 10 Nov 2011 12:13:02 +0100 Received: by wyf23 with SMTP id 23so562861wyf.27 for ; Thu, 10 Nov 2011 03:13:02 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=TQgWXubCCTZII2xSg7SC+j1SX9lpN16b17C4w4A3giw=; b=xSmLMEWYuduzKQnSibCwPobjPLQc+VW7Idvdr4hWmMEJZc17UaWzCUXN+yuLcvJfm2 g1oX6VJkwY3HqXoz83ntahoqT03LGga9MzCD6rKsxckUchXBoFiAHm9iSX652mt1AJO0 LItEClS46hHRFa5CRXSc3Qa3dD3YeItN6cxLo= MIME-Version: 1.0 Received: by 10.216.154.10 with SMTP id g10mr1154016wek.103.1320923582375; Thu, 10 Nov 2011 03:13:02 -0800 (PST) Received: by 10.216.17.137 with HTTP; Thu, 10 Nov 2011 03:13:02 -0800 (PST) In-Reply-To: <006501cc9e61$ac282470$04786d50$@ffconsultancy.com> References: <006501cc9e61$ac282470$04786d50$@ffconsultancy.com> Date: Thu, 10 Nov 2011 12:13:02 +0100 Message-ID: From: Diego Olivier Fernandez Pons To: Jon Harrop Cc: Caml List Content-Type: multipart/alternative; boundary=0016e652f614e728ff04b15f7c12 Subject: Re: [Caml-list] Dynamic graph algorithms --0016e652f614e728ff04b15f7c12 Content-Type: text/plain; charset=ISO-8859-1 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 --0016e652f614e728ff04b15f7c12 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
=A0 =A0 Jon,

In ML there has been work on self adj= usting computations (check the work of Amut Acar and unfold recursively).= =A0
Dynamic graphs are in a sense an optimization of self-adjusting com= putations in the same way logical persistence is an optimization of physica= l persistence

Lets say I have an backtracking algorithm that uses a set da= ta structure. I have two implementation possibilities
- physical = persistence : restore the data structure to its (physical) previous states<= /div>
- logical persistence : store changes and restore them when I am backt= racking (the sets will be represented by a different physical tree)

(* Physical persistence *)
let rec subsets= um =3D fun target candidates ->
=A0 match target with
=A0 =A0 | 0 -> Some []
= =A0 =A0 | n when n > 0 ->
=A0 =A0 =A0 if IntSet.is_empty ca= ndidates then None
=A0 =A0 =A0 else
(
=A0let value =3D IntSet.= choose candidates in
=A0let remaining_candidates =3D IntSet.remove value candidates in
=A0match subsetsum (targ= et - value) (IntSet.filter (fun x -> x <=3D target - value) remaining= _candidates)
=A0wit= h=A0
=A0 =A0| None -> subs= etsum target remaining_candidates
=A0 =A0| Some list -> Some (value :: list)
)
=A0 =A0 | _ -= > failwith "incorrect argument : negative target"
<= div>
(* Logical persistence *)

let add_list =3D List.fold_left (fun s v -> IntSet.a= dd v s)

let rec subsetsum =3D fun target candidate= s ->
=A0 match target with
=A0 =A0 | 0 -> Some []=
=A0 =A0 | n when n < 0 || IntSet.is_empty candidates -> None
=A0 =A0 | _ ->=A0
=A0 =A0 =A0 let value =3D IntSet.choo= se candidates in
=A0 =A0 =A0 let removed =3D IntSet.elements (Int= Set.filter (fun x -> x > target - value) candidates) in
=A0 =A0 =A0 let candidates =3D IntSet.remove value (IntSet.filter (fun= x -> x <=3D target - value) candidates) in
=A0 =A0 =A0 mat= ch subsetsum (target - value) candidates
=A0 =A0 =A0 with=A0
| None -> subsetsum t= arget (add_list (IntSet.add value candidates) removed)
| Some list -> Some (v= alue :: list)

In self-adjusting system= s, whenever a data changes, the sequence of computations is replayed from t= he last common node (like the inner match in the loop of a backtracking alg= orithm). In dynamic algorithms for problem XXX there is an algorithm that r= estores an equivalent state (typically an invariant).

=A0 =A0 =A0 =A0 Diego Olivier
--0016e652f614e728ff04b15f7c12--