Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!qt.cs.utexas.edu!yale.edu!cs.yale.edu!news-mail-gateway
From: hudak-paul@CS.YALE.EDU (Paul Hudak)
Newsgroups: comp.lang.functional
Subject: "reverse diff" arrays
Message-ID: <9106281433.AA09774@NEBULA.SYSTEMSZ.CS.YALE.EDU>
Date: 28 Jun 91 14:33:37 GMT
Sender: daemon@cs.yale.edu
Organization: Yale CS Mail/News Gateway
Lines: 40

As someone already pointed out, the "reverse diff arrays" are really
an old idea.  Besides the Prolog paper, Adrienne Bloss and I described
the technique (we called it "trailers") in our 1985 POPL paper [1].
Since then Adrienne implemented several versions of array updating,
and came up with some interesting results.  For example, besides the
obvious fact that "multiply-threaded arrays" don't work well with
trailers, she found that in certain cases trailers performed worse
than outright copying!  See her FPCA paper [2] or better yet her
thesis [3] for more details.

  -Paul


[1] @InProceedings{
    ,author={Hudak, P. and Bloss, A.}
    ,title={The aggregate update problem in functional programming systems}
    ,booktitle={12th ACM Symposium on Principles of Programming Languages}
    ,organization={ACM}
    ,year=1985
    ,pages={300-314}
    }

[2] @inproceedings{
    ,author={Bloss, A.}
    ,title={Update Analysis and the Efficient Implementation of
            Functional Aggregates}
    ,booktitle={Proceedings of 4th Int'l Conference on Functional
                Programming Languages and Computer Architecture}
    ,organization={ACM, IFIP}
    ,year=1989
    ,pages={26-38}
    }

[3] @phdthesis{
    ,author={Bloss, A.}
    ,title={Path Analysis: Using Order-of-Evaluation Information to
            Optimize Lazy Functional Languages}
    ,school={Yale University, Department of Computer Science}
    ,year=1988
    }