Editing Functional programming (section)

== History ==
The [[lambda calculus]], developed in the 1930s by [[Alonzo Church]], is a [[formal system]] of [[computation]] built from [[function application]]. In 1937 [[Alan Turing]] proved that the lambda calculus and [[Turing machines]] are equivalent models of computation,<ref>{{cite journal|first=A. M.|last=Turing|doi=10.2307/2268280|title=Computability and λ-definability|year=1937|journal=The Journal of Symbolic Logic|pages=153–163|volume=2|issue=4|publisher=Cambridge University Press|jstor=2268280|s2cid=2317046}}</ref> showing that the lambda calculus is [[Turing complete]]. Lambda calculus forms the basis of all functional programming languages. An equivalent theoretical formulation, [[combinatory logic]], was developed by [[Moses Schönfinkel]] and [[Haskell Curry]] in the 1920s and 1930s.<ref>{{cite book|author1=Haskell Brooks Curry|author2=Robert Feys|title=Combinatory Logic|url=https://archive.org/details/combinatorylogic0002curr|url-access=registration|access-date=10 February 2013|year=1958|publisher=North-Holland Publishing Company}}</ref>

Church later developed a weaker system, the [[simply typed lambda calculus]], which extended the lambda calculus by assigning a [[data type]] to all terms.<ref>{{cite journal |last1=Church |author-link=Alonzo Church |first1=A. |year=1940 |title=A Formulation of the Simple Theory of Types |journal=Journal of Symbolic Logic |volume=5 |issue=2 |pages=56–68 |doi=10.2307/2266170 |jstor=2266170| s2cid=15889861}}</ref> This forms the basis for statically typed functional programming.

The first [[High-level programming language|high-level]] functional programming language, [[Lisp (programming language)|Lisp]], was developed in the late 1950s for the [[IBM 700/7000 series#Scientific Architecture|IBM 700/7000 series]] of scientific computers by [[John McCarthy (computer scientist)|John McCarthy]] while at [[Massachusetts Institute of Technology]] (MIT).<ref>{{cite conference |first=John |last=McCarthy |author-link=John McCarthy (computer scientist) |title=History of Lisp |journal=History of Programming Languages |pages=173–185 |date=June 1978 |url=http://jmc.stanford.edu/articles/lisp/lisp.pdf|doi=10.1145/800025.808387 |place=Los Angeles, CA}}</ref> Lisp functions were defined using Church's lambda notation, extended with a label construct to allow [[Recursion (computer science)|recursive]] functions.<ref>{{cite journal|author=John McCarthy|author-link=John McCarthy (computer scientist)|title=Recursive functions of symbolic expressions and their computation by machine, Part I.|journal=Communications of the ACM|volume=3|issue=4|year=1960|pages=184–195|url=http://jmc.stanford.edu/articles/recursive/recursive.pdf|publisher=ACM New York, NY, US|doi=10.1145/367177.367199|s2cid=1489409}}</ref> Lisp first introduced many paradigmatic features of functional programming, though early Lisps were [[Programming paradigm#Multi-paradigm|multi-paradigm languages]], and incorporated support for numerous programming styles as new paradigms evolved. Later dialects, such as [[Scheme (programming language)|Scheme]] and [[Clojure]], and offshoots such as [[Dylan (programming language)|Dylan]] and [[Julia (programming language)|Julia]], sought to simplify and rationalise Lisp around a cleanly functional core, while [[Common Lisp]] was designed to preserve and update the paradigmatic features of the numerous older dialects it replaced.<ref>{{cite book|author1=Guy L. Steele |author2=Richard P. Gabriel |title=History of programming languages---II |chapter=The evolution of Lisp |pages= 233–330 |date=February 1996 |url=http://dreamsongs.com/Files/HOPL2-Uncut.pdf |doi= 10.1145/234286.1057818 |isbn=978-0-201-89502-5 |s2cid=47047140}}</ref>

[[Information Processing Language]] (IPL), 1956, is sometimes cited as the first computer-based functional programming language.<ref>The memoir of [[Herbert A. Simon]] (1991), ''Models of My Life'' pp.189-190 {{ISBN|0-465-04640-1}} claims that he, Al Newell, and Cliff Shaw are "...commonly adjudged to be the parents of [the] artificial intelligence [field]," for writing [[Logic Theorist]], a program that proved theorems from ''[[Principia Mathematica]]'' automatically. To accomplish this, they had to invent a language and a paradigm that, viewed retrospectively, embeds functional programming.</ref> It is an [[assembly language|assembly-style language]] for manipulating lists of symbols. It does have a notion of ''generator'', which amounts to a function that accepts a function as an argument, and, since it is an assembly-level language, code can be data, so IPL can be regarded as having higher-order functions. However, it relies heavily on the mutating list structure and similar imperative features.

[[Kenneth E. Iverson]] developed [[APL (programming language)|APL]] in the early 1960s, described in his 1962 book ''A Programming Language'' ({{ISBN|9780471430148}}). APL was the primary influence on [[John Backus]]'s [[FP (programming language)|FP]]. In the early 1990s, Iverson and [[Roger Hui]] created [[J (programming language)|J]]. In the mid-1990s, [[Arthur Whitney (computer scientist)|Arthur Whitney]], who had previously worked with Iverson, created [[K (programming language)|K]], which is used commercially in financial industries along with its descendant [[Q (programming language from Kx Systems)|Q]].

In the mid-1960s, [[Peter Landin]] invented [[SECD machine]],<ref>{{cite journal
| last=Landin
| first=Peter J.
| year=1964
| title=The mechanical evaluation of expressions
| journal=[[The Computer Journal]]
| volume=6
| issue=4
| pages=308–320
| publisher=[[British Computer Society]]
| doi=10.1093/comjnl/6.4.308
| doi-access=free
}}</ref> the first [[abstract machine]] for a functional programming language,<ref>{{Cite book |last1=Diehl |first1=Stephan |last2=Hartel |first2=Pieter |last3=Sestoft |first3=Peter |date=2000 |chapter=Abstract machines for programming language implementation |title=Future Generation Computer Systems |volume=16 |issue=7 |pages=739–751}}</ref> described a correspondence between [[ALGOL 60]] and the [[lambda calculus]],<ref>{{cite journal
| last=Landin
| first=Peter J.
|date=February 1965a
| title=Correspondence between ALGOL 60 and Church's Lambda-notation: part I
| journal=[[Communications of the ACM]]
| volume=8
| issue=2
| pages=89–101
| publisher=[[Association for Computing Machinery]]
| doi=10.1145/363744.363749
| s2cid=6505810
| doi-access=free
}}</ref><ref>{{cite journal
| last=Landin
| first=Peter J.
|date=March 1965b
| title=A correspondence between ALGOL 60 and Church's Lambda-notation: part II
| journal=[[Communications of the ACM]]
| volume=8
| issue=3
| pages=158–165
| publisher=[[Association for Computing Machinery]]
| doi=10.1145/363791.363804
| s2cid=15781851
| doi-access=free
}}</ref> and proposed the [[ISWIM]] programming language.<ref>{{cite journal
| last=Landin
| first=Peter J.
| date=March 1966b
| title=The next 700 programming languages
| journal=[[Communications of the ACM]]
| volume=9
| issue=3
| pages=157–166
| publisher=[[Association for Computing Machinery]]
| doi=10.1145/365230.365257
| s2cid=13409665
| doi-access=free
}}</ref>

[[John Backus]] presented [[FP (programming language)|FP]] in his 1977 [[Turing Award]] lecture "Can Programming Be Liberated From the [[Von Neumann architecture|von Neumann]] Style? A Functional Style and its Algebra of Programs".<ref name="Backus 1977">{{Cite journal |doi=10.1145/359576.359579| title=Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs| journal=Communications of the ACM| volume=21| issue=8| pages=613–641| year=1978| last1=Backus |first1=J. |doi-access=free}}</ref> He defines functional programs as being built up in a hierarchical way by means of "combining forms" that allow an "algebra of programs"; in modern language, this means that functional programs follow the [[principle of compositionality]].{{Citation needed|reason=I dont completely agree with this interpretation of John Backus definition of functional programs, which I feel is widely misunderstood. As he is very sadly no longer alive, we can't ask him, but a reference for this interpretation, especially if it includes a justification, would be very beneficial.|date=February 2017}} Backus's paper popularized research into functional programming, though it emphasized [[function-level programming]] rather than the lambda-calculus style now associated with functional programming.

The 1973 language [[ML (programming language)|ML]] was created by [[Robin Milner]] at the [[University of Edinburgh]], and [[David Turner (computer scientist)|David Turner]] developed the language [[SASL (programming language)|SASL]] at the [[University of St Andrews]]. Also in Edinburgh in the 1970s, Burstall and Darlington developed the functional language [[NPL (programming language)|NPL]].<ref>R.M. Burstall. Design considerations for a functional programming language. Invited paper, Proc. Infotech State of the Art Conf. "The Software Revolution", Copenhagen, 45–57 (1977)</ref> NPL was based on [[Kleene's recursion theorem|Kleene Recursion Equations]] and was first introduced in their work on program transformation.<ref>R.M. Burstall and J. Darlington. A transformation system for developing recursive programs. Journal of the Association for Computing Machinery 24(1):44–67 (1977)</ref> Burstall, MacQueen and Sannella then incorporated the [[Polymorphism (computer science)|polymorphic]] type checking from ML to produce the language [[Hope (programming language)|Hope]].<ref>R.M. Burstall, D.B. MacQueen and D.T. Sannella. HOPE: an experimental applicative language. Proceedings 1980 LISP Conference, Stanford, 136–143 (1980).</ref> ML eventually developed into several dialects, the most common of which are now [[OCaml]] and [[Standard ML]].

In the 1970s, [[Guy L. Steele]] and [[Gerald Jay Sussman]] developed [[Scheme (programming language)|Scheme]], as described in the [[Lambda Papers]] and the 1985 textbook ''[[Structure and Interpretation of Computer Programs]]''. Scheme was the first dialect of lisp to use [[lexical scope|lexical scoping]] and to require [[tail-call optimization]], features that encourage functional programming.

In the 1980s, [[Per Martin-Löf]] developed [[intuitionistic type theory]] (also called ''constructive'' type theory), which associated functional programs with [[constructive proof]]s expressed as [[dependent type]]s. This led to new approaches to [[interactive theorem proving]] and has influenced the development of subsequent functional programming languages.{{citation needed|date=July 2018}}

The lazy functional language, [[Miranda (programming language)|Miranda]], developed by David Turner, initially appeared in 1985 and had a strong influence on [[Haskell]]. With Miranda being proprietary, Haskell began with a consensus in 1987 to form an [[open standard]] for functional programming research; implementation releases have been ongoing as of 1990.

More recently it has found use in niches such as parametric [[Computer Aided Design|CAD]] in the [[OpenSCAD]] language built on the [[CGAL]] framework, although its restriction on reassigning values (all values are treated as constants) has led to confusion among users who are unfamiliar with functional programming as a concept.<ref>{{cite web|url=https://forum.openscad.org/Make-discovering-assign-easier-td10964.html|website=OpenSCAD|title =Make discovering assign() easier!|archive-url=https://web.archive.org/web/20230419060430/https://forum.openscad.org/Make-discovering-assign-easier-td10964.html |archive-date=2023-04-19 }}</ref>

Functional programming continues to be used in commercial settings.<ref>{{cite web |url=https://arstechnica.com/gadgets/2018/03/developers-love-trendy-new-languages-but-earn-more-with-functional-programming/ |title=Developers love trendy new languages but earn more with functional programming |author=Peter Bright |date=March 13, 2018 |website=[[Ars Technica]]}}</ref><ref>{{cite web |url=https://www.computing.co.uk/ctg/analysis/3003123/the-slow-but-steady-rise-of-functional-programming |title=The stealthy rise of functional programming |author=John Leonard |date=January 24, 2017 |publisher=Computing}}</ref><ref>{{cite magazine |url=https://www.infoworld.com/article/3190185/software/is-functional-programming-better-for-your-startup.html |title=Is functional programming better for your startup? |author=Leo Cheung |date=May 9, 2017 |magazine=[[InfoWorld]]}}</ref>