Programming language theory (PLT) is a branch of
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
that deals with the design, implementation, analysis, characterization, and classification of
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sym ...
s known as
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s. Programming language theory is closely related to other fields including
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
,
software engineering
Software engineering is a systematic engineering approach to software development.
A software engineer is a person who applies the principles of software engineering to design, develop, maintain, test, and evaluate computer software. The term '' ...
, and
linguistics
Linguistics is the scientific study of human language. It is called a scientific study because it entails a comprehensive, systematic, objective, and precise analysis of all aspects of language, particularly its nature and structure. Ling ...
. There are a number of
academic conference
An academic conference or scientific conference (also congress, symposium, workshop, or meeting) is an event for researchers (not necessarily academics) to present and discuss their scholarly work. Together with academic or scientific journal ...
s and
journals in the area.
History
In some ways, the history of programming language theory predates even the development of programming languages themselves. The
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation th ...
, developed by Alonzo Church and
Stephen Cole Kleene in the 1930s, is considered by some to be the world's first programming language, even though it was intended to
''model'' computation rather than being a means for programmers to
''describe'' algorithms to a computer system. Many modern
functional programming languages have been described as providing a "thin veneer" over the lambda calculus, and many are easily described in terms of it.
The first programming language to be invented was
Plankalkül, which was designed by
Konrad Zuse
Konrad Ernst Otto Zuse (; 22 June 1910 – 18 December 1995) was a German civil engineer, pioneering computer scientist, inventor and businessman. His greatest achievement was the world's first programmable computer; the functional program- ...
in the 1940s, but not publicly known until 1972 (and not implemented until 1998). The first widely known and successful
high-level programming language
In computer science, a high-level programming language is a programming language with strong abstraction from the details of the computer. In contrast to low-level programming languages, it may use natural language ''elements'', be easier to u ...
was
Fortran, developed from 1954 to 1957 by a team of
IBM researchers led by
John Backus. The success of FORTRAN led to the formation of a committee of scientists to develop a "universal" computer language; the result of their effort was
ALGOL 58. Separately,
John McCarthy of
MIT developed
Lisp, the first language with origins in academia to be successful. With the success of these initial efforts, programming languages became an active topic of research in the 1960s and beyond.
Some other key events in the history of programming language theory since then:
1950s
*
Noam Chomsky
Avram Noam Chomsky (born December 7, 1928) is an American public intellectual: a linguist, philosopher, cognitive scientist, historian, social critic, and political activist. Sometimes called "the father of modern linguistics", Chomsky i ...
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
Simula language was developed by
Ole-Johan Dahl and
Kristen Nygaard; it is widely considered to be the first example of an
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
In computer science, Peter Landin's J operator is a programming construct that post-composes a lambda expression with the continuation to the current lambda-context. The resulting “function” is first-class and can be passed on to subsequent ...
, essentially a form of
continuation.
* In 1966, Landin introduces
ISWIM, an abstract computer
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
in his article ''The Next 700 Programming Languages''. It is influential in the design of languages leading to the
Haskell programming language.
* In 1966,
Corrado Böhm
Corrado Böhm (17 January 1923 – 23 October 2017) was a Professor Emeritus at the University of Rome "La Sapienza" and a computer scientist known especially for his contributions to the theory of structured programming, constructive mathemati ...
introduced the programming language
CUCH (Curry-Church).
* In 1967,
Christopher Strachey publishes his influential set of lecture notes ''
Fundamental Concepts in Programming Languages
''Fundamental Concepts in Programming Languages'' were an influential set of lecture notes written by Christopher Strachey for the International Summer School in Computer Programming at Copenhagen in August, 1967. It introduced much programming l ...
'', introducing the terminology ''
R-values'', ''
L-values'', ''
parametric polymorphism'', and ''
ad hoc polymorphism''.
* In 1969,
J. Roger Hindley publishes ''The Principal Type-Scheme of an Object in Combinatory Logic'', later generalized into the
Hindley–Milner type inference
Type inference refers to the automatic detection of the type of an expression in a formal language. These include programming languages and mathematical type systems, but also natural languages in some branches of computer science and linguistic ...
algorithm.
* In 1969,
Tony Hoare introduces the
Hoare logic, a form of
axiomatic semantics.
* In 1969,
William Alvin Howard observed that a "high-level"
proof system, referred to as
natural deduction, can be directly interpreted in its
intuitionistic
In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of f ...
version as a typed variant of the
model of computation known as
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation th ...
. This became known as the
Curry–Howard correspondence
In programming language theory and proof theory, the Curry–Howard correspondence (also known as the Curry–Howard isomorphism or equivalence, or the proofs-as-programs and propositions- or formulae-as-types interpretation) is the direct rela ...
.
1970s
* 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
John Charles Reynolds (June 1, 1935 – April 28, 2013) was an American computer scientist.
Education and affiliations
John Reynolds studied at Purdue University and then earned a Doctor of Philosophy (Ph.D.) in theoretical physics from Harvard U ...
discovers
System F. It had already been discovered in 1971 by the mathematical logician
Jean-Yves Girard.
* From 1975,
Gerald Jay Sussman and
Guy Steele develop the
Scheme programming language, a Lisp dialect incorporating
lexical scoping, a unified namespace, and elements from the
actor model including first-class
continuations.
* Backus, at the 1977
Turing Award
The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in compu ...
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
In computer science, Programming Computable Functions (PCF) is a typed functional language introduced by Gordon Plotkin in 1977, based on previous unpublished material by Dana Scott. It can be considered to be an extended version of the typed lam ...
, an abstract typed functional language.
* In 1978,
Robin Milner introduces the
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.
1980s
* In 1981,
Gordon Plotkin publishes his paper on
structured operational semantics.
* In 1988,
Gilles Kahn published his paper on
natural semantics.
* There emerged
process calculi, such as the
Calculus of Communicating Systems of
Robin Milner, and the
Communicating sequential processes model of
C. A. R. Hoare
Sir Charles Antony Richard Hoare (Tony Hoare or C. A. R. Hoare) (born 11 January 1934) is a British computer scientist who has made foundational contributions to programming languages, algorithms, operating systems, formal verification, and c ...
, 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
Gregor Kiczales is an American computer scientist. He is currently a full time professor of computer science at the University of British Columbia in Vancouver, British Columbia, Canada. He is best known for developing the concept of aspect-ori ...
, Jim Des Rivieres and
Daniel G. Bobrow
Daniel Gureasko Bobrow (29 November 1935 – 20 March 2017) was an American computer scientist who created an oft-cited artificial intelligence program STUDENT, with which he earned his PhD., worked at BBN Technologies (BBN), then was a Research Fe ...
published the book ''
The Art of the Metaobject Protocol
''The Art of the Metaobject Protocol'' (AMOP) is a 1991 book by Gregor Kiczales, Jim des Rivieres, and Daniel G. Bobrow (all three working for Xerox PARC) on the subject of metaobject protocol.
Overview
The book contains an explanation of what a ...
''.
*
Eugenio Moggi and
Philip Wadler introduced the use of
monads for structuring programs written in
functional programming languages.
Sub-disciplines and related fields
There are several fields of study which 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
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, including
computability theory,
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
, and
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
.
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 system
In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progra ...
s; 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".
[Benjamin C. Pierce. 2002]
Types and Programming Languages
MIT Press, Cambridge, Massachusetts, USA. 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
Compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...
theory is the theory of writing ''compilers'' (or more generally, ''translators''); programs which translate a program written in one language into another form. The actions of a compiler are traditionally broken up into ''syntax analysis'' (
scan
Scan may refer to:
Acronyms
* Schedules for Clinical Assessment in Neuropsychiatry (SCAN), a psychiatric diagnostic tool developed by WHO
* Shared Check Authorization Network (SCAN), a database of bad check writers and collection agency for ba ...
ning and
parsing
Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from ...
), ''semantic analysis'' (determining what a program should do), ''
optimization'' (improving the performance of a program as indicated by some metric; typically execution speed) and ''
code generation'' (generation and output of an equivalent program in some target language; often the
instruction set
In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes instructions described by that ISA, such as a central processing unit (CPU), is called an ...
of a CPU).
Run-time systems
Run-time systems refer to the development of programming language
runtime environment
In computer programming, a runtime system or runtime environment is a sub-system that exists both in the computer where a program is created, as well as in the computers where the program is intended to be run. The name comes from the compile ...
s and their components, including
virtual machine
In computing, a virtual machine (VM) is the virtualization/ emulation of a computer system. Virtual machines are based on computer architectures and provide functionality of a physical computer. Their implementations may involve specialized h ...
s,
garbage collection
Waste collection is a part of the process of waste management. It is the transfer of solid waste from the point of use and disposal to the point of treatment or landfill. Waste collection also includes the curbside collection of recyclabl ...
, and
foreign function interfaces.
Journals, publications, and conferences
Conferences are the primary venue for presenting research in programming languages. The most well known conferences include the ''
Symposium on Principles of Programming Languages'' (POPL),
''Programming Language Design and Implementation'' (PLDI), the ''
International Conference on Functional Programming The ACM SIGPLAN International Conference on Functional Programming (ICFP) is an annual academic conference in the field of computer science sponsored by the ACM SIGPLAN, in association with IFIP Working Group 2.8 (Functional Programming). The con ...
'' (ICFP), ''the
International Conference on Object Oriented Programming, Systems, Languages and Applications'' (OOPSLA) and ''the
International Conference on Architectural Support for Programming Languages and Operating Systems'' (ASPLOS)''.''
Notable journals that publish PLT research include the ''
ACM Transactions on Programming Languages and Systems'' (TOPLAS), ''
Journal of Functional Programming
The ''Journal of Functional Programming'' is a peer-reviewed scientific journal covering the design, implementation, and application of functional programming languages, spanning the range from mathematical theory to industrial practice. Topics co ...
'' (JFP), ''
Journal of Functional and Logic Programming
A journal, from the Old French ''journal'' (meaning "daily"), may refer to:
*Bullet journal, a method of personal organization
*Diary, a record of what happened over the course of a day or other period
*Daybook, also known as a general journal, a ...
'', and ''
Higher-Order and Symbolic Computation''.
See also
*
SIGPLAN
*
Timeline of programming languages
This is a record of notable programming languages, by decade. Prior to 1950 there were 8 unique programming languages, where 6 were unique languages and 2 were combinations of unique languages. By 1960 there were around 45-50 unique programming ...
*
Very high-level programming language
References
Further reading
*
Abadi, Martín and
Cardelli, Luca. ''A Theory of Objects''. Springer-Verlag.
*
Michael J. C. Gordon
Michael John Caldwell Gordon FRS (28 February 1948 – 22 August 2017) was a British computer scientist.
Life
Mike Gordon was born in Ripon, Yorkshire, England. He attended Dartington Hall School and Bedales School. In 1966, he was accepted ...
. ''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
{{Commons category
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
Benjamin Crawford Pierce is the Henry Salvatori Professor of computer science at the University of Pennsylvania. Pierce joined Penn in 1998 from Indiana University and held research positions at the University of Cambridge and the University of ...
(
University of Pennsylvania
The University of Pennsylvania (also known as Penn or UPenn) is a Private university, private research university in Philadelphia. It is the fourth-oldest institution of higher education in the United States and is ranked among the highest- ...
).
Classic Papers in Programming Languages and Logic Collected by
Karl Crary Karl may refer to:
People
* Karl (given name), including a list of people and characters with the name
* Karl der Große, commonly known in English as Charlemagne
* Karl Marx, German philosopher and political writer
* Karl of Austria, last Austrian ...
(
Carnegie Mellon University).
Programming Language Research Directory by Mark Leone.
λ-Calculus: Then & Nowby
Dana S. Scott
Dana Stewart Scott (born October 11, 1932) is an American logician who is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, C ...
for the ACM Turing Centenary Celebration
Grand Challenges in Programming Languages Panel session at
POPL 2009.