Article

Free access

Reasoning about continuations with control effects

Authors:

D. K. GiffordAuthors Info & Claims

PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation

Pages 218 - 226

https://doi.org/10.1145/73141.74837

Published: 21 June 1989 Publication History

Abstract

We present a new static analysis method for first-class continuations that uses an effect system to classify the control domain behavior of expressions in a typed polymorphic language. We introduce two new control effects, goto and comefrom, that describe the control flow properties of expressions. An expression that does not have a goto effect is said to be continuation following because it will always call its passed return continuation. An expression that does not have a comefrom effect is said to be continuation discarding because it will never preserve its return continuation for later use. Unobservable control effects can be masked by the effect system. Control effect soundness theorems guarantee that the effects computed statically by the effect system are a conservative approximation of the dynamic behavior of an expression.

The effect system that we describe performs certain kinds of control flow analysis that were not previously feasible. We discuss how this analysis can enable a variety of compiler optimizations, including parallel expression scheduling in the presence of complex control structures, and stack allocation of continuations. The effect system we describe has been implemented as an extension to the FX-87 programming language.

References

[1]

Abramsky, C., and Itankin, C. T. Eds. Abstract Interpretation for Declaralive Languages. J. Wiley and Sons, 1987.

Digital Library

[2]

Bawden, A. Submission to the Scheme electronic mailing list scheme~mc.lcs.mit.edu. March 2, 1989.

[3]

Clark, R. L. A Linguistic Contribution to GOTO-Less Programming. Dalamat~on, December 1973, 62-63. Reprinted in Communications of the A CM ~, 27 (1984), 349-350.

Digital Library

[4]

Cousot, P., and Cousot, R. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction and Approximation of Fixed Points. In Proceedings of the ~ih Ann~tal A CM Conference on Principles of Programming Languages. ACM, New York, 1977, pp. 238- 252.

Digital Library

[5]

Clinger, W. D., Hartheimer, A. H., and Ost, E. O. Implementation Strategies for Continuations. in Proceedings of the 1988 A CM Conference on Lisp and Functional Programming. ACM, New York, 1988, pp. 124-131.

Digital Library

[6]

Danvy, O., and Filinski, A. A Funciional Abstraction of Typed Conlezts. DIKU Report 89/5, University of Copenhagen, 1989,

[7]

Friedman, D. P., and Haynes, C. T. Constraining Control. In Proceedings of the 12ih Annual A CM Conference on Principles of Programming Languages. ACM, New York, 1985, pp. 245-254.

Digital Library

[8]

Felleisen, M. A-v-CS: An Extended A-CalcuIus for Scheme. In Proceedings of the 1988 A CM Conference on Lisp and Functional Programming. ACM, New York, 1988, pp. 72-85.

Digital Library

[9]

Felleisen, M. The Theory and Practice of First- Class Prompts. In Proceedings of ~he 15th Annual A CM Conference on Principles of Programming Languages. ACM, New York, 1988, pp. 180- 190.

Digital Library

[10]

Gifford, D. K., Jouvelot, P., Lucassen, J. M., and Sheldon, M. A. The FX-37 Reference Manual. MIT/LCS/TR-407, 1987.

[11]

Hughes, J. Strictness Analysis by Abstract Interpretation of Continuations. In {AH87}.

[12]

Haynes, C. T., and Friedman, D. P. Embedding Continuations in Procedural Objects. A CM Trans. on Prog. Lang. and $yst. 9, 4 (1987), 582-598.

Digital Library

[13]

Haynes, C. T., Friedman, D. P., and Wand, M. Obtaining Coroutines with Continuations. Comput. Lang. 11, 3/4 (1986), 143-153.

Digital Library

[14]

Jouvejot, P. and Gifford, D. K. The FX-87 Interpreter. In Proceedings of the ~nd IEEE International Conference on Computer Languages. IEEE, New York, 1988, pp. 65-72.

[15]

Jouvetot, P. and Gifford, D. K. Parallel Functional Programming: The FX-87 Project. To appear in Proceedings of the International Workshop on Parallel and Distributed Algorithms. North Holland, Amsterdam, 1989.

[16]

Jouvelot, P. and Gifford, D. K. Communication Effects for Message-Based Concurrency. MIT/LCS/TM-386, 1989.

[17]

Lucassen, j. M. Types and Effects: Towards the Integration of Functional and Imperative Programming. PhD Dissertation, MIT/LCS/TR-408, 1987.

[18]

Lucassen, J. M., and Gifford, D. K. Polymorphic Effect Systems. In Proceedings of the 15th Annual A CM Conference on Principles of Programming Languages. ACM, New York, 1988, pp. 47- 57.

Digital Library

[19]

Moon, D. MacLISP Reference Manual, Revision 0. MIT Project MAC, 1974.

[20]

McCracken, N. J. An Investigation of a Programming Language with a Polymorphic Type Structure. PhD Dissertation, Syracuse University, 1979.

Digital Library

[21]

