Purely functional functions (or expressions) have no memory or I/O side effects (unless the computation of the result in itself is counted as a side-effect). 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 parameters that cause no side-effects, the result is constant with respect to that parameter list (sometimes called referential transparency), i.e. if the pure function is again called with the same parameters, the same result will be returned (this can enable caching optimisations such as memoization).
* If there is no data dependency between two pure expressions, then 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 optimisations 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 optimisations. Fortran 95 allows functions to be designated "pure".
Recursion
Iteration (looping) in functional languages is usually accomplished via recursion. Recursive functions invoke themselves, allowing an operation to be performed over and over. Recursion may require maintaining a stack, but tail recursion can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages. The Scheme programming 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 compilation, among other approaches.
Common patterns of recursion can be factored out using higher order functions, catamorphisms and anamorphisms (or "folds" and "unfolds") being the most obvious examples. Such higher order functions 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. See Turner 2004 for more discussion.
Strict versus non-strict evaluation
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 will itself fail. For example, the expression
print length([2+1, 3*2, 1/0, 5-4])
will fail under strict evaluation because of the division by zero in the third element of the list. Under nonstrict evaluation, the length function will return the value 4, since evaluating it will not attempt to evaluate the terms making up the list. In brief, strict evaluation always fully evaluates function arguments before invoking the function. Non-strict evaluation does not evaluate function arguments unless their values are required to evaluate the function call itself.
The usual implementation strategy for non-strict evaluation in functional languages is graph reduction. Non-strict evaluation is used by default in several pure functional languages, including Miranda, Clean and Haskell.
Hughes 1984 argues for non-strict evaluation as a mechanism for improving program modularity through separation of concerns, by easing independent implementation of producers and consumers of data streams. 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. Harper 2009 proposes including both strict and nonstrict evaluation in the same language, using the language's type system to distinguish them.
Type systems and pattern matching
Especially since the development of Hindley-Milner type inference in the 1970s, functional programming languages have tended to use typed lambda calculus, as opposed to the untyped lambda calculus used in Lisp and its variants (such as Scheme). The use of algebraic datatypes and pattern matching makes manipulation of complex data structures more convenient and expressive; the presence of strong compile-time type checking makes programs more reliable, while type inference frees the programmer from the need to manually declare types to the compiler.
Some research-oriented functional languages such as Coq, Agda, Cayenne, and Epigram are based on Intuitionistic type theory, which allows types to depend on terms. Such types are called dependent types. These type systems do not have decidable type inference and are difficult to understand and program with. But dependent types can express arbitrary propositions in predicate logic. Through the Curry-Howard isomorphism, then, well-typed programs in these languages become a means of writing formal mathematical proofs from which a compiler can generate certified code. While these languages are primarily of interest in academic research (including in formalized mathematics), they have begun to be used in engineering as well. Compcert is a compiler for a subset of the C programming language that is written in Coq and formally verified.
A limited form of dependent types called generalized algebraic data types (GADT's) can be implemented in a way that provides some of the benefits of dependently-typed programming while avoiding most of its inconvenience.[30] GADT's are available in the Glasgow Haskell Compiler and in Scala (as "case classes"), and have been proposed as additions to other languages including Java and C#.
Functional programming in non-functional languages
It is possible to employ a functional style of programming in languages that are not traditionally considered functional languages.[32] Some non-functional languages have borrowed features such as higher-order functions, and list comprehensions from functional programming languages. This makes it easier to adopt a functional style when using these languages. Functional constructs such as higher-order functions and lazy lists can be obtained in C++ via libraries.[33] In C, function pointers can be used to get some of the effects of higher-order functions. For example the common function map can be implemented using function pointers. In C# version 3.0 and higher, lambda functions can be employed to write programs in a functional style.[citation needed] In Java, anonymous classes can sometimes be used to simulate closures,[citation needed] however anonymous classes are not always proper replacements to closures because they have more limited capabilities.
Many object-oriented design patterns are expressible in functional programming terms: for example, the Strategy pattern simply dictates use of a higher-order function, and the Visitor pattern roughly corresponds to a Catamorphism, or fold.
The benefits of immutable data can be seen even in imperative programs, so programmers often strive to make some data immutable even in imperative programs.
Comparison of functional and 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 disallows side effects completely. Disallowing side effects provides for referential transparency, which makes it easier to verify, optimize, and parallelize programs, and easier to write automated tools to perform those tasks.
Higher order functions are rarely used in older imperative programming. Where a traditional imperative program might use a loop to traverse a list, a functional style would often use a higher-order function, map, that takes as arguments a function and a list, applies the function to each element of the list, and returns a list of the results.
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 monads, derived from category theory. Monads are powerful and 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 find them difficult to understand conceptually, e.g., when asked to define new monads (which is sometimes needed for certain types of libraries).
Alternative methods such as Hoare logic and uniqueness have been developed to track side effects in programs. Some modern research languages use effect systems to make explicit the presence of side effects.
Domain and Range
Overview
A function is generally defined as a rule that partners to each number x in a set a unique number y in another set. The set of x values to which the rule applies is the function's domain, and the set of y values to which it applies is its range.Calculus allows us to mathematically study rates of change and motion, something not precisely possible prior to discovery of the fundamental theorem of calculus. The domain and range of a function are the essence or foundation of algebraic equations and calculus formulas. Everyday uses include graphs, charts and maps.
