Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-07T22:53:21.951Z Has data issue: false hasContentIssue false
  • English
  • Français

On the equivalence between CMC and TIM

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Rafael D. Lins ,
Simon J. Thompson  and
Simon Peyton Jones
Rafael D. Lins
Affiliation:
Departament de Informática, Universidade Federal de Pernambuco, Recife, Brazil
Simon J. Thompson
Affiliation:
Computing Laboratory, The University of Kent, Canterbury, UK
Simon Peyton Jones
Affiliation:
Department of Computing Science, University of Glasgow, Glasgow, Scotland
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we present an equivalence between TIM, a machine developed to implement non-strict functional programming languages, and the set of Categorical Multi-Combinators, a rewriting system developed with similar aims. These two models of computation at first appear to be quite different, but we show a direct equivalence between them, thereby adding some new structure to the ‘design-space’ of abstract machines for non-strict languages.

Information

Type
Articles
Information
Journal of Functional Programming , Volume 4 , Issue 1 , January 1994 , pp. 47 - 63
Copyright
Copyright © Cambridge University Press 1994

References

Argo, G. (1989) Improving the three instruction machine. Functional Programming Languages and Computer Architecture. Addison-WesleyGoogle Scholar
Fairbairn, J. and Wray, S. (1987) Tim: A simple, lazy abstract machine to execute supercombinators. In Proc. 3rd Int. Conf. on Functional Programming and Computer Architecture. Volume 274 of Lecture Notes in Computer Science. Springer-Verlag, pp. 34–45.CrossRefGoogle Scholar
Hannan, J. (1991) Making abstract machines less abstract. Functional Programming Languages and Computer Architecture (FPCA). Volume 523 of Lecture Notes in Computer Science. Springer-Verlag.Google Scholar
Johnsson, T. (1989) Compiling Lazy Functional Languages. PhD thesis, Chalmers Tekniska Högskola, Göteborg, Sweden.Google Scholar
Kelsey, R. and Hudak, P. (1989) Realistic compilation by program transformation. In Proc. ACM Conf. on Principles of Programming Lang., pp. 281–292.Google Scholar
Lester, D. (1989) Combinator graph reduction: a congruence and its applications. PhD Thesis, Programming Research Group, Oxford.Google Scholar
Lins, R. D. (1986) On the Efficiency of Categorical Combinators in Applicative Languages. PhD thesis, University of Kent at Canterbury.Google Scholar
Lins, R. D. (1987) Categorical multi-combinators. In Kahn, G., editor, Functional Programming Languages and Computer Architecture. Volume 274 of Lecture Notes in Computer Science. Springer-Verlag, pp. 60–79.CrossRefGoogle Scholar
Lins, R. D. and Lira, B. O. (1993) ΓCMC: A Novel Way to Implement Functional Languages. Journal of Programming Language Design and Implementation. (To appear.)Google Scholar
Lins, R. D. and Thompson, S. J. (1990 a) Implementing SASL using categorical multicombinators. IEEE Trans. Softw. — Practice and Experience 20(11):1137–1165.Google Scholar
Lins, R. D. and Thompson, S. J. (1990 b) CM-CM: A categorical multi-combinator machine. In Proc. XVI Latino-American Conf. on Informatics, vol(1) - pp. 181–198, Asunción,Paraguay.Google Scholar
Meijer, E. (1989) Cleaning up the design space of function evaluating machines. Department of Informatics, University of Nijmegen, 03.Google Scholar
Meijer, E. (1992) Calculating Compilers. PhD thesis, University of Nijmegen, 02.Google Scholar
Musicante, M. A. and Lins, R. D. (1991) GMC – a graph multi-combinator machine. Microprocess. and Microprogram. 31(1–5):81–84, 04.CrossRefGoogle Scholar
Peyton Jones, S. (1987) The Implementation of Functional Languages. Prentice-Hall.Google Scholar
Peyton Jones, S. and Lester, D. (1992) Implementing Functional Languages: A Tutorial. Prentice-Hall.Google Scholar
Thompson, S. J. and Lins, R. D. (1992) The Categorical Multi-Combinator Machine: CM-CM. The Computer Journal 35(2):170–176, 04.CrossRefGoogle Scholar
Wand, M. (1991) Correctness of procedure representations. Department of Computer Science, Northeastern University, 03.Google Scholar
Wraith, G. and Bosley, D. (1988) Private communication.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.