Optimising Partial Applications in TIM

David Wakeling and Alan Dix
University of York?

Technical Report Number 215 (November 1993)

1 Introduction

In [3] Fairbairn and Wray introduced TIM, a simple abstract machine for executing supercombinators. Their abstract machine is an elegant design optimised for normal order evaluation. However, the addition of a mechanism to implement lazy evaluation considerably increases its complexity and imposes a significant overhead.

We originally made this observation in March 1989, when a draft of this paper was circulated privately. Since then, there have been a number of publications about TIM (see, for example, [1, 10, 8]). Inevitably, some of the ideas presented here have been invented independently, or have been improved upon in these subsequent publications. However, we feel our central idea for optimising partial applications in TIM has still to gain the attention that it deserves.

2 The TIM Architecture

A frustrating aspect of the TIM literature is that every author seems to adopt slightly different terminology and notation to describe the same abstract machine. For the sake of definiteness, we take Fairbairn and Wray's 1987 paper [3] as the source of our terminology and notation, referring to the machine described there as the standard TIM . However, in addition to that paper, the reader may also wish to consult the book by Peyton Jones and Lester [8] for an excellent tutorial.

TIM represents all values as closures of the form < c; f >, where c is the code pointer and f is the frame pointer. The frame pointer points to a frame containing the arguments used by the code at c. The are just three kinds of instructions for manipulating closures. The instruction

Enter < c; f >

?Authors' address: Department of Computer Science, University of York, Heslington, York Y01 5DD, United Kingdom. Electronic mail: [email protected], [email protected]