Functional programming: Difference between revisions

Revision as of 10:38, 12 December 2024

Latest revision as of 03:15, 10 August 2025

(17 intermediate revisions by 11 users not shown)

Line 13:

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 conferencebook |first=John |last=McCarthy |author-link=John McCarthy (computer scientist) |title=The first ACM SIGPLAN conference on History of Lispprogramming languages - HOPL-1 |journalchapter=History of Programming LanguagesLISP |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 ana assembly[[Low-level programming language|low-level programming 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]].

Line 165:

=== Imperative vs. functional programming ===

The following two examples (written in [[JavaScript (programming language)|JavaScript]]) achieve the same effect: they multiply all even numbers in an array by 10 and add them all, storing the final sum in the variable "<code>result"</code>.

Traditional imperative loop:

Line 184:

.map(a => a * 10)

.reduce((a, b) => a + b, 0);

</syntaxhighlight>Sometimes the abstractions offered by functional programming might lead to development of more robust code that avoids certain issues that might arise when building upon large amount of complex, imperative code, such as [[Offoff-by-one error|off-by-one errors]]s (see [[Greenspun's tenth rule]]).

=== Simulating state ===

Line 197:

<!-- TO DO: Expand / example code?? -->

Alternative methods such as [[Hoare logic]] and [[uniqueness type|uniqueness]] have been developed to track side effects in programs. Some modern research languages use [[effect system]]s to make the presence of side effects explicit.<ref>{{Citationcite book |lastlast1=Hartmanis |firstfirst1=Juris |title=Complexity classes without machines: On complete languages for UP |date=1986 |work=Lecture Notes in Computer Science |pages=123–135 |url=https://doi.org/10.1007/3-540-16761-7_62 |access-date=2024-12-12 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |isbn=978-3-540-16761-7 |last2=Hemachandra |first2=Lane|title=Automata, Languages and Programming |chapter=Complexity classes without machines: On complete languages for UP |series=Lecture Notes in Computer Science |volume=226 |doi=10.1007/3-540-16761-7_62 }}</ref>

<!-- TO DO: Expand -->

Line 228:

</syntaxhighlight>

has the mean execution time of 4.76 ms, while the second one, in which <syntaxhighlight lang="clojure" inline>.equals</syntaxhighlight> is a direct invocation of the underlying [[Java (programming language)|Java]] method, has a mean execution time of 2.8 μs – roughly 1700 times faster. Part of that can be attributed to the type checking and exception handling involved in the implementation of <syntaxhighlight lang="clojure" inline>even?</syntaxhighlight>,. so let's take forFor instance the [https://github.com/samber/lo lo library] for [[Go (programming language)|Go]], which implements various higher-order functions common in functional programming languages using [[Generic programming|generics]]. In a benchmark provided by the library's author, calling <code>map</code> is 4% slower than an equivalent <code>for</code> loop and has the same [[Memory management|allocation]] profile,<ref>{{Citation |last=Berthe |first=Samuel |title=samber/lo |date=2024-04-29 |url=https://github.com/samber/lo |access-date=2024-04-29}}</ref> which can be attributed to various compiler optimizations, such as [[inlining]].<ref>{{Cite web |title=Go Wiki: Compiler And Runtime Optimizations - The Go Programming Language |url=https://go.dev/wiki/CompilerOptimizations |access-date=2024-04-29 |website=go.dev |language=en}}</ref>

One distinguishing feature of [[Rust (programming language)|Rust]] are ''zero-cost abstractions''. This means that using them imposes no additional runtime overhead. This is achieved thanks to the compiler using [[loop unrolling]], where each iteration of a loop, be it imperative or using iterators, is converted into a standalone [[Assembly language|Assembly]] instruction, without the overhead of the loop controlling code. If an iterative operation writes to an array, the resulting array's elements [[Register allocation|will be stored in specific CPU registers]], allowing for [[Time complexity|constant-time access]] at runtime.<ref>{{Cite web |title=Comparing Performance: Loops vs. Iterators - The Rust Programming Language |url=https://doc.rust-lang.org/book/ch13-04-performance.html |access-date=2024-04-29 |website=doc.rust-lang.org}}</ref>

Line 236:

It is possible to use a functional style of programming in languages that are not traditionally considered functional languages.<ref>{{cite journal |last=Hartel |first=Pieter |author2=Henk Muller |author3=Hugh Glaser |title=The Functional C experience |journal=Journal of Functional Programming |volume=14 |issue=2 |pages=129–135 |date=March 2004 |url=http://www.ub.utwente.nl/webdocs/ctit/1/00000084.pdf |doi=10.1017/S0956796803004817 |s2cid=32346900 |accessdate=2006-05-28 |archivedate=2011-07-19 |archiveurl=https://web.archive.org/web/20110719201553/http://www.ub.utwente.nl/webdocs/ctit/1/00000084.pdf |url-status=deviated }}; {{cite web |title=Functional programming in Python, Part 3 |url=http://www-128.ibm.com/developerworks/linux/library/l-prog3.html |archive-url=https://web.archive.org/web/20071016124848/http://www-128.ibm.com/developerworks/linux/library/l-prog3.html |archive-date=2007-10-16 |author=David Mertz |access-date=2006-09-17 |work=IBM developerWorks }}([https://web.archive.org/web/20071016124848/http://www-128.ibm.com/developerworks/linux/library/l-prog.html Part 1], [https://web.archive.org/web/20071016124848/http://www-128.ibm.com/developerworks/linux/library/l-prog2.html Part 2])</ref> For example, both [[D (programming language)|D]]<ref>{{cite web |url=http://www.digitalmars.com/d/2.0/function.html#pure-functions |title=Functions&nbsp;— D Programming Language 2.0 |publisher=Digital Mars |date=30 December 2012}}</ref> and [[Fortran 95]]<ref name=fortran95/> explicitly support pure functions.

[[JavaScript]], [[Lua (programming language)|Lua]],<ref>{{cite web|url=http://www.luafaq.org/#T1.2|title=Lua Unofficial FAQ (uFAQ)}}</ref> [[Python (programming language)|Python]] and [[Go (programming language)|Go]]<ref>{{Cite web|title=First-Class Functions in Go - The Go Programming Language|url=https://golang.org/doc/codewalk/functions/|access-date=2021-01-04|website=golang.org}}</ref> had [[First-class function|first class functions]] from their inception.<ref>{{cite web|url=https://brendaneich.com/2008/04/popularity/|first=Brendan|last= Eich|title=Popularity|date=3 April 2008}}</ref> Python had support for "[[anonymous function|lambda]]", "[[Map (higher-order function)|map]]", "[[Fold (higher-order function)|reduce]]", and "[[Filter (higher-order function)|filter]]" in 1994, as well as closures in Python 2.2,<ref>{{cite web |url=http://python-history.blogspot.de/2009/04/origins-of-pythons-functional-features.html |title=Origins of Python's "Functional" Features |last=van Rossum |first=Guido |author-link=Guido van Rossum |date=2009-04-21 |access-date=2012-09-27}}</ref> though Python 3 relegated "reduce" to the <code>functools</code> standard library module.<ref>{{cite web |url=https://docs.python.org/dev/library/functools.html#functools.reduce |title=functools — Higher order functions and operations on callable objects |publisher=Python Software Foundation |date=2011-07-31 |access-date=2011-07-31}}</ref> First-class functions have been introduced into other mainstream languages such as [[Perl]] 5.0 in 1994, [[PHP]] 5.3, [[Visual Basic 9]], [[C Sharp (programming language)|C#]] 3.0, [[C++11]], and [[Kotlin (programming language)|Kotlin]].<ref name=":0"/>{{citation needed|date=April 2015}}

In Perl, [[anonymous function|lambda]], [[Map (higher-order function)|map]], [[Fold (higher-order function)|reduce]], [[Filter (higher-order function)|filter]], and [[Closure (computer science)|closures]] are fully supported and frequently used. The book [[Higher-Order Perl]], released in 2005, was written to provide an expansive guide on using Perl for functional programming.

In PHP, [[anonymous class]]es, [[Closure (computer science)|closures]] and lambdas are fully supported. Libraries and language extensions for immutable data structures are being developed to aid programming in the functional style.

Line 244 ⟶ 246:

In [[C Sharp (programming language)|C#]], anonymous classes are not necessary, because closures and lambdas are fully supported. Libraries and language extensions for immutable data structures are being developed to aid programming in the functional style in C#.

Many [[Object-oriented programming|object-oriented]] [[Design pattern (computer science)|design patterns]] are expressible in functional programming terms: for example, the [[strategy pattern]] simply dictates use of a higher-order function, and the [[visitor (design pattern)|visitor]] pattern roughly corresponds to a [[catamorphism]], or [[fold (higher-order function)|fold]].

Similarly, the idea of immutable data from functional programming is often included in imperative programming languages,<ref>{{cite book |title=Effective Java |edition=Second |first=Joshua |last=Bloch |chapter=Item 15: Minimize Mutability |isbn=978-0321356680 |date=2008 |publisher=Addison-Wesley |url-access=registration |url=https://archive.org/details/effectivejava00bloc_0}}</ref> for example the tuple in Python, which is an immutable array, and Object.freeze() in JavaScript.<ref>{{Cite web|last=|first=|date=|title=Object.freeze() - JavaScript {{!}} MDN|url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/freeze|access-date=2021-01-04|website=developer.mozilla.org|quote=The Object.freeze() method freezes an object. A frozen object can no longer be changed; freezing an object prevents new properties from being added to it, existing properties from being removed, prevents changing the enumerability, configurability, or writability of existing properties, and prevents the values of existing properties from being changed. In addition, freezing an object also prevents its prototype from being changed. freeze() returns the same object that was passed in.}}</ref>

Line 335 ⟶ 337:

=== Education ===

Many [[University|universities]] teach functional programming.<ref name="oxfordFP">{{cite web|url=https://www.cs.ox.ac.uk/teaching/courses/2019-2020/fp/|title=Functional Programming: 2019-2020|publisher=University of Oxford Department of Computer Science|access-date=28 April 2020}}</ref><ref name="imperialFP">{{cite web|url=https://www.imperial.ac.uk/computing/current-students/courses/120_1/|title=Programming I (Haskell)|publisher=Imperial College London Department of Computing|access-date=28 April 2020}}</ref><ref name="nottinghamFP">{{cite web|url=https://www.nottingham.ac.uk/ugstudy/course/Computer-Science-BSc#yearsmodules|title=Computer Science BSc - Modules|access-date=28 April 2020}}</ref><ref name="mitFP">{{cite book|last1=Abelson|first1=Hal|author-link1=Hal Abelson|last2=Sussman|first2=Gerald Jay|author-link2=Gerald Jay Sussman |title=Structure and Interpretation of Computer Programs |url=http://mitpress.mit.edu/sicp/ |year=1985|publisher=MIT Press|chapter=Preface to the Second Edition|edition=2|bibcode=1985sicp.book.....A |chapter-url=https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-6.html}}</ref> Some treat it as an introductory programming concept<ref name="mitFP"/> while others first teach imperative programming methods.<ref name="nottinghamFP"/><ref name="61A">{{cite web|url=https://cs61a.org/articles/about.html|title=Computer Science 61A, Berkeley|author=John DeNero|date=Fall 2019|publisher=Department of Electrical Engineering and Computer Sciences, Berkeley|access-date=2020-08-14}}</ref>

Outside of computer science, functional programming is used to teach problem-solving, algebraic and geometric concepts.<ref name="bootstrapworld">{{Triangulation|196|Emmanuel Schanzer of Bootstrap}}</ref> It has also been used to teach classical mechanics, as in the book ''[[Structure and Interpretation of Classical Mechanics]]''.

Line 369 ⟶ 371:

<ref name="larson2009">{{cite journal |last=Larson |first=Jim |title=Erlang for concurrent programming |journal=Communications of the ACM |volume= 52 |issue= 3 |date=March 2009 |doi=10.1145/1467247.1467263 |page=48 |s2cid=524392 |doi-access=free}}</ref>

<ref name="minksy2008">{{cite journal |last1=Minsky |first1=Yaron |last2=Weeks |first2=Stephen |title=Caml Trading&nbsp;— experiences with functional programming on Wall Street |journal=Journal of Functional Programming |volume=18 |issue=4 |pages=553–564 |date=July 2008 |doi=10.1017/S095679680800676X |doi-broken-date=1 November 2024 |s2cid=30955392 |doi-access=free }}</ref>

<ref name="leroy2007">{{cite conference |last=Leroy |first=Xavier |title=Some uses of Caml in Industry |url=http://cufp.galois.com/2007/slides/XavierLeroy.pdf |conference=CUFP 2007 |access-date=2009-08-26 |archivedate=2011-10-08 |archiveurl=https://web.archive.org/web/20111008170929/http://cufp.galois.com/2007/slides/XavierLeroy.pdf |url-status=dead }}</ref><ref name="haskell-industry">{{cite web |title=Haskell in industry |work=Haskell Wiki |url=http://www.haskell.org/haskellwiki/Haskell_in_industry |access-date=2009-08-26 |quote=Haskell has a diverse range of use commercially, from aerospace and defense, to finance, to web startups, hardware design firms and lawnmower manufacturers.}}</ref>

Line 385 ⟶ 387:

<ref name="Amath-CO">{{cite web |website=Department of Applied Math |publisher=University of Colorado |title=Functional vs. Procedural Programming Language |url=http://amath.colorado.edu/computing/mmm/funcproc.html |archive-url=https://web.archive.org/web/20071113175801/http://amath.colorado.edu/computing/mmm/funcproc.html |archive-date=2007-11-13 |access-date=2006-08-28 |url-status=dead }}</ref>

<ref name="Novatchev">{{cite web |url=httphttps://fxsl.sourceforge.net/articles/FuncProg/Functional%20Programming.html |first=Dimitre |last=Novatchev |title=The Functional Programming Language XSLT — A proof through examples |access-date=May 27, 2006}}</ref><ref name="Mertz">{{cite web |url=http://gnosis.cx/publish/programming/xml_models_fp.html |first=David |last=Mertz |title=XML Programming Paradigms (part four): Functional Programming approached to XML processing |access-date=May 27, 2006 |work=IBM developerWorks}}</ref>

<ref name="Chamberlin_Boyce">{{cite journal |title=SEQUEL: A structured English query language |first1=Donald D. |last1=Chamberlin |author-link1=Donald D. Chamberlin |first2=Raymond F. |last2=Boyce |author-link2=Raymond F. Boyce |journal=Proceedings of the 1974 ACM SIGFIDET |pages=249–264 |year=1974}}</ref><ref name="Sim-Diasca">{{cite web |title=Sim-Diasca: a large-scale discrete event concurrent simulation engine in Erlang |url=http://research.edf.com/research-and-the-scientific-community/software/sim-diasca-80704.html |date=November 2011 |access-date=2011-11-08 |archive-date=2013-09-17 |archive-url=https://web.archive.org/web/20130917092159/http://research.edf.com/research-and-the-scientific-community/software/sim-diasca-80704.html |url-status=dead }}</ref>

<ref name="Spiewak">{{cite web |url=http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala |first=Daniel |last=Spiewak |title=Implementing Persistent Vectors in Scala |date=26 August 2008 |website=Code Commit |access-date=17 April 2012 |archivedate=23 September 2015 |archiveurl=https://web.archive.org/web/20150923205254/http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala |url-status=deviated }}</ref>

Line 393 ⟶ 395:

== Further reading ==

* {{cite book |last1=Abelson |first1=Hal |author-link1=Hal Abelson |last2=Sussman |first2=Gerald Jay |author-link2=Gerald Jay Sussman |title=Structure and Interpretation of Computer Programs |url=https://mitpress.mit.edu/9780262510363/structure-and-interpretation-of-computer-programs/ |year=1985 |publisher=MIT Press|bibcode=1985sicp.book.....A }}

* Cousineau, Guy and Michel Mauny. ''The Functional Approach to Programming''. Cambridge, UK: [[Cambridge University Press]], 1998.

* Curry, Haskell Brooks and Feys, Robert and Craig, William. ''Combinatory Logic''. Volume I. North-Holland Publishing Company, Amsterdam, 1958.

Line 428 ⟶ 430:

{{Programming paradigms navbox}}

{{Types of programming languages}}

{{Authority control}}

Line 434 ⟶ 435:

[[Category:Functional programming| ]]

[[Category:Programming paradigms]]

[[Category:Programming language comparisons]]

<!-- Hidden categories below -->

[[Category:Articles with example C code]]

[[Category:Articles with example JavaScript code]]

[[Category:Articles with example Lisp (programming language) code]]