Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-23T21:58:36.680Z Has data issue: false hasContentIssue false
  • English
  • Français

Operational interpretations of an extension of Fω with control operators

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Robert Harper  and
Mark Lillibridge
Robert Harper
Affiliation:
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA
Mark Lillibridge
Affiliation:
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We study the operational semantics of an extension of Girard's System Fω with two control operators: an abort operation that abandons the current control context, and a callcc operation that captures the current control context. Two classes of operational semantics are considered, each with a call-by-value and a call-by-name variant, differing in their treatment of polymorphic abstraction and instantiation. Under the standard semantics, polymorphic abstractions are values and polymorphic instantiation is a significant computation step; under the ML-like semantics evaluation proceeds beneath polymorphic abstractions and polymorphic instantiation is computationally insignificant. Compositional, type-preserving continuation-passing style (cps) transformation algorithms are given for the standard semantics, resulting in terms on which all four evaluation strategies coincide. This has as a corollary the soundness and termination of well-typed programs under the standard evaluation strategies. In contrast, such results are obtained for the call-by-value ML-like strategy only for a restricted sub-language in which constructor abstractions are limited to values. The ML-like call-by-name semantics is indistinguishable from the standard call-by-name semantics when attention is limited to complete programs.

Type
Articles
Information
Journal of Functional Programming , Volume 6 , Issue 3 , May 1996 , pp. 393 - 418
Copyright
Copyright © Cambridge University Press 1996

References

