Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-13T01:13:06.118Z Has data issue: false hasContentIssue false
  • English
  • Français

On the reification of semantic linearity

Published online by Cambridge University Press:  10 November 2014

MARCO GABOARDI ,
LUCA PAOLINI  and
MAURO PICCOLO
MARCO GABOARDI
Affiliation:
School of Computing, University of Dundee, Dundee, DD1 4HN, Scotland, U.K.
LUCA PAOLINI
Affiliation:
Dipartimento di Informatica, Università degli Studi di Torino, C.so Svizzera 185, 10149 Torino, Italy Email: [email protected]
MAURO PICCOLO
Affiliation:
Dipartimento di Informatica, Università degli Studi di Torino, C.so Svizzera 185, 10149 Torino, Italy Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Linearity is a multi-faceted and ubiquitous notion in the analysis and development of programming language concepts. We study linearity in a denotational perspective by picking out programs that correspond to linear functions between domains.

We propose a PCF-like language imposing linear constraints on the use of variable to program only linear functions. To entail a full abstraction result, we introduce some higher-order operators related to exception handling and parallel evaluation. We study several notions of operational equivalence and show them to coincide with our language. Finally, we present a new operational evaluation of the language that provides the base for a real implementation. It exploits the denotational linearity to provide an efficient evaluation semantics SECD-like, that avoids the use of closures.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 26 , Issue 5 , June 2016 , pp. 829 - 867
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramsky, S., Malacaria, P. and Jagadeesan, R. (2000) Full abstraction for PCF. Information and Computation 163 (2)409–470.(An extended abstract can be found in Theoretical Aspects of Computer Software (Sendai, 1994), Lecture Notes in Computer Science, 789 1–15, Springer-Verlag, Berlin, 1994.)Google Scholar
Abramsky, S. and McCusker, G. (1996) Linearity, sharing and state: A fully abstract game semantics for idealized algol with active expressions. Electronic Notes in Theoretical Computer Science 3 2–14.Google Scholar
Alves, S., Fernández, M., Florido, M. and Mackie, I. (2006) The power of linear functions. In: Ésik, Z. (ed.) Proceedings of the 20th International Workshop on Computer Science Logic, 15th Annual Conference of the European Association for Computer Science Logic, Szeged, Hungary, 25–29 September. Springer-Verlag Lecture Notes in Computer Science 4207 119–134.Google Scholar
Alves, S., Fernández, M., Florido, M. and Mackie, I. (2007) Linear recursive functions. In: Comon-Lundh, H., Kirchner, C. and Kirchner, H. (eds.) Rewriting, Computation and Proof, Essays Dedicated to Jean-Pierre Jouannaud on the Occasion of His 60th Birthday. Springer-Verlag Lecture Notes in Computer Science 4600 182–195.Google Scholar
Alves, S., Fernndez, M., Florido, M. and Mackie, I. (2010) Gödel's system T revisited. Theoretical Computer Science 411 (11–13)1484–1500.CrossRefGoogle Scholar
Augustsson, L. (1987) Compiling Lazy Functional Languages, Part II, Ph.D. thesis, Department of Computer Sciences, Chalmers University of Technology, Goteborg, Sweden.Google Scholar
Berry, G. (1978) Stable models of typed λ-calculi. In: Ausiello, G. and Böhm, C. (eds.) Fifth International Colloquium on Automata, Languages and Programming. (Udine, Italy, July 17–21). Springer-Verlag Lecture Notes in Computer Science 62 72–89.Google Scholar
Berry, G. and Curien, P.-L. (1982) Sequential algorithms on concrete data structures. Theoretical Computer Science 20 265–321.CrossRefGoogle Scholar
Bierman, G. M. (2000) Program equivalence in a linear functional language. Journal of Functional Programming 10 (2)167–190.Google Scholar
Bierman, G. M., Pitts, A. M. and Russo, C. V. (2000) Operational properties of lily, a polymorphic linear lambda calculus with recursion. Electronic Notes in Theoretical Computer Science 41 (3)70–88.CrossRefGoogle Scholar
Bucciarelli, A., Carraro, A., Ehrhard, T. and Salibra, A. (2010) On linear information systems. In: LINEARITY'09, Satellite Workshop of Computer Science Logic 2009 Electronic Proceedings in Theoretical Computer Science 22 38–48.Google Scholar
Bucciarelli, A. and Ehrhard, T. (1991) Sequentiality and strong stability. In: Proceedings of the Symposium on Logic in Computer Science 138–145.Google Scholar
Bucciarelli, A. and Ehrhard, T. (1993) A theory of sequentiality. Theoretical Computer Science 113 (2)273–291.Google Scholar
Bucciarelli, A. and Ehrhard, T. (1994) Sequentiality in an extensional framework. Information and Computation 110 (2)265–296.CrossRefGoogle Scholar
Curien, P.-L. (2007) Definability and full abstraction. Electronic Notes in Theoretical Computer Science 172 301–310.Google Scholar
Cutland, N. (1980) Computability: An Introduction to Recursive Function Theory, Cambridge University Press.Google Scholar
Davis, M. and Weyuker, E. J. (1983) Computability, Complexity and Languages, Computer Science and Applied Mathematics, Academic Press.Google Scholar
de Bruijn, N. G. (1972) Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church–Rosser theorem. Indagationes Mathematicae (Proceedings) 75 (5)381–392.CrossRefGoogle Scholar
Ehrhard, T. (1995) Hypercoherence: A strongly stable model of linear logic. In: Girard, J.-Y., Lafont, Y. and Regnier, L. (eds.) Proceedings of the Workshop on Advances in Linear Logic. London Mathematical Society Lecture Note Series 222, Cambridge University Press, Ithaca, New York 83–108.Google Scholar
Gaboardi, M. and Paolini, L. (2007) Syntactical, operational and denotational linearity. In: Workshop on Linear Logic, Ludics, Implicit Complexity and Operator Algebras. Dedicated to Jean-Yves Girard on his 60th birthday. Certosa di Pontignano, Siena.Google Scholar
Gaboardi, M., Paolini, L. and Piccolo, M. (2011) Linearity and PCF: a semantic insight! In: Chakravarty, M. M. T., Hu, Z. and Danvy, O. (eds.) Proceeding of the 16th Association for Computing Machinery's Special interest Group on Programming Language, International Conference on Functional Programming Tokyo, Japan372–384.Google Scholar
Girard, J.-Y. (1986) The system F of variable types, fifteen years later. Theoretical Computer Science 45 (2)159–192.Google Scholar
Girard, J.-Y. (1987) Linear logic. Theoretical Computer Science 50 1–102.Google Scholar
Girard, J.-Y., Lafont, Y. and Taylor, P. (1989) Proofs and Types, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, Cambridge.Google Scholar
Gunter, C. A. (1992) Semantics of Programming Languages: Structures and Techniques, Foundations of Computing Series, The MIT Press, Cambridge, MA.Google Scholar
Hindley, J. R. (1989) BCK-combinators and linear λ-terms have types. Theoretical Computer Science 64 97–105.CrossRefGoogle Scholar
Huth, M. (1993) Linear domains and linear maps. In: Brookes, S. D., Main, M. G., Melton, A., Mislove, M. W. and Schmidt, D. A. (eds.) Proceedings of Mathematical Foundations of Programming Semantics, 9th International Conference, (New Orleans, LA, USA, April 7–10). Springer Lecture Notes in Computer Science 802 438–453.Google Scholar
Hyland, J. M. E. and Ong, L. C.-H. (2000) On full abstraction for PCF: I, II, and III. Information and Computation 163 (2)285–408.Google Scholar
Johnsson, T. (1985) Lambda lifting: Transforming programs to recursive equations. In: Jouannaud, J.-P. (ed), Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science 201 190–203.Google Scholar
Johnsson, T. (1987) Compiling Lazy Functional Languages, Ph.D. thesis, Department of Computer Sciences, Chalmers University of Technology, Goteborg, Sweden.Google Scholar
Klop, J. W. (2007) New fix point combinators from old. In: Barendsen, E., Capretta, V., Geuvers, H. and Niqui, M. (eds.) Reflections on Type Theory, Radboud University Nijmegen.Google Scholar
Longley, J. R. (2000) Notions of computability at higher types I. In: Cori, R., Razborov, A., Todorcevic, S. and Wood, C. (eds.) Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic – Logic Colloquium. Lecture Notes in Logic 19 32–142, Paris, France. Association for Symbolic Logic.Google Scholar
Longley, J. R. (2002) The sequentially realizable functionals. Annals of Pure and Applied Logic 117 1–93.Google Scholar
Normann, D. (2006) Computing with functionals - computability theory or computer science? Bulletin of Symbolic Logic 12 (1)43–59.Google Scholar
Ong, C.-H. L. (1995) Correspondence between operational and denotational semantics: the full abstraction for PCF. In: Abramsky, S., Gabbay, D. and Maibaum, T. S. E. (eds.) Handbook of Logic in Computer Science, volume 4, Oxford University Press 269–356.Google Scholar
Paolini, L. (2006) A stable programming language. Information and Computation 204 (3)339–375.Google Scholar
Paolini, L. and Piccolo, M. (2008) Semantically linear programming languages. In: Antoy, S. and Albert, E. (eds.) Proceedings of the 10th International Association for Computing Machinery's Special interest Group on Programming Languages Conference on Principles and Practice of Declarative Programming, Valencia, Spain, ACM 97–107.Google Scholar
Plotkin, G. D. (1977) LCF considered as a programming language. Theoretical Computer Science 5 225–255.Google Scholar
Walker, D. (2005) Substructural type systems. In: Advanced Topics in Types and Programming Languages. The MIT Press.Google Scholar