Quick question regarding indirection cells...

David Lester dlester@cs.man.ac.uk
Tue, 27 Jan 1998 14:18:53 GMT


Simon says:

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

Thanks Simon,

But there is a little piece in Section 6.4 of the thesis [1] about
shorting out indirections. I've just reread that bit, and although the
argument is not entirely rigourous, I think that the proof techniques
outlined works.

It should be noted that the use of indirections was to ease the
semantic proofs, rather than for any efficiency reason.

I should also point out that I am not the originator of the idea (mine
is a variant of the obvious idea), and I think that the original might
be found in one of the SKIM papers [2,3].

---
David Lester

[1] David Lester, "Combinator Graph Reduction: A Congruence and its
    Applications", DPhil, Oxford 1988. Also available as PRG-73,
    ISBN 0-902928-55-4

[2] Clarke et al "SKIM", Proc ACM Lisp Conference, Stanford, 1980.

[3] Stoye et al "Some practical methods for rapid combinator redurtion".
    ACM Lisp and FP conference, Austin Texas, 1984.