Polymorphic effect systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Polymorphic effect systems

Full text

Pdf (1.02 MB)

Source

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

San Diego, California, United States

Pages: 47 - 57

Year of Publication: 1988

ISBN:0-89791-252-7

Authors

J. M. Lucassen	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts
D. K. Gifford	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 68, Citation Count: 79

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

ABSTRACT

We present a new approach to programming languages for parallel computers that uses an effect system to discover expression scheduling constraints. This effect system is part of a 'kinded' type system with three base kinds: types, which describe the value that an expression may return; effects, which describe the side-effects that an expression may have; and regions, which describe the area of the store in which side-effects may occur. Types, effects and regions are collectively called descriptions. Expressions can be abstracted over any kind of description variable -- this permits type, effect and region polymorphism. Unobservable side-effects can be masked by the effect system; an effect soundness property guarantees that the effects computed statically by the effect system are a conservative approximation of the actual side-effects that a given expression may have. The effect system we describe performs certain kinds of side-effect analysis that were not previously feasible. Experimental data from the programming language FX indicate that an effect system can be used effectively to compile programs for parallel computers.

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.

	Arv87	t,~xecuting a Program on the MIT Tagged- Token Dataflow Architecture, Arvind, Rishiyur S. Nikhil, MIT LCS Computation Structures Group Memo No. 271 (March 1987)
	Ban79	John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
	Bar78	Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
	Gif86	David K. Gifford , John M. Lucassen, Integrating functional and imperative programming, Proceedings of the 1986 ACM conference on LISP and functional programming, p.28-38, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319848]
	Gif87	FX-87 Reference Manual, David K. Gifford et al.~ MIT LCS TR-409, MIT Laboratory for Computer Science, September 1987.
	Fel87	M. Felleisen , D. P. Friedman, A calculus for assignments in higher-order languages, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.314, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41654]
	Lam77	B. W. Lampson , J. J. Horning , R. L. London , J. G. Mitchell , G. J. Popek, Report on the programming language Euclid, ACM SIGPLAN Notices, v.12 n.2, p.1-79, February 1977 [doi>10.1145/954666.971189]
	Luc87	Types and Effects ~ Towards the Integration of Functional and Imperative Programming, John M. Lucassen, Ph. D. Thesis, MIT Laboratory for Computer Science LCS TR-408 (August 1987)
	McC79	An Investigation of a Programming Language with a Polymorphic Type Structure, Nancy Jean McCracken, Ph.D. Thesis, Syracuse University School of Computer and Information Science (June 1979)
	Nei87	A. Neirynck , A. J. Demers, Computation of aliases and support sets, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.274-283, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41650]
	Pop77	G. J. Popek , J. J. Horning , B. W. Lampson , J. G. Mitchell , R. L. London, Notes on the design of Euclid, Proceedings of an ACM conference on Language design for reliable software, p.11-18, March 28-30, 1977, Raleigh, North Carolina
	Rey74	John C. Reynolds, Towards a theory of type structure, Programming Symposium, Proceedings Colloque sur la Programmation, p.408-423, April 09-11, 1974
	Rey78	John C. Reynolds, Syntactic control of interference, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.39-46, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512766]
	Ste78	Rabbit: A Compiler ~or Scheme (A Study in Compiler Optimization), AI-TR-474, MIT AI Laboratory, May 1978.
	Tra86	A Compiler for the MIT Tagged-Token Dataflow Architecture, Kenneth R. Traub, S.M. Thesis, MIT Laboratory for Computer Science (August, 1987)
	Wei80	William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]

