SUPPORT THE WORK

GetWiki

functional programming

ARTICLE SUBJECTS
news  →
unix  →
wiki  →
ARTICLE TYPES
feed  →
help  →
wiki  →
ARTICLE ORIGINS
functional programming
[ temporary import ]
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki

Concepts

A number of concepts 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.WEB,weblinkweblink" title="web.archive.org/web/20060827094123weblink">weblink 2006-08-27, Functional Programming Comes of Age, Dick Pountain, BYTE.com (August 1994), August 31, 2006,

First-class and higher-order functions

Higher-order functions are functions that can either take other functions as arguments or return them as results. In calculus, an example of a higher-order function is the differential operator d/dx, which returns the derivative of a function f.Higher-order functions are closely related to first-class functions in that higher-order functions and first-class functions both allow functions as arguments and results of other functions. The distinction between the two is subtle: "higher-order" describes a mathematical concept of functions that operate on other functions, while "first-class" is a computer science term that describes programming language entities that have no restriction on their use (thus first-class functions can appear anywhere in the program that other first-class entities like numbers can, including as arguments to other functions and as their return values).Higher-order functions enable partial application or currying, a technique that applies a function to its arguments one at a time, with each application returning a new function that accepts the next argument. This lets a programmer succinctly express, for example, the successor function as the addition operator partially applied to the natural number one.

Pure functions

Pure functions (or expressions) have no side effects (memory or I/O). This means that pure functions have several useful properties, many of which can be used to optimize the code:
• If the result of a pure expression is not used, it can be removed without affecting other expressions.
• If a pure function is called with arguments that cause no side-effects, the result is constant with respect to that argument list (sometimes called referential transparency), i.e., calling the pure function again with the same arguments returns the same result. (This can enable caching optimizations such as memoization.)
• If there is no data dependency between two pure expressions, their order can be reversed, or they can be performed in parallel and they cannot interfere with one another (in other terms, the evaluation of any pure expression is thread-safe).
• 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).
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 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.JOURNAL, ISO/IEC JTC 1/SC 22/WG5/N2137, International Organization for Standardization, July 6, 2017,weblink C++11 added constexpr keyword with similar semantics.

Recursion

Iteration (looping) in functional languages is usually accomplished via recursion. Recursive functions invoke themselves, letting an operation be repeated until it reaches the base case. Although some recursion requires maintaining a stack, tail recursion can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages. The Scheme language standard requires implementations to recognize and optimize tail recursion. Tail recursion optimization can be implemented by transforming the program into continuation passing style during compiling, among other approaches.Common patterns of recursion can be abstracted away using higher-order functions, with catamorphisms and anamorphisms (or "folds" and "unfolds") being the most obvious examples. Such recursion schemes play a role analogous to built-in control structures such as loops in imperative languages.Most general purpose functional programming languages allow unrestricted recursion and are Turing complete, which makes the halting problem undecidable, can cause unsoundness of equational reasoning, and generally requires the introduction of inconsistency into the logic expressed by the language's type system. Some special purpose languages such as Coq allow only well-founded recursion and are strongly normalizing (nonterminating computations can be expressed only with infinite streams of values called codata). As a consequence, these languages fail to be Turing complete and expressing certain functions in them is impossible, but they can still express a wide class of interesting computations while avoiding the problems introduced by unrestricted recursion. Functional programming limited to well-founded recursion with a few other constraints is called total functional programming.JOURNAL, Turner, D.A., David Turner (computer scientist), Total Functional Programming, Journal of Universal Computer Science, 10, 2004-07-28, 751â€“768,weblink 10.3217/jucs-010-07-0751, 7,

Strict versus non-strict evaluation

Functional languages can be categorized by whether they use strict (eager) or non-strict (lazy) evaluation, concepts that refer to how function arguments are processed when an expression is being evaluated. The technical difference is in the denotational semantics of expressions containing failing or divergent computations. Under strict evaluation, the evaluation of any term containing a failing subterm fails. For example, the expression:
print length([2+1, 3*2, 1/0, 5-4])
fails under strict evaluation because of the division by zero in the third element of the list. Under lazy evaluation, the length function returns the value 4 (i.e., the number of items in the list), since evaluating it does not attempt to evaluate the terms making up the list. In brief, strict evaluation always fully evaluates function arguments before invoking the function. Lazy evaluation does not evaluate function arguments unless their values are required to evaluate the function call itself.The usual implementation strategy for lazy evaluation in functional languages is graph reduction.The Implementation of Functional Programming Languages. Simon Peyton Jones, published by Prentice Hall, 1987 Lazy evaluation is used by default in several pure functional languages, including Miranda, 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.WEB,weblink Why Functional Programming Matters, John Hughes (computer scientist), John, Hughes, 1984, harv, Launchbury 1993 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.JOURNAL, John Launchbury, John_Launchbury, A Natural Semantics for Lazy Evaluation, 1993, 10.1.1.35.2016, Harper 2009 proposes including both strict and lazy evaluation in the same language, using the language's type system to distinguish them.BOOK,weblinkweblink" title="web.archive.org/web/20160407095249weblink">weblink 2016-04-07, Practical Foundations for Programming Languages, Robert W. Harper, Robert_Harper_(computer_scientist), 2009,

