Selective and lightweight closure conversion

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Selective and lightweight closure conversion

Full text

Pdf (909 KB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Portland, Oregon, United States

Pages: 435 - 445

Year of Publication: 1994

ISBN:0-89791-636-0

Authors

Mitchell Wand	College of Computer Science, Northeastern University, 360 Huntington Avenue, 161CN, Boston, MA
Paul Steckler	College of Computer Science, Northeastern University, 360 Huntington Avenue, 161CN, Boston, MA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 15, Citation Count: 22

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/174675.178044 What is a DOI?

ABSTRACT

We consider the problem of selective and lightweight closure conversion, in which multiple procedure-calling protocols may coexist in the same code. Flow analysis is used to match the protocol expected by each procedure and the protocol used at each of its possible call sites. We formulate the flow analysis as the solution of a set of constraints, and show that any solution to the constraints justifies the resulting transformation. Some of the techniques used are suggested by those of abstract interpretation, but others arise out of alternative approaches.

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	Martin Abadi, Luca Cardelli, Pierre-Louis Curien, and Jean-Jacques Levy. Explicit Substitutions. Journal of Functional Programming, 1(4):375-417, October 1991.
	2	Alex Aiken , Brian Murphy, Static type inference in a dynamically typed language, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.279-290, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99621]
	3	Alexander Aiken and Edward L. Wimmers. Solving Systems of Set Constraints (Extended Abstract). In Proc. 7th IEEE Symposium on Logic ~n Computer Science, pages 329-340, 1992.
	4	Andrew W. Appel. Compzhng w~th Contznuatzons. Cambridge University Press, Cambridge, 1992.
	5	A. W. Appel , T. Jim, Continuation-passing, closure-passing style, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.293-302, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75303]
	6	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 [doi>10.1145/96709.96725]
	7	B. Goldberg , Y. G. Park, Higher order escape analysis: optimizing stack allocation in functional program implementations, Proceedings of the third European symposium on programming on ESOP '90, p.152-160, May 1990, Copenhagen, Denmark
	8	Nevin Charles Heintze, Set based program analysis, Carnegie Mellon University, Pittsburgh, PA, 1992
	9	Neil D. Jones, Flow Analysis of Lambda Expressions (Preliminary Version), Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.114-128, July 13-17, 1981
	10	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]
	11	Jens Palsberg , Michael I. Schwartzbach, Safety analysis versus type inference, Information and Computation, v.118 n.1, p.128-141, April 1995 [doi>10.1006/inco.1995.1058]
	12	Gordon D. Plotkin. Call-by-Name, Call-by-Value and the )~-Calculus. Theoretical Computer Science, 1:125- 159, 1975.
	13	Peter Sestoft. Replacing Function Parameters by Global Variables. Master's thesis, DIKU, University of Copenhagen, October 1988.
	14	Peter Sestoft. Analysis and Efficient Implementation of Functional Programs. PhD thesis, DIKU, University of Copenhagen, October 1991.
	15	Olin Shivers. Control-Flow Analysis o/ Higher-Order Languages. PhD thesis, Carnegie-Mellon University, May 1991.
	16	Mitchell Wand, Correctness of Procedure Representations in Higher-Order Assembly Language, Proceedings of the 7th International Conference on Mathematical Foundations of Programming Semantics, p.294-311, March 25-28, 1991
	17	Mitchell Wand, Specifying the correctness of binding-time analysis, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.137-143, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158614]
	18	Mitchell Wand , Dino P. Oliva, Proving the correctness of storage representations, Proceedings of the 1992 ACM conference on LISP and functional programming, p.151-160, June 22-24, 1992, San Francisco, California, United States

CITED BY 22

	Jens Palsberg , Patrick O'Keefe, A type system equivalent to flow analysis, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.367-378, January 23-25, 1995, San Francisco, California, United States
	William D. Clinger , Lars Thomas Hansen, Lambda, the ultimate label or a simple optimizing compiler for Scheme, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.128-139, July-Sept. 1994
	J. Michael Ashley, A practical and flexible flow analysis for higher-order languages, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-194, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Kirsten L. Solberg Gasser , Flemming Nielson , Hanne Riis Nielson, Systematic realisation of control flow analyses for CML, ACM SIGPLAN Notices, v.32 n.8, p.38-51, Aug. 1997
	Paul A. Steckler , Mitchell Wand, Lightweight closure conversion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.1, p.48-86, Jan. 1997
	Jens Palsberg , Christina Pavlopoulou, From polyvariant flow information to intersection and union types, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.197-208, January 19-21, 1998, San Diego, California, United States
	Dan Stefanescu , Yuli Zhou, An equational framework for the flow analysis of higher order functional programs, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.318-327, July-Sept. 1994
	Jens Palsberg, Closure analysis in constraint form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.47-62, Jan. 1995
	Flemming Nielson , Hanne Riis Nielson, Infinitary control flow analysis: a collecting semantics for closure analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.332-345, January 15-17, 1997, Paris, France
	Zhong Shao , Andrew W. Appel, Efficient and safe-for-space closure conversion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.1, p.129-161, Jan. 2000
	Olivier Danvy , Ulrik P. Schultz, Lambda-dropping: transforming recursive equations into programs with block structure, ACM SIGPLAN Notices, v.32 n.12, p.90-106, Dec. 1997
	Allyn Dimock , Robert Muller , Franklyn Turbak , J. B. Wells, Strongly typed flow-directed representation transformations (extended abstract), ACM SIGPLAN Notices, v.32 n.8, p.11-24, Aug. 1997
	Jens Palsberg , Patrick O'Keefe, A type system equivalent to flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.4, p.576-599, July 1995
	Yasuhiko Minamide , Greg Morrisett , Robert Harper, Typed closure conversion, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.271-283, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Matthew Might , Olin Shivers, Environment analysis via ΔCFA, ACM SIGPLAN Notices, v.41 n.1, p.127-140, January 2006
	Allyn Dimock , Ian Westmacott , Robert Muller , Franklyn Turbak , J. B. Wells, Functioning without closure: type-safe customized function representations for standard ML, ACM SIGPLAN Notices, v.36 n.10, October 2001
	Matthew Might , Olin Shivers, Improving flow analyses via ΓCFA: abstract garbage collection and counting, ACM SIGPLAN Notices, v.41 n.9, September 2006
	Matthew Might , Olin Shivers, Analyzing the environment structure of higher-order languages using frame strings, Theoretical Computer Science, v.375 n.1-3, p.137-168, May, 2007
	David A. Schmidt, Trace-Based Abstract Interpretation of Operational Semantics, Lisp and Symbolic Computation, v.10 n.3, p.237-271, May 1998
	Jens Palsberg , Christina Pavlopoulou, From Polyvariant flow information to intersection and union types, Journal of Functional Programming, v.11 n.3, p.263-317, May 2001
	J. B. Wells , Allyn Dimock , Robert Muller , Franklyn Turbak, A calculus with polymorphic and polyvariant flow types, Journal of Functional Programming, v.12 n.3, p.183-227, May 2002
	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