Appel, A. W. (1992) Compiling with Continuations. Cambridge University Press.Google Scholar
Breazu-Tannen, V., Coquand, Th., Gunter, C. A. and Scedrov, A. (1991) Inheritance as implicit coercion. Information & Computation 93:172–221.CrossRefGoogle Scholar
Burstall, R., MacQueen, D. and Sannella, D. (1980) HOPE: An experimental applicative language. Proc. 1980 LISP Conference, pp. 136–143, Stanford, CA.CrossRefGoogle Scholar
Cardelli, L. (1989) Typeful programming. Technical Report 45, DEC Systems Research Center.Google Scholar
Cardelli, L., Martini, S., Mitchell, J. C. and Scedrov, A. (1991) An extension of System F with subtyping. Research Report 80, Digital Systems Research Center, Palo Alto, CA.CrossRefGoogle Scholar
Clinger, W. and Rees, J. (1991) Revised4 Report on the Algorithmic Language Scheme. LISP Pointers, 5(3):1–55.Google Scholar
Cooper, E. C. and Morrisett, J. G. (1990) Adding threads to Standard ML. Technical Report CMU-CS-90-186, School of Computer Science, Carnegie Mellon University.Google Scholar
Curien, P.-L. and Ghelli, G. (1990) Coherence of subsumption. Technical Report LIENS–90–10, Laboratoire d'Informatique de l'Ecole Normale Supérieure, Paris.CrossRefGoogle Scholar
Duba, B., Harper, R. and MacQueen, D. (1991) Typing first-class continuations in ML. 18th ACM Symposium on Principles of Programming Languages.CrossRefGoogle Scholar
Felleisen, M. and Hieb, R. (1992) The revised report on the syntactic theories of sequential control and state. Theoretical Computer Science 10(2):235–271.CrossRefGoogle Scholar
Fischer, M. J. (1993) Lambda-calculus schemata. LISP and Symbolic Computation 6(3/4):259–288.CrossRefGoogle Scholar
Projet, Formel.(1987) CAML: The reference manual. Technical report, INRIA–ENS.Google Scholar
Girard, J.-Y. (1972) Interprétation Fonctionnelle et Élimination des Coupures dans I'Arithmétique d'Ordre Supérieure. PhD thesis, Université Paris VII.Google Scholar
Girard, J.-Y., Lafont, Y. and Taylor, P. (1989) Proofs and Types: Cambridge Tracts in Theoretical Computer Science vol. 7. Cambridge University Press.Google Scholar
Gordon, M., Milner, R. and Wadsworth, C. (1979) Edinburgh LCF: A Mechanized Logic of Computation: Lecture Notes in Computer Science 78. Springer-Verlag.Google Scholar
Griffin, T. (1990) A formulae-as-types notion of control. 17th ACM Symposium on Principles of Programming Languages,San Francisco, CA.CrossRefGoogle Scholar
Harper, R., Duba, B. and MacQueen, D. (1993) Typing first-class continuations in ML. J. Functional Programming, 3(4):465–484, October. (See also (Duba et al., 1992).).CrossRefGoogle Scholar
Harper, R. and Lillibridge, M. (1993) Explicit polymorphism and CPS conversion. 20th ACM Symposium on Principles of Programming Languages, pp. 206–219, Charleston, SC.CrossRefGoogle Scholar
Harper, R. and Lillibridge, M. (1992) Polymorphic type assignment and CPS conversion. In: Danvy, O. and Talcott, C., editors, Proc. ACM SIGPLAN Workshop on Continuations CW92, pp. 13–22, Stanford, CA. (Published as technical report STAN–CS–92–1426.)Google Scholar
Harper, R. and Lillibridge, M. (1993) Polymorphic type assignment and CPS conversion. LISP and Symbolic Computation, 6(4):361–380, November. (See also (Harper and Lillibridge, 1992).).CrossRefGoogle Scholar
Harper, R. and Mitchell, J. C. (1993) On the type structure of Standard ML. ACM Trans, Programming Languages and Systems, 15(2):211–252, April.CrossRefGoogle Scholar
Harper, R. and Morrisett, G. (1994) Compiling with non-parametric polymorphism. Technical Report CMU–CS–94–122, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA. (Also published as Fox Memorandum CMU–CS–FOX–94–03.)CrossRefGoogle Scholar
Haynes, C. T., Friedman, D. P. and Wand, M. (1986) Obtaining coroutines from continuations. J. Computer Languages, 11:143–153.CrossRefGoogle Scholar
Hudak, P. and Wadler, P. (1990) Report on the Programming Language Haskell, Version 1.0. Research Report YALEU/DCS/RR–777, Yale University.Google Scholar
Kranz, D., Kelsey, R., Rees, J., Hudak, P., Philbin, J. and Adams, N. (1986) Orbit: An optimizing compiler for Scheme. Proc. SIGPLAN Symposium on Compiler Construction, pp. 219–233.Google Scholar
Leroy, X. (1992) Unboxed objects and polymorphic typing. Conference Record of the 19th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 177–188, Albuquerque, NM.CrossRefGoogle Scholar
Leroy, X. and Mauny, M. (1992) The Caml Light system, version 0.5—documentation and user's guide. Technical Report L-5, INRIA.Google Scholar
MacQueen, D. (1986) Using dependent types to express modular structure. 13th ACM Symposium on Principles of Programming Languages.CrossRefGoogle Scholar
Meyer, A. R. and Wand, M. (1985) Continuation semantics in typed lambda calculi (summary). In: Parikh, R., editor, Logics of Programs: Lecture Notes in Computer Science 193, pp. 219–224. Springer-Verlag.CrossRefGoogle Scholar
Milner, R. (1978) A theory of type polymorphism in programming languages. J. Computer and System Sciences, 17:348–375.CrossRefGoogle Scholar
Milner, R. and Tofte, M. (1991) Commentary on Standard ML. MIT Press.Google Scholar
Milner, R., Tofte, M. and Harper, R. (1990) The Definition of Standard ML. MIT Press.Google Scholar
Mitchell, J. and Harper, R. (1988) The essence of ML. 15th ACM Symposium on Principles of Programming Languages,San Diego, CA.CrossRefGoogle Scholar
Pierce, B. C. (1993) Intersection types and bounded polymorphism. In: Bezem, M. and Groote, J. F., editors, Proc. International Conference on Typed Lambda Calculi and Applications, TLCA'93, pp. 346–360, Utrecht, The Netherlands.(Springer-Verlag LNCS 664.) (To appear in Mathematical Structures in Computer Science, 1995.)Google Scholar
Plotkin, G. (1975) Call-by-name, call-by-value, and the lambda calculus. Theoretical Computer Science 1:125–159.CrossRefGoogle Scholar
Reppy, J. H. (1991) CML: A higher-order concurrent language. ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 293–305.Google Scholar
Reynolds, J. C. (1972) Definitional interpreters for higher-order programming languages. Conference Record of the 25th National ACM Conference, pp. 717–740, Boston, MA.CrossRefGoogle Scholar
Reynolds, J. C. (1974) Towards a theory of type structure. Colloq. sur la Programmation: Lecture Notes in Computer Science 19, pp. 408–423. Springer-Verlag.Google Scholar
Reynolds, J. C. (1988) Preliminary design of the programming language Forsythe. Technical Report CMU–CS–88–159, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, June.Google Scholar
Reynolds, J. C. (1993) The discoveries of continuations. LISP and Symbolic Computation 6(3/4):233–248, November.CrossRefGoogle Scholar
Steele, G. L. Jr., (1978) RABBIT: A compiler for SCHEME. Technical Report Memo 474, MIT AI Laboratory.Google Scholar
Tofte, M. (1990) Type inference for polymorphic references. Information and Computation 89:1–34, November.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.