|
 ABSTRACT
There is a growing interest nowadays in functional programming languages and systems, and in special hardware for executing them. Many of these implementations are based on a system called graph reduction (GR), in which a program is represented as a graph which is transformed, or reduced, by the machine until it represents the desired answer. The various graph reduction implementations differ in the structure of the “machine code” (the program graph) and the compilation algorithms necessary to produce it from a source language. This paper describes a new implementation method using super-combinators which is apparently more efficient than its predecessors. Consideration of the new method also helps clarify the relationships between several other graph-reduction schemes. This paper is necessarily brief, but a fuller account can be found in [Hughes]. The simplest machine language we shall consider consists of constants combined by function application. This is the language of constant applicative forms (cafs). Some of the constants are basic functions.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
H.B.Curry & R.Feys: "Combinatory Logic", North-Holland Publishing Company, Amsterdam, 1958.
|
 |
2
|
|
| |
3
|
R.J.M.Hughes: "Graph-Reduction with Super-combinators". Oxford University Programming Research Group technical monograph PRG-28 (to appear).
|
| |
4
|
D.A.Turner: "A New Implementation Technique for Applicative Languages", Software. Practice and Experience, Vol. 9, 1979.
|
CITED BY 33
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A. Guha , R. Ramnarayan , M. Derstine, Architectural issues in designing symbolic processors in optics, Proceedings of the 14th annual international symposium on Computer architecture, p.145-151, June 02-05, 1987, Pittsburgh, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lennart Augustsson , Thomas Johnsson, Parallel graph reduction with the (v , G)-machine, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.202-213, September 11-13, 1989, Imperial College, London, United Kingdom
|
|
|
W. R. Stoye , T. J. W. Clarke , A. C. Norman, Some practical methods for rapid combinator reduction, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.159-166, August 06-08, 1984, Austin, Texas, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.2