Jump to content

Programming language theory: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
mNo edit summary
WP:REFerence WP:CITation parameters: update-standardize-conform, reorders, adds, fills. WP:LINKs: adds, update-standardizes, needless WP:PIPEs > WP:NOPIPEs, WP:RED until article exists. Small WP:COPYEDITs WP:EoS: WP:TERSE, clarify. MOS:FIRSTABBReviations clarify, define before parenthetic WP:ABBRs.
Line 2: Line 2:
{{Redirect |Theory of programming|the branch of CS that deals with what problems can be solved|Theory of computation}}
{{Redirect |Theory of programming|the branch of CS that deals with what problems can be solved|Theory of computation}}
{{More footnotes |date=October 2015}}
{{More footnotes |date=October 2015}}
[[File:Lambda lc.svg|thumb|250px|The lowercase [[Greek alphabet|Greek]] letter λ ([[lambda]]) is an unofficial symbol of the field of programming-language theory.{{Citation needed|date= July 2020}} This usage derives from the [[lambda calculus]], a [[model of computation]] introduced by [[Alonzo Church]] in the 1930s and widely used by programming-language researchers. It graces the cover<ref>{{Cite book |last=Abelson |first=Harold |url=https://www.worldcat.org/oclc/34576857 |title=Structure and Interpretation of Computer Programs |date=1996 |publisher=MIT Press |others=Gerald Jay Sussman, Julie Sussman |isbn=0-262-01153-0 |edition=2nd |location=Cambridge, Mass. |oclc=34576857}}</ref> of the classic text ''[[Structure and Interpretation of Computer Programs]]'', and the title of the so-called [[Lambda Papers]] of 1975 to 1980, written by [[Gerald Jay Sussman]] and [[Guy Steele]], the developers of the [[Scheme (programming language)|Scheme programming language]].{{Technical statement|date=July 2020}}]]
[[File:Lambda lc.svg|thumb|250px|The lowercase [[Greek alphabet|Greek]] letter λ ([[lambda]]) is an unofficial symbol of the field of programming-language theory.{{Citation needed|date=July 2020}} This usage derives from the [[lambda calculus]], a [[model of computation]] introduced by [[Alonzo Church]] in the 1930s and widely used by programming-language researchers. It graces the cover of the classic text ''[[Structure and Interpretation of Computer Programs]]'',<ref>{{Cite book |last1=Abelson |first1=Harold |author1-link=Hal Abelson |last2=Sussman |first2=Gerald Jay |author2-link=Gerald Jay Sussman |last3=Sussman |first3=Julie |author3-link=Julie Sussman |date=1996 |url=https://www.worldcat.org/oclc/34576857 |title=Structure and Interpretation of Computer Programs |edition=2nd |publisher=[[MIT Press]] |isbn=0-262-01153-0 |location=Cambridge, Massachusetts |oclc=34576857}}</ref> and the title of the so-called [[Lambda Papers]] of 1975 to 1980, written by [[Gerald Jay Sussman]] and [[Guy L. Steele Jr.]], the developers of the [[Scheme (programming language)|Scheme]] language.]]


'''Programming language theory''' ('''PLT''') is a branch of [[computer science]] that deals with the design, implementation, analysis, characterization, and classification of [[formal language]]s known as [[programming language]]s. Programming language theory is closely related to other fields including [[mathematics]], [[software engineering]], and [[linguistics]].
'''Programming language theory''' ('''PLT''') is a branch of [[computer science]] that deals with the design, implementation, analysis, characterization, and classification of [[formal language]]s known as [[programming language]]s. Programming language theory is closely related to other fields including [[linguistics]], [[mathematics]], and [[software engineering]].


== History ==
== History ==
{{see also|History of programming languages|Programming language#History}}
{{see also|History of programming languages|Programming language#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 of computation|''model'']] computation rather than being a means for programmers to [[Computer programming|''describe'']] algorithms to a computer system. Many modern [[functional programming language]]s have been described as providing a "thin veneer" over the lambda calculus,<ref>{{Cite web |date=December 3, 2014 |title=Models Of Computation |url=http://www.c2.com/cgi/wiki?ModelsOfComputation |url-status=live |archive-url=https://web.archive.org/web/20201130055927/http://wiki.c2.com/?ModelsOfComputation |archive-date=Nov 30, 2020 |website=wiki.c2.com}}</ref> and many are easily described in terms of it.
In some ways, the history of programming language theory predates even the development of programming languages. 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 of computation|model]]'' computation rather than being a means for programmers to ''[[Computer programming|describe]]'' [[algorithm]]s to a computer system. Many modern [[functional programming]] languages have been described as providing a "thin veneer" over the lambda calculus,<ref>{{Cite web |date=December 3, 2014 |title=Models Of Computation |url=http://www.c2.com/cgi/wiki?ModelsOfComputation |url-status=live |archive-url=https://web.archive.org/web/20201130055927/http://wiki.c2.com/?ModelsOfComputation |archive-date=November 30, 2020 |website=wiki.c2.com}}</ref> and many are described easily 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|FORTRAN]] (Stands for Formula Translation), 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 (computer scientist)|John McCarthy]] of [[MIT]] developed [[Lisp (programming language)|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.
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|FORTRAN]] (for Formula Translation), 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 (computer scientist)|John McCarthy]] of [[Massachusetts Institute of Technology]] (MIT) developed [[Lisp (programming language)|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.


===Timeline===
===Timeline===
Line 22: Line 22:


; 1960s
; 1960s
* In 1962, 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 [[coroutine]]s.
* In 1962, 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 [[coroutine]]s.
* 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 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 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)|Haskell]] programming language.
* 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]] language.
* In 1966, [[Corrado Böhm]] introduced the programming language [[CUCH]] (Curry-Church).<ref>[[Corrado Böhm|C. Böhm]] and W. Gross (1996). Introduction to the CUCH. In E. R. Caianiello (ed.), ''Automata Theory'', p. 35-64/</ref>
* In 1966, [[Corrado Böhm]] introduced the language CUCH (Curry-Church).<ref>[[Corrado Böhm|C. Böhm]] and W. Gross (1996). Introduction to the CUCH. In E. R. Caianiello (ed.), ''Automata Theory'', p. 35–64.</ref>
* In 1967, [[Christopher Strachey]] publishes his influential set of lecture notes ''[[Fundamental Concepts in Programming Languages]]'', introducing the terminology ''[[Value (computer science)|R-values]]'', ''[[Value (computer science)|L-values]]'', ''[[parametric polymorphism]]'', and ''[[ad hoc polymorphism]]''.
* In 1967, [[Christopher Strachey]] publishes his influential set of lecture notes ''[[Fundamental Concepts in Programming Languages]]'', introducing the terminology ''[[Value (computer science)|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&ndash;Milner]] [[type inference]] algorithm.
* In 1969, [[J. Roger Hindley]] publishes ''The Principal Type-Scheme of an Object in Combinatory Logic'', later generalized into the [[Hindley–Milner type system|Hindley–Milner]] [[type inference]] algorithm.
* In 1969, [[Tony Hoare]] introduces the [[Hoare logic]], a form of [[axiomatic semantics]].
* In 1969, [[Tony Hoare]] introduces the [[Hoare logic]], a form of [[axiomatic semantics]].
* In 1969, [[William Alvin Howard]] observed that a "high-level" [[proof calculus|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 1969, [[William Alvin Howard]] observed that a "high-level" [[proof calculus|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]].
Line 35: Line 35:
* In 1970, [[Dana Scott]] first publishes his work on [[denotational semantics]].
* 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.
* 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.
* A team of scientists at [[PARC (company)|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]].
* 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)|Scheme programming language]], a Lisp dialect incorporating [[lexical scoping]], a unified namespace, and elements from the [[actor model]] including first-class [[continuation]]s.
* From 1975, [[Gerald Jay Sussman]] and [[Guy Steele]] develop the [[Scheme (programming language)|Scheme]] language, a Lisp dialect incorporating [[lexical scoping]], a unified namespace, and elements from the [[actor model]] including first-class [[continuation]]s.
* 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.
* 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 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 (programming language)|ML]]. [[Type theory]] became applied as a discipline to programming languages, this application has led to tremendous advances in type theory over the years.
* In 1978, [[Robin Milner]] introduces the [[Hindley–Milner type system]] inference algorithm for [[ML (programming language)|ML]] language. [[Type theory]] became applied as a discipline to programming languages, this application has led to great advances in type theory over the years.


; 1980s
; 1980s
Line 46: Line 46:
* In 1988, [[Gilles Kahn]] published his paper on [[natural semantics]].
* In 1988, [[Gilles Kahn]] published his paper on [[natural semantics]].
* There emerged [[process calculus|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]].
* There emerged [[process calculus|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 (programming language)|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.
* In 1985, the release of [[Miranda (programming language)|Miranda]] sparks an academic interest in lazy-evaluated [[purely 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)|Eiffel programming language]].
* [[Bertrand Meyer]] created the methodology ''[[design by contract]]'' and incorporated it into the [[Eiffel (programming language)|Eiffel]] language.


; 1990s
; 1990s
* [[Gregor Kiczales]], Jim Des Rivieres and [[Daniel G. Bobrow]] published the book ''[[The Art of the Metaobject Protocol]]''.
* [[Gregor Kiczales]], Jim Des Rivieres and [[Daniel G. Bobrow]] published the book ''[[The Art of the Metaobject Protocol]]''.
* [[Eugenio Moggi]] and [[Philip Wadler]] introduced the use of [[Monads in functional programming|monads]] for structuring programs written in [[functional programming language]]s.
* [[Eugenio Moggi]] and [[Philip Wadler]] introduced the use of [[Monad (functional programming)|monads]] for structuring programs written in [[functional programming]] languages.


== Sub-disciplines and related fields ==
== Sub-disciplines and related fields ==
Line 57: Line 57:


=== Formal semantics ===
=== Formal semantics ===
{{main|Formal semantics of programming languages}}
{{Further|Formal semantics of programming languages}}
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]].
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 ===
{{main|Type theory}}
{{Further|Type theory}}
Type theory is the study of [[type system]]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".<ref>Benjamin C. Pierce. 2002. [https://books.google.com/books?id=ti6zoAC9Ph8C&dq=%22Types+and+Programming+Languages%22&pg=PR13 Types and Programming Languages]. MIT Press, Cambridge, Massachusetts, USA.</ref> Many programming languages are distinguished by the characteristics of their type systems.
Type theory is the study of [[type system]]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".<ref>Benjamin C. Pierce. 2002. [https://books.google.com/books?id=ti6zoAC9Ph8C&dq=%22Types+and+Programming+Languages%22&pg=PR13 Types and Programming Languages]. MIT Press, Cambridge, Massachusetts, USA.</ref> Many programming languages are distinguished by the characteristics of their type systems.


=== Program analysis and transformation ===
=== Program analysis and transformation ===
{{main|Program analysis|Program transformation}}
{{Further|Program analysis|Program transformation}}
Program analysis is the general problem of examining a program and determining key characteristics (such as the absence of classes of [[Software bug|program errors]]). 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 [[Software bug|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 ===
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]]s.
Comparative programming language analysis seeks to classify languages into different types based on their characteristics; broad categories of languages are often known as [[programming paradigm]]s.


=== Generic and metaprogramming ===
=== Generic and metaprogramming ===
Line 75: Line 75:


=== Domain-specific languages ===
=== Domain-specific languages ===
[[Domain-specific language]]s are languages constructed to efficiently solve problems of a particular part of domain.
[[Domain-specific language]]s are those constructed to efficiently solve problems in a given domain, or part of such.


=== Compiler construction ===
=== Compiler construction ===
{{main|Compiler construction}}
{{Further|Compiler construction}}
[[Compiler]] theory is the theory of writing ''compilers'' (or more generally, ''translators''); programs that translate a program written in one language into another form. The actions of a compiler are traditionally broken up into ''syntax analysis'' ([[Lexical analysis#Scanner|scan]]ning and [[parsing]]), ''semantic analysis'' (determining what a program should do), ''[[Compiler optimization|optimization]]'' (improving the performance of a program as indicated by some metric; typically execution speed) and ''[[Code generation (compiler)|code generation]]'' (generation and output of an equivalent program in some target language; often the [[instruction set]] of a CPU).
[[Compiler]] theory is the theory of writing ''compilers'' (or more generally, ''translators''); programs that translate a program written in one language into another form. The actions of a compiler are traditionally broken up into ''syntax analysis'' ([[Lexical analysis#Scanner|scan]]ning and [[parsing]]), ''semantic analysis'' (determining what a program should do), ''[[Compiler optimization|optimization]]'' (improving the performance of a program as indicated by some metric; typically execution speed) and ''[[Code generation (compiler)|code generation]]'' (generation and output of an equivalent program in some target language; often the [[instruction set architecture]] of a [[central processing unit]] (CPU)).


=== Run-time systems ===
=== Run-time systems ===
Line 85: Line 85:


== Journals, publications, and conferences ==
== 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), [[Conference on Programming Language Design and Implementation|''Programming Language Design and Implementation'']] (PLDI), the ''[[International Conference on Functional Programming]]'' (ICFP), ''the [[OOPSLA|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)''.''
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 (conference)|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 Programming|Journal of Functional and Logic Programming]]'', and ''[[Higher-Order and Symbolic Computation]]''.
Notable journals that publish PLT research include the ''[[ACM Transactions on Programming Languages and Systems]]'' (TOPLAS), ''[[Journal of Functional Programming]]'' (JFP), ''[[Journal of Functional Programming|Journal of Functional and Logic Programming]]'', and ''[[Higher-Order and Symbolic Computation]]''.
Line 94: Line 94:


== References ==
== References ==
{{reflist}}
{{Reflist}}


== Further reading ==
== Further reading ==
Line 105: Line 105:
* [[John C. Mitchell|Mitchell, John C.]] ''Foundations for Programming Languages''.
* [[John C. Mitchell|Mitchell, John C.]] ''Foundations for Programming Languages''.
* [[John C. Mitchell|Mitchell, John C.]] ''Introduction to Programming Language Theory''.
* [[John C. Mitchell|Mitchell, John C.]] ''Introduction to Programming Language Theory''.
* [[Peter. W. O'Hearn|O'Hearn, Peter. W.]] and Tennent, Robert. D. (1997). ''[https://web.archive.org/web/20110719175135/http://www.eecs.qmul.ac.uk/~ohearn/Algol/algol.html Algol-like Languages]''. Progress in Theoretical Computer Science. Birkhauser, Boston.
* [[Peter. W. O'Hearn|O'Hearn, Peter. W.]] and Tennent, Robert. D. (1997). ''[https://web.archive.org/web/20110719175135/http://www.eecs.qmul.ac.uk/~ohearn/Algol/algol.html ALGOL-like Languages]''. Progress in Theoretical Computer Science. Birkhauser, Boston.
* [[Benjamin C. Pierce|Pierce, Benjamin C.]] (2002). ''[http://www.cis.upenn.edu/~bcpierce/tapl/main.html Types and Programming Languages]''. MIT Press.
* [[Benjamin C. Pierce|Pierce, Benjamin C.]] (2002). ''[http://www.cis.upenn.edu/~bcpierce/tapl/main.html Types and Programming Languages]''. MIT Press.
* Pierce, Benjamin C. ''Advanced Topics in Types and Programming Languages''.
* Pierce, Benjamin C. ''Advanced Topics in Types and Programming Languages''.
Line 114: Line 114:
*[http://lambda-the-ultimate.org/policies#Purpose Lambda the Ultimate], a community weblog for professional discussion and repository of documents on programming language theory.
*[http://lambda-the-ultimate.org/policies#Purpose Lambda the Ultimate], a community weblog for professional discussion and repository of documents on programming language theory.
*[http://www.cis.upenn.edu/~bcpierce/courses/670Fall04/GreatWorksInPL.shtml Great Works in Programming Languages]. Collected by [[Benjamin C. Pierce]] ([[University of Pennsylvania]]).
*[http://www.cis.upenn.edu/~bcpierce/courses/670Fall04/GreatWorksInPL.shtml Great Works in Programming Languages]. Collected by [[Benjamin C. Pierce]] ([[University of Pennsylvania]]).
*[https://www.cs.cmu.edu/~crary/819-f09/ Classic Papers in Programming Languages and Logic]. Collected by [[Karl Crary]] ([[Carnegie Mellon University]]).
*[https://www.cs.cmu.edu/~crary/819-f09/ Classic Papers in Programming Languages and Logic]. Collected by Karl Crary ([[Carnegie Mellon University]]).
*[https://www.cs.cmu.edu/afs/cs.cmu.edu/user/mleone/web/language-research.html Programming Language Research]. Directory by Mark Leone.
*[https://www.cs.cmu.edu/afs/cs.cmu.edu/user/mleone/web/language-research.html Programming Language Research]. Directory by Mark Leone.
*[http://turing100.acm.org/lambda_calculus_timeline.pdf λ-Calculus: Then & Now] by [[Dana S. Scott]] for the ACM Turing Centenary Celebration
*[http://turing100.acm.org/lambda_calculus_timeline.pdf λ-Calculus: Then & Now] by [[Dana S. Scott]] for the ACM Turing Centenary Celebration

Revision as of 04:40, 21 April 2025

"Theory of programming" redirects here. For the branch of CS that deals with what problems can be solved, see Theory of computation.
The lowercase Greek letter λ (lambda) is an unofficial symbol of the field of programming-language theory.[citation needed] This usage derives from the lambda calculus, a model of computation introduced by Alonzo Church in the 1930s and widely used by programming-language researchers. It graces the cover of the classic text Structure and Interpretation of Computer Programs,[1] and the title of the so-called Lambda Papers of 1975 to 1980, written by Gerald Jay Sussman and Guy L. Steele Jr., the developers of the Scheme language.

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 linguistics, mathematics, and software engineering.

History

See also: History of programming languages and Programming language § History

In some ways, the history of programming language theory predates even the development of programming languages. 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,[2] and many are described easily 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 (for Formula Translation), 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 Massachusetts Institute of Technology (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.

Timeline

See also: Timeline of programming languages

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

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.
1960s
1970s
1980s
1990s

There are several fields of study that 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.

Formal semantics

Further information: Formal semantics of programming languages

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

Further information: 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".[4] Many programming languages are distinguished by the characteristics of their type systems.

Program analysis and transformation

Further information: Program analysis and Program 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 languages into different types based on their characteristics; broad categories of 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 those constructed to efficiently solve problems in a given domain, or part of such.

Compiler construction

Further information: Compiler construction

Compiler theory is the theory of writing compilers (or more generally, translators); programs that 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 architecture of a central processing unit (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.

See also

References

  1. ^ Abelson, Harold; Sussman, Gerald Jay; Sussman, Julie (1996). Structure and Interpretation of Computer Programs (2nd ed.). Cambridge, Massachusetts: MIT Press. ISBN 0-262-01153-0. OCLC 34576857.
  2. ^ "Models Of Computation". wiki.c2.com. December 3, 2014. Archived from the original on November 30, 2020.
  3. ^ C. Böhm and W. Gross (1996). Introduction to the CUCH. In E. R. Caianiello (ed.), Automata Theory, p. 35–64.
  4. ^ Benjamin C. Pierce. 2002. Types and Programming Languages. MIT Press, Cambridge, Massachusetts, USA.

Further reading

See also: Programming language § Further reading, and Semantics of programming languages § Further reading
Wikimedia Commons has media related to Programming language theory.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Programming_language_theory&oldid=1286647407"