Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!think.com!mintaka!ai-lab!life!tmb
From: tmb@ai.mit.edu (Thomas M. Breuel)
Newsgroups: comp.lang.functional
Subject: Re: Reverse diffs [was Re: functional programming formulation of graph algorithms]
Message-ID: <TMB.91May30000745@volterra.ai.mit.edu>
Date: 30 May 91 04:07:45 GMT
References: <TMB.91May29174602@volterra.ai.mit.edu> <5332@ztivax.UUCP>
	<REDDY.91May28195125@reddy.cs.uiuc.edu>
	<1991May29.222935.13101@ncsu.edu>
Sender: news@ai.mit.edu
Organization: MIT Artificial Intelligence Lab
Lines: 150
In-reply-to: jwb@cepmax.ncsu.edu's message of 29 May 91 22:29:35 GMT

In article <1991May29.222935.13101@ncsu.edu> jwb@cepmax.ncsu.edu (John W. Baugh Jr.) writes:

   [Reddy, suggesting the addition of "sequence" primitives to allow
   a compiler to generate in-place updates rather than copying for modifying
   an array even in a purely functional language]

   > I think this is the wrong approach. Using data structures based on
   > reverse diffs (as in RCS), an update involving side effects [...]
   > is no more efficient (except for possibly a small, constant time
   > overhead) than a more functional formulation.

   I've never heard of reverse diffs--could you please give some examples
   and/or references.  Also, can reverse diffs deal effectively with
   other structured data types (like matrices: constant access & constant
   update)?

At the end, you find some old SML code (sorry about the style, it was
just a quick initial hack for playing around with the idea) that
should illustrate the point. The primitives you can use to operate on
INTDICT arrays are completely functional: sub, assoc, length, and
generate.  From the programmer's point of view, there is no way to
modify an INTDICT, although internally, the implementation uses
side-effects for efficiency.

The code gives you constant-time update and access to the latest
version of the array. If you try to update older versions, you pay
more overhead.  For converting code containing side-effects to a
functional style, it doesn't matter that updates of old versions take
long, since code written using side-effects by necessity will only
access and update the latest version of an array. For other purposes,
there are more complicated, tree-based mechanisms for keeping diffs
that give you log-time update and log-time retrieval for old versions.

The technique can be applied to any of the data structures used in
imperative languages.

As an efficiency hack, and to assert that you ever only want to use
the latest version of an array (as is the case for converted imperative
programs), you could also simply tag old versions as completely invalid
and raise an exception when an attempt is made to use them. I suspect
this would be equivalent to the "sequence" primitives that Reddy
mentions, but it does not require any language constructs beyond
what the functional subset of languages like SML already offers.

For other tricks you can play with reverse diffs, look at the RCS
documentation.

						Thomas.

signature VALUETYPE =
    sig
	type T
	val makestring:T->string
    end

signature INTDICT =
    sig
	type T
	type dict
	val generate : (int -> T) -> int -> dict
	val sub : dict * int -> T
	val length : dict -> int
	val assoc : dict * int * T -> dict
	val print : dict -> unit
    end

functor ReverseDiffArray(T:VALUETYPE):INTDICT =
    struct
	type T = T.T
	val makestring = T.makestring
	datatype rdiff = BASE of (T array) | DIFF of (int * T * rdiff ref)
	type dict = rdiff ref
	    
	nonfix sub
	    
	fun generate f n = ref(BASE(ArrayU.generate f n))
	    
	fun sub(ref(BASE(x)),i:int) = Array.sub(x,i)
	  | sub(ref(DIFF(key,value,next)),i:int) =
	    if i = key then value else sub(next,i);
		
	fun length(ref(BASE(x))) = Array.length(x)
	  | length(ref(DIFF(_,_,x))) = length(x)
	    
	fun assoc(last:dict as ref(BASE(x)),key:int,value:T) =
	    let
		val old = Array.sub(x,key)
		val new = (Array.update(x,key,value); ref(BASE(x)))
		val back = ref(DIFF(key,old,new))
	    in
		last := !back; new
	    end
	  | assoc(last:dict,key:int,value:T) =
	    let
		val n = length(last)
		val x = Array.array(length(last),sub(last,0))
		fun loop i = if i>=n then () else (Array.update(x,i,sub(last,i)); loop(i+1))
	    in
		loop 0; Array.update(x,key,value); ref(BASE(x))
	    end
	
	fun print(a:dict) =
	    let
		fun p(x) = output(std_out,x)
		val n = length(a)
		fun loop i =
		    if i>=n then ()
		    else (p(makestring(sub(a,i))); if i<n-1 then p " " else (); loop(i+1))
	    in
		p "<"; loop 0; p ">\n"
	    end
    end

structure IID = ReverseDiffArray(struct type T = int val makestring:T->string = makestring end);

- open IID;
open IID
- val a = generate (fn x => x) 10;
val a = ref (BASE prim?) : dict
- print a;
<0 1 2 3 4 5 6 7 8 9>
val it = () : unit
- val b = assoc(a,5,55);                   <-- constant time update
val b = ref (BASE prim?) : dict
- print b;
<0 1 2 3 4 55 6 7 8 9>
val it = () : unit
- print a;
<0 1 2 3 4 5 6 7 8 9>
val it = () : unit
- val c = assoc(b,6,66);                   <-- constant time update
val c = ref (BASE prim?) : dict
- print c;
<0 1 2 3 4 55 66 7 8 9>
val it = () : unit
- print b;
<0 1 2 3 4 55 6 7 8 9>
val it = () : unit
- print a;
<0 1 2 3 4 5 6 7 8 9>
val it = () : unit
- val d = assoc(a,3,33);                   <-- causes full copy (could be more efficient)
val d = ref (BASE prim?) : dict
- print d;
<0 1 2 33 4 5 6 7 8 9>
val it = () : unit
- print a;
<0 1 2 3 4 5 6 7 8 9>
val it = () : unit
-