Optimising Partial Applications in TIM

Download full paper - compressed postscript (68K) or Adobe PDF (180K).

Full reference:

D. Wakeling and A. Dix (1993).
Optimizing Partial Applications in TIM.
YCS 215, Department of Computer Science, University of York.
http://www.hcibook.com/alan/papers/tim93/

See also Garbage collection in the TIM machine

Abstract

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 signicant 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, orhave 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.

Keywords: functional progrtamming implementation, Three Instruction Machine, TIM, supercombinators, optimising partial applications

References

[1] G. Argo. Improving the Three Instruction Machine. In Proceedings of the 1989 Conference onFunctional Programming Languages and Computer Architecture, pages 100-115. ACM Press, September 1989.

[2] R. Bird and P. Wadler. Introduction to Functional Programming. Prentice-Hall, 1988.

[3] J. Fairbairn and S. Wray. TIM: A Simple, Lazy Abstract Machine to Execute Supercombinators. In Proceedings of the 1987 Conference on Functional Programming Languages and Computer Architecture, pages 34-45. Springer-Verlag, September 1987. LNCS 274.

[4] B. Goldberg. Detecting sharing of partial applications in functional programs. In Proceedings of the 1987 Conference on Functional Programming Languages and Computer Architecture, pages 408-425. Springer-Verlag, September 1987. LNCS 274.

[5] R. J. M. Hughes. Super-combinators: A New Implementation Method for Applicative Languages. In 1982 ACM Symposium on LISP and Functional Programming, pages 1-10, August 1982.

[6] T. Johnsson. Lambda lifting: Transforming programs to recursive equations. In Proceedings of the 1985 Conference on Functional Programming Languages and Computer Architecture, pages 190-203. Springer-Verlag, September 1985. LNCS 201.

[7] T. Johnsson. Compiling Lazy Functional Languages. PhD thesis, Chalmers University of Technology, S-412 96 Göteborg, February 1987.

[8] S. L. Peyton Jones and D. Lester. Implementing Functional Languages: A Tutorial. Prentice-Hall, 1992.

[9] S. L. Peyton Jones. FLIC - a functional language intermediate code. ACM SIGPLAN Notices, 23(8):30-48, August 1988.

[10] S. Wray and J. Fairbairn. Non-strict Languages - Programming and Implementation. Computer Journal, 32(2):142-151, April 1989.