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 practical disciplines (includin ...

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 s ...

s known as programming languages. Programming language theory is closely related to other fields including mathematics, software engineering, 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. Lingu ...

. 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 journals ...

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, 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 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 ...

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 ALGOL 58, originally named IAL, is one of the family of ALGOL computer programming languages. It was an early compromise design soon superseded by ALGOL 60. According to John Backus The Zurich ACM-GAMM Conference had two principal motives in p ...

. Separately, John McCarthy of MIT developed

Lisp A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech. Types * A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lispi ...

, 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 is ...

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 Simula is the name of two simulation programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard. Syntactically, it is an approximate superset of AL ...

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 subseque ...

, essentially a form of continuation. * In 1966, Landin introduces ISWIM, an abstract computer programming language 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 introduced the programming language CUCH (Curry-Church). * 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,

J. Roger Hindley J. Roger Hindley is a prominent British logician best known for the Hindley–Milner type inference algorithm. Since 1998, he has been an Honorary Research Fellow at Swansea University. Education Hindley graduated in 1960 from Queen's Univers ...

publishes ''The Principal Type-Scheme of an Object in Combinatory Logic'', later generalized into the Hindley–Milner type inference 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 version as a typed variant of the

model of computation In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes h ...

known as lambda calculus. This became known as the Curry–Howard correspondence.

1970s

* In 1970, Dana Scott first publishes his work on denotational semantics. * In 1972, logic programming and

Prolog Prolog is a logic programming language associated with artificial intelligence and computational linguistics. Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily a ...

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, 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 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, Robin Milner introduces the Hindley–Milner type inference algorithm for ML.

Type theory In mathematics, logic, and computer science, a type theory is the formal system, formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theor ...

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 Operational semantics is a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execut ...

. * 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, 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''. *

Eugenio Moggi Eugenio Moggi is a professor of computer science at the University of Genoa, Italy. He first described the general use of monads to structure programs. Biography Academic qualifications: * PhD in Computer Science, University of Edinburgh ...

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, including computability theory, category theory, 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 concer ...

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".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 paradigm Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms. Some paradigms are concerned mainly with implications for the execution model of the language, s ...

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 that ...

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'' ( scanning and parsing), ''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 a ...

of a CPU).

Run-time systems

Run-time systems refer to the development of programming language runtime environments and their components, including virtual machines, garbage collection, 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'' (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'' (JFP), '' Journal of Functional and Logic Programming'', and '' Higher-Order and Symbolic Computation''.

References

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 E ...

(

University of Pennsylvania The University of Pennsylvania (also known as Penn or UPenn) is a private research university in Philadelphia. It is the fourth-oldest institution of higher education in the United States and is ranked among the highest-regarded universit ...

).
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 & Now
by

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, ...

for the ACM Turing Centenary Celebration
Grand Challenges in Programming Languages
Panel session at POPL 2009.