Programming language theory

"Theory of programming" redirects here. For the branch of CS that deals with what problems can be solved, seeTheory of computation.

The lowercaseGreekletter λ (lambda) is an unofficial symbol of the field of programming-language theory.This usage derives from thelambda calculus,amodel of computationintroduced byAlonzo Churchin the 1930s and widely used by programming-language researchers. It graces the coverof the classic textStructure and Interpretation of Computer Programs,and the title of the so-calledLambda Papersof 1975 to 1980, written byGerald Jay SussmanandGuy Steele,the developers of theScheme programming language.

Programming language theory(PLT) is a branch ofcomputer sciencethat deals with the design, implementation, analysis, characterization, and classification offormal languagesknown asprogramming languages.Programming language theory is closely related to other fields includingmathematics,software engineering,andlinguistics.There are a number ofacademic conferencesandjournalsin the area.

History

See also:History of programming languagesandProgramming language § History

In some ways, the history of programming language theory predates even the development of programming languages themselves. Thelambda calculus,developed by Alonzo Church andStephen Cole Kleenein the 1930s, is considered by some to be the world's first programming language, even though it was intended tomodelcomputation rather than being a means for programmers todescribealgorithms to a computer system. Many modernfunctional programming languageshave 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 wasPlankalkül,which was designed byKonrad Zusein the 1940s, but not publicly known until 1972 (and not implemented until 1998). The first widely known and successfulhigh-level programming languagewasFortran,developed from 1954 to 1957 by a team ofIBMresearchers led byJohn 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 wasALGOL 58.Separately,John McCarthyofMITdevelopedLisp,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 Chomskydeveloped theChomsky hierarchyin the field of linguistics, a discovery which has directly impacted programming language theory and other branches of computer science.

1960s

• In 1962, theSimulalanguage was developed byOle-Johan DahlandKristen Nygaard;it is widely considered to be the first example of anobject-oriented programming language;Simula also introduced the concept ofcoroutines.
• In 1964,Peter Landinis the first to realize Church's lambda calculus can be used to model programming languages. He introduces theSECD machinewhich "interprets" lambda expressions.
• In 1965, Landin introduces theJ operator,essentially a form ofcontinuation.
• In 1966, Landin introducesISWIM,an abstract computerprogramming languagein his articleThe Next 700 Programming Languages.It is influential in the design of languages leading to theHaskellprogramming language.
• In 1966,Corrado Böhmintroduced the programming languageCUCH(Curry-Church).
• In 1967,Christopher Stracheypublishes his influential set of lecture notesFundamental Concepts in Programming Languages,introducing the terminologyR-values,L-values,parametric polymorphism,andad hoc polymorphism.
• In 1969,J. Roger HindleypublishesThe Principal Type-Scheme of an Object in Combinatory Logic,later generalized into theHindley–Milnertype inferencealgorithm.
• In 1969,Tony Hoareintroduces theHoare logic,a form ofaxiomatic semantics.
• In 1969,William Alvin Howardobserved that a "high-level"proof system,referred to asnatural deduction,can be directly interpreted in itsintuitionisticversion as a typed variant of themodel of computationknown aslambda calculus.This became known as theCurry–Howard correspondence.

1970s

• In 1970,Dana Scottfirst publishes his work ondenotational semantics.
• In 1972,logic programmingandPrologwere developed thus allowing computer programs to be expressed as mathematical logic.
• A team of scientists atXerox PARCled byAlan KaydevelopSmalltalk,an object-oriented language widely known for its innovative development environment.
• In 1974,John C. ReynoldsdiscoversSystem F.It had already been discovered in 1971 by the mathematical logicianJean-Yves Girard.
• From 1975,Gerald Jay SussmanandGuy Steeledevelop theScheme programming language,a Lisp dialect incorporatinglexical scoping,a unified namespace, and elements from theactor modelincluding first-classcontinuations.
• Backus, at the 1977Turing Awardlecture, assailed the current state of industrial languages and proposed a new class of programming languages now known asfunction-level programminglanguages.
• In 1977,Gordon PlotkinintroducesProgramming Computable Functions,an abstract typed functional language.
• In 1978,Robin Milnerintroduces theHindley–Milner type inference algorithmforML.Type theorybecame applied as a discipline to programming languages, this application has led to tremendous advances in type theory over the years.

