research-article

Free access

Mathematical concepts in programming language semantics

Author:

Dana ScottAuthors Info & Claims

AFIPS '72 (Spring): Proceedings of the May 16-18, 1972, spring joint computer conference

Pages 225 - 234

https://doi.org/10.1145/1478873.1478903

Published: 16 November 1971 Publication History

Abstract

In mathematics after some centuries of development the semantical situation is very clean. This may not be surprising, as the subject attracts people who enjoy clarity, generality, and neatness. On the one hand we have our concepts of mathematical objects (numbers, relations, functions, sets), and on the other we have various formal means of expression. The mathematical expressions are generated for the most part in a very regular manner, and every effort is made to supply all expressions with denotations. (This is not always so easy to do. The theory of distributions, for example, provided a non-obvious construction of denotations for expressions of an operational calculus. The derivative operator was well serviced, but one still cannot multiply two distributions.)

References

[1]

C Strachey Towards a formal semantics In T B Steel (ed) Formal Language Description Languages (North-Holland 1966) pp 198--220. Cf. also Ref 15 for another description of the present program

[2]

H B Curry et al Combinatory logic Vol 1 (North-Holland 1958) Vol 2 (North-Holland 1972 in press) This is a basic reference with a very large bibliography

[3]

P J Landon The mechanical evaluation of expressions Comp J 6 pp 308--320 1964

[4]

A Evans Jr PAL-a language for teaching programming linguists In Proc ACM 23rd Nat Conf Brandon Systems Princeton NJ The PAL language carries out many of the ideas introduced by Landon

Digital Library

[5]

Cf. Ref 2 p 78

[6]

The first proof of inconsistency was given by Kleene and Rosser for a system of Church. The proof was later much simplified. Cf. Ref 2 pp 258 ff

[7]

D Scott Outline of a mathematical theory of computation Proc Fourth Annual Princeton Conf on Info Sci and Sys Princeton 1970 pp 169--176

[8]

D Scott Continuous lattices Proc Dalhousie Conf Springer Lecture Notes in Math 1972 in press

[9]

D Scott The lattice of flow diagrams In E Engeler (ed) Semantics of Algorithmic Languages Springer Lecture Notes in Math Vol 188 1971 pp 311--366. This paper provides many examples of the limit concept. Cf. also Ref 10

[10]

D Scott Lattice theory, data types and semantics NYU Symp on Formal Semantics Prentice-Hall 1972 in press. This is a general introduction more detailed in some respects than Ref 7

[11]

C Strachey Varieties of programming language Proc ACM Conf Venice 1972 to appear. This paper contains more examples

[12]

R A Fairthorne Remarks in P Atherton (ed) Classification Research Munksgaard Copenhagen 1965 p 210

[13]

C Strachey An abstract model of storage In preparation. This report will give complete details

[14]

Cf. Ref 11

[15]

D Scott C Strachey Toward a mathematical semantics for computer languages Proc of Symp on Computers and Automata Microwave Research Institute Symp Ser Vol 21 Polytechnic Institute of Brooklyn 1972 in press. A nearly identical language and its semantics is outlined in this paper together with some more of the mathematical background

[16]

Cf. Ref 13

[17]

Cf. Refs 7 and 8

[18]

R Milner Implementation and applications of Scott's logic for computable functions SIGPLAN Notices Vol 7 No 1 January 1972 pp 1--6. (=SIGACT News No 14)

Digital Library

[19]

J W De Bakker Recursive procedures Math Centre Tracts 24 Mathematisch Centrum Amsterdam 1971. Other useful references are contained in these two papers

[20]

Cf. Refs 9, 15 and 19 for further discussion of recursion

Cited By

