A semantic model of reference counting and its abstraction (detailed summary)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A semantic model of reference counting and its abstraction (detailed summary)

Full text

Pdf (917 KB)

Source

Conference on LISP and Functional Programming archive
Proceedings of the 1986 ACM conference on LISP and functional programming table of contents

Cambridge, Massachusetts, United States

Pages: 351 - 363

Year of Publication: 1986

ISBN:0-89791-200-4

Author

Paul Hudak

Yale University, Department of Computer Science, Box 2158 Yale Station, New Haven, CT

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 33, Citation Count: 61

Additional Information:

references cited by 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/319838.319876 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	Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
	2	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	3	C.A.R. Hoare. quicksort. Computing J., 5(4):10-15, April 1962.
	4	P. Hudak. Collecting interpretations of first-order lambda calculus. Research Report in preparation, Yale University, Department of Computer Science, 1986.
	5	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]
	6	Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
	7	A. Mycroft. Abstract Interpretation and Optimizing Transformations for Appli~otive Programs. PhD thesis, Univ. of Edinburgh, 1981.
	8	J. Schwarz. Verifying the safe use of destructive operations in applicative programs, in B. Robinet, editor, Program Transformations - Proc. of the $rd Int'l $ym. on Programming, pages 395-411, Dunod Informatique, 1978.

