Quick question regarding indirection cells...

Melissa O'Neill oneill@cs.sfu.ca
Mon, 26 Jan 1998 16:04:31 -0800 (PST)


Hi Simon,

I'm in the throws of finishing a paper, and, needing a supporting
citation for indirection cells, I turned to your book ``The
Implementation of Funtional Programming Languages'', which I think may
be the place I first learned of such things, some time ago. I was
imagining that it would cite some paper in the mid-70s that first
introduced such things, but alas in Section 12.4.1 (p. 214) where you
first introduce indirection cells, there is no citation, and similarly
in Section 12.4.4 where you state ``Chains of indirection nodes can be
prevented'' (which is a property I have come to rely on), there is no
citation (or explanation/proof).

While I could prove the properties I need relating to shorting out of
indirection cells (i.e. that using indirection nodes may exact only a
constant amortized time penalty), I'm sure there must be a
foundational reference out there that I've not discovered despite some
amount of searching. So, I'm wondering if you might know of such a
thing, or whether you were the first to write about such things in
your book.

Hope you can help,

    Melissa.