Arrial VGuerrieri GKesner DSobocinski PLago UEsparza J(2024)Genericity Through StratificationProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662113(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662113
Cousot PGiacobazzi RRanzato F(2019)A²I: abstract² interpretationProceedings of the ACM on Programming Languages10.1145/32903553:POPL(1-31)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1145/3290355
Kerjean MPacaud Lemay J(2019)Higher-Order Distributions for Differential Linear LogicFoundations of Software Science and Computation Structures10.1007/978-3-030-17127-8_19(330-347)Online publication date: 5-Apr-2019
https://doi.org/10.1007/978-3-030-17127-8_19
Show More Cited By

Recommendations

Understanding programming language concepts via operational semantics
Domain modeling and the duration calculus

The origins of "formal methods" lie partly in language description (although applications of methods like VDM, RAISE or B to areas other than programming languages are probably more widely known). This paper revisits the language description task but ...
SEMANOL (73) a metalanguage for programming the semantics of programming languages

SEMANOL is a practical programming system for writing readable formal specifications of the syntax and semantics of programming languages. SEMANOL is based on a theory of semantics which embraces algorithmic (operational) and extensional (input/output) ...
Towards Effects in Mathematical Operational Semantics

In this paper, we study extensions of mathematical operational semantics with algebraic effects. Our starting point is an effect-free coalgebraic operational semantics, given by a natural transformation of syntax over behaviour. The operational ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

AFIPS '72 (Spring): Proceedings of the May 16-18, 1972, spring joint computer conference

May 1972

1234 pages

ISBN:9781450379090

DOI:10.1145/1478873

Copyright © 1971 ACM.

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]

Sponsors

AFIPS: American Federation of Information Processing Societies

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 November 1971

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
438
Total Downloads

Downloads (Last 12 months)82
Downloads (Last 6 weeks)8

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Arrial VGuerrieri GKesner DSobocinski PLago UEsparza J(2024)Genericity Through StratificationProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662113(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662113
Cousot PGiacobazzi RRanzato F(2019)A²I: abstract² interpretationProceedings of the ACM on Programming Languages10.1145/32903553:POPL(1-31)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1145/3290355
Kerjean MPacaud Lemay J(2019)Higher-Order Distributions for Differential Linear LogicFoundations of Software Science and Computation Structures10.1007/978-3-030-17127-8_19(330-347)Online publication date: 5-Apr-2019
https://doi.org/10.1007/978-3-030-17127-8_19
Jeannin J(2012)Capsules and closuresLogic and Program Semantics10.5555/2340820.2340829(106-123)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2340820.2340829
Møgelberg RStaton S(2011)Linearly-used state in models of call-by-valueProceedings of the 4th international conference on Algebra and coalgebra in computer science10.5555/2040096.2040119(298-313)Online publication date: 30-Aug-2011
https://dl.acm.org/doi/10.5555/2040096.2040119
Aboul-Hosn KKozen D(2006)Local variable scoping and kleene algebra with testsProceedings of the 9th international conference on Relational Methods in Computer Science, and 4th international conference on Applications of Kleene Algebra10.1007/11828563_5(78-90)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.1007/11828563_5
Aboul-Hosn KKozen D(2006)Relational semantics for higher-order programsProceedings of the 8th international conference on Mathematics of Program Construction10.1007/11783596_5(29-48)Online publication date: 3-Jul-2006
https://dl.acm.org/doi/10.1007/11783596_5
Campbell-Kelly M(1985)Christopher Strachey, 1916-1975IEEE Annals of the History of Computing10.1109/MAHC.1985.100017:1(19-42)Online publication date: 1-Jan-1985
https://dl.acm.org/doi/10.1109/MAHC.1985.10001
Cohen EGraham RHarrison MReynolds J(1975)A semantic model for parallel systems with schedulingProceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages10.1145/512976.512986(87-94)Online publication date: 1-Jan-1975
https://dl.acm.org/doi/10.1145/512976.512986
Linden T(1972)A summary of progress toward proving program correctnessProceedings of the December 5-7, 1972, fall joint computer conference, part I10.1145/1479992.1480019(201-211)Online publication date: 5-Dec-1972
https://dl.acm.org/doi/10.1145/1479992.1480019

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents