NDLI: A fixed-program machine for combinator expression evaluation

Please wait, while we are loading the content...

Super-combinators a new implementation method for applicative languages

A fixed-program machine for combinator expression evaluation

Expressions as processes

Combinatory foundation of functional programming

Functional specifications of a text editor

Experiments with a supercompiler

A parallel Prolog: The construction of a data driven model

How to define a language using PROLOG

Logic enhancement: A method for extending logic programming languages

Implementation of Interlisp on the VAX

PSL: A Portable LISP System

An overview of COMMON LISP

S-1 Common Lisp implementation

T: a dialect of Lisp or LAMBDA: The ultimate software tool

Performance of Lisp systems

Prolog compared with LISP

An investigation of the relative efficiencies of combinators and lambda expressions

Improved effectiveness from a real time LISP garbage collector

Garbage collection and task deletion in distributed applicative processing systems

Functional geometry

A scheme for implementing functional values on a stack machine

Constant time interpretation for shallow-bound variables in the presence of mixed special/local declarations

Data sharing in an FFP machine

Design of a Lisp machine - FLATS

Highlights of the history of the lambda-calculus

Nondeterministic call by need is neither lazy nor by name

Toward an algebra of nondeterministic programs

A semantic model of types for applicative languages

The semantics of lazy (and industrious) evaluation

A fixed-program machine for combinator expression evaluation

Content Provider	ACM Digital Library
Author	Jones, Neil D. Muchnick, Steven S.
Abstract	It is our purpose here to present an alternative evaluation mechanism for combinator expressions, namely a relatively straightforward compilation algorithm which translates combinators to fixed-program code for a stack machine. The resulting code is faithful to Turner's use of non-strict functions, in that it performs normal order evaluation. We show how this code can be made more efficient by performing call-by-need evaluation (without changing the semantics of the language) and consider some flow-analysis-based optimizations, as well. The remainder of this paper is organized as follows: We first review (briefly) Turner's arguments in favor of using combinators and how to translate function definitions to combinator expressions in Section 2. Next, in Section 3, we present our translation of combinator expressions to call-by-name stack machine code and the evaluation of a simple program in our model. In Section 4 we show how to eliminate repeated evaluation of argument expressions (or, equivalently, optimize evaluation of S combinator expressions) by using call by need. In Section 5 we consider flow-analysis-based optimizations which can significantly improve the code generated by the naive algorithms of Sections 3 and 4. Finally, Section 6 presents conclusions and suggestions for further work in this area.
Starting Page	11
Ending Page	20
Page Count	10
File Format	PDF
ISBN	0897910826
DOI	10.1145/800068.802130
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1982-08-15
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in