Real-time deques, multihead Turing machines, and purely functional programming

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Real-time deques, multihead Turing machines, and purely functional programming

Full text

Pdf (1.09 MB)

Source

Functional Programming Languages and Computer Architecture archive
Proceedings of the conference on Functional programming languages and computer architecture table of contents

Copenhagen, Denmark

Pages: 289 - 298

Year of Publication: 1993

ISBN:0-89791-595-X

Authors

Tyng-Ruey Chuang
Benjamin Goldberg

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IFIP WG 2.8 : IFIP WG 2.8
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms review 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/165180.165225 What is a DOI?

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	A. Aasa , Sören Holmström , Christina Nilsson, An efficiency comparison of some representations of purely functional arrays, BIT, v.28 n.3, p.490-503, 1988
	2	Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
	3	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]
	4	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]
	5	Henry G. Baker, Shallow binding makes functional arrays fast, ACM SIGPLAN Notices, v.26 n.8, p.145-147, Aug. 1991 [doi>10.1145/122598.122614]
	6	Adrienne Gael Bloss. Path Analysis and the Optimization of Non-Strict Functional Languages. PhD thesis, Department of Computer Science, Yale University, May 1989. Also appears as report YALEU/DCS/RR-704.
	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	Adam L. Buchsbaum. Private communication, 1993.
	9	Adam L. Buchsbaum , Robert E. Tarjan, Confluently persistent deques via data structuaral bootstrapping, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.155-164, January 25-27, 1993, Austin, Texas, United States
	10	Tyng-Ruey Chuang, Fully persistent arrays for efficient incremental updates and voluminous reads, Symposium proceedings on 4th European symposium on programming, p.110-129, January 1992, Rennes, France
	11	James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
	12	James R. Driscoll , Daniel D. K. Sleator , Robert E. Tarjan, Fully persistent lists with catenation, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.89-99, January 28-30, 1991, San Francisco, California, United States
	13	Patrick C. Fischer , Albert R. Meyer , Arnold L. Rosenberg, Real-Time Simulation of Multihead Tape Units, Journal of the ACM (JACM), v.19 n.4, p.590-607, Oct. 1972 [doi>10.1145/321724.321726]
	14	H Gajewska , R E Tarjan, Deques with heap order, Information Processing Letters, v.22 n.4, p.197-200, April 1986 [doi>10.1016/0020-0190(86)90028-1]
	15	David Gries, The Science of Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	16	Juan C. Guzm~n and Paul Hudak. Single-threaded polymorphic lambda calculus. In Proceedings of 5th Annual IEEE Symposium on Logic in Computer Science, pages 333-343. IEEE, June 1990.
	17	Robert Hood and Robert Melville. Real-time queue operations in pure Lisp. Information Processing Letters, 13(2):50-53, 1981.
	18	Rob R. Hoogerwoord. A symmetric set of efficient list operations. Journal of Functional Programming, 2(4):505-513, October 1992.
	19	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]
	20	Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158524]
	21	Benton L. Leong , Joel I. Seiferas, New Real-Time Simulations of Multihead Tape Units, Journal of the ACM (JACM), v.28 n.1, p.166-180, Jan. 1981 [doi>10.1145/322234.322246]
	22	Eugene W. Myers. An applicative random-access stack. Information Processing Letters, 17(5):241-248, Decembet 1983.
	23	Eugene W. Myers, Efficient applicative data types, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.66-75, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800517]
	24	Martin Odersky, How to make destructive updates less destructive, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-36, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99590]
	25	Carl G. Ponder , Patrick McGeer , Anthony P-C. Ng, Are applicative languages inefficient?, ACM SIGPLAN Notices, v.23 n.6, p.135-139, June, 1988 [doi>10.1145/44546.44559]
	26	Neil Ivor Sarnak, Persistent data structures, 1986
	27	Berry Schoenmakers. Data Structures and Amortized Complexity in a Functional Setting. PhD thesis, Deaprtment of Mathematics and Computing Science, Eindhoven University of Technology, September 1992.
	28	J. T. Schwartz. Optimization of very high level languages- i. value transmission and its coroHaxies. Compurer Languages, 1(2):161-194, June 1975.
	29	J. T. Schwartz. Optimization of very high level languages- ii. deducing relationships of inclusion and membership. Computer Languages, 1(3):197-218, September 1975.
	30	Robert Endre Tarjan. Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods, 6(2):306-318, April 1985.
	31	Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France [doi>10.1145/91556.91592]
	32	Philip Wadler, Is there a use for linear logic?, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.255-273, June 17-19, 1991, New Haven, Connecticut, United States

CITED BY 12

	Haim Kaplan , Robert E. Tarjan, Purely functional, real-time deques with catenation, Journal of the ACM (JACM), v.46 n.5, p.577-603, Sept. 1999
	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
	Chris Okasaki, The role of lazy evaluation in amortized data structures, ACM SIGPLAN Notices, v.31 n.6, p.62-72, June 15, 1996
	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, Catenable double-ended queues, ACM SIGPLAN Notices, v.32 n.8, p.66-74, Aug. 1997
	Tyng-Ruey Chuang, A randomized implementation of multiple functional arrays, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.173-184, July-Sept. 1994
	Haim Kaplan , Robert E. Tarjan, Persistent lists with catenation via recursive slow-down, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.93-102, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Shin-Cheng Mu , Richard Bird, Theory and applications of inverting functions as folds, Science of Computer Programming, v.51 n.1-2, p.87-116, May 2004
	George Lagogiannis , Yannis Panagis , Spyros Sioutas , Athanasios Tsakalidis, A survey of persistent data structures, Proceedings of the 9th WSEAS International Conference on Computers, p.1-6, July 14-16, 2005, Athens, Greece
	Martin Erwig, Inductive graphs and functional graph algorithms, Journal of Functional Programming, v.11 n.5, p.467-492, September 2001
	Graeme E. Moss , Colin Runciman, Inductive benchmarking for purely functional data structures, Journal of Functional Programming, v.11 n.5, p.525-556, September 2001
	Shin-Cheng Mu, Maximum segment sum is back: deriving algorithms for two segment problems with bounded lengths, Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 07-08, 2008, San Francisco, California, USA

INDEX TERMS

Primary Classification:
D. Software
D.1 PROGRAMMING TECHNIQUES

Additional Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.2 Language Classifications
Subjects: Applicative (functional) languages
D.3.3 Language Constructs and Features
Subjects: Data types and structures

F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.1 Models of Computation
Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

General Terms:
Algorithms, Languages, Performance

REVIEW

"Zoran D. Budimac : Reviewer"

The authors describe an implementation of a real-time double-ended queue (deque) in a (strict) purely functional language. Deques are called “real-time” if every push or pop operation on either side of the deque is acco more...

Collaborative Colleagues:

Tyng-Ruey Chuang: colleagues

Benjamin Goldberg: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player