Hostname: page-component-7c8c6479df-hgkh8 Total loading time: 0 Render date: 2024-03-28T23:19:02.674Z Has data issue: false hasContentIssue false

Note on Algol and conservatively extending functional programming

Published online by Cambridge University Press:  07 November 2008

Peter W. O'Hearn
Affiliation:
Syracuse University
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.

A simple Idealized Algol is considered, based on Reynolds's ‘essence of Algol’. It is shown that observational equivalence in this language conservatively extends observational equivalence in its assignment-free functional sublanguage.

Type
Articles
Copyright
Copyright © Cambridge University Press 1996

References

Gunter, C. A. 1992. Semantics of Programming Languages: Structures and Techniques. MIT Press.Google Scholar
Guzmàn, J. and Hudak, P. 1990. Single-threaded polymorphic lambda calculus. Pages 333–345 of: Proceedings, Fifth Annual IEEE Symposium on Logic in Computer Science. Philadelphia, PA: IEEE Computer Society Press, Los Alamitos, California.Google Scholar
Launchbury, J. and PeytonJones, S. 1995. State in Haskell. Lisp and Symbolic Computation. Special issue on State in Programming Languages. To appear.CrossRefGoogle Scholar
Meyer, A. R. and Sieber, K. 1988. Towards fully abstract semantics for local variables: preliminary report. Pages 191–203 of: Conf. Record 15th ACM Symp. on Principles of Programming Languages. ACM, New York.Google Scholar
Milner, R. 1977. Fully abstract models of typed λ-calculi. Theoretical Computer Science, 4, 122.CrossRefGoogle Scholar
Odersky, M. 1994. A functional theory of local names. In: Conf. Record 21st ACM Symp. on Principles of Programming Languages. ACM, New York.Google Scholar
Odersky, M., Rabin, D. and Hudak, P. 1993. Call-by-name, assignment, and the λ-calculus. In: Conf. Record 20th ACM Symp. on Principles of Programming Languages. Charleston, South Carolina: ACM, New York.Google Scholar
O'Hearn, P. W. and Reddy, U. S. 1995. Objects, Interference and the Yoneda embedding. In: Proceedings of the Eleventh Conference on the Mathematical Foundations of Programming Semantics. To appear. Electronic Notes in Theoretical Computer Science, volume 1.Google Scholar
O'Hearn, P. W. and Tennent, R. D. 1995. Parametricity and Local Variables. Journal of the ACM. To appear. Preliminary version appeared in Conf. Record 20th ACM Symp. on Principles of Programming Languages, Charleston, South Carolina, pages 171184. ACM, New York, 1993.Google Scholar
O'Hearn, P. W., Power, A. J., Takeyama, M. and Tennent, R. D. 1995. Syntactic control of interference, revisited. In: Proceedings of the Eleventh Conference on the Mathematical Foundations of Programming Semantics. To appear. Electronic Notes in theoretical Computer Science, volume 1.Google Scholar
Oles, F. J. 1982. A Category-Theoretic Approach to the Semantics of Programming Languages. Ph.D. thesis, Syracuse University, Syracuse, N.Y.Google Scholar
Peyton-Jones, S. and Wadler, P. 1993. Imperative Functional Programming. In: Conf. Record 20th ACM Symp. on Principles of Programming Languages. Charleston, South Carolina: ACM, New York.Google Scholar
Plotkin, G. D. 1977. LCF considered as a programming language. Theoretical Computer Science, 5, 223255.CrossRefGoogle Scholar
Reddy, U. S. 1994. Passivity and independence. Pages 342–352 of: Proceedings, 9th Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press, Los Alamitos, California.Google Scholar
Reddy, U. S. 1995. Global states considered unnecessary: Introduction to object-based semantics. Lisp and Symbolic Computation. Special issue on State in Programming Languages. To appear.CrossRefGoogle Scholar
Reynolds, J. C. 1978. Syntactic control of interference. Pages 39–46 of: Conf. Record 5th ACM Symp. on Principles of Programming Languages. Tucson, Arizona: ACM, New York.Google Scholar
Reynolds, J. C. 1981. The essence of Algol. Pages 345–372 of: de Bakker, J. W. and van Vliet, J. C. (eds), Algorithmic Languages. Amsterdam: North-Holland.Google Scholar
Reynolds, J. C. 1988. Preliminary design of the programming language Forsythe. Tech. rept. CMU-CS-88-159. Computer Science, Carnegie Mellon University, Pittsburgh.Google Scholar
Reynolds, J. C. 1992. Replacing complexity with generality: the programming language Forsythe.Google Scholar
Riecke, J. G. 1993. Delimiting the scope of effects. ACM Conference on Functional Programming and Computer Architecture, 146158.Google Scholar
Riecke, J. G. and Viswanathan, R. 1995. Isolating side effects in sequential languages. In: Conf. Record 22nd ACM Symp. on Principles of Programming Languages. ACM, New York. San Francisco.Google Scholar
Sieber, K. 1994. Full abstraction for the second order subset of an Algol-like language (preliminary report). Technischer Bericht A 01/94, Universitaet des Saarlandes, February.Google Scholar
Strachey, C. 1972. The varieties of programming language. Pages 222233 of: Proceedings of the International Computing Symposium. Cini Foundation, Venice. Also technical monograph PRG-10, Programming Research Group, University of Oxford, Oxford.Google Scholar
Swarup, V., Reddy, U. S. and Ireland, E. 1991. Assignments for applicative languages. Pages 193214 of: Hughes, (ed), Functional Programming Languages and Computer Architecture. LNCS 523, Springer Verlag.Google Scholar
Tennent, R. D. 1989. Elementary data structures in Algol-like languages. Science of Computer Programming, 13, 73110.CrossRefGoogle Scholar
Tennent, R. D. 1990. Semantical analysis of specification logic. Information and Computation, 85 (2), 135162.CrossRefGoogle Scholar
Tennent, R. D. 1991. Semantics of Programming Languages. Prentice-Hall International.Google Scholar
Wadler, P. 1990a. Comprehending monads. Pages 6178 of: Proceedings of the ACM Conference on LISP and Functional Programming.CrossRefGoogle Scholar
Wadler, P. 1990b. Linear types can change the world! In: Broy, M. and Jones, C. (eds), Programming Concepts and Methods. North Holland.Google Scholar
Weeks, S., and Felleissen, M. 1993. On the orthogonality of procedures and assignments in Algol. In: Conf. Record 20th ASCM Symp. on Principles of Programming Languages. Charleston, South Carolina: ACM, New York.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.