Some practical methods for rapid combinator reduction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some practical methods for rapid combinator reduction

Full text

Pdf (632 KB)

Source

Conference on LISP and Functional Programming archive
Proceedings of the 1984 ACM Symposium on LISP and functional programming table of contents

Austin, Texas, United States

Pages: 159 - 166

Year of Publication: 1984

ISBN:0-89791-142-3

Authors

W. R. Stoye
T. J. W. Clarke
A. C. Norman

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 32, Citation Count: 21

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800055.802032 What is a DOI?

ABSTRACT

The SKIM II processor is a microcoded hardware machine for the rapid evaluation of functional languages. This paper gives details of some of the more novel methods employed by SKIM II, and resulting performance measurements. The authors conclude that combinator reduction can still form the basis for the efficient implementation of a functional language.

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	T. J.W. Clarke , P. J.S. Gladstone , C. D. MacLean , A. C. Norman, SKIM - The S, K, I reduction machine, Proceedings of the 1980 ACM conference on LISP and functional programming, p.128-135, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802798]
	2	CORPORATE Motorola, Inc. Staff, MC 68000 16-Bit Microprocessor User's Manual, Prentice Hall PTR, Upper Saddle River, NJ, 1982
	3	Conference record of the 1982 ACM Symposium on Lisp and Functional Programming, August 15-18, 1982, ACM order no 552820
	4	R. J. M. Hughes, Super-combinators a new implementation method for applicative languages, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.1-10, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802129]
	5	J. Fairbairn, Ponder and its Type System, Cambridge University Computer Laboratory Technical Note, 1982.
	6	D. A. Turner, A New Implementation Technique for Applicative Languages, Software Practice and Experience, Volume 19, pp 31-34, 1979.
	7	A. Mycroft, Abstract Interpretation and Optimising Transformations for Applicative Programs, University of Edinburgh Dept. of Comp. Science, 1981.
	8	E. Goto, Monocopy and Associative Algorithms in an Extended Lisp, University of Tokyo, Japan, May 1974.
	9	H. Schorr , W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM, v.10 n.8, p.501-506, Aug. 1967 [doi>10.1145/363534.363554]
	10	W. R. Stoye, The SKIM II Microprogrammer's Guide, Cambridge University Computer Laboratory Technical Note, 1983.
	11	W. R. Stoye, An Operating System written in a Purely Functional Language, document in preparation.

CITED BY 21

	Lal George, An abstract machine for parallel graph reduction, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.214-229, September 11-13, 1989, Imperial College, London, United Kingdom
	Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, ACM SIGPLAN Notices, v.36 n.11, p.367-380, 11/01/2001
	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
	David J. Roth , David S. Wise, One-bit counts between unique and sticky, ACM SIGPLAN Notices, v.34 n.3, p.49-56, March 1999
	Mark Scheevel, NORMA: a graph reduction processor, Proceedings of the 1986 ACM conference on LISP and functional programming, p.212-219, August 1986, Cambridge, Massachusetts, United States
	Paul Griffin , Witawas Srisa-an , J. Morris Chang, An energy efficient garbage collector for java embedded devices, ACM SIGPLAN Notices, v.40 n.7, July 2005
	Simon B. Jones , Daniel Le Métayer, Compile-time garbage collection by sharing analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.54-74, September 11-13, 1989, Imperial College, London, United Kingdom
	John D. Ramsdell, The CURRY chip, Proceedings of the 1986 ACM conference on LISP and functional programming, p.122-131, August 1986, Cambridge, Massachusetts, United States
	Chris Clack , Simon L. Peyton Jones, The four-stroke reduction engine, Proceedings of the 1986 ACM conference on LISP and functional programming, p.220-232, August 1986, Cambridge, Massachusetts, United States
	David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.25 n.6, p.296-310, Jun. 1990
	Hans-J. Boehm, The space cost of lazy reference counting, ACM SIGPLAN Notices, v.39 n.1, p.210-219, January 2004
	David Chase , Mark Wegman , F. Ken Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Witawas Srisa-an , Chia-Tien Dan Lo , Ji-en Morris Chang, Active Memory Processor: A Hardware Garbage Collector for Real-Time Java Embedded Devices, IEEE Transactions on Mobile Computing, v.2 n.2, p.89-101, January 2003
	Paul Griffin , Witawas Srisa-An , J. Morris Chang, On designing a low-power garbage collector for java embedded devices: a case study, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Yossi Levanoni , Erez Petrank, An on-the-fly reference-counting garbage collector for java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.1, p.1-69, January 2006
	Henry G. Baker, “Use-once” variables and linear objects: storage management, reflection and multi-threading, ACM SIGPLAN Notices, v.30 n.1, p.45-52, Jan. 1995
	Paul Hudak , John Hughes , Simon Peyton Jones , Philip Wadler, A history of Haskell: being lazy with class, Proceedings of the third ACM SIGPLAN conference on History of programming languages, p.12-1-12-55, June 09-10, 2007, San Diego, California
	Jon Fairbairn , Stuart C. Wray, Code generation techniques for functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.94-104, August 1986, Cambridge, Massachusetts, United States
	M. Lemaître , M. Castan , M.-H. Durand , G. Durrieu , B. Lecussan, Mechanisms for efficient multiprocessor combinator reduction, Proceedings of the 1986 ACM conference on LISP and functional programming, p.113-121, August 1986, Cambridge, Massachusetts, United States
	Henry G. Baker, Minimizing reference count updating with deferred and anchored pointers for functional data structures, ACM SIGPLAN Notices, v.29 n.9, p.38-43, Sept. 1994
	Melissa E. O'Neill , F. Warren Burton, A new method for functional arrays, Journal of Functional Programming, v.7 n.5, p.487-513, September 1997