CITED BY 61

	C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States
	Greg Morrisett , Matthias Felleisen , Robert Harper, Abstract models of memory management, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.66-77, June 26-28, 1995, La Jolla, California, United States
	Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, A general data dependence test for dynamic, pointer-based data structures, ACM SIGPLAN Notices, v.29 n.6, p.218-229, June 1994
	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
	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
	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
	Alan Deutsch, On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-168, December 1989, San Francisco, California, United States
	Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France
	Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, ACM SIGPLAN Notices, v.31 n.6, p.213-225, June 15, 1996
	Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States
	Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999
	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
	David Cann , John Feo, SISAL versus FORTRAN: a comparison using the Livermore loops, Proceedings of the 1990 conference on Supercomputing, p.626-636, October 1990, New York, New York, United States
	Alan Demmers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States
	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
	A. V. S. Sastry , William Clinger , Zena Ariola, Order-of-evaluation analysis for destructive updates in strict functional languages with flat aggregates, Proceedings of the conference on Functional programming languages and computer architecture, p.266-275, June 09-11, 1993, Copenhagen, Denmark
	Paul Hudak , Jonathan Young, Collecting interpretations of expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.269-290, April 1991
	Alain Deutsch, Semantic models and abstract interpretation techniques for inductive data structures and pointers, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.226-229, June 21-23, 1995, La Jolla, California, United States
	David N. Turner , Philip Wadler , Christian Mossin, Once upon a type, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.1-11, June 26-28, 1995, La Jolla, California, United States
	Ole Agesen , David Detlefs , J. Eliot Moss, Garbage collection and local variable type-precision and liveness in Java virtual machines, ACM SIGPLAN Notices, v.33 n.5, p.269-279, May 1998
	Adrienne Bloss, Path analysis and the optimization of nonstrict functional languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.328-369, May 1994
	Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, ACM SIGPLAN Notices, v.34 n.10, p.20-34, Oct. 1999
	Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond k-limiting, ACM SIGPLAN Notices, v.29 n.6, p.230-241, June 1994
	Mads Tofte , Jean-Pierre Talpin, Implementation of the typed call-by-value λ-calculus using a stack of regions, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.188-201, January 16-19, 1994, Portland, Oregon, United States
	Yanhong A. Liu , Scott D. Stoller, From recursion to iteration: what are the optimizations?, ACM SIGPLAN Notices, v.34 n.11, p.73-82, Nov. 1999
	Saleh E. Abdullahi , Graem A. Ringwood, Garbage collecting the Internet: a survey of distributed garbage collection, ACM Computing Surveys (CSUR), v.30 n.3, p.330-373, Sept. 1998
	Bruno Blanchet, Escape analysis: correctness proof, implementation and experimental results, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-37, January 19-21, 1998, San Diego, California, United States
	Laurie J. Hendren , Alexandru Nicolau, Intererence analysis tools for parallelizing programs with recursive data structures, Proceedings of the 3rd international conference on Supercomputing, p.205-214, June 05-09, 1989, Crete, Greece
	P. Hudak , J. Young, A collecting interpretation of expressions, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.107-118, January 10-13, 1988, San Diego, California, United States
	Philip Wadler, Is there a use for linear logic?, ACM SIGPLAN Notices, v.26 n.9, p.255-273, Sept. 1991
	Steven Anderson , Paul Hudak, Compilation of Haskell array comprehensions for scientific computing, ACM SIGPLAN Notices, v.25 n.6, p.137-149, Jun. 1990
	Steven Anderson , Paul Hudak, Compilation of Haskell array comprehensions for scientific computing, ACM SIGPLAN Notices, v.25 n.6, p.137-149, Jun. 1990
	Sandip K. Biswas, In-place updates in the presence of control operators, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.283-293, July-Sept. 1994
	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
	Young Gil Park , Benjamin Goldberg, Reference escape analysis: optimizing reference counting based on the lifetime of references, ACM SIGPLAN Notices, v.26 n.9, p.178-189, Sept. 1991
	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
	D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, ACM SIGPLAN Notices, v.23 n.7, p.47-56, July 1988
	Jawahar Chirimar , Carl A. Gunter , Jon G. Riecke, Proving memory management invariants for a language based on linear logic, ACM SIGPLAN Lisp Pointers, v.V n.1, p.139-150, Jan. 1992
	Olin Shivers, The semantics of Scheme control-flow analysis, ACM SIGPLAN Notices, v.26 n.9, p.190-198, Sept. 1991
	L. J. Hendren , A. Nicolau, Parallelizing Programs with Recursive Data Structures, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.35-47, January 1990
	Bruno Blanchet, Escape analysis for Java^TM: Theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.713-775, November 2003
	O. Shivers, Control flow analysis in scheme, ACM SIGPLAN Notices, v.23 n.7, p.164-174, July 1988
	A. V. S. Sastry , William Clinger, Parallel destructive updating in strict functional languages, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.263-272, July-Sept. 1994
	David Chase , Mark Wegman , F. Ken Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Olin Shivers, Higher-order control-flow analysis in retrospect: lessons learned, lessons abandoned, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Zhonghua Li , Chris Kirkham, Efficient implementation of aggregates in united functions and objects, Proceedings of the 33rd annual on Southeast regional conference, March 17-18, 1995, Clemson, South Carolina
	Matthew Might , Olin Shivers, Environment analysis via ΔCFA, ACM SIGPLAN Notices, v.41 n.1, p.127-140, January 2006
	G. A. Venkatesh , Charles N. Fischer, SPARE: A Development Environment for Program Analysis Algorithms, IEEE Transactions on Software Engineering, v.18 n.4, p.304-318, April 1992
	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
	Henry G. Baker, Efficient implementation of bit-vector operation in Common Lisp, ACM SIGPLAN Lisp Pointers, v.III n.2-4, p.8-22, April-June 1990
	Pramod G. Joisha, Compiler optimizations for nondeferred reference: counting garbage collection, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Matthew Might, Logic-flow analysis of higher-order programs, ACM SIGPLAN Notices, v.42 n.1, January 2007
	Matthew Might , Olin Shivers, Improving flow analyses via ΓCFA: abstract garbage collection and counting, ACM SIGPLAN Notices, v.41 n.9, September 2006
	Giuseppe Amato , Fosca Giannotti , Gianni Mainetto, Data Sharing Analysis for a Database Programming Lanaguage via Abstract Interpretation, Proceedings of the 19th International Conference on Very Large Data Bases, p.405-415, August 24-27, 1993
	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
	Henry G. Baker, Shallow binding makes functional arrays fast, ACM SIGPLAN Notices, v.26 n.8, p.145-147, Aug. 1991
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994
	Mitchell Wand , William D. Clinger, Set constraints for destructive array update optimization, Journal of Functional Programming, v.11 n.3, p.319-346, May 2001
	Owen Kaser , C. R. Ramakrishnan , I. V. Ramakrishnan , R. C. Sekar, EQUALS – a fast parallel implementation of a lazy language, Journal of Functional Programming, v.7 n.2, p.183-217, March 1997
	Pramod G. Joisha, A principled approach to nondeferred reference-counting garbage collection, Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 05-07, 2008, Seattle, WA, USA
	Matthew Might , Olin Shivers, Exploiting reachability and cardinality in higher-order flow analysis, Journal of Functional Programming, v.18 n.5-6, p.821-864, September 2008

Collaborative Colleagues:

Paul Hudak: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player