Quick question regarding indirection cells...

[Simon L Peyton Jones]

I'm replying to the whole list in case anyone knows more
info.

> 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.

It's a good question!  No, I don't know of any earlier work
on indirections.  I regard what I wrote in my book as a writing-down
of folk-lore, certainly not a formal treatment.  David Lester did
prove some properties of graph reduction in his thesis (Oxford),
though not this one I think.  There's quite a bit more about
indirections and indirection chains in my other book (also out of
print, but available online) in the context of the TIM machine
where the issue of indirections is especially delicate.

Maybe some Clean people know of other work.  Certainly, a lot
of work on the foundations of graph reduction has taken place
in that community.

Simon