Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!icdoc!sot-ecs!sra From: sra@ecs.soton.ac.uk (Stephen Adams) Newsgroups: comp.lang.functional Subject: Re: "Reverse Diff" Arrays Message-ID: Date: 27 Jun 91 09:14:45 GMT References: <591sis-b@massey.ac.nz> Sender: news@ecs.soton.ac.uk Organization: Southampton University Computer Science Lines: 51 In-reply-to: news@massey.ac.nz's message of 26 Jun 91 22:27:07 GMT 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