[erlang-questions] beginner: other array implementations

[Thomas Lindgren]

--- Jonathan Amsterdam <jbamsterdam@REDACTED> wrote:

> 2. A functional array with an imperative
> implementation, the simplest
> of which uses the "shallow binding" or "trailers"
> technique

FWIW, we actually implemented a simple version of that
in Hipe in the old days (or rather, a version based on
a similar technique for Prolog, developed earlier at
Uppsala). This worked okay for simple copying GC, but
with generational GC, you need to record pointers from
the old generation to the new, which that gen GC
didn't have (and still doesn't). So at that point, the
update operation was crippled and Hipe switched to
more conventional data structures. (The gen GC was
introduced after my time, though, so I only heard this
second-hand.)

My experience with functional arrays was mixed even
before the gen GC issue. The canonical bad example was
if you preinitialize an array before a loop, then use
the preinitialized version in each iteration
(typically to save some init work). After the first
iteration, your 'clean' array will have exception
chains, and these will steadily accumulate with each
iteration. Thus, if you keep the original data
structure around, you may end up dragging around a lot
of exception chains with disappointing results (both
wrt access times and, importantly, leaking memory).
Note that the gotcha was in keeping the old version
around; the data structure is optimized for using the
latest version.

Basically, you ended up watching out for these sort of
bad cases and coding around them, which was
undesirable. So to get it right, you probably need a
much smarter GC and/or runtime, capable of detecting
and cleaning up these data structures, which is
non-trivial in the GC (because you don't know
beforehand which versions are live).

In my judgement, because of these problems it's not
ready for general use yet, but a careful revisit by,
say, a good student to clean up and solve these issues
somehow might well be worth doing. (Or move on to
something more suitable.)

Best,
Thomas




      ____________________________________________________________________________________
Be a better friend, newshound, and 
know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