skip to main content
article

Delimited dynamic binding

Published: 16 September 2006 Publication History

Abstract

Dynamic binding and delimited control are useful together in many settings, including Web applications, database cursors, and mobile code. We examine this pair of language features to show that the semantics of their interaction is ill-defined yet not expressive enough for these uses.We solve this open and subtle problem. We formalise a typed language DB+DC that combines a calculus DB of dynamic binding and a calculus DC of delimited control. We argue from theoretical and practical points of view that its semantics should be based on delimited dynamic binding: capturing a delimited continuation closes over part of the dynamic environment, rather than all or none of it; reinstating the captured continuation supplements the dynamic environment, rather than replacing or inheriting it. We introduce a type- and reduction-preserving translation from DB + DC to DC, which proves that delimited control macro-expresses dynamic binding. We use this translation to implement DB+DC in Scheme, OCaml, and Haskell.We extend DB + DC with mutable dynamic variables and a facility to obtain not only the latest binding of a dynamic variable but also older bindings. This facility provides for stack inspection and (more generally) folding over the execution context as an inductive data structure.

References

[1]
Ariola, Z. M., Herbelin, H., and Sabry, A. A type-theoretic foundation of continuations and prompts. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (2004), ACM Press, pp. 40--53.
[2]
Baker, H. G. Shallow binding in Lisp 1. 5. Communications of the ACM 21, 7 (July 1978), 565--569.
[3]
Baker, H. G. Shallow binding makes functional arrays fast. ACM SIGPLAN Notices 26, 8 (Aug. 1991), 145--147.
[4]
Balat, V., and Danvy, O. Memoization in type-directed partial evaluation. In ACM SIGPLAN/SIGSOFT Conference on Generative Programming and Component Engineering (2002), D. S. Batory, C. Consel, and W. Taha, Eds., no. 2487 in Lecture Notes in Computer Science, Springer-Verlag, pp. 78--92.
[5]
Balat, V., Di Cosmo, R., and Fiore, M. Extensional normalisation and type-directed partial evaluation for typed lambda calculus with sums. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (2004), ACM Press, pp. 64--76.
[6]
Bawden, A. Reification without evaluation. Memo 946, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, 1 June 1988.
[7]
Biernacka, M., Biernacki, D., and Danvy, O. An operational foundation for delimited continuations in the CPS hierarchy. Logical Methods in Computer Science 1, 2:5 (2005).
[8]
Biernacki, D., and Danvy, O. From interpreter to logic engine by defunctionalization. In LOPSTR 2003: 13th International Symposium on Logic Based Program Synthesis and Transformation (2004), M. Bruynooghe, Ed., no. 3018 in Lecture Notes in Computer Science, Springer-Verlag, pp. 143--159.
[9]
Cartwright, R., and Felleisen, M. Extensible denotational language specifications. In Theoretical Aspects of Computer Software: International Symposium (1994), M. Hagiya and J. C. Mitchell, Eds., no. 789 in Lecture Notes in Computer Science, Springer-Verlag, pp. 244--272.
[10]
Clements, J., and Felleisen, M. A tail-recursive semantics for stack inspections. In Programming Languages and Systems: Proceedings of ESOP 2003, 12th European Symposium on Programming (2003), P. Degano, Ed., no. 2618 in Lecture Notes in Computer Science, Springer-Verlag, pp. 22--37.
[11]
Cobbe, R., and Felleisen, M. Environmental acquisition revisited. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (2005), ACM Press, pp. 14--25.
[12]
Danvy, O. Type-directed partial evaluation. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (1996), ACM Press, pp. 242--257.
[13]
Danvy, O., and Filinski, A. A functional abstraction of typed contexts. Tech. Rep. 89/12, DIKU, University of Copenhagen, Denmark, 1989. http://www.daimi.au.dk/~danvy/Papers/fatc.ps.gz.
[14]
Danvy, O., and Filinski, A. Abstracting control. In Proceedings of the ACM Conference on Lisp and Functional Programming (27--29 June 1990), ACM Press, pp. 151--160.
[15]
Danvy, O., and Filinski, A. Representing control: A study of the CPS transformation. Mathematical Structures in Computer Science 2, 4 (Dec. 1992), 361--391.
[16]
Danvy, O., and MalmkjÆr, K. Intensions and extensions in a reflective tower. In Proceedings of the ACM Conference on Lisp and Functional Programming (1988), ACM Press, pp. 327--341.
[17]
Dybjer, P., and Filinski, A. Normalization and partial evaluation. In APPSEM 2000: International Summer School on Applied Semantics, Advanced Lectures (2002), G. Barthe, P. Dybjer, L. Pinto, and J. Saraiva, Eds., no. 2395 in Lecture Notes in Computer Science, Springer-Verlag, pp. 137--192.
[18]
Dybvig, R. K., Peyton Jones, S. L., and Sabry, A. A monadic framework for delimited continuations. Tech. Rep. 615, Department of Computer Science, Indiana University, June 2005.
[19]
Feeley, M. Parameter objects. Scheme Request for Implementation SRFI-39. http://srfi.schemers.org/srfi-39/,2003.
[20]
Felleisen, M. The Calculi of λv-CS Conversion: A Syntactic Theory of Control and State in Imperative Higher-Order Programming Languages. PhD thesis, Computer Science Department, Indiana University, Aug. 1987. Also as Tech. Rep. 226.
[21]
Felleisen, M. The theory and practice of first-class prompts. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Jan. 1988), ACM Press, pp. 180--190.
[22]
Felleisen, M. On the expressive power of programming languages. Science of Computer Programming 17, 1--3 (1991), 35--75.
[23]
Felleisen, M., Friedman, D. P., Duba, B. F., and Merrill, J. Beyond continuations. Tech. Rep. 216, Computer Science Department, Indiana University, Feb. 1987.
[24]
Filinski, A. Representing monads. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (1994), ACM Press, pp. 446--457.
[25]
Filinski, A. Representing layered monads. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (1999), ACM Press, pp. 175--188.
[26]
Filinski, A. Normalization by evaluation for the computational lambda-calculus. In Proceedings of the 5th International Conference on Typed Lambda Calculi and Applications (May 2001), S. Abramsky, Ed., no. 2044 in Lecture Notes in Computer Science, Springer-Verlag, pp. 151--165.
[27]
Franz Inc. Allegro Common Lisp 8.0, 17 Mar. 2006.
[28]
Friedman, D. P., and Haynes, C. T. Constraining control. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (1985), ACM Press, pp. 245--254.
[29]
Gasbichler, M., Knauel, E., Sperber, M., and Kelsey, R. A. How to add threads to a sequential language without getting tangled up. In Proceedings of the 4th Workshop on Scheme and Functional Programming (7 Nov. 2003), M. Flatt, Ed., no. UUCS-03-023 in Tech. Rep., School of Computing, University of Utah, pp. 30--47.
[30]
Gasbichler, M., and Sperber, M. Processes vs. user-level threads in Scsh. In Proceedings of the 3rd Workshop on Scheme and Functional Programming (3 Oct. 2002).
[31]
Gil, J., and Lorenz, D. H. Environmental acquisitionùa new inheritance-like abstraction mechanism. In Proceedings of the 11th Conference on Object oriented Programming Systems, Languages, and Applications (6-10 Oct. 1996), vol. 31(10) of ACM SIGPLAN Notices, ACM Press, pp. 214--231.
[32]
Graunke, P. T. Web Interactions. PhD thesis, College of Computer Science, Northeastern University, June 2003.
[33]
Grobauer, B., and Yang, Z. The second Futamura projection for typedirected partial evaluation. Higher-Order and Symbolic Computation 14, 2-3 (2001), 173--219.
[34]
Gunter, C. A., RÉmy, D., and Riecke, J. G. A generalization of exceptions and control in ML-like languages. In Functional Programming Languages and Computer Architecture: 7th Conference (26-28 June 1995), S. L. Peyton Jones, Ed., ACM Press, pp. 12--23.
[35]
Gunter, C. A., RÉmy, D., and Riecke, J. G. Return types for functional continuations. http://pauillac.inria.fr/~remy/work/cupto/,Sept. 1998.
[36]
Haynes, C. T., and Friedman, D. P. Embedding continuations in procedural objects. ACM Transactions on Programming Languages and Systems 9, 4 (Oct. 1997), 582--598.
[37]
Kameyama, Y., and Hasegawa, M. A sound and complete axiomatization of delimited continuations. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (2003), ACM Press, pp. 177--188.
[38]
Kiselyov, O. General ways to traverse collections. http://okmij.org/ftp/Scheme/enumerators-callcc.html;http://okmij. org/ftp/Computation/Continuations.html,1Jan.2004.
[39]
Kiselyov, O., Shan, C. -c., Friedman, D. P., and Sabry, A. Backtracking, interleaving, and terminating monad transformers (functional pearl). In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (2005), ACM Press, pp. 192--203.
[40]
Lawall, J. L., and Danvy, O. Continuation-based partial evaluation. In Proceedings of the ACM Conference on Lisp and Functional Programming (1994), ACM Press, pp. 227--238.
[41]
Leroy, X., and Pessaux, F. Type-based analysis of uncaught exceptions. ACM Transactions on Programming Languages and Systems 22, 2 (2000), 340--377.
[42]
Liang, S., Hudak, P., and Jones, M. Monad transformers and modular interpreters. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (1995), ACM Press, pp. 333--343.
[43]
Matthews, J. I learned today that PLT Scheme actually has two kinds of thread-local storage boxes. http://keepworkingworkerbee.blogspot.com/2005/08/i-learned-today-that-plt-scheme.html,26Aug.2005.
[44]
Matthews, J., and Findler, R. B. An operational semantics for R5RS Scheme. In Proceedings of the 6th Workshop on Scheme and Functional Programming (24 Sept. 2005), J.M. Ashley and M. Sperber, Eds., no. 619 in Tech. Rep., Computer Science Department, Indiana University, pp. 41--54.
[45]
Moggi, E. An abstract view of programming languages. Tech. Rep. ECS-LFCS-90-113, Laboratory for Foundations of Computer Science, Department of Computer Science, University of Edinburgh, 1990.
[46]
Moreau, L. A syntactic theory of dynamic binding. Higher-Order and Symbolic Computation 11, 3 (1998), 233--279.
[47]
Queinnec, C. Continuations and web servers. Higher-Order and Symbolic Computation 17, 4 (Dec. 2004), 277--295.
[48]
Sabry, A. Note on axiomatizing the semantics of control operators. Tech. Rep. CIS-TR-96-03, Department of Computer and Information Science, University of Oregon, 1996.
[49]
Sewell, P., Leifer, J. J., Wansbrough, K., Zappa Nardelli, F., Allen-Williams, M., Habouzit, P., and Vafeiadis, V. Acute: High-level programming language design for distributed computation. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (2005), ACM Press, pp. 15--26.
[50]
Sitaram, D. Handling control. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (June 1993), ACM Press, pp. 147--155.
[51]
Sitaram, D. Unwind-protect in portable Scheme. In Proceedings of the 4th Workshop on Scheme and Functional Programming (7 Nov. 2003), M. Flatt, Ed., no. UUCS-03-023 in Tech. Rep., School of Computing, University of Utah, pp. 48--52.
[52]
Sitaram, D., and Felleisen, M. Reasoning with continuations II: Full abstraction for models of control. In Proceedings of the ACM Conference on Lisp and Functional Programming (27-29 June 1990), ACM Press, pp. 161--175.
[53]
Smith, B. C. Reflection and Semantics in a Procedural Language. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Feb. 1982. Also as Tech. Rep. MIT/LCS/TR-272.
[54]
Sumii, E. An implementation of transparent migration on standard Scheme. In Proceedings of the Workshop on Scheme and Functional Programming (Sept. 2000), M. Felleisen, Ed., no. 00-368 in Tech. Rep., Department of Computer Science, Rice University, pp. 61--63.
[55]
Thielecke, H. Contrasting exceptions and continuations. http://www. cs. bham. ac. uk/~hxt/research/exncontjournal. pdf, 2001.
[56]
Thiemann, P. Combinators for program generation. Journal of Functional Programming 9, 5 (1999), 483--525.
[57]
Wand, M., and Friedman, D. P. The mystery of the tower revealed: A non-reflective description of the reflective tower. Lisp and Symbolic Computation 1, 1 (1988), 11--37.