CITED BY 79

	P. Jouvelot , D. K. Gifford, Reasoning about continuations with control effects, ACM SIGPLAN Notices, v.24 n.7, p.218-226, July 1989
	Hayo Thielecke, From control effects to typed continuation passing, ACM SIGPLAN Notices, v.38 n.1, p.139-149, January 2003
	H.-J. Boehm, Type inference in the presence of type abstraction, ACM SIGPLAN Notices, v.24 n.7, p.192-206, July 1989
	Cormac Flanagan , Stephen N. Freund, Detecting race conditions in large programs, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.90-96, June 2001, Snowbird, Utah, United States
	Ian A. Mason , Carolyn L. Talcott, Program transformations for configuring components, ACM SIGPLAN Notices, v.26 n.9, p.297-308, Sept. 1991
	Suresh Jagannathan , Stephen Weeks, Analyzing stores and references in a parallel symbolic language, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.294-305, July-Sept. 1994
	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
	Vincent Dornic , Pierre Jouvelot , David K. Gifford, Polymorphic time systems for estimating program complexity, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.33-45, March 1992
	David F. Bacon , Robert E. Strom , Ashis Tarafdar, Guava: a dialect of Java without data races, ACM SIGPLAN Notices, v.35 n.10, p.382-400, Oct. 2000
	Xavier Leroy , Pierre Weis, Polymorphic type inference and assignment, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.291-302, January 21-23, 1991, Orlando, Florida, United States
	Pierre Jouvelot , David Gifford, Algebraic reconstruction of types and effects, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.303-310, January 21-23, 1991, Orlando, Florida, 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
	John Hogg, Islands: aliasing protection in object-oriented languages, ACM SIGPLAN Notices, v.26 n.11, p.271-285, Nov. 1991
	Lorenz Huelsbergen , James R. Larus, Dynamic program parallelization, ACM SIGPLAN Lisp Pointers, v.V n.1, p.311-323, Jan. 1992
	Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, Abstract description of pointer data structures: an approach for improving the analysis and optimization of imperative programs, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.243-260, Sept. 1992
	Daniel Jackson, Abstract analysis with aspect, ACM SIGSOFT Software Engineering Notes, v.18 n.3, p.19-27, July 1993
	Sophia Drossopoulou , Ferruccio Damiani , Mariangiola Dezani-Ciancaglini , Paola Giannini, More dynamic object reclassification: Fickle∥, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.2, p.153-191, March 2002
	Brian Reistad , David K. Gifford, Static dependent costs for estimating execution time, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.65-78, July-Sept. 1994
	Hanne Riis Nielson , Flemming Nielson, Higher-order concurrent programs with finite communication topology (extended abstract), Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.84-97, January 16-19, 1994, Portland, Oregon, United States
	David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, ACM SIGPLAN Notices, v.33 n.10, p.48-64, Oct. 1998
	Lars Birkedal , Mads Tofte , Magnus Vejlstrup, From region inference to von Neumann machines via region representation inference, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.171-183, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	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
	Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Using types to analyze and optimize object-oriented programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.30-72, Jan. 2001
	Xavier Leroy , François Pessaux, Type-based analysis of uncaught exceptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.340-377, March 2000
	Matthias Felleisen, &lgr;-V-CS: an extended &lgr;-calculus for scheme, Proceedings of the 1988 ACM conference on LISP and functional programming, p.72-85, July 25-27, 1988, Snowbird, Utah, United States
	Mads Tofte , Lars Birkedal, A region inference algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.4, p.724-767, July 1998
	Jeffrey S. Foster , Tachio Terauchi , Alex Aiken, Flow-sensitive type qualifiers, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Cormac Flanagan , Stephen N. Freund, Type-based race detection for Java, ACM SIGPLAN Notices, v.35 n.5, p.219-232, May 2000
	Jeffrey S. Foster , Manuel Fähndrich , Alexander Aiken, A theory of type qualifiers, ACM SIGPLAN Notices, v.34 n.5, p.192-203, May 1999
	François Pessaux , Xavier Leroy, Type-based analysis of uncaught exceptions, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.276-290, January 20-22, 1999, San Antonio, Texas, United States
	Dave Clarke , Sophia Drossopoulou, Ownership, encapsulation and the disjointness of type and effect, ACM SIGPLAN Notices, v.37 n.11, November 2002
	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
	John Whaley , Michael C. Martin , Monica S. Lam, Automatic extraction of object-oriented component interfaces, ACM SIGSOFT Software Engineering Notes, v.27 n.4, July 2002
	Philip Wadler , Peter Thiemann, The marriage of effects and monads, ACM Transactions on Computational Logic (TOCL), v.4 n.1, p.1-32, January 2003
	Guillermo Juan Rozas, Taming the Y operator, ACM SIGPLAN Lisp Pointers, v.V n.1, p.226-234, Jan. 1992
	Daniel Jackson, Aspect: detecting bugs with abstract dependences, ACM Transactions on Software Engineering and Methodology (TOSEM), v.4 n.2, p.109-145, April 1995
	Michael Hanus , Frank Steiner, Type-based nondeterminism checking in functional logic programs, Proceedings of the 2nd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.202-213, September 20-23, 2000, Montreal, Quebec, Canada
	Alex Aiken , Jeffrey S. Foster , John Kodumal , Tachio Terauchi, Checking and inferring local non-aliasing, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Jens Palsberg, Type-based analysis and applications, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.20-27, June 2001, Snowbird, Utah, United States
	Jon G. Riecke , Ramesh Viswanathan, Isolating side effects in sequential languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-12, January 23-25, 1995, San Francisco, California, United States
	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
	Chandrasekhar Boyapati , Robert Lee , Martin Rinard, Ownership types for safe programming: preventing data races and deadlocks, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Chandrasekhar Boyapati , Barbara Liskov , Liuba Shrira, Ownership types for object encapsulation, ACM SIGPLAN Notices, v.38 n.1, p.213-223, January 2003
	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
	Torben Amtoft , Robert Muller, Inferring annotated types for inter-procedural register allocation with constructor flattening, ACM SIGPLAN Notices, v.38 n.3, March 2003
	Martin Abadi , Cormac Flanagan , Stephen N. Freund, Types for safe locking: Static race detection for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.2, p.207-255, March 2006
	Hayo Thielecke, Frame rules from answer types for code pointers, ACM SIGPLAN Notices, v.41 n.1, p.309-319, January 2006
	Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Chandrasekhar Boyapati , Barbara Liskov , Liuba Shrira , Chuang-Hue Moh , Steven Richman, Lazy modular upgrades in persistent object stores, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Mark A. Sheldon , David K. Gifford, Static dependent types for first class modules, Proceedings of the 1990 ACM conference on LISP and functional programming, p.20-29, June 27-29, 1990, Nice, France
	Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, ACM SIGPLAN Notices, v.36 n.11, p.56-69, 11/01/2001
	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
	Paul Hudak, Conception, evolution, and application of functional programming languages, ACM Computing Surveys (CSUR), v.21 n.3, p.359-411, Sep. 1989
	Dan Grossman, Type-safe multithreading in cyclone, ACM SIGPLAN Notices, v.38 n.3, March 2003
	Adrian Birka , Michael D. Ernst, A practical type system and language for reference immutability, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Mads Tofte , Lars Birkedal , Martin Elsman , Niels Hallenberg, A Retrospective on Region-Based Memory Management, Higher-Order and Symbolic Computation, v.17 n.3, p.245-265, September 2004
	Cormac Flanagan , Stephen N. Freund , Marina Lifshin, Type inference for atomicity, Proceedings of the 2005 ACM SIGPLAN international workshop on Types in languages design and implementation, p.47-58, January 10-10, 2005, Long Beach, California, USA
	Matthew S. Tschantz , Michael D. Ernst, Javari: adding reference immutability to Java, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Miley Semmelroth , Amr Sabry, Monadic encapsulation in ML, ACM SIGPLAN Notices, v.34 n.9, p.8-17, Sept. 1999
	Christian Mossin, Exact flow analysis, Mathematical Structures in Computer Science, v.13 n.1, p.125-156, February 2003
	Gary T. Leavens , Albert L. Baker , Clyde Ruby, Preliminary design of JML: a behavioral interface specification language for java, ACM SIGSOFT Software Engineering Notes, v.31 n.3, May 2006
	Cristiano Calcagno, Stratified operational semantics for safety and correctness of the region calculus, ACM SIGPLAN Notices, v.36 n.3, p.155-165, March 2001
	Iulian Neamtiu , Michael Hicks , Gareth Stoyle , Manuel Oriol, Practical dynamic software updating for C, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Einar Broch Johnsen , Olaf Owe , Ingrid Chieh Yu, Creol: a type-safe object-oriented model for distributed concurrent systems, Theoretical Computer Science, v.365 n.1, p.23-66, 10 November 2006
	Jeffrey S. Foster , Robert Johnson , John Kodumal , Alex Aiken, Flow-insensitive type qualifiers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.6, p.1035-1087, November 2006
	Nick Benton , Peter Buchlovsky, Semantics of an effect analysis for exceptions, Proceedings of the 2007 ACM SIGPLAN international workshop on Types in languages design and implementation, January 16-16, 2007, Nice, Nice, France
	Hans Hüttel , Morten Kühnrich, Types for Access Control in a Calculus of Mobile Resources, Electronic Notes in Theoretical Computer Science (ENTCS), v.180 n.1, p.3-15, June, 2007
	William C. Benton , Charles N. Fischer, Interactive, scalable, declarative program analysis: from prototype to implementation, Proceedings of the 9th ACM SIGPLAN international symposium on Principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland
	Brian Chin , Daniel Marino , Shane Markstrum , Todd Millstein, Enforcing and validating user-defined programming disciplines, Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.85-86, June 13-14, 2007, San Diego, California, USA
	Nick Benton , Andrew Kennedy , Lennart Beringer , Martin Hofmann, Relational semantics for effect-based program transformations with dynamic allocation, Proceedings of the 9th ACM SIGPLAN international symposium on Principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland
	Shang Lujun, Cluster: an informal report, ACM SIGPLAN Notices, v.26 n.1, p.57-74, Jan. 1991
	John Hogg , Doug Lea , Alan Wills , Dennis deChampeaux , Richard Holt, The Geneva convention on the treatment of object aliasing, ACM SIGPLAN OOPS Messenger, v.3 n.2, p.11-16, April 1992
	E. Moggi , Amr Sabry, Monadic encapsulation of effects: a revised approach (extended version), Journal of Functional Programming, v.11 n.6, p.591-627, November 2001
	Peter O'hearn, On bunched typing, Journal of Functional Programming, v.13 n.4, p.747-796, July 2003
	Xin Qi , Andrew C. Myers, Masked types for sound object initialization, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Cormac Flanagan , Stephen N. Freund , Marina Lifshin , Shaz Qadeer, Types for atomicity: Static checking and inference for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.4, p.1-53, July 2008
	Nicholas R. Cameron , Sophia Drossopoulou , James Noble , Matthew J. Smith, Multiple ownership, ACM SIGPLAN Notices, v.42 n.10, October 2007
	Hayo Thielecke, Control effects as a modality, Journal of Functional Programming, v.19 n.1, p.17-26, January 2009
	Robert Atkey, Parameterised notions of computation, Journal of Functional Programming, v.19 n.3-4, p.335-376, July 2009