🚀 go-pugleaf

taff@ucsc.edu (Tom Affinito) writes:

>I'm trying to get an intuition for Fairburn & Wray's TIM machine. I've read  
>their '87 paper, and am familar with SECD, SKI reduction, and the G-machine.

>What I'm trying to get is some deep feeling on how TIM relates to SECD and SKI  
>reduction. It seems to me that TIM is very similar to what compiled code for an  
>SECD system would be like....a series of instructions for manipulating the  
>stacks, building environments, and storing partial results. Is the difference  
>solely in the fact that environments need not be created in TIM because of the  
>preliminary lambda-lifting phase? IE, if SECD had had a supercombinator  
>preprocessor, might it have looked like TIM?

>In what ways do SECD + graph reduction = TIM? In what ways should that = be <>?
>(Abstractly of course)

Indeed, there is a lot of similarity between TIM and SECD, and yes, if
you used a name-free form for lambda expressions (supercombinators or
deBruin notation), SECD is even closer to TIM. The main difference is
that SECD is a call-by-value abstract machine, which can be modified
to call-by-need by the delay/force mechanism, whereas TIM is a
call-by-name abstract machine, which can be modified to call-by-need
by the marker mechanism.

Torben Mogensen (torbenm@diku.dk)