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.