Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-28T22:26:32.530Z Has data issue: false hasContentIssue false
  • English
  • Français

Fully abstract translations between functional languages

Published online by Cambridge University Press:  04 March 2009

Jon G. Riecke
Jon G. Riecke
Affiliation:
AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ 07974
Get access Rights & Permissions [Opens in a new window]

Abstract

We examine the problem of finding fully abstract translations between programming languages, i.e., translations that preserve code equivalence and nonequivalence. We present three examples of fully abstract translations: one from call-by-value to lazy PCF, one from call-by-name to call-by-value PCF, and one from lazy to call-by-value PCF. The translations yield lower bounds on decision procedures for proving equivalences of code. We define a notion of ‘functional translation’ that captures the essence of the proofs of full abstraction, and show that some languages cannot be translated into others.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 3 , Issue 4 , December 1993 , pp. 387 - 415
Copyright
Copyright © Cambridge University Press 1993

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

REFERENCES

Abramsky, S. (1990) The lazy lambda calculus. In: Turner, D. A. (ed.) Research Topics in Functional Programming, Addison-Wesley 65–117.Google Scholar
Barendregt, H. P. (1981) The Lambda Calculus: Its Syntax and Semantics. Studies in Logic 103, North-Holland. (Revised Edition 1984)Google Scholar
Bloom, B. (1988) Can LCF be topped? In: Proceedings, Third Annual Symposium on Logic in Computer Science, IEEE 282–295.Google Scholar
Bloom, B. (1990) Can LCF be topped? Flat lattice models of typed λ-calculus. Information and Computation 87 264–301.CrossRefGoogle Scholar
Bloom, B. and Riecke, J. G. (1989) LCF should be lifted. In: Rus, T. (ed.) Proc. Conf. Algebraic Methodology and Software Technology, Department of Computer Science, University of Iowa 133–136.Google Scholar
Cosmadakis, S. S., Meyer, A. R. and Riecke, J. G. (1990) Completeness for typed lazy inequalities (preliminary report). Proceedings, Fifth Annual IEEE Symposium on Logic in Computer Science 312–320.CrossRefGoogle Scholar
Despeyroux, J. (1986) Proof of translation in natural semantics. Proceedings, Symposium on Logic in Computer Science, IEEE 193–205.Google Scholar
Felleisen, M. (1990) On the expressive power of programming languages. In: Proc. of European Symp. on Programming. Springer-Verlag Lecture Notes in Computer Science 432 134–151. (Expanded version to appear in Science of Computer Programming.)CrossRefGoogle Scholar
Friedman, H. (1975) Equality between functionals. In: Parikh, R. (ed.) Logic Colloquium '73. Springer-Verlag Lecture Notes in Math. 453 22–37.Google Scholar
Gunter, C. A. (1992) Semantics of Programming Languages: Structures and Techniques, MIT Press.Google Scholar
Gunter, C. A. and Scott, D. S. (1990) Semantic domains. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science B, Elsevier633–674.Google Scholar
Kahn, G. (1987) Natural semantics. Proceedings, Symposium on Theoretical Aspects of Computer Science. Springer-Verlag Lecture Notes in Computer Science 247.CrossRefGoogle Scholar
Meyer, A. R. (1988) Semantical paradigms: Notes for an invited lecture, with two appendices by Stavros S. Cosmadakis. In: Proceedings, Third Annual Symposium on Logic in Computer Science, IEEE 236–255.Google Scholar
Milner, R. (1977) Fully abstract models of the typed lambda calculus. Theoretical Computer Sci. 4 1–22.CrossRefGoogle Scholar
Mitchell, J. C. (1986) Lisp is not universal (summary). Unpublished manuscript, AT&T Bell Laboratories.Google Scholar
Mitchell, J. C. (1990) Type systems for programming languages. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science B, Elsevier365–458.Google Scholar
Mitchell, J. C. (1991) On abstraction and the expressive power of programming languages. In: Theoretical Aspects of Computer Software. Springer-Verlag Lecture Notes in Computer Science (to appear).CrossRefGoogle Scholar
Moggi, E. (1988) The Partial Lambda Calculus, PhD thesis, University of Edinburgh.Google Scholar
Moggi, E. (1989) Computational lambda-calculus and monads. Proceedings, Fourth Annual Symposium on Logic in Computer Science, IEEE 14–23.CrossRefGoogle Scholar
Moggi, E. (1991) Notions of computation and monads. Information and Control 93 55–92.Google Scholar
Ong, C.-H. L. (1988a) Fully abstract models of the lazy lambda calculus. 29th Annual Symposium on Foundations of Computer Science, IEEE 368–376.CrossRefGoogle Scholar
Ong, C.-H. L. (1988b) The Lazy Lambda Calculus: An Investigation into the Foundations of Functional Programming, PhD thesis, Imperial College, University of London.Google Scholar
Plotkin, G. D. (1975) Call-by-name, call-by-value and the λ-calculus. Theoretical Computer Sci. 1 125–159.CrossRefGoogle Scholar
Plotkin, G. D. (1977) LCF considered as a programming language. Theoretical Computer Sci. 5 223–257.CrossRefGoogle Scholar
Plotkin, G. D. (1981) A structural approach to operational semantics. Technical Report DAIMI FN-19, Aarhus Univ., Computer Science Dept., Denmark.Google Scholar
Plotkin, G. D. (1982) Notes on completeness of the full continuous type hierarchy. Unpublished manuscript, Massachusetts Institute of Technology.Google Scholar
Riecke, J. G. (1991a) Fully abstract translations between functional languages (preliminary report). Conference Record of the Eighteenth Annual ACM Symposium on Principles of Programming Languages, ACM 245–254.CrossRefGoogle Scholar
Riecke, J. G. (1991b) The Logic and Expressibility of Simply-Typed Call-by-Value and Lazy Languages, PhD thesis, Massachusetts Institute of Technology. (Available as technical report MIT/LCS/TR-523, MIT Laboratory for Computer Science.)Google Scholar
Sazonov, V. (1976) Expressibility of functions in D. Scott's LCF language. Algebra i Logika 15 308–330. (In Russian)Google Scholar
Schwichtenberg, H. (1982) Complexity of normalization in the pure typed lambda-calculus. In: Troelstra, A. and van Dalen, D. (eds.) The L.E.J. Brouwer Centenary Symposium, North-Holland453–457.Google Scholar
Scott, D. (1969) A type theoretical alternative to CUCH, 1SWIM, OWHY. Unpublished manuscript, Oxford University.Google Scholar
Shapiro, E. (1991) Separating concurrent languages with categories of language embeddings. Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing.CrossRefGoogle Scholar
Sieber, K. (1990) Relating full abstraction results for different programming languages. In: Foundations of Software Technology and Theoretical Computer Science, Bangalore, India.CrossRefGoogle Scholar
Sitaram, D. and Felleisen, M. (1990) Reasoning with continuations II: Full abstraction for models of control. Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, ACM 161–175.CrossRefGoogle Scholar
Statman, R. (1979) The typed λ-calculus is not elementary recursive. Theoretical Computer Sci. 9 73–81.CrossRefGoogle Scholar
Statman, R. (1985) Logical relations in the typed λ-calculus. Information and Control 65 86–97.CrossRefGoogle Scholar
Stoughton, A. (1988) Fully Abstract Models of Progamming Languages. Research Notes in Theoretical Computer Science, Pitman/Wiley. (Revision of Ph.D thesis, Dept. of Computer Science, Univ. Edinburgh, Report No. CST-40–86, 1986.)Google Scholar
Thomsen, B. (1989) A calculus of higher order communicating systems. Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, ACM 143–154.CrossRefGoogle Scholar