Editing Functional programming (section)

== Comparison to imperative programming ==
Functional programming is very different from [[imperative programming]]. The most significant differences stem from the fact that functional programming avoids [[side effect (computer science)|side effects]], which are used in imperative programming to implement state and I/O. Pure functional programming completely prevents side-effects and provides referential transparency.

Higher-order functions are rarely used in older imperative programming. A traditional imperative program might use a loop to traverse and modify a list. A functional program, on the other hand, would probably use a higher-order "map" function that takes a function and a list, generating and returning a new list by applying the function to each list item.

=== Imperative vs. functional programming ===

The following two examples (written in [[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:
<syntaxhighlight lang="javascript">
const numList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let result = 0;
for (let i = 0; i < numList.length; i++) {
  if (numList[i] % 2 === 0) {
    result += numList[i] * 10;
  }
}
</syntaxhighlight>

Functional programming with higher-order functions:
<syntaxhighlight lang="javascript">
const result = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
               .filter(n => n % 2 === 0)
               .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 [[off-by-one error]]s (see [[Greenspun's tenth rule]]).

=== Simulating state ===
There are tasks (for example, maintaining a bank account balance) that often seem most naturally implemented with state. Pure functional programming performs these tasks, and I/O tasks such as accepting user input and printing to the screen, in a different way.

The pure functional programming language [[Haskell]] implements them using [[Monad (functional programming)|monads]], derived from [[category theory]].<ref>Michael Barr, Charles Well - Category theory for computer science.</ref> Monads offer a way to abstract certain types of computational patterns, including (but not limited to) modeling of computations with mutable state (and other side effects such as I/O) in an imperative manner without losing purity. While existing monads may be easy to apply in a program, given appropriate templates and examples, many students find them difficult to understand conceptually, e.g., when asked to define new monads (which is sometimes needed for certain types of libraries).<ref>{{cite web |last=Newbern |first=J. |title=All About Monads: A comprehensive guide to the theory and practice of monadic programming in Haskell |url=http://monads.haskell.cz/html/index.html/html/ |access-date=2008-02-14}}</ref>

Functional languages also simulate states by passing around immutable states. This can be done by making a function accept the state as one of its parameters, and return a new state together with the result, leaving the old state unchanged.<ref>{{Cite web|url=https://fsharpforfunandprofit.com/posts/13-ways-of-looking-at-a-turtle/#2-basic-fp---a-module-of-functions-with-immutable-state|title=Thirteen ways of looking at a turtle |website=fF# for fun and profit|language=en|access-date=2018-11-13}}</ref>
<!-- TO DO: Expand -->

Impure functional languages usually include a more direct method of managing mutable state. [[Clojure]], for example, uses managed references that can be updated by applying pure functions to the current state. This kind of approach enables mutability while still promoting the use of pure functions as the preferred way to express computations.{{citation needed|date=July 2018}}
<!-- 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>{{cite book |last1=Hartmanis |first1=Juris |date=1986 |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 -->

=== Efficiency issues ===
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? &#124; 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 its approach to data immutability which involves immutable [[Reference (computer science)|references]]<ref>{{Cite web |title=References and Borrowing - The Rust Programming Language |url=https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html |access-date=2024-04-29 |website=doc.rust-lang.org}}</ref> and a concept called ''lifetimes.''<ref>{{Cite web |title=Validating References with Lifetimes - The Rust Programming Language |url=https://doc.rust-lang.org/book/ch10-03-lifetime-syntax.html |access-date=2024-04-29 |website=doc.rust-lang.org}}</ref>

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 |last1=Cesarini |first1=Francesco |title=Erlang programming: a concurrent approach to software development |last2=Thompson |first2=Simon |publisher=O'Reilly Media, Inc. |year=2009 |isbn=978-0-596-55585-6 |edition=1st |publication-date=2009-06-11 |page=6 |language=en}}</ref> This approach is common in [[Erlang (programming language)|Erlang]]/[[Elixir (programming language)|Elixir]] or [[Akka (toolkit)|Akka]].

[[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.
However, the most general implementations of lazy evaluation making extensive use of dereferenced code and data perform poorly on modern processors with deep pipelines and multi-level caches (where a cache miss may cost hundreds of cycles) {{Citation needed|date=June 2014}}.

==== Abstraction cost ====

Some functional programming languages might not optimize abstractions such as higher order functions like "[[Map (higher-order function)|map]]" or "[[Filter (higher-order function)|filter]]" as efficiently as the underlying imperative operations. Consider, as an example, the following two ways to check if 5 is an even number in [[Clojure]]:
<syntaxhighlight lang="clojure">
(even? 5)
(.equals (mod 5 2) 0)
</syntaxhighlight>
When [[Benchmarking|benchmarked]] using the [https://clojars.org/criterium Criterium] tool on a [[Zen 3|Ryzen 7900X]] GNU/Linux PC in a [[Leiningen (software)|Leiningen]] [[REPL]] 2.11.2, running on [[JVM|Java VM]] version 22 and Clojure version 1.11.1, the first implementation, which is implemented as:
<syntaxhighlight lang="clojure>
(defn even?
  "Returns true if n is even, throws an exception if n is not an integer"
  {:added "1.0"
   :static true}
   [n] (if (integer? n)
        (zero? (bit-and (clojure.lang.RT/uncheckedLongCast n) 1))
        (throw (IllegalArgumentException. (str "Argument must be an integer: " n)))))
</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>. For 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>

=== 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 |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.

In [[Java (programming language)|Java]], anonymous classes can sometimes be used to simulate closures;<ref>{{cite book |last=Skarsaune |first=Martin |title=The SICS Java Port Project Automatic Translation of a Large Object Oriented System from Smalltalk to Java |year=2008}}</ref> however, anonymous classes are not always proper replacements to closures because they have more limited capabilities.<ref>{{cite web|last=Gosling|first=James|title=Closures|url= http://blogs.oracle.com/jag/entry/closures|work=James Gosling: on the Java Road|publisher=Oracle|access-date=11 May 2013|archive-url= https://web.archive.org/web/20130414180002/https://blogs.oracle.com/jag/entry/closures|archive-date=2013-04-14|url-status=dead}}</ref> Java 8 supports lambda expressions as a replacement for some anonymous classes.<ref>{{cite web|url=https://blogs.oracle.com/javatraining/entry/java_se_8_lambda_quick|title=Java SE 8 Lambda Quick Start|first=Michael|last=Williams|date=8 April 2013}}</ref>

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]] [[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>