Cited By

View all
  • (2022)Formalizing dynamic-wind in the lambda calculusProceedings of the 2022 11th International Conference on Software and Computer Applications10.1145/3524304.3524318(90-96)Online publication date: 24-Feb-2022
  • (2018)Eff Directly in OCamlElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.285.2285(23-58)Online publication date: 31-Dec-2018
  • (2013)Constraining delimited control with contractsProceedings of the 22nd European conference on Programming Languages and Systems10.1007/978-3-642-37036-6_14(229-248)Online publication date: 16-Mar-2013
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices
ACM SIGPLAN Notices  Volume 41, Issue 9
Proceedings of the 2006 ICFP conference
September 2006
296 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1160074
Issue’s Table of Contents
  • cover image ACM Conferences
    ICFP '06: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming
    September 2006
    308 pages
    ISBN:1595933093
    DOI:10.1145/1159803
    • General Chair:
    • John Reppy,
    • Program Chair:
    • Julia Lawall
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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 September 2006
Published in SIGPLAN Volume 41, Issue 9

Check for updates

Author Tags

  1. delimited continuations
  2. dynamic binding
  3. monads

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)31
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Formalizing dynamic-wind in the lambda calculusProceedings of the 2022 11th International Conference on Software and Computer Applications10.1145/3524304.3524318(90-96)Online publication date: 24-Feb-2022
  • (2018)Eff Directly in OCamlElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.285.2285(23-58)Online publication date: 31-Dec-2018
  • (2013)Constraining delimited control with contractsProceedings of the 22nd European conference on Programming Languages and Systems10.1007/978-3-642-37036-6_14(229-248)Online publication date: 16-Mar-2013
  • (2012)A call-by-name CPS hierarchyProceedings of the 11th international conference on Functional and Logic Programming10.1007/978-3-642-29822-6_21(260-274)Online publication date: 23-May-2012
  • (2009)A semantics for context-oriented programming with layersProceedings of the 1st ACM International Workshop on Context-Oriented Programming10.1145/1562112.1562122(1-6)Online publication date: 7-Jul-2009
  • (2009)Side EffectsWiley Encyclopedia of Computer Science and Engineering10.1002/9780470050118.ecse370(2534-2543)Online publication date: 16-Mar-2009
  • (2023)Typed Equivalence of Labeled Effect Handlers and Labeled Delimited Control OperatorsProceedings of the 25th International Symposium on Principles and Practice of Declarative Programming10.1145/3610612.3610616(1-13)Online publication date: 22-Oct-2023
  • (2022)First-class names for effect handlersProceedings of the ACM on Programming Languages10.1145/35632896:OOPSLA2(30-59)Online publication date: 31-Oct-2022
  • (2022)Effects, capabilities, and boxes: from scope-based reasoning to type-based reasoning and backProceedings of the ACM on Programming Languages10.1145/35273206:OOPSLA1(1-30)Online publication date: 29-Apr-2022
  • (2021)Generalized evidence passing for effect handlers: efficient compilation of effect handlers to CProceedings of the ACM on Programming Languages10.1145/34735765:ICFP(1-30)Online publication date: 19-Aug-2021
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media