Referential transparency

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.WEB, Huges, John, Why Functional Programming Matters,weblink chalmers.se/cse, Chalmers Tekniska HÂ¨ogskola, Consider C assignment statement x = x * 10, this changes the value assigned to the variable x. Let us say that the initial value of x was 1, then two consecutive evaluations of the variable x yields 10 and 100 respectively. Clearly, replacing x = x * 10 with either 10 or 100 gives a program with different meaning, and so the expression is not referentially transparent. In fact, assignment statements are never referentially transparent.Now, consider another function such as int plusone(int x) {return x+1;} is transparent, as it does not implicitly change the input x and thus has no such side effects.Functional programs exclusively use this type of function and are therefore referentially transparent.

Data structures

Purely functional data structures are often represented in a different way than their imperative counterparts.Purely functional data structures by Chris Okasaki, Cambridge University Press, 1998, {{ISBN|0-521-66350-4}} For example, the array with constant access and update times is a basic component of most imperative languages, and many imperative data-structures, such as the hash table and binary heap, are based on arrays. Arrays can be replaced by maps or random access lists, which admit purely functional implementation, but have logarithmic access and update times. Purely functional data structures have persistence, a property of keeping previous versions of the data structure unmodified. In Clojure, persistent data structures are used as functional alternatives to their imperative counterparts. Persistent vectors, for example, use trees for partial updating. Calling the insert method will result in some but not all nodes being created.WEB,weblink polymatheia - Understanding Clojure's Persistent Vector, pt. 1, (hyPiRion), Jean Niklas L'orange, www.hypirion.com, 2018-11-13,

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

Efficiency issues

Functional programming languages are typically less efficient in their use of CPU and memory than imperative languages such as C and Pascal.BOOK, Larry C. Paulson, ML for the Working Programmer,weblink 10 February 2013, 28 June 1996, Cambridge University Press, 978-0-521-56543-1, This is related to the fact that some mutable data structures like arrays have a very straightforward implementation using present hardware (which is a highly evolved Turing machine). 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. 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). However, such slowdowns are not universal. For programs that perform intensive numerical computations, functional languages such as OCaml and Clean are only slightly slower than C according to The Computer Language Benchmarks Game.WEB,weblink Which programs are fastest? | Computer Language Benchmarks Game, benchmarksgame.alioth.debian.org, 2011-06-20, For programs that handle large matrices and multidimensional databases, array functional languages (such as J and 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.JOURNAL, Immutability specification and its applications, Igor Pechtchanski, Vivek Sarkar, Concurrency and Computation: Practice and Experience, 17, 5â€“6, 639â€“662, 2005, 10.1002/cpe.853, 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 leaks if used improperly). Launchbury 1993 discusses theoretical issues related to memory leaks from lazy evaluation, and O'Sullivan et al. 2008WEB,weblink Chapter 25. Profiling and optimization, Book.realworldhaskell.org, 2011-06-20, 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}}.

Coding styles

{{unreferenced section|date=July 2013}}Imperative programs have the environment and a sequence of steps manipulating the environment. Functional programs have an expression that is successively substituted until it reaches normal form. An example illustrates this with different solutions to the same programming goal (calculating Fibonacci numbers).

Java

Get Fibonacci number
public UnaryOperator fib(Integer acc, Integer next) {
return x -> {
if(x > 0) {
return fib(acc + next, acc).apply(--x);
}
else {
return acc;
}
};
}
System.out.println(fib(0, 1).apply(5));

OCAML

Printing first 10 Fibonacci numberslet fib_list =
let rec fib_list_aux first second = function
| 0 -> []
| x -> first::fib_list_aux second (first+second) (x-1)
in
fib_list_aux 0 1
let () = List.iter (Printf.printf "%d ") (fib_list 10)

PHP