1980s

• In 1981,Gordon Plotkinpublishes his paper onstructured operational semantics.
• In 1988,Gilles Kahnpublished his paper onnatural semantics.
• There emergedprocess calculi,such as theCalculus of Communicating SystemsofRobin Milner,and theCommunicating sequential processesmodel ofC. A. R. Hoare,as well as similar models of concurrency such as theactor modelofCarl Hewitt.
• In 1985, the release ofMirandasparks 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 Meyercreated the methodologyDesign by contractand incorporated it into theEiffel programming language.

1990s

• Gregor Kiczales,Jim Des Rivieres andDaniel G. Bobrowpublished the bookThe Art of the Metaobject Protocol.
• Eugenio MoggiandPhilip Wadlerintroduced the use ofmonadsfor structuring programs written infunctional programming languages.

Sub-disciplines and related fields

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 ofmathematics,includingcomputability theory,category theory,andset theory.

Formal semantics

Main article: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 aredenotational semantics,operational semanticsandaxiomatic semantics.

Type theory

Main article:Type theory

Type theory is the study oftype 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".Many programming languages are distinguished by the characteristics of their type systems.

Program analysis and transformation

Main articles:Program analysisandProgram transformation

Program analysis is the general problem of examining a program and determining key characteristics (such as the absence of classes ofprogram 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 asprogramming paradigms.

Generic and metaprogramming

Metaprogrammingis 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 languagesare languages constructed to efficiently solve problems of a particular part of domain.

Compiler construction

Main article:Compiler construction

Compilertheory is the theory of writingcompilers(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 intosyntax analysis(scanningandparsing),semantic analysis(determining what a program should do),optimization(improving the performance of a program as indicated by some metric; typically execution speed) andcode generation(generation and output of an equivalent program in some target language; often theinstruction setof a CPU).

Run-time systems

Run-time systemsrefer to the development of programming languageruntime environmentsand their components, includingvirtual machines,garbage collection,andforeign function interfaces.

Journals, publications, and conferences

Conferences are the primary venue for presenting research in programming languages. The most well known conferences include theSymposium on Principles of Programming Languages(POPL),Programming Language Design and Implementation(PLDI), theInternational Conference on Functional Programming(ICFP),theInternational Conference on Object Oriented Programming, Systems, Languages and Applications(OOPSLA) andtheInternational Conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS).

Notable journals that publish PLT research include theACM Transactions on Programming Languages and Systems(TOPLAS),Journal of Functional Programming(JFP),Journal of Functional and Logic Programming,andHigher-Order and Symbolic Computation.

See also

• SIGPLAN
• Very high-level programming language

Further reading

See also:Programming language § Further reading,andSemantics of programming languages § Further reading

• Abadi, MartínandCardelli, Luca.A Theory of Objects.Springer-Verlag.
• Michael J. C. Gordon.Programming Language Theory and Its Implementation.Prentice Hall.
• Gunter, Carl andMitchell, 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

• Lambda the Ultimate,a community weblog for professional discussion and repository of documents on programming language theory.
• Great Works in Programming Languages.Collected byBenjamin C. Pierce(University of Pennsylvania).
• Classic Papers in Programming Languages and Logic.Collected byKarl Crary(Carnegie Mellon University).
• Programming Language Research.Directory by Mark Leone.
• λ-Calculus: Then & NowbyDana S. Scottfor the ACM Turing Centenary Celebration
• Grand Challenges in Programming Languages.Panel session atPOPL2009.