Content deleted Content added
Tags: Mobile edit Mobile web edit |
Rescuing 17 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
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 which treats all functions as [[Deterministic system|deterministic]] mathematical [[Function (mathematics)|functions]], or [[pure function]]s. When a pure function is called with some given arguments, it will always return the same result, and cannot be affected by any mutable [[State (computer science)|state]] or other [[Side effect (computer science)|side effects]]. This is in contrast with impure [[Procedure (computer science)|procedures]], common in [[imperative programming]], which can have side effects (such as modifying the program's state or taking input from a user). Proponents of purely functional programming claim that by restricting side effects, programs can have fewer [[Software bug|bugs]], be easier to [[Debugging|debug]] and [[Software testing|test]], and be more suited to [[formal verification]].<ref name="hudak1989">{{cite journal |last=Hudak |first=Paul |author-link=Paul Hudak |title=Conception, evolution, and application of functional programming languages |journal=ACM Computing Surveys |volume=21 |issue=3 |pages=359–411 |date=September 1989 |url=http://www.dbnet.ece.ntua.gr/~adamo/languages/books/p359-hudak.pdf |doi=10.1145/72551.72554 |s2cid=207637854 |accessdate=2013-08-10 |archivedate=2016-01-31 |archiveurl=https://web.archive.org/web/20160131083528/http://www.dbnet.ece.ntua.gr/~adamo/languages/books/p359-hudak.pdf |url-status=deviated }}</ref><ref name="hughesWhyFPMatters"/>
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 |accessdate=2009-08-29 |archivedate=2015-07-08 |archiveurl=https://web.archive.org/web/20150708125937/http://cufp.galois.com/2008/abstracts.html#MansellHoward |url-status=deviated }}</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=
== History ==
Line 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 |archivedate=2006-08-27 |archiveurl=https://web.archive.org/web/20060827094123/http://byte.com/art/9408/sec11/art1.htm |url-status=deviated }}</ref>
=== First-class and higher-order functions ===
Line 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 234:
=== 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 [[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}}
Line 325:
=== 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]] [[telecommunication]]s systems,<ref name="armstrong2007"/> but has since become popular for building a range of applications at companies such as [[Nortel]], [[Facebook]], [[Électricité de France]] and [[WhatsApp]].<ref name="erlang-faq"/><ref name="larson2009"/><ref>{{cite conference |last=Piro |first=Christopher |title=Functional Programming at Facebook |url=http://cufp.galois.com/2009/abstracts.html#ChristopherPiroEugeneLetuchy |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#ChristopherPiroEugeneLetuchy |archive-date=2009-10-17 |url-status=
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=
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}}
Line 357:
<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 |accessdate=2009-08-26 |archivedate=2010-12-21 |archiveurl=https://web.archive.org/web/20101221110947/http://cufp.galois.com/2007/abstracts.html#EricKidd |url-status=deviated }}</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 |accessdate=2009-08-26 |archivedate=2010-05-27 |archiveurl=https://web.archive.org/web/20100527100429/http://cufp.galois.com/2006/abstracts.html#RichardCleis |url-status=deviated }}</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 369:
<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 |accessdate=2009-08-26 |archivedate=2011-10-08 |archiveurl=https://web.archive.org/web/20111008170929/http://cufp.galois.com/2007/slides/XavierLeroy.pdf |url-status=deviated }}</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 |archivedate=2012-12-15 |archiveurl=https://web.archive.org/web/20121215014637/http://www.gameenginebook.com/gdc09-statescripting-uncharted2.pdf |url-status=deviated }}</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 381:
<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=http://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>
Line 387:
<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}}</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>
}}
| |||