Printing first 10 Fibonacci numbers, using functionfunction fib(int \$n) : int {
return (\$n === 0 || \$n === 1) ? \$n : fib(\$n - 1) + fib(\$n - 2);
}for (\$i = 0; \$i
if n == 0 then [] else
[first] ++ fibonacci_aux (n - 1) second (first + second)
fibonacci = n-> fibonacci_aux n 0 1main = putStrLn (show (fibonacci 10))Printing the 11th Fibonacci number, functional expression stylefibonacci = n-> if n == 0 then 0
else if n == 1 then 1
else fibonacci(n - 1) + fibonacci(n - 2)
main = putStrLn (show (fibonacci 10))Printing the 11th Fibonacci number, functional expression style, tail recursivefibonacci_aux = n first second->
if n == 0 then first else
fibonacci_aux (n - 1) second (first + second)
fibonacci = n-> Fibonacci_aux n 0 1main = putStrLn (show (fibonacci 10))Printing the 11th Fibonacci number, functional expression style with recursive listsfibonacci_aux = first second-> first : fibonacci_aux second (first + second)select = n zs-> if n==0 then head zs
else select (n - 1) (tail zs)
fibonacci = n-> select n (fibonacci_aux 0 1)main = putStrLn (show (fibonacci 10))Printing the 11th Fibonacci number, functional expression style with primitives for recursive listsfibonacci_aux = first second-> first : fibonacci_aux second (first + second)fibonacci = n-> (fibonacci_aux 0 1) !! nmain = putStrLn (show (fibonacci 10))Printing the 11th Fibonacci number, functional expression style with primitives for recursive lists, more conciselyfibonacci_aux = 0:1:zipWith (+) fibonacci_aux (tail fibonacci_aux)fibonacci = n-> fibonacci_aux !! nmain = putStrLn (show (fibonacci 10))Printing the 11th Fibonacci number, functional declaration stylefibonacci 0 = 0fibonacci 1 = 1fibonacci n = fibonacci (n-1) + fibonacci (n-2)main = putStrLn (show (fibonacci 10))Printing the 11th Fibonacci number, functional declaration style, tail recursivefibonacci_aux 0 first _ = firstfibonacci_aux n first second = fibonacci_aux (n - 1) second (first + second)fibonacci n = fibonacci_aux n 0 1main = putStrLn (show (fibonacci 10))Printing the 11th Fibonacci number, functional declaration style, using lazy infinite lists and primitivesfibs = 1 : 1 : zipWith (+) fibs (tail fibs)-- an infinite list of the fibonacci numbers-- fibs is defined in terms of fibsfibonacci = (fibs !!)main = putStrLn \$ show \$ fibonacci 11Printing the first 10 Fibonacci numbers, list comprehension (generator) stylefibs = [0, 1] ++ [(fibs !! x) + (fibs !! (x + 1)) | x UInt:D ) {*}multi fib ( 0 --> 0 ) { }multi fib ( 1 --> 1 ) { }multi fib ( n ) {
fib(n - 1) + fib(n - 2)
}for ^10 -> \$n { say fib(\$n) }An alternative to this is to construct a lazy iterative sequence, which appears as an almost direct illustration of the sequence:my @fib = 0, 1, *+* ... *; # Each additional entry is the sum of the previous two
# and this sequence extends lazily indefinitely
say @fib[^10]; # Display the first 10 entries

Erlang

Erlang is a functional, concurrent, general-purpose programming language. A Fibonacci algorithm implemented in Erlang (Note: This is only for demonstrating the Erlang syntax. Use other algorithms for fast performanceWEB,weblink" title="web.archive.org/web/20131226033005weblink">weblink yes,weblink 26 December 2013, Fibonacci Sequence Recursion in Erlang, Thorp, Noah, 16 February 2008, Aquabu, ):-module(fib). % This is the file 'fib.erl', the module and the filename must match-export([fib/1]). % This exports the function 'fib' of arity 1fib(1) -> 1; % If 1, then return 1, otherwise (note the semicolon ; meaning 'else')fib(2) -> 1; % If 2, then return 1, otherwisefib(N) -> fib(N - 2) + fib(N - 1).

Elixir

Elixir is a functional, concurrent, general-purpose programming language that runs on the Erlang virtual machine (BEAM).The Fibonacci function can be written in Elixir as follows:defmodule Fibonacci do
def fib(0), do: 0
def fib(1), do: 1
def fib(n), do: fib(n-1) + fib(n-2)
end

Lisp

The Fibonacci function can be written in Common Lisp as follows:(defun fib (n &optional (a 0) (b 1))
(if (= n 0)
a
(fib (- n 1) b (+ a b))))
or(defun fib (n)
(if (or (= n 0) (= n 1))
n
(+ (fib (- n 1)) (fib (- n 2)))))
The program can then be called as(fib 10)

Clojure

The Fibonacci function can be written in Clojure as follows:(defn fib
[n]
(loop [a 0 b 1 i n]
(if (zero? i)
a
(recur b (+ a b) (dec i)))))
The program can then be called as(fib 7)Explicitly using "lazy-seq", the infinite sequence of Fibonacci numbers can be defined recursively.
lazy infinite sequence
(def fibs (cons 0 (cons 1 (lazy-seq (map + fibs (rest fibs))))))
list of first 10 Fibonacci numbers taken from infinite sequence
(take 10 fibs)

Kotlin

The Fibonacci function can be written in Kotlin as follows:fun fib(x: Int): Int = if (x in 0..1) x else fib(x - 1) + fib(x - 2)The program can then be called asfib(7)

Swift

The Fibonacci function can be written in Swift as follows:func fib(_ x: Int) -> Int {
if x == 0 || x == 1 {
return x
} else {
return fib(x - 1) + fib(x - 2)
}
}The function can then be called asfib(7)

JavaScript

The Fibonacci function can be written in JavaScript as follows:const fib = (x) => (function sub_fib(a, b) { return x-- > 0 ? sub_fib(b, a+b) : a})(0,1)orconst sub_fib = (x, a, b) => x > 0 ? sub_fib(x-1, b, a+b) : aconst fib = (x) => sub_fib(x, 0,1)or const fib = (x) => x0 ? throw new Error("The Fibonacci function is only defined for 0 and positive integers") : x n { (n == 0 || n == 1) ? n : fib[n - 1] + fib[n - 2] }

Tcl

The Fibonacci function can be written in Tcl as a recursive function as follows:proc fibo {x} {
expr {\$x 1
case _ => fibRec(n - 1) + fibRec(n - 2)
}Recursive style with tail call optimization, fastdef fibTailRec(n: Int): Int = {
@tailrec
def fib(i: Int, v: Int, vNext: Int): Int =
if(i == n) v
else fib(i + 1, vNext, v + vNext)
fib(0, 0, 1)
}Using Scala streamsval fibStream: Stream[Int] =
0 #:: 1 #:: (fibStream zip fibStream.tail).map(n => n._1 + n._2)

In education

Functional programming is being used as a method to teach problem solving, algebra and geometric concepts.{{Triangulation|196|Emmanuel Schanzer of Bootstrap}}It has also been used as a tool to teach classical mechanics in Structure and Interpretation of Classical Mechanics.

References

• BOOK, Abelson, Hal, Hal Abelson, Sussman, Gerald Jay, Gerald Jay Sussman, Structure and Interpretation of Computer Programs,weblink 1985, MIT Press,
• 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.
• BOOK, Curry, Haskell B., J. Roger, Hindley, Jonathan P., Seldin, Haskell Curry, J. Roger Hindley, Jonathan P. Seldin, Combinatory Logic, Vol. II, 1972, North Holland, Amsterdam, 978-0-7204-2208-5,
• Dominus, Mark Jason. Higher-Order Perl. Morgan Kaufmann. 2005.
• BOOK, Felleisen, Matthias, Findler, Robert, Flatt, Matthew, Shriram, Krishnamurthi, How to Design Programs,weblink 2001, MIT Press,
• Graham, Paul. ANSI Common LISP. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
• MacLennan, Bruce J. Functional Programming: Practice and Theory. Addison-Wesley, 1990.
• BOOK, O'Sullivan, Brian, Stewart, Don, Goerzen, John, Real World Haskell,weblink 2008, O'Reilly,
• Pratt, Terrence, W. and Marvin V. Zelkowitz. Programming Languages: Design and Implementation. 3rd ed. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
• Salus, Peter H. Functional and Logic Programming Languages. Vol. 4 of Handbook of Programming Languages. Indianapolis, Indiana: Macmillan Technical Publishing, 1998.
• Thompson, Simon. Haskell: The Craft of Functional Programming. Harlow, England: Addison-Wesley Longman Limited, 1996.

{{Spoken Wikipedia|En-Functional_programming.ogg|2011-08-25}}
• WEB, Ford, Neal, Functional thinking: Why functional programming is on the rise, 2013-02-24, 2012-01-29,weblink
,
• WEB, Akhmechet, Slava, defmacro â€“ Functional Programming For The Rest of Us, 2013-02-24, 2006-06-19,weblink
, An introduction
{{Programming language}}{{Authority control}}

- content above as imported from Wikipedia
- "functional programming" does not exist on GetWiki (yet)
- time: 1:36am EDT - Mon, Jun 17 2019
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 MAY 2016
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
GETWIKI 20 AUG 2014
GETWIKI 19 AUG 2014
GETWIKI 18 AUG 2014
Wikinfo
Culture
CONNECT