Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!math.fu-berlin.de!opal!wg
From: wg@opal.cs.tu-berlin.de (Wolfgang Grieskamp)
Newsgroups: comp.lang.functional
Subject: Re: Reverse diffs [was Re: functional programming formulation of graph algorithms]
Message-ID: <3556@opal.cs.tu-berlin.de>
Date: 2 Jun 91 11:57:55 GMT
References: <TMB.91May29174602@volterra.ai.mit.edu> <5332@ztivax.UUCP> 	<REDDY.91May28195125@reddy.cs.uiuc.edu> 	<1991May29.222935.13101@ncsu.edu> <TMB.91May30000745@volterra.ai.mit.edu>
Sender: news@opal.cs.tu-berlin.de
Reply-To: wg@opal.cs.tu-berlin.de
Followup-To: comp.lang.functional
Organization: Technical University of Berlin
Lines: 53
Nntp-Posting-Host: poseidon

tmb@ai.mit.edu (Thomas M. Breuel) writes:

 > [INTDICT "reverse-diff" implementation, cf. original posting]

Nice demonstration of the "clean" use of references in SML. Although I 
believe updatable arrays should be build in or implemented 
in a foreign language anyway, and a compiler can do the job slightly
better then the SML programmer, if it implements reference
counting and/or performs sharing analysis.

In the first case (RC) the generated code might check at run-time
if the object to update is "exclusive", i.e. only one reference
exists to it. If so, no "diffs" have to be created. In the second case,
static analysis detects that a given object is always exclusive 
in some context.

In any case one has to find a sequentialization order which 
minimizes sharing. Consider a expression which swaps two values of 
an array:

	assoc(assoc(A,j,A sub i),i,A sub j)

This, then, may be expressed by the "parallel" let (I hope "and" 
does something like this in SML; have the manual not in hand):

	let val xi = A sub i
	and val A1 = assoc(A,j,xi)
	and val xj = A sub j
	and val A2 = assoc(A1,i,xj) 
	in  A2

Textual sequentialization leads to the result that A is shared during 
the first call to assoc. But a simple heuristic can find the desired
ordering (i.e. first performing the sub applications, then the assoc
applications).  Let each parameter of a function be marked to be 
either "destructive" (function might sel-update the parameter) or 
"non-destructive" (function will definitively not). This information 
will be pre-given for primitive functions, and will be inherited 
by user defined functions.

Naturally, "assoc" is destructive in it's array argument, and sub is not 
(either pre-given or by analysis). The above parallel let will be
sequentialized performing first the non-destructive sub applications and 
then the destructive assoc applications.

To conclude, selective update is not _such_ a efficience penalty in 
functional languages provided your compiler really takes care of
it. Unfortunately, most functional language compilers I know of
won't (except the OPAL compiler).

--
Wolfgang Grieskamp 
wg@opal.cs.tu-berlin.de tub!tubopal!wg wg%opal@DB0TUI11.BITNET