Rationalized three instruction machine
Pages 94 - 102
Abstract
The declarative nature of functional programming languages causes many difficulties in their efficient implementation on conventional machines. The problem is much harder when the language has non-strict (lazy) semantics. Abstract machines serve as an intellectual aid in bridging the semantic gap between such languages and the conventional von Neumann architecture. However they become more and more complex with time as efficiency considerations force the instruction set of the machine to grow in size. In this paper we explain the phenomenon in context of the Three Instruction Machine (TIM). We then define a rationalized instruction set for TIM that allows us to view all enhancements to TIM in a uniform way. This instruction set is quite close to RISC instructions and clearly identifies the key operations on closures. Translation of functional programs to our rationalized instruction set opens up scope for various local and global optimizations. We illustrate this by showing how to build control flow graphs and perform optimizations on it. Lazy arguments in functional programs make it hard to predict evaluation order statistically. We define the notion of pseudo-lazy arguments to statically expose the control flow information, wherever possible, for doing better flow analysis.
References
[1]
{1} Aho A. V., Sethi R. & Ullman J. D., Compilers - Principles Techniques and Tools, Addison-Wesley, 1986.
[2]
{2} Argo G., A New Sharing Mechanism for TIM, Functional Programming, Glasgow, Aug '91. pp. 25-35, R. Heldal et al.(Eds), Springer-Verlag.
[3]
{3} Argo G., Improving the Three Instruction Machine, Proceedings of the 1989 conference on functional programming languages and computer architecture, pp. 100-115, London, 1989.
[4]
{4} Augustsson L., Compiling lazy functional languages, Part II, Ph.D. Thesis, Chalmers University of Technology, 1987.
[5]
{5} Chitnis S.V, Oberoi S. & Satpathy M., Flow Analysis of Abstract Machine Code for Functional Programming Languages Technical Report TR-144-94, Dept. of Computer Science and Engg., IIT Bombay, 1994.
[6]
{6} Fairbairn J & Wray S., TIM: A simple abstract machine for executing supercombinators, Proceedings of the 1987 conference on functional programming languages and computer architecture, pp. 34-45, Portland, Oregon, Sep. 1987, LNCS 274.
[7]
{7} Johnsson T., Compiling lazy functional languages, Ph. D. Thesis, Chalmers University of Technology, 1987.
[8]
{8} Morel E. & Renvoise C., Global Optimization by Suppression of Partial Redundancies, Comm. of ACM, vol. 22(2), 1979.
[9]
{9} Oberoi S., Satpathy M. & Chitnis S. V., Compiling Functional Languages to Conventional Code, Technical report TR-142-94, Dept. of Computer Science and Engg. IIT Bombay, 1994.
[10]
{10} Oberoi S. & Nagaraja G., Implementing data structures on the Three Instruction Machine, Proceedings of the Second National Seminar on Theoretical Computer Science, pp. 91-101, Calcutta, June 1992.
[11]
{11} Ramkumar S., Venkatesh G. & Sanyal A., Stack Based Implementations of The Three Instruction Machine, TR-066-92, Dept. of Computer Science & Engineering, I.I.T. Bombay, 1992.
[12]
{12} Peyton-Jones S. L. The Implementation of functional programming Languages, Prentice-Hall 1987.
[13]
{13} Peyton-Jones S. L. & Lester D., Implementing Functional Languages: a tutorial, Prentice-Hall 1992.
[14]
{14} Sestoft P., Analysis and Efficient Implementation of Functional Programs, Ph. D. Thesis, Department of Computer Science, Univ. of Copenhagen, 1991.
[15]
{15} Satpathy M., TIMER: TIM extended with registers (Under preparation), Dept. of Computer Science & Engineering, I.I.T. Bombay, 1995.
[16]
{16} Wray S.C. & Fairbairn J., Non-strict Languages - Programming and Implementation, The Computer Journal, vol. 32, no. 2, 1989, pp. 142-151.
Index Terms
- Rationalized three instruction machine
Recommendations
Rationalized three instruction machine
The declarative nature of functional programming languages causes many difficulties in their efficient implementation on conventional machines. The problem is much harder when the language has non-strict (lazy) semantics. Abstract machines serve as an ...
Formally deriving an STG machine
PPDP '03: Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programmingStarting from P. Sestoft semantics for lazy evaluation, we define a new semantics in which normal forms consist of variables pointing to lambdas or constructions. This is in accordance with the more recent changes in the Spineless Tagless G-machine (STG)...
Operational semantics-directed compilers and machine architectures
We consider the task of automatically constructing intermediate-level machine architectures and compilers generating code for these architectures, given operational semantics for source languages. We use operational semantics in the form of abstract ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1995 Authors.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 March 1995
Check for updates
Author Tags
Qualifiers
- Article
Conference
POPL95: 22nd ACM Symposium on Principles of Programming Languages
January 22, 1995
California, San Francisco, USA
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 388Total Downloads
- Downloads (Last 12 months)55
- Downloads (Last 6 weeks)9
Reflects downloads up to 07 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in