Programming language theory (commonly known as PLT) is a branch of computer science which deals with the design, implementation, analysis, characterization, and classification of programming languages and programming language features. It is a multi-disciplinary field, both depending on (and in some cases affecting) mathematics, software engineering, linguistics, and even the cognitive sciences. It is a well-recognized branch of computer science, and as of 2006, an active research area, with results published in numerous journals dedicated to PLT, as well as in general computer science and engineering publications. Most undergraduate computer science programs require coursework in the topic. Image File history File links No higher resolution available. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... e. ... Linguistics is the scientific study of language, which can be theoretical or applied. ... Cognitive science is usually defined as the scientific study either of mind or of intelligence (e. ... 2006 is a common year starting on Sunday of the Gregorian calendar. ... This article is about the journal as a written medium. ...

An unofficial symbol of the field of programming language theory is the lowercase Greek letter lambda. This usage derives from the lambda calculus, a computational model widely used by programming language researchers. Many texts and papers on programming and programming languages utilize the lambda in some fashion. It graces the cover of the classic text Structure and Interpretation of Computer Programs, and the title of many of the so-called Lambda Papers, written by Gerald Jay Sussman and Guy Steele, the developers of the Scheme programming language. A popular website on programming language theory is called Lambda the Ultimate, in honor of Sussman and Steele's work. Look up Λ, λ in Wiktionary, the free dictionary. ... The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ... An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system. ... Front cover Structure and Interpretation of Computer Programs (SICP) is a textbook published in 1985 about general computer programming concepts from MIT press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman. ... Lambda the Ultimate Papers were written by Gerald Jay Sussman and Guy Steele Jr. ... // Gerald Jay Sussman is the Panasonic Professor of Electrical Engineering at the Massachusetts Institute of Technology (MIT). ... Guy Lewis Steele, Jr. ... The Scheme programming language is a functional programming language and a dialect of Lisp. ...

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 [1], and many are easily described in terms of it. The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ... Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who was responsible for some of the foundations of theoretical computer science. ... Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ...

The first programming language to be proposed was Plankalkül, which was designed by Konrad Zuse in the 1940s, but not publicly known until 1972 (and not implemented until 2000, five years after Zuse's death). The first widely known and successful 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 the Lisp programming language (based on the lambda calculus), 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. Plankalkül (German, Plan Calculus) is a computer language developed for engineering purposes by Konrad Zuse. ... Konrad Zuse (1992) Statue in Bad Hersfeld Konrad Zuse (June 22, 1910 – December 18, 1995) was a German engineer and computer pioneer. ... 1972 (MCMLXXII) was a leap year starting on Saturday. ... 2000 (MM) was a leap year starting on Saturday of the Gregorian calendar. ... Fortran (previously FORTRAN[1]) is a general-purpose[2], procedural,[3] imperative programming language that is especially suited to numeric computation and scientific computing. ... 1954 (MCMLIV) was a common year starting on Friday of the Gregorian calendar. ... 1957 (MCMLVII) was a common year starting on Tuesday of the Gregorian calendar. ... International Business Machines Corporation (known as IBM or Big Blue; NYSE: IBM) is a multinational computer technology and consulting corporation headquartered in Armonk, New York, USA. The company is one of the few information technology companies with a continuous history dating back to the 19th century. ... John Backus (born December 3, 1924) is an American computer scientist, notable as the inventor of the first high-level programming language (FORTRAN), the Backus-Naur form (BNF, the almost universally used notation to define formal language syntax), and the concept of Function-level programming. ... ALGOL 58 is the first language in the ALGOL programming language family. ... John McCarthy (born September 4, 1927, in Boston, Massachusetts, sometimes known affectionately as Uncle John McCarthy), is a prominent computer scientist who received the Turing Award in 1971 for his major contributions to the field of Artificial Intelligence. ... Mapúa Institute of Technology (MIT, MapúaTech or simply Mapúa) is a private, non-sectarian, Filipino tertiary institute located in Intramuros, Manila. ... Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...

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

• In the 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.
• In 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 the 1970s:
  • A team of scientists at Xerox PARC led by Alan Kay develop Smalltalk, an object-oriented language widely known for its innovative (and theretofore unknown) development environment.
  • Sussman and 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 ACM Turing Award lecture, assailed the current state of industrial languages and proposed a new class of programming languages now known as functional programming languages.
  • The emergence of 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,
  • The application of type theory as a discipline to programming languages, led by Milner; this application has led to tremendous advances in type theory in years.
• In the 1990s:
  • Philip Wadler introduced the use of monads for structuring programs written in functional programming languages

1950 (MCML) was a common year starting on Sunday. ... Avram Noam Chomsky (Hebrew and Yiddish: אברם נועם חומסקי) , Ph. ... The Chomsky hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages. ... Linguistics is the scientific study of language, which can be theoretical or applied. ... 1960 (MCMLX) was a leap year starting on Friday (the link is to a full 1960 calendar). ... Simula is a name for two 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. ... Professor emeritus Ole-Johan Dahl (October 12, 1931 – June 29, 2002) was a Norwegian computer scientist and is considered to be one of the fathers of Simula and object-oriented programming along with Kristen Nygaard. ... Kristen Nygaard Kristen Nygaard (August 27, 1926 - August 10, 2002) was a Norwegian mathematician, computer programming language pioneer and politician. ... An object-oriented programming language (also called an OO language) is one that allows or encourages, to some degree, object-oriented programming techniques such as encapsulation, inheritance, interfaces, and polymorphism. ... In computer science, coroutines are program components that generalize subroutines to allow multiple entry points and suspending and resuming of execution at certain locations. ... 1970 (MCMLXX) was a common year starting on Thursday. ... Bold text // Headline text Link title This article is about the computer research center. ... Alan Curtis Kay (born May 17, 1940) is an American computer scientist, known for his early pioneering work on object-oriented programming and windowing graphical user interface design. ... For other uses, see Small Talk (disambiguation). ... The Scheme programming language is a functional programming language and a dialect of Lisp. ... This article or section should be merged with scope (programming) In computer science, static scoping, as opposed to dynamic scoping, is a way that the scope (programming) of free variables is determined according to its position in program code. ... In computer science, the Actor model is a mathematical model of concurrent computation that treats actors as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and determine how to respond to... In computing, a continuation is a representation of the execution state of a program (for example, the call stack or values of variables) at a certain point. ... For the album by Ash, see 1977 (album). ... The A.M. Turing Award is given annually by the Association for Computing Machinery to a person selected for contributions of a technical nature made to the computing community. ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ... In the first half of the 20th century, various formalisms were proposed to capture the informal concept of computable function, μ-recursive functions, Turing Machines and the lambda calculus possibly being the most well-known examples today. ... The Calculus of Communicating Systems (or CCS) (one of the first process calculi) was developed by Robin Milner. ... Robin Milner is a prominent British computer scientist. ... In computer science, Communicating Sequential Processes (CSP) is a formal language for describing patterns of interaction in concurrent systems. ... Sir Charles Antony Richard Hoare (Tony Hoare or C.A.R. Hoare, born January 11, 1934) is a British computer scientist, probably best known for the development of Quicksort, the worlds most widely used sorting algorithm, in 1960. ... In computer science, the Actor model is a mathematical model of concurrent computation that treats actors as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and determine how to respond to... Carl E. Hewitt is an Associate Professor (Emeritus) in the Electrical Engineering and Computer Science department at the Massachusetts Institute of Technology (MIT). ... At the broadest level, type theory is the branch of mathematics and logic that first creates a hierarchy of types, then assigns each mathematical (and possibly other) entity to a type. ... MCMXC redirects here; for the Enigma album, see MCMXC a. ... Philip Wadler is a computer scientist well-known for his contributions to programming language design and type theory. ... Wikibooks Haskell has a page on the topic of Understanding monads Some functional programming languages make use of monads[1] [2] to structure programs which include operations that must be executed in a specific order. ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ...

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.

• Compiler 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 of a CPU.
• Type theory is the study of type systems; which are "tractable syntactic method(s) for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute." (Types and Programming Languages, MIT Press, 2002). Many programming languages are distinguished by the characteristics of their type systems.
• Formal semantics is the formal specification of the behavior of computer programs and programming languages.
• Program transformation is the process of transforming a program in one form (language) to another form; program analysis is the general problem of examining a program and determining key characteristics (such as the absence of classes of program errors).
• Runtime systems refers to the development of programming language runtime environments and their components, including virtual machines, garbage collection, and foreign function interfaces.
• 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.
• 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 are languages constructed to efficiently solve problems in a particular problem domain.

In addition, PLT makes use of many other branches of mathematics, including computability theory, category theory, and set theory A diagram of the operation of an ideal compiler. ... It has been suggested that some sections of this article be split into a new article entitled instruction set architecture. ... At the broadest level, type theory is the branch of mathematics and logic that first creates a hierarchy of types, then assigns each mathematical (and possibly other) entity to a type. ... In computer science, a type system defines how a programming language classifies values and expressions into types, how it can manipulate those types and how they interact. ... In theoretical computer science formal semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation. ... ÁInsert non-formatted text here ... Computer program analysis is the process of automatically analysing the behavior of computer programs. ... A run-time system (RTS) was a concept peculiar to the RSTS/E operating system. ... Computer programming (often simply programming) is the craft of implementing one or more interrelated abstract algorithms using a particular programming language to produce a concrete computer program. ... In computer science, a virtual machine is software that creates a virtualized environment between the computer platform and its operating system, so that the end user can operate software on an abstract machine. ... In computer science, garbage collection (also known as GC) is a form of automatic memory management. ... A foreign function interface (or FFI) is a mechanism by which a program written in one programming language can call routines or make use of services written in another. ... A programming paradigm is a paradigmatic style of programming (compare with a methodology, which is a paradigmatic style of doing software engineering). ... Metaprogramming is the writing of computer programs that write or manipulate other programs (or themselves) as their data or that do part of the work during compile time that is otherwise done at run time. ... A domain-specific language (DSL) is a programming language designed to be useful for a specific set of tasks, in contrast to general-purpose programming languages. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Computability theory is the branch of theoretical computer science that studies which problems are computationally solvable using different models of computation. ... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ...

PLT-specific journals and publications

Journals which publish original research in programming language theory include:

• ACM Transactions on Programming Languages and Systems [2]
• Computer Languages, Systems, and Structures [3]
• Journal of Functional Programming, The
• Journal of Functional and Logic Programming, The
• Journal of Symbolic Computation, The
• Theoretical Computer Science

A more complete bibliography is available here; also see the list of publications in computer science. This is a list of important publications in computer science, organized by field. ...

See also

• Timeline of programming languages

This is a timeline, i. ...

External links

• The History of Haskell
• Computer Languages History
• List of Online PLT References
• A collection of information and resources for research in programming language theory, design, implementation, and related areas
• Types and Programming Languages by Benjamin Pierce (MIT Press 2002) [4]
• Programming Language Pragmatics, 2nd Edition by Michael Scott (Morgan-Kaufmann, 2006) [5]
• Essentials of Programming Languages by Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes (MIT Press 2001) [6]