🚀 go-pugleaf

In article <591sis-b@massey.ac.nz>, news@massey.ac.nz (USENET News System) writes:
> Would anyone else care to comment on why such a simple technique (at
> least in hindsight) appears to have received so little attention?

Possibly it has been regarded as too well known?  The technique was
applied to Prolog in a paper in the Uppsala conference (I've never had
the proceedings for that) in 83? 84? something like that.  There's a
small literature on multi-version data structures.

> Why
> bother with compile-time analysis to detect "single-threadedness" when
> a simple run-time organisation for arrays will suffice?

Because with reverse diffs you still have to keep the reverse diffs around
and maybe garbage collect later; with compile-time analysis you should be
able to generate exactly the same code you'd have had in an imperative
language.  (See Trilogy.)
-- 
I agree with Jim Giles about many of the deficiencies of present UNIX.

In article <591sis-b@massey.ac.nz> news@massey.ac.nz (USENET News System) writes:

 > ...
 > who) posted two messages on "reverse diff" arrays, one of the messages
 > including ML source code which I assume implemented these arrays using
 > references.
 > ...
 > Would anyone else care to comment on why such a simple technique (at
 > least in hindsight) appears to have received so little attention?  Why
 > bother with compile-time analysis to detect "single-threadedness" when
 > a simple run-time organisation for arrays will suffice?

I find there are many things which seem simple in hindsight.
Here are my opinions on why so many may not have stumbled
across reverse diffs or enthused about them before.

 0.  As a data stucture tailored to some specific
     requirements, they are great.

 1.  Unless built in I cant get the benefits of reverse
     diffs in *pure* functional languages.  I would like to
     use them in, say, Hope and Miranda, but I cant.

 2.  Because of (1) my vision is limited by the functional
     programming paradigm and I am unlikely to think of a
     similar solution (i.e. one that uses mutable data
     structures and requires a proof that the abstract data
     type is still referentially transparent).

 3.  Reverse diffs can be really bad if the data structure
     is not quite single threaded.  If I make a zillion
     updates to an array which just happens to have another
     copy I will wonder where all my memory is going and why
     it takes so long to look up anything in the original
     copy.  They are not a general solution so they should
     not be used by default.  And if I am to do analysis to
     detect this I might as well go the whole hog and to
     thing properly.

 4.  As always, anything that you do a run time has a cost.
     An access to the most recent version of the reverse
     diff array still costs 2-3 times a normal array
     reference.

 5.  Reverse diff arrays are a different type to my ordinary
     arrays.  I have to recode my array library.
--
Stephen Adams                        S.R.Adams@ecs.soton.ac.uk
Computer Science
University of Southampton
Southampton SO9 5NH, UK

In article <SRA.91Jun27101445@pessoa.ecs.soton.ac.uk> sra@ecs.soton.ac.uk
(Stephen Adams) writes:
> 3.  Reverse diffs can be really bad if the data structure
>     is not quite single threaded.  If I make a zillion
>     updates to an array which just happens to have another
>     copy I will wonder where all my memory is going and why
>     it takes so long to look up anything in the original
>     copy.

One might consider this behaviour to be more acceptable than the
equivalent case in an imperative paradigm!

--

David Lester, Manchester University, UK.