🚀 go-pugleaf

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