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.
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 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:
- 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.
- 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, 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 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 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, 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 became applied as a discipline to programming languages, this application has led to tremendous advances in type theory over the years.
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.