Content deleted Content added
add info |
Reverting edit(s) by Eddie0svn (talk) to rev. 1305054549 by Bender the Bot: No reliable source (UV 0.1.6) |
||
| (48 intermediate revisions by 30 users not shown) | |||
Line 6:
In functional programming, functions are treated as [[first-class citizen]]s, meaning that they can be bound to names (including local [[Identifier (computer languages)|identifiers]]), passed as [[Parameter (computer programming)|arguments]], and [[Return value|returned]] from other functions, just as any other [[data type]] can. This allows programs to be written in a [[Declarative programming|declarative]] and [[Composability|composable]] style, where small functions are combined in a [[Modular programming|modular]] manner.
Functional programming is sometimes treated as synonymous with [[purely functional programming]], a subset of functional programming
Functional programming has its roots in [[academia]], evolving from the [[lambda calculus]], a formal system of computation based only on functions. Functional programming has historically been less popular than imperative programming, but many functional languages are seeing use today in industry and education, including [[Common Lisp]], [[Scheme (programming language)|Scheme]],<ref name="clinger1987"/><ref name="hartheimer1987"/><ref name="kidd2007"/><ref name="cleis2006"/> [[Clojure]], [[Wolfram Language]],<ref name="reference.wolfram.com">{{cite web |title=Wolfram Language Guide: Functional Programming |url=http://reference.wolfram.com/language/guide/FunctionalProgramming.html |year=2015 |access-date=2015-08-24}}</ref><ref name="Amath-CO"/> [[Racket (programming language)|Racket]],<ref name="racket-video-games"/> [[Erlang (programming language)|Erlang]],<ref name="erlang-faq"/><ref name="armstrong2007"/><ref name="larson2009"/> [[Elixir (programming language)|Elixir]],<ref>{{Cite web|title=The Elixir Programming Language|url=https://elixir-lang.org/|access-date=2021-02-14}}</ref> [[OCaml]],<ref name="minksy2008"/><ref name="leroy2007"/> [[Haskell]],<ref name="haskell-industry"/><ref name="hudak2007"/> and [[F Sharp (programming language)|F#]].<ref name="quantFSharp">{{cite conference |last=Mansell |first=Howard |title=Quantitative Finance in F# |url=http://cufp.galois.com/2008/abstracts.html#MansellHoward |year=2008 |conference=CUFP 2008 |access-date=2009-08-29 |archivedate=2015-07-08 |archiveurl=https://web.archive.org/web/20150708125937/http://cufp.galois.com/2008/abstracts.html#MansellHoward |url-status=dead }}</ref><ref name="businessAppsFSharp">{{cite conference |last=Peake |first=Alex |title=The First Substantial Line of Business Application in F# |url=http://cufp.galois.com/2009/abstracts.html#AlexPeakeAdamGranicz |year=2009 |conference=CUFP 2009 |access-date=2009-08-29 |archive-url=https://web.archive.org/web/20091017070140/http://cufp.galois.com/2009/abstracts.html#AlexPeakeAdamGranicz |archive-date=2009-10-17 |url-status=dead }}</ref> [[Lean (proof assistant)|Lean]] is a functional programming language commonly used for verifying mathematical theorems.<ref>{{cite conference |conference=Conference on Automated Deduction |title=The Lean 4 Theorem Prover and Programming Language |last1=de Moura |first1=Leonardo |last2=Ullrich |first2=Sebastian |date=July 2021 |book-title=Lecture Notes in Artificial Intelligence |volume=12699 |pages=625–635 |issn=1611-3349 |doi=10.1007/978-3-030-79876-5_37 |doi-access=free}}</ref> Functional programming is also key to some languages that have found success in specific domains, like [[JavaScript]] in the Web,<ref>{{Cite web|last=Banz|first=Matt|date=2017-06-27|title=An introduction to functional programming in JavaScript|url=https://opensource.com/article/17/6/functional-javascript|access-date=2021-01-09|website=Opensource.com|language=en}}</ref> [[R (programming language)|R]] in statistics,<ref name="useR"/><ref name="Chambers"/> [[J (programming language)|J]], [[K (programming language)|K]] and [[Q (programming language from Kx Systems)|Q]] in financial analysis, and [[XQuery]]/[[XSLT]] for [[XML]].<ref name="Novatchev"/><ref name="Mertz"/> Domain-specific declarative languages like [[SQL]] and [[Lex (software)|Lex]]/[[Yacc]] use some elements of functional programming, such as not allowing [[mutable object|mutable values]].<ref name="Chamberlin_Boyce"/> In addition, many other programming languages support programming in a functional style or have implemented features from functional programming, such as [[C++11]], [[C Sharp (programming language)|C#]],<ref>{{Citation|title=Functional Programming with C# - Simon Painter - NDC Oslo 2020| date=8 August 2021 |url=https://www.youtube.com/watch?v=gvyTB4aMI4o| archive-url=https://ghostarchive.org/varchive/youtube/20211030/gvyTB4aMI4o| archive-date=2021-10-30|language=en|access-date=2021-10-23}}{{cbignore}}</ref> [[Kotlin (programming language)|Kotlin]],<ref name=":0">{{Cite web|url=https://kotlinlang.org/docs/tutorials/kotlin-for-py/functional-programming.html|title=Functional programming - Kotlin Programming Language|website=Kotlin|access-date=2019-05-01}}</ref> [[Perl]],<ref>{{cite book |last=Dominus |first=Mark J. |author-link=Mark Jason Dominus |title=Higher-Order Perl |publisher=[[Morgan Kaufmann]] |year=2005 |isbn=978-1-55860-701-9 |title-link=Higher-Order Perl}}</ref> [[PHP]],<ref>{{cite book |last=Holywell |first=Simon |title=Functional Programming in PHP |publisher=php[architect] |year=2014 |isbn=9781940111056}}</ref> [[Python (programming language)|Python]],<ref name="AutoNT-13">{{cite web |url=https://www.python.org/community/pycon/dc2004/papers/24/metaclasses-pycon.pdf |archive-url=https://web.archive.org/web/20090530030205/http://www.python.org/community/pycon/dc2004/papers/24/metaclasses-pycon.pdf |archive-date=30 May 2009 |title=Python Metaclasses: Who? Why? When? |last=The Cain Gang Ltd. |access-date=27 June 2009 |url-status=dead |df=dmy-all }}</ref> [[Go (programming language)|Go]],<ref>{{Cite web|last=|first=|date=22 December 2020|title=GopherCon 2020: Dylan Meeus - Functional Programming with Go|url=https://www.youtube.com/watch?v=wqs8n5Uk5OM|access-date=|website=YouTube}}</ref> [[Rust (programming language)|Rust]],<ref>{{Cite web|title=Functional Language Features: Iterators and Closures - The Rust Programming Language|url=https://doc.rust-lang.org/book/ch13-00-functional-features.html|access-date=2021-01-09|website=doc.rust-lang.org}}</ref> [[Raku (programming language)|Raku]],<ref>{{cite web|last=Vanderbauwhede |first=Wim |url=https://wimvanderbauwhede.github.io/articles/decluttering-with-functional-programming/|archive-url=https://web.archive.org/web/20200728013926/https://wimvanderbauwhede.github.io/articles/decluttering-with-functional-programming/|archive-date=28 July 2020|title=Cleaner code with functional programming |date=18 July 2020 |access-date=6 October 2020}}</ref> [[Scala (programming language)|Scala]],<ref name="effective-scala"/> and [[Java (programming language)|Java (since Java 8)]].<ref name="java-8-javadoc"/>
== 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
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
[[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
[[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 77 ⟶ 76:
[[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.
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.
Line 90 ⟶ 89:
== Concepts ==
A number of concepts<ref>Sean Tull - Monoidal Categories for Formal Concept Analysis.</ref> and paradigms are specific to functional programming, and generally foreign to [[imperative programming]] (including [[object-oriented programming]]). However, programming languages often cater to several programming paradigms, so programmers using "mostly imperative" languages may have utilized some of these concepts.<ref>{{cite web |url=http://byte.com/art/9408/sec11/art1.htm |archive-url=https://web.archive.org/web/20060827094123/http://byte.com/art/9408/sec11/art1.htm |archive-date=2006-08-27 |title=Functional Programming Comes of Age |first=Dick |last=Pountain |work=[[Byte (magazine)|Byte]] (August 1994) |access-date=August 31, 2006 |url-status=dead }}</ref>
=== First-class and higher-order functions ===
Line 109 ⟶ 108:
* If the entire language does not allow side-effects, then any evaluation strategy can be used; this gives the compiler freedom to reorder or combine the evaluation of expressions in a program (for example, using [[deforestation (computer science)|deforestation]]).
While most compilers for imperative programming languages detect pure functions and perform common-subexpression elimination for pure function calls, they cannot always do this for pre-compiled libraries, which generally do not expose this information, thus preventing optimizations that involve those external functions. Some compilers, such as [[GNU Compiler Collection|gcc]], add extra keywords for a programmer to explicitly mark external functions as pure, to enable such optimizations. [[Fortran 95]] also lets functions be designated ''pure''.<ref name=fortran95>{{cite
=== Recursion ===
Line 116 ⟶ 115:
[[Iteration]] (looping) in functional languages is usually accomplished via [[recursion]]. [[recursion (computer science)|Recursive functions]] invoke themselves, letting an operation be repeated until it reaches the [[Recursion (computer science)|base case]]. In general, recursion requires maintaining a [[Call stack|stack]], which consumes space in a linear amount to the depth of recursion. This could make recursion prohibitively expensive to use instead of imperative loops. However, a special form of recursion known as [[tail recursion]] can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages. Tail recursion optimization can be implemented by transforming the program into [[continuation passing style]] during compiling, among other approaches.
The [[Scheme (programming language)|Scheme]] language standard requires implementations to support proper tail recursion, meaning they must allow an unbounded number of active tail calls.<ref name='SchemeProperTailRec'>{{cite web|url=http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_sec_5.11 |title=Revised^6 Report on the Algorithmic Language Scheme |publisher=R6rs.org |access-date=2013-03-21}}</ref><ref>{{cite web|url=http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale-Z-H-7.html#node_sec_5.3 |title=Revised^6 Report on the Algorithmic Language Scheme - Rationale |publisher=R6rs.org |access-date=2013-03-21}}</ref> Proper tail recursion is not simply an optimization; it is a language feature that assures users that they can use recursion to express a loop and doing so would be safe-for-space.<ref>{{cite book|chapter=Proper tail recursion and space efficiency|last=Clinger|first=William|title=Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation - PLDI '98|date=1998|pages=174–185|doi=10.1145/277650.277719|isbn=0897919874|s2cid=16812984}}</ref> Moreover, contrary to its name, it accounts for all tail calls, not just tail recursion. While proper tail recursion is usually implemented by turning code into imperative loops, implementations might implement it in other ways. For example, [[Chicken (Scheme implementation)|Chicken]] intentionally maintains a stack and lets the [[stack overflow]]. However, when this happens, its [[Garbage collection (computer science)|garbage collector]] will claim space back,<ref>{{cite web |url=http://home.pipeline.com/~hbaker1/CheneyMTA.html |title=CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A. |last=Baker |first=Henry |date=1994 |access-date=2020-04-29 |archivedate=2006-03-03 |archiveurl=https://web.archive.org/web/20060303155622/http://home.pipeline.com/~hbaker1/CheneyMTA.html |url-status=deviated }}</ref> allowing an unbounded number of active tail calls even though it does not turn tail recursion into a loop.
Common patterns of recursion can be abstracted away using higher-order functions, with [[catamorphism]]s and [[anamorphism]]s (or "folds" and "unfolds") being the most obvious examples. Such recursion schemes play a role analogous to built-in control structures such as [[Program loops|loops]] in [[imperative languages]].
Line 134 ⟶ 133:
The usual implementation strategy for lazy evaluation in functional languages is [[graph reduction]].<ref>[http://research.microsoft.com/~simonpj/papers/slpj-book-1987/index.htm The Implementation of Functional Programming Languages]. Simon Peyton Jones, published by Prentice Hall, 1987</ref> Lazy evaluation is used by default in several pure functional languages, including [[Miranda (programming language)|Miranda]], [[Clean (programming language)|Clean]], and [[Haskell]].
{{Harvnb|Hughes|1984}} argues for lazy evaluation as a mechanism for improving program modularity through [[separation of concerns]], by easing independent implementation of producers and consumers of data streams.<ref name="hughesWhyFPMatters">{{cite web |url=http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html |title=Why Functional Programming Matters |author-link=John Hughes (computer scientist) |first=John |last=Hughes |year=1984}}</ref> Launchbury 1993 <!-- a cite arguing more strongly against lazy evaluation would be preferable here, if someone knows of one. --> describes some difficulties that lazy evaluation introduces, particularly in analyzing a program's storage requirements, and proposes an [[operational semantics]] to aid in such analysis.<ref name=launchbury1993>{{cite
=== Type systems ===
Line 140 ⟶ 139:
<!-- expand this section!!! also split it into several sections -->
Especially since the development of [[Hindley–Milner type inference]] in the 1970s, functional programming languages have tended to use [[typed lambda calculus]], rejecting all invalid programs at compilation time and risking [[false positives and false negatives#False positive error|false positive errors]], as opposed to the [[untyped lambda calculus]], that accepts all valid programs at compilation time and risks [[false positives and false negatives#False negative error|false negative errors]], used in Lisp and its variants (such as [[Scheme (programming language)|Scheme]]), as they reject all invalid programs at runtime when the information is enough to not reject valid programs. The use of [[algebraic
Some research-oriented functional languages such as [[Coq (software)|Coq]], [[Agda (
A limited form of dependent types called [[generalized algebraic data type]]s (GADT's) can be implemented in a way that provides some of the benefits of dependently typed programming while avoiding most of its inconvenience.<ref>{{cite journal |url=http://research.microsoft.com/en-us/um/people/simonpj/papers/gadt/ |title=Simple unification-based type inference for GADTs |first1=Simon |last1=Peyton Jones |first2=Dimitrios |last2=Vytiniotis |first3=Stephanie |last3=Weirich |author3-link= Stephanie Weirich |author4=Geoffrey Washburn |journal=Icfp 2006 |pages=50–61 |date=April 2006}}</ref> GADT's are available in the [[Glasgow Haskell Compiler]], in [[OCaml]]<ref>{{Cite web|title=OCaml Manual|url=https://caml.inria.fr/pub/docs/manual-ocaml/gadts.html|access-date=2021-03-08|website=caml.inria.fr}}</ref> and in [[Scala (programming language)|Scala]],<ref>{{Cite web|title=Algebraic Data Types|url=https://docs.scala-lang.org/scala3/book/types-adts-gadts.html|access-date=2021-03-08|website=Scala Documentation}}</ref> and have been proposed as additions to other languages including Java and C#.<ref>{{cite
=== Referential transparency ===
Line 150 ⟶ 149:
Functional programs do not have assignment statements, that is, the value of a variable in a functional program never changes once defined. This eliminates any chances of side effects because any variable can be replaced with its actual value at any point of execution. So, functional programs are referentially transparent.<ref>{{cite web|last1=Hughes |first1=John |title=Why Functional Programming Matters |url=http://www.cse.chalmers.se/~rjmh/Papers/whyfp.pdf |publisher=[[Chalmers University of Technology]]}}</ref>
Consider [[C (programming language)|C]] assignment statement <code>x=x
Now, consider another function such as <syntaxhighlight lang="c" inline>int plusone(int x) {return x+1;}</syntaxhighlight> ''is'' transparent, as it does not implicitly change the input x and thus has no such [[side effect (computer science)|side effects]].
Line 166 ⟶ 165:
=== Imperative vs. functional programming ===
The following two examples (written in [[
Traditional
<syntaxhighlight lang="javascript">
const numList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
Line 179 ⟶ 178:
</syntaxhighlight>
Functional
<syntaxhighlight lang="javascript">
const result = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Line 185 ⟶ 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 [[
=== Simulating state ===
Line 198 ⟶ 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>{{
<!-- TO DO: Expand -->
Line 204 ⟶ 203:
Functional programming languages are typically less efficient in their use of [[central processing unit|CPU]] and memory than imperative languages such as [[C (programming language)|C]] and [[Pascal (programming language)|Pascal]].<ref>{{cite book |first=Larry C. |last=Paulson |author-link=Lawrence Paulson |title=ML for the Working Programmer|url=https://books.google.com/books?id=XppZdaDs7e0C|access-date=10 February 2013|date=28 June 1996|publisher=Cambridge University Press|isbn=978-0-521-56543-1}}</ref> <!-- Paulson mentions the reputation for inefficiency in Sec. 1.5; perhaps a more in-depth discussion could be found. --> This is related to the fact that some mutable data structures like arrays have a very straightforward implementation using present hardware. Flat arrays may be accessed very efficiently with deeply pipelined CPUs, prefetched efficiently through caches (with no complex [[pointer chasing]]), or handled with SIMD instructions. <!-- perhaps this could be formulated by someone who knows the subject, I was simply curious about unexplained statement "logarithmic slowdown" --> It is also not easy to create their equally efficient general-purpose immutable counterparts. For purely functional languages, the worst-case slowdown is logarithmic in the number of memory cells used, because mutable memory can be represented by a purely functional data structure with logarithmic access time (such as a balanced tree).<ref name="Spiewak"/> However, such slowdowns are not universal. For programs that perform intensive numerical computations, functional languages such as [[OCaml]] and [[Clean (programming language)|Clean]] are only slightly slower than C according to [[The Computer Language Benchmarks Game]].<ref>{{cite web |url=http://benchmarksgame.alioth.debian.org/u32/which-programs-are-fastest.php?gcc=on&ghc=on&clean=on&ocaml=on&sbcl=on&fsharp=on&racket=on&clojure=on&hipe=on&calc=chart |title=Which programs are fastest? | Computer Language Benchmarks Game |publisher=benchmarksgame.alioth.debian.org |access-date=2011-06-20 |archive-url=https://web.archive.org/web/20130520162513/http://benchmarksgame.alioth.debian.org/u32/which-programs-are-fastest.php?gcc=on&ghc=on&clean=on&ocaml=on&sbcl=on&fsharp=on&racket=on&clojure=on&hipe=on&calc=chart |archive-date=2013-05-20 |url-status=dead}}</ref> For programs that handle large [[matrix (mathematics)|matrices]] and multidimensional [[database]]s, [[array programming|array]] functional languages (such as [[J (programming language)|J]] and [[K (programming language)|K]]) were designed with speed optimizations.
Immutability of data can in many cases lead to execution efficiency by allowing the compiler to make assumptions that are unsafe in an imperative language, thus increasing opportunities for [[inline expansion]].<ref>{{cite journal |title=Immutability specification and its applications |author1=Igor Pechtchanski |author2=Vivek Sarkar |journal=Concurrency and Computation: Practice and Experience |volume=17 |issue=5–6 |pages=639–662 |year=2005 |doi=10.1002/cpe.853 |s2cid=34527406}}</ref> Even if the involved copying that may seem implicit when dealing with persistent immutable data structures might seem computationally costly, some functional programming languages, like [[Clojure]] solve this issue by implementing mechanisms for safe memory sharing between ''formally'' ''immutable'' data.<ref>{{Cite web |title=An In-Depth Look at Clojure Collections |url=https://www.infoq.com/articles/in-depth-look-clojure-collections/ |access-date=2024-04-29 |website=InfoQ |language=en}}</ref> [[Rust (programming language)|Rust]] distinguishes itself by
Immutable data with separation of identity and state and [[Shared-nothing architecture|shared-nothing]] schemes can also potentially be more well-suited for [[Parallel computing|concurrent and parallel]] programming by the virtue of reducing or eliminating the risk of certain concurrency hazards, since concurrent operations are usually [[Linearizability|atomic]] and this allows eliminating the need for locks. This is how for example <code>java.util.concurrent</code> classes are implemented, where some of them are immutable variants of the corresponding classes that are not suitable for concurrent use.<ref>{{Cite web |title=Concurrent Collections (The Java™ Tutorials > Essential Java Classes > Concurrency) |url=https://docs.oracle.com/javase/tutorial/essential/concurrency/collections.html |access-date=2024-04-29 |website=docs.oracle.com}}</ref> Functional programming languages often have a concurrency model that instead of shared state and synchronization, leverages [[message passing]] mechanisms (such as the [[actor model]], where each actor is a container for state, behavior, child actors and a message queue).<ref>{{Cite web |date=2023-01-28 |title=Understanding The Actor Model To Build Non-blocking, High-throughput Distributed Systems - Scaleyourapp |url=https://scaleyourapp.com/actor-model/ |access-date=2024-04-29 |website=scaleyourapp.com |language=en-US}}</ref><ref>{{Cite book |
[[Lazy evaluation]] may also speed up the program, even asymptotically, whereas it may slow it down at most by a constant factor (however, it may introduce [[memory leak]]s if used improperly). Launchbury 1993<ref name=launchbury1993/> discusses theoretical issues related to memory leaks from lazy evaluation, and O'Sullivan ''et al.'' 2008<ref>{{cite web |url=http://book.realworldhaskell.org/read/profiling-and-optimization.html#x_eK1 |title=Chapter 25. Profiling and optimization |publisher=Book.realworldhaskell.org |access-date=2011-06-20}}</ref> give some practical advice for analyzing and fixing them.
Line 229 ⟶ 228:
</syntaxhighlight>
has the mean execution time of 4.76
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>
=== Functional programming in non-functional languages ===
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
[[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 245 ⟶ 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 315 ⟶ 316:
=== Text editors ===
[[Emacs]], a highly extensible text editor family uses
[[Helix (text editor)|Helix]], since version 24.03 supports previewing [[Abstract syntax tree|AST]] as [[S-expression|S-expressions]], which are also the core feature of the Lisp programming language family.<ref>{{Cite web |title=Helix |url=https://helix-editor.com/news/release-24-03-highlights/ |access-date=2024-04-29 |website=helix-editor.com}}</ref>
Line 321 ⟶ 322:
=== Spreadsheets ===
[[Spreadsheet]]s can be considered a form of pure, [[Higher-order function|zeroth-order]], strict-evaluation functional programming system.<ref name="Wakeling2007">{{cite journal|last1=Wakeling|first1=David|title=Spreadsheet functional programming|journal=Journal of Functional Programming|volume=17|issue=1|year=2007|pages=131–143|issn=0956-7968|doi=10.1017/S0956796806006186|s2cid=29429059|url=http://www.activemode.org/webroot/Workers/ActiveTraining/Programming/Pro_SpreadsheetFunctionalProgramming.pdf}}</ref> However, spreadsheets generally lack higher-order functions as well as code reuse, and in some implementations, also lack recursion. Several extensions have been developed for spreadsheet programs to enable higher-order and reusable functions, but so far remain primarily academic in nature.<ref name="excel">{{cite web |title=Improving the world's most popular functional language: user-defined functions in Excel |first1=Simon |last1=Peyton Jones |author-link1=Simon Peyton Jones |first2=Margaret |last2=Burnett|author2-link=Margaret Burnett |first3=Alan |last3=Blackwell |author-link3=Alan Blackwell |url=http://research.microsoft.com/~simonpj/Papers/excel/index.htm |date=March 2003 |archive-url=https://web.archive.org/web/20051016011341/http://research.microsoft.com/~simonpj/Papers/excel/index.htm |archive-date=2005-10-16}}</ref>
=== Microservices ===
Due to their [[composability]], functional programming paradigms can be suitable for [[microservices]]-based architectures.<ref>{{Cite book |last=Rodger |first=Richard |title=The Tao of Microservices |date=11 December 2017 |publisher=Manning |isbn=9781638351733}}</ref>
=== Academia ===
Line 326 ⟶ 330:
=== Industry ===
Functional programming has been employed in a wide range of industrial applications. For example, [[Erlang (programming language)|Erlang]], which was developed by the [[Sweden|Swedish]] company [[Ericsson]] in the late 1980s, was originally used to implement [[Fault tolerance|fault-tolerant]] [[
Other functional programming languages that have seen use in industry include [[Scala (programming language)|Scala]],<ref>{{cite conference |last=Momtahan |first=Lee |title=Scala at EDF Trading: Implementing a Domain-Specific Language for Derivative Pricing with Scala |url=http://cufp.galois.com/2009/abstracts.html#LeeMomtahan |year=2009 |conference=CUFP 2009 |access-date=2009-08-29 |archive-url=https://web.archive.org/web/20091017070140/http://cufp.galois.com/2009/abstracts.html#LeeMomtahan |archive-date=2009-10-17 |url-status=dead }}</ref> [[F Sharp (programming language)|F#]],<ref name='quantFSharp'/><ref name='businessAppsFSharp'/> [[Wolfram Language]],<ref name="reference.wolfram.com"/> [[Lisp (programming language)|Lisp]],<ref>{{cite web |last=Graham |first=Paul |title=Beating the Averages |url=http://www.paulgraham.com/avg.html |year=2003 |access-date=2009-08-29}}</ref> [[Standard ML]]<ref>{{cite conference |last=Sims |first=Steve |title=Building a Startup with Standard ML |url=http://cufp.galois.com/2006/slides/SteveSims.pdf |year=2006 |conference=CUFP 2006 |access-date=2009-08-29}}</ref><ref>{{cite conference |last=Laurikari |first=Ville |title=Functional Programming in Communications Security. |url=http://cufp.galois.com/2007/abstracts.html#VilleLaurikari |year=2007 |conference=CUFP 2007 |access-date=2009-08-29 |archivedate=2010-12-21 |archiveurl=https://web.archive.org/web/20101221110947/http://cufp.galois.com/2007/abstracts.html#VilleLaurikari |url-status=dead }}</ref> and Clojure.<ref>{{cite web |url=http://www.infoq.com/news/2009/01/clojure_production |last=Lorimer |first=R. J. |title=Live Production Clojure Application Announced |date=19 January 2009|work=InfoQ}}</ref> Scala has been widely used in [[Data science]],<ref>{{Cite book |last=Bugnion |first=Pascal |title=Scala for Data Science |publisher=[[Packt]] |year=2016 |isbn=9781785281372 |edition=1st |language=en-US}}</ref>
Functional "platforms" have been popular in finance for risk analytics (particularly with large investment banks). Risk factors are coded as functions that form interdependent graphs (categories) to measure correlations in market shifts, similar in manner to [[Gröbner basis]] optimizations but also for regulatory frameworks such as [[Comprehensive Capital Analysis and Review]]. Given the use of OCaml and [[Caml]] variations in finance, these systems are sometimes considered related to a [[categorical abstract machine]]. Functional programming is heavily influenced by [[category theory]].{{Citation needed|date=August 2022}}
=== 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 341 ⟶ 345:
== See also ==
{{Portal|Computer programming}}
* [[List of functional programming languages]]▼
* [[Purely functional programming]]▼
* [[Comparison of programming paradigms]]▼
* [[Eager evaluation]]
▲* [[List of functional programming languages]]
* [[List of functional programming topics]]
* [[Nested function]]
* [[
== Notes and references ==
Line 358 ⟶ 361:
<ref name="hartheimer1987">{{cite journal |last=Hartheimer |first=Anne |title=Programming a Text Editor in MacScheme+Toolsmith |journal=MacTech |volume=3 |issue=1 |year=1987 |url=http://www.mactech.com/articles/mactech/Vol.03/03.1/SchemeWindows/index.html |access-date=2008-08-28 |url-status=dead |archive-url=https://web.archive.org/web/20110629183752/http://www.mactech.com/articles/mactech/Vol.03/03.1/SchemeWindows/index.html |archive-date=2011-06-29}}</ref>
<ref name="kidd2007">{{cite conference |last=Kidd |first=Eric |url=http://cufp.galois.com/2007/abstracts.html#EricKidd |title=Terrorism Response Training in Scheme |conference=CUFP 2007 |access-date=2009-08-26 |archivedate=2010-12-21 |archiveurl=https://web.archive.org/web/20101221110947/http://cufp.galois.com/2007/abstracts.html#EricKidd |url-status=dead }}</ref>
<ref name="cleis2006">{{cite conference |last=Cleis |first=Richard |url=http://cufp.galois.com/2006/abstracts.html#RichardCleis |title=Scheme in Space |conference=CUFP 2006 |access-date=2009-08-26 |archivedate=2010-05-27 |archiveurl=https://web.archive.org/web/20100527100429/http://cufp.galois.com/2006/abstracts.html#RichardCleis |url-status=dead }}</ref>
<ref name="erlang-faq">{{cite web |title=Who uses Erlang for product development? |work=Frequently asked questions about Erlang |url=http://erlang.org/faq/introduction.html#idp32582608 |access-date=2018-04-27}}</ref>
Line 370 ⟶ 373:
<ref name="minksy2008">{{cite journal |last1=Minsky |first1=Yaron |last2=Weeks |first2=Stephen |title=Caml Trading — 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 |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>
<ref name="effective-scala">{{cite web |title=Effective Scala |work=Scala Wiki |url=https://twitter.github.com/effectivescala/?sd |access-date=2012-02-21 |quote=Effective Scala. |archivedate=2012-06-19 |archiveurl=https://web.archive.org/web/20120619075044/http://twitter.github.com/effectivescala/?sd |url-status=deviated }}</ref>
<ref name="java-8-javadoc">{{cite web |title=Documentation for package java.util.function since Java 8 (also known as Java 1.8) |url=https://docs.oracle.com/javase/8/docs/api/java/util/function/package-summary.html |access-date=2021-06-16}}</ref>
<ref name="racket-video-games">{{cite web |title=State-Based Scripting in Uncharted 2 |url=http://www.gameenginebook.com/gdc09-statescripting-uncharted2.pdf |archive-url=https://web.archive.org/web/20121215014637/http://www.gameenginebook.com/gdc09-statescripting-uncharted2.pdf |archive-date=2012-12-15 |access-date=2011-08-08 |url-status=dead }}</ref>
<ref name="hudak2007">{{cite conference |last1=Hudak |first1=Paul |last2=Hughes |first2=J. |last3=Jones |first3=S. P. |last4=Wadler |first4=P. |author-link1=Paul Hudak |title=A history of Haskell: being lazy with class |url=http://dl.acm.org/citation.cfm?doid=1238844.1238856 |conference=Third ACM SIGPLAN Conference on History of Programming Languages |___location=San Diego, California| date=June 2007 |doi=10.1145/1238844.1238856 |access-date=2013-09-26}}</ref>
Line 382 ⟶ 385:
<ref name="useR">{{cite web |url=http://www.r-project.org/useR-2006/program.html |title=The useR! 2006 conference schedule includes papers on the commercial use of R |publisher=R-project.org |date=2006-06-08 |access-date=2011-06-20}}</ref><ref name="Chambers">{{cite book |last=Chambers |first=John M. |author-link=John Chambers (programmer) |title=Programming with Data: A Guide to the S Language |publisher=Springer Verlag |year=1998 |pages=67–70 |isbn=978-0-387-98503-9}}</ref>
<ref name="Amath-CO">{{cite web |website=
<ref name="Novatchev">{{cite web |url=
<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>
}}
== 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=
* 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 400 ⟶ 403:
* Graham, Paul. ''ANSI Common LISP''. Englewood Cliffs, New Jersey: [[Prentice Hall]], 1996.
* MacLennan, Bruce J. ''Functional Programming: Practice and Theory''. Addison-Wesley, 1990.
*{{cite book |last1=Michaelson |first1=Greg |title=An Introduction to Functional Programming Through Lambda Calculus |date=10 April 2013 |publisher=Courier Corporation |isbn=978-0-486-28029-5 |language=en}}
* {{cite book|last1=O'Sullivan|first1=Brian|last2=Stewart|first2=Don|last3=Goerzen|first3=John |title=Real World Haskell |url=http://book.realworldhaskell.org/read/ |year=2008|publisher=O'Reilly}}
* Pratt, Terrence W. and [[Marvin Victor Zelkowitz]]. ''Programming Languages: Design and Implementation''. 3rd ed. Englewood Cliffs, New Jersey: [[Prentice Hall]], 1996.
Line 427 ⟶ 430:
{{Programming paradigms navbox}}
{{Types of programming languages}}
{{Authority control}}
Line 433 ⟶ 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]]
| |||