HOME

TheInfoList



OR:

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 & 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, C ...
for the ACM Turing Centenary Celebration
Grand Challenges in Programming Languages
Panel session at POPL 2009.