Shallow binding makes functional arrays fast

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shallow binding makes functional arrays fast

Full text

Pdf (300 KB)

Source

ACM SIGPLAN Notices archive
Volume 26 , Issue 8 (August 1991) table of contents

Pages: 145 - 147

Year of Publication: 1991

ISSN:0362-1340

Author

Henry G. Baker

Nimble Computer Corporation, 16231 Meadow Ridge Way, Encino, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 18, Citation Count: 11

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/122598.122614 What is a DOI?

ABSTRACT

Access and update for random elements of arrays in imperative programming languages are O(1) operations. Implementing functional programming languages to achieve equivalent efficiency has proved difficult. We show how the straight-forward application of shallow binding to functional arrays automatically achieves O(1) update for single-threaded usage.

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	Arvind , Rishiyur S. Nikhil , Keshav Pingali, I-structures: Data structures for parallel computing, Proceedings of the Workshop on Graph Reduction, p.336-369, September 29-October 01, 1986
	2	Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
	3	Henry G. Baker, Jr., Shallow binding in Lisp 1.5, Communications of the ACM, v.21 n.7, p.565-569, July 1978 [doi>10.1145/359545.359566]
	4	Henry G. Baker, Unify and conquer, Proceedings of the 1990 ACM conference on LISP and functional programming, p.218-226, June 27-29, 1990, Nice, France [doi>10.1145/91556.91652]
	5	Baker, Henry. "Worlds in Collision: A Mostly Functional Model of Concurrency Control and Recovery". Tech. Memo, Nimble Computer Corp., 1990, 14p.
	6	Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
	7	Adrienne Bloss, Update analysis and the efficient implementation of functional aggregates, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.26-38, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99373]
	8	Eriksson, Lars-Henrik and Rayner, Manny. "Incorporating Mutable Arrays into Logic Programming". Proc. 1984 Logic Programming Conference, 101-114.
	9	Kourosh Gharachorloo , Vivek Sarkar , John L. Hennessy, A simple and efficient implmentation approach for single assignment languages, Proceedings of the 1988 ACM conference on LISP and functional programming, p.259-268, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62718]
	10	K. Gopinath , J. L. Hennessy, Copy elimination in functional languages, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.303-314, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75304]
	11	Hanson, Christopher, and Lamping, John. "Dynamic Binding in Scheme". Unpublished manuscript, 1984.
	12	Chris Hanson, Efficient stack allocation for tail-recursive languages, Proceedings of the 1990 ACM conference on LISP and functional programming, p.106-118, June 27-29, 1990, Nice, France [doi>10.1145/91556.91603]
	13	Christopher T. Haynes , Daniel P. Friedman, Embedding continuations in procedural objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.582-598, Oct. 1987 [doi>10.1145/29873.30392]
	14	Hederman, Lucy. Compile Time Garbage Collection. MS Thesis, Rice Univ. Comp. Sci. Dept., Sept. 1988.
	15	Paul Hudak , Adrienne Bloss, The aggregate update problem in functional programming systems, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.300-314, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318660]
	16	Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
	17	Lampson, B. W., and Sturgis, H. E. "Crash Recovery in a Distributed Storage System". Unpublished paper, Xerox PARC, Palo Alto, 1976.
	18	John T. O'Donnell, An architecture that efficiently updates associative aggregates in applicative programming languages, Proc. of a conference on Functional programming languages and computer architecture, p.164-189, January 1985, Nancy, France
	19	Polya, G. How to Solve It: A New Aspect of Mathematical Method, 2nd Ed. Princeton U. Press, Princeton, NJ, 1957.
	20	Schwartz, J. T. "Optimization of very high level languages-I. Value transmission and its corollaries". J. Computer Lang. 1 (1975), 161-194.
	21	Schwartz, J. T. "Optimization of very high level languages-II. Deducing relationships of inclusion and membership". J. Computer Lang. 1, 3 (1975), 197-218.
	22	Guy Steele, Common Lisp: The Language, Digital Press, Newton, MA, 1990

CITED BY 11

	Tyng-Ruey Chuang , Wen L. Hwang, A probabilistic approach to the problem of automatic selection of data representations, ACM SIGPLAN Notices, v.31 n.6, p.190-200, June 15, 1996
	Chris Okasaki, Purely functional random-access lists, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.86-95, June 26-28, 1995, La Jolla, California, United States
	Tyng-Ruey Chuang, A randomized implementation of multiple functional arrays, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.173-184, July-Sept. 1994
	Tyng-Ruey Chuang , Benjamin Goldberg, Real-time deques, multihead Turing machines, and purely functional programming, Proceedings of the conference on Functional programming languages and computer architecture, p.289-298, June 09-11, 1993, Copenhagen, Denmark
	Oleg Kiselyov , Chung-chieh Shan , Amr Sabry, Delimited dynamic binding, ACM SIGPLAN Notices, v.41 n.9, September 2006
	Henry G. Baker, Lively linear Lisp: “look ma, no garbage!”, ACM SIGPLAN Notices, v.27 n.8, p.89-98, Aug. 1992
	Henry G. Baker, Equal rights for functional objects or, the more things change, the more they are the same, ACM SIGPLAN OOPS Messenger, v.4 n.4, p.2-27, Oct. 1993
	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
	Sven-Bodo Scholz, Single Assignment C: efficient support for high-level array operations in a functional setting, Journal of Functional Programming, v.13 n.6, p.1005-1059, November 2003
	Sylvain Conchon , Jean-Christophe Filliâtre, A persistent union-find data structure, Proceedings of the 2007 workshop on Workshop on ML, October 05-05, 2007, Freiburg, Germany
	Pascal Costanza, Context-oriented programming in ContextL: state of the art, Celebrating the 50th Anniversary of Lisp, p.1-5, October 20-20, 2008, Nashville, Tennessee