License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.Gabbrielli.8
URN: urn:nbn:de:0030-drops-132307
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13230/
Go to the corresponding OASIcs Volume Portal

Martini, Simone

The Standard Model for Programming Languages: The Birth of a Mathematical Theory of Computation

pdf-format:
OASIcs-Gabbrielli-8.pdf (0.4 MB)

Abstract

Despite the insight of some of the pioneers (Turing, von Neumann, Curry, Böhm), programming the early computers was a matter of fiddling with small architecture-dependent details. Only in the sixties some form of "mathematical program development" will be in the agenda of some of the most influential players of that time. A "Mathematical Theory of Computation" is the name chosen by John McCarthy for his approach, which uses a class of recursively computable functions as an (extensional) model of a class of programs. It is the beginning of that grand endeavour to present programming as a mathematical activity, and reasoning on programs as a form of mathematical logic. An important part of this process is the standard model of programming languages - the informal assumption that the meaning of programs should be understood on an abstract machine with unbounded resources, and with true arithmetic. We present some crucial moments of this story, concluding with the emergence, in the seventies, of the need of more "intensional" semantics, like the sequential algorithms on concrete data structures. The paper is a small step of a larger project - reflecting and tracing the interaction between mathematical logic and programming (languages), identifying some of the driving forces of this process.

to Maurizio Gabbrielli, on his 60th birthday

BibTeX - Entry

@InProceedings{martini:OASIcs:2020:13230,
  author =	{Simone Martini},
  title =	{{The Standard Model for Programming Languages: The Birth of a Mathematical Theory of Computation}},
  booktitle =	{Recent Developments in the Design and Implementation of Programming Languages},
  pages =	{8:1--8:13},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-171-9},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{86},
  editor =	{Frank S. de Boer and Jacopo Mauro},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13230},
  URN =		{urn:nbn:de:0030-drops-132307},
  doi =		{10.4230/OASIcs.Gabbrielli.8},
  annote =	{Keywords: Semantics of programming languages, history of programming languages, mathematical theory of computation}
}

Keywords: Semantics of programming languages, history of programming languages, mathematical theory of computation
Collection: Recent Developments in the Design and Implementation of Programming Languages
Issue Date: 2020
Date of publication: 27.11.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI