Programming language theory

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (October 2015) (Learn how and when to remove this template message)

Programming language theory (PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of formal languages known as programming languages. Programming language theory is closely related to other fields including mathematics, software engineering, and linguistics. There are a number of academic conferences and journals in the area.

History

In some ways, the history of programming language theory predates even the development of programming languages themselves. The

Some other key events in the history of programming language theory since then:

1950s

• Noam Chomsky developed the Chomsky hierarchy in the field of linguistics, a discovery which has directly impacted programming language theory and other branches of computer science.

1960s

• The
  object-oriented programming language; Simula also introduced the concept of coroutines
  .
• In 1964, Peter Landin is the first to realize Church's lambda calculus can be used to model programming languages. He introduces the SECD machine which "interprets" lambda expressions.
• In 1965, Landin introduces the J operator, essentially a form of continuation.
• In 1966, Landin introduces
  Haskell
  programming language.
• In 1966, Corrado Böhm introduced the programming language CUCH (Curry-Church).^[3]
• In 1967, Christopher Strachey publishes his influential set of lecture notes Fundamental Concepts in Programming Languages, introducing the terminology R-values, L-values, parametric polymorphism, and ad hoc polymorphism.
• In 1969,
  Hindley–Milner type inference
  algorithm.
• In 1969, Tony Hoare introduces the Hoare logic, a form of axiomatic semantics.
• In 1969,
  intuitionistic version as a typed variant of the model of computation known as lambda calculus. This became known as the Curry–Howard correspondence
  .

• In 1970, Dana Scott first publishes his work on denotational semantics.
• In 1972, logic programming and Prolog were developed thus allowing computer programs to be expressed as mathematical logic.
• A team of scientists at
  Xerox PARC led by Alan Kay develop Smalltalk
  , an object-oriented language widely known for its innovative development environment.
• In 1974, John C. Reynolds discovers System F. It had already been discovered in 1971 by the mathematical logician Jean-Yves Girard.
• From 1975,
  lexical scoping, a unified namespace, and elements from the actor model including first-class continuations
  .
• Backus, at the 1977 Turing Award lecture, assailed the current state of industrial languages and proposed a new class of programming languages now known as function-level programming languages.
• In 1977, Gordon Plotkin introduces Programming Computable Functions, an abstract typed functional language.
• In 1978,
  Hindley–Milner type inference algorithm for ML. Type theory
  became applied as a discipline to programming languages, this application has led to tremendous advances in type theory over the years.

• In 1981,
  structured operational semantics
  .
• In 1988,
  natural semantics
  .
• There emerged
  C. A. R. Hoare, as well as similar models of concurrency such as the actor model of Carl Hewitt
  .
• In 1985, the release of Miranda sparks an academic interest in lazy-evaluated pure functional programming languages. A committee was formed to define an open standard resulting in the release of the Haskell 1.0 standard in 1990.
• Bertrand Meyer created the methodology Design by contract and incorporated it into the Eiffel programming language.

1990s

• Gregor Kiczales, Jim Des Rivieres and Daniel G. Bobrow published the book The Art of the Metaobject Protocol.
• functional programming languages
  .

Sub-disciplines and related fields

There are several fields of study that either lie within programming language theory, or which have a profound influence on it; many of these have considerable overlap. In addition, PLT makes use of many other branches of mathematics, including computability theory, category theory, and set theory.

Formal semantics

Formal semantics is the formal specification of the behaviour of computer programs and programming languages. Three common approaches to describe the semantics or "meaning" of a computer program are denotational semantics, operational semantics and axiomatic semantics.

Type theory

Type theory is the study of type systems; which are "a tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute".^[4] Many programming languages are distinguished by the characteristics of their type systems.

Program analysis and transformation

Program analysis is the general problem of examining a program and determining key characteristics (such as the absence of classes of program errors). Program transformation is the process of transforming a program in one form (language) to another form.

Comparative programming language analysis

Comparative programming language analysis seeks to classify programming languages into different types based on their characteristics; broad categories of programming languages are often known as programming paradigms.

Generic and metaprogramming

Metaprogramming is the generation of higher-order programs which, when executed, produce programs (possibly in a different language, or in a subset of the original language) as a result.

Domain-specific languages

Domain-specific languages are languages constructed to efficiently solve problems of a particular part of domain.

Compiler construction

Run-time systems

(ASPLOS).

Notable journals that publish PLT research include the ACM Transactions on Programming Languages and Systems (TOPLAS), Journal of Functional Programming (JFP), Journal of Functional and Logic Programming, and Higher-Order and Symbolic Computation.

See also

• SIGPLAN
• Very high-level programming language

References

1. OCLC 34576857
   .
2. ^ "Models Of Computation". wiki.c2.com. December 3, 2014. Archived from the original on Nov 30, 2020.
3. ^ C. Böhm and W. Gross (1996). Introduction to the CUCH. In E. R. Caianiello (ed.), Automata Theory, p. 35-64/
4. ^ Benjamin C. Pierce. 2002. Types and Programming Languages. MIT Press, Cambridge, Massachusetts, USA.

Further reading

See also:

Semantics of programming languages § Further reading

• Abadi, Martín and Cardelli, Luca. A Theory of Objects. Springer-Verlag.
• Michael J. C. Gordon. Programming Language Theory and Its Implementation. Prentice Hall.
• Gunter, Carl and Mitchell, John C. (eds.). Theoretical Aspects of Object Oriented Programming Languages: Types, Semantics, and Language Design. MIT Press.
• Harper, Robert. Practical Foundations for Programming Languages. Draft version.
• Knuth, Donald E. (2003). Selected Papers on Computer Languages. Stanford, California: Center for the Study of Language and Information.
• Mitchell, John C. Foundations for Programming Languages.
• Mitchell, John C. Introduction to Programming Language Theory.
• O'Hearn, Peter. W. and Tennent, Robert. D. (1997). Algol-like Languages
  . Progress in Theoretical Computer Science. Birkhauser, Boston.
• Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press.
• Pierce, Benjamin C. Advanced Topics in Types and Programming Languages.
• Pierce, Benjamin C. et al. (2010). Software Foundations.

External links

Wikimedia Commons has media related to Programming language theory.

• Lambda the Ultimate, a community weblog for professional discussion and repository of documents on programming language theory.
• Great Works in Programming Languages. Collected by Benjamin C. Pierce (University of Pennsylvania).
• Classic Papers in Programming Languages and Logic. Collected by Karl Crary (Carnegie Mellon University).
• Programming Language Research. Directory by Mark Leone.
• λ-Calculus: Then & Now by
  Dana S. Scott
  for the ACM Turing Centenary Celebration
• Grand Challenges in Programming Languages. Panel session at
  POPL
  2009.