Meyer, A. R., and Riecke, J. Continuations May Be Unreasonable. In Proceedings of the 1988 A CM Conference on Lisp and Functional Programming. ACM, New York, 1988, pp. 63-71.

Digital Library

[22]

Rees, J. A., and Clinger, W. Eds. The Reviseaa Report on the Algorilhmic Language Scheme. MIT/AI Memo 848a, 1986.

[23]

Steele, G. L., and Sussman, G. J. The Art of the Interpreter or, The Modularity Complez (Parts Zero, One and Two). MIT/AI Memo 453, 1978.

Digital Library

[24]

Schmidt, D. A. Denotational Semantics: A Methodology for Language Development. Allyn and Bacon, 1986.

Digital Library

[25]

Sussman, G. J., and McDermott, D. From PLANNER to CONNIVER - A Genetic Approach. In Proceedings of the Fall Joint Computer Conference. AFIPS Press, Reston, 1972, pp 1171-1179.

[26]

Wand, M. Continuation-based Multiprocessing. In Proceedings of the 1980 A CM Conference on Lisp and Functional Programming. ACM, New York, 1980, pp. 19-28.

Digital Library

Cited By

He WMestre JPupyrev SWang LYu H(2022)Profile inference revisitedProceedings of the ACM on Programming Languages10.1145/34987146:POPL(1-24)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498714
Ye QDelaware B(2022)Oblivious algebraic data typesProceedings of the ACM on Programming Languages10.1145/34987136:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498713
Padon OWilcox JKoenig JMcMillan KAiken A(2022)Induction duality: primal-dual search for invariantsProceedings of the ACM on Programming Languages10.1145/34987126:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498712
Show More Cited By

Index Terms

Reasoning about continuations with control effects

Recommendations

Reasoning about continuations with control effects
Proceedings of the SIGPLAN '89 symposium on Interpreters and interpretive techniques

We present a new static analysis method for first-class continuations that uses an effect system to classify the control domain behavior of expressions in a typed polymorphic language. We introduce two new control effects, goto and comefrom, that ...
Reasoning with continuations II: full abstraction for models of control
LFP '90: Proceedings of the 1990 ACM conference on LISP and functional programming

A fully abstract model of a programming language assigns the same meaning to two terms if and only if they have the same operational behavior. Such models are well-known for functional languages but little is known about extended functional languages ...
Compiling with Continuations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation

June 1989

355 pages

ISBN:089791306X

DOI:10.1145/73141

Editor:
R. L. Wexelblat
ACM Headquarters, New York, NY

ACM SIGPLAN Notices Volume 24, Issue 7
Proceedings of the SIGPLAN '89 symposium on Interpreters and interpretive techniques
July 1989
355 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/74818
Editor:
Richard Wexelblat
Issue’s Table of Contents

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI89

Sponsor:

SIGPLAN

PLDI89: Programming Language Design & Implementation

June 19 - 23, 1989

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
501
Total Downloads

Downloads (Last 12 months)111
Downloads (Last 6 weeks)17

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

He WMestre JPupyrev SWang LYu H(2022)Profile inference revisitedProceedings of the ACM on Programming Languages10.1145/34987146:POPL(1-24)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498714
Ye QDelaware B(2022)Oblivious algebraic data typesProceedings of the ACM on Programming Languages10.1145/34987136:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498713
Padon OWilcox JKoenig JMcMillan KAiken A(2022)Induction duality: primal-dual search for invariantsProceedings of the ACM on Programming Languages10.1145/34987126:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498712
Kokologiannakis MMarmanis IGladstein VVafeiadis V(2022)Truly stateless, optimal dynamic partial order reductionProceedings of the ACM on Programming Languages10.1145/34987116:POPL(1-28)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498711
Muller S(2022)Static prediction of parallel computation graphsProceedings of the ACM on Programming Languages10.1145/34987086:POPL(1-31)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498708
Sangiorgi D(2022)From enhanced coinduction towards enhanced inductionProceedings of the ACM on Programming Languages10.1145/34986796:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498679
Thielecke H(2016)Command injection attacks, continuations, and the Lambek calculusElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.212.6212(81-96)Online publication date: 19-Jun-2016
https://doi.org/10.4204/EPTCS.212.6
Mycroft AOrchard DPetricek T(2015)Effect Systems Revisited--Control-Flow Algebra and SemanticsEssays Dedicated to Hanne Riis Nielson and Flemming Nielson on the Occasion of Their 60th Birthdays on Semantics, Logics, and Calculi - Volume 956010.1007/978-3-319-27810-0_1(1-32)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-27810-0_1
Irigoin FJouvelot PTriolet R(2014)Semantical interprocedural parallelizationACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2667163(143-150)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2591635.2667163
Dutchyn CHarrison W(2007)Specializing continuations a model for dynamic join pointsProceedings of the 6th workshop on Foundations of aspect-oriented languages10.1145/1233833.1233840(45-57)Online publication date: 13-Mar-2007
https://dl.acm.org/doi/10.1145/1233833.1233840
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents