Functional Programming

Article Info

Contributed by
3 authors

Last updated on
2022-02-15 11:48:16

Lambda Calculus
Declarative Programming
Imperative Programming
Higher-Order Function
Functional Programming in Python
Haskell

Article Versions

5 2022-02-15 11:48:16
3306,1851 5,3306

By devbot5S

Migrating blockquotes to markdown syntax
4 2020-01-06 03:57:22
1851,1244 4,1851

By arvindpdmn

Updated See Also
3 2019-03-13 15:30:17
1244,83 3,1244

By arvindpdmn

Just save to update word count due to fix in v0.21.0.
2 2017-04-09 11:06:27
83,40 2,83

By kkris

Content added.
1 2017-03-17 07:10:30
1,40

By arvindpdmn

Request for article

Chat Room

Submitting ...

You are editing an existing chat message.
2019-03-28 08:49:22
-
1

By learnbyexample

* first discussion, third sentence: should be Its not It's

* the picture shown along with 'concepts/features' discussion doesn't have any of those terms in that discussion - would suggest to move the picture to previous discussion question, which has terms like 'pure' and 'first-class' function

* suggestion: highlight all the terms described in discussion 4, 5 and 6 like 'pure functions', 'currying', 'pipelining' etc - would make it easier to spot them on rereads

Functional programming (FP) puts emphasis on functions, where functions are closer in spirit to mathematical functions than functions or subroutines in computer science. A function is something that takes inputs and returns outputs without any side effects. A set of inputs given to a function will always return the same set of outputs. This implies that functions do not depend on global variables, shared resources, the thread context or the timing across threads. Absence of side effects is essential to FP.

Functional programming has been around since the 1950s but they got sidelined by imperative languages such as C, C++ and Java. Today, in the context of parallel computing, synchronization across parallel threads can be difficult. FP has come to the rescue. FP enables clean abstractions, component design and interfaces making the program more declarative and shorter.

Discussion

What exactly do you mean by side effects?
When a function relates to its external world in a hidden manner, then it has side effects. For a function without side effects, its inputs are passed explicitly as function arguments. It's output is via function return. Such a function does not receive inputs via global variables such as message queues, shared buffers, databases or files. Likewise, it does not modify external entities such as writing to a file or making an AJAX call in a web application.
The goal of FP is to reduce side effects, not completely eliminate them in the entire program. Since programs have to interface to users, write to files or make network calls, they cannot be without side effects. We can however make most of the program functional by writing functions without side effects. It's important to track which parts of the system are impure. Some languages have a type system to facilitate this.
Sometimes input and output are independently recognized as side causes and side effects respectively. More commonly, it's sufficient to use the term side effects to refer to both.
What conditions should a programming language satisfy to be considered functional?
A pure FP language should prohibit side effects. FP places importance on expressions rather than statements. In this sense, FP is an instance of declarative programming, which implies that focus is on what is to be computed rather than how to compute it. Objects are immutable: once created, they cannot be changed. The focus is on data manipulated by functions rather than states stored within objects. It has been said that "immutability and statelessness are core to functional programming."
Program state is tracked as part of function arguments. Thus, function recursion is preferred to looping based on loop variables. Data flow is more important than control flow and this facilitates concurrency. The order of function calls doesn't matter if the data flow is preserved.
FP does not require dynamic typing or static typing for that matter. The use of compile-time AST (Abstract Syntax Tree) macros does not imply FP.
How is FP different from imperative programming?
Comparing looping and recursion. Source: http://secretgeek.net/image/function_v_imperative.PNG
With imperative programming, assignment of a variable is a common operation. For example, x = x + 1 is a valid operation in C, C++ or Java. But this makes no sense from a mathematical perspective; that is, if we consider it as an equation, there's no solution for it. In FP, data is transformed but not mutated. Expressions are important but storing the result is not. Results are passed around to other functions.
Imperative programming is about objects and their states. FP is about pure functions and higher-order functions. Complex behaviour in FP can be constructed by composing simpler functions. If OOP is about passing objects, FP is about passing functions. With imperative programming, operations are specified step by step. Loops with loop variables are used to iterate over lists. With FP, the style is declarative. Recursion and list processing using iterators are common control structures.
Michel Feathers tweeted in 2010 that,
OO makes code understandable by encapsulating moving parts. FP makes code understandable by minimizing moving parts.
Can you explain pure functions, first-class functions and higher-order functions?
Pure functions conform to the rules of lambda calculus. Programs written in pure FP will be referentially transparent and their correctness can be formally proven. A practical way to define pure functions is that they have no side effects and always produce the same outputs for the same inputs. This is also called determinism. Impure FP therefore have elements of FP such as higher-order functions but may allow mutation of variables or even access to data outside the scope of functions. Side effects could be a language feature or due to monads. Closures cannot be considered as pure functions.
First-class functions can be assigned to variables, passed as arguments to other functions and can be returned from other functions. Functions in FP are first-class functions. Higher-order functions are functions that accept a function as argument and/or return a function as output. Thus, first-class functions is about the status that functions have in the language whereas higher-order functions are explicitly those that accept/return functions as input/output respectively. They eliminate loops. Code can be refactored to avoid repetitive code. Closures are examples of higher-order functions.
Can you point out some concepts/features of FP?
Some characteristics of FP. Source: Grimm 2017.
We may note the following:
- Closure: This is a data structure with a code pointer and an environment of bound variables, implemented as anonymous functions. Alternatively, "a closure is a function's scope that's kept alive by a reference to that function."
- Referential transparency: This is a property of pure functions that always return the same outputs for the same inputs. Another way of stating this is that an object can be replaced by its value since objects are immutable. Equational reasoning can be applied to code for either provability or optimization.
- Currying: A function with multiple arguments is transformed into a chain of functions, each taking a single argument. Currying is useful to adapt a function to a form that some other function or interface expects. Currying is sometimes confused for partial functions.
- Composability: When functions perform specific tasks, we can use them as building blocks to compose more complex functionality. While composability is a concept, currying and pipelining may be considered as an implementations for it.
What techniques do FP languages use?
We may note the following:
- Tail call optimization: With recursion, FP usually supports tail call optimization that reuses the same stack frame for a sequence of recursive calls. Without this, program can run out of stack memory when recursion descends many levels deep.
- Pattern matching: A concise way to match a value or type and thereby avoid complex control structures.
- Lazy evaluation: Code will be executed only when required. Haskell does this well. Graph reduction is a technique to implement lazy evaluation.
- Partial functions: They wrap a function by fixing some arguments to values and retaining the rest as arguments. In fact, partial functions simplify implementation of closures.
- Pipelining: Pass the output of one function as input to another. Many function calls can be chained in a sequence in this way. Pipelining makes possible code reuse, unit testing and parallel execution.
- Continuation: This enforces execution in a specified order, which is particularly useful when lazy evaluation would skip execution.
Why or when should we use FP?
With multicore, multi-processor or networked systems, concurrency is becoming a challenge. With no side effects, FP is an approach that eliminates shared variables, critical sections and deadlocks. Erlang implements Actor concurrency model, meaning that messages are passed between threads rather than sharing variables.
Since there are no side effects (and side causes), FP are easier to test and debug. Unit tests need to worry about only function arguments. Peeking into the stack is enough to debug issues. Hot code deployment is possible with FP since object instances holding states don't really exist in FP. Reability of code generally improves with FP. Code is concise since the focus is on what rather than how.
For mission-critical systems, program correctness can be proven formally. Likewise, compilers can transform code into more optimized forms. These are possible due to the mathematical basis on which FP is founded. Due to lazy evaluation, it's possible to optimize code, abstract control structures and implement infinite data structures.
Where is FP used in the real world?
Ericsson uses Erlang in telecommunication switches. AT&T uses Haskell for network security. Akamai content delivery network uses Clojure while Twitter uses Scala. Elm is a pure FP language that compiles to JavaScript. It is used by NoRedInk. Computer aided design (CAD) software often support AutoLISP. OCaml has been used for financial analysis and research. Scala is widely used for data science. Clojure is being used in wide range of applications from finance to retail. Hughes shows examples of using FP for numerical problems as well as gaming.
Many uses of Haskell in industry is well documented. An annual conference named Commercial Uses of Functional Programming (CUFP) has been going on as early as 2004 to track and share use cases and best practices. As an example, the uses of Caml in industry was presented in 2007.
Which programming languages are considered as functional?
Some examples of FP languages. Source: Kestelyn 2015.
While LISP is one of the earliest FP language, the following (non-exhaustive list) are among those being used commercially: Haskell, F#, Clojure, Scala, OCaml, SML, Erlang. Wikipedia gives lists of FP languages that are considered pure and impure. Excel may be considered as a FP language.
It's likely that object-oriented programming (OOP) will coexist with FP. For complex applications requiring concurrency, FP may be preferred. F# and Scala combine elements of FP and OOP. Some have even used the term "object-functional programming" to mark this trend.
Many popular languages while not designed as FP, can be used in part as FP. Examples include Java, Python, and R. Sometimes third-party libraries or packages enable FP, such as Swiftz for Swift, Underscore.js for JavaScript and Fn.py for Python. Immutable.js in JavaScript enables data immutability.
Why did FP take so long to get popular?
FP started with ideas rooted in mathematics, logic and formalism. This appealed to academics who approached it theoretically. It didn't appeal to the programming community who considered functions more as code blocks for partitioning behaviour and reusing code. To them, imperative programming (including OOP) was more practical. It was also believed that FP, with all its limitations, could not be used to build big complex programs. FP was also believed to be slower.
Some have argued that FP involves abstraction. This can be difficult for programmers used to coding with loops and assignments.
How is FP different from lambda calculus?
FP may be regarded as a practical implementation of lambda calculus. Lambda calculus was a tool to study the problem of computability. It is independent of physical constraints. FP is application of some ideas of lambda calculus.

Milestones

1936

Alonzo Church invents lambda calculus at Princeton University while formally investigating ways to program machines. This is part a bigger effort at Princeton where others including Alan Turing, John von Neumann and Kurt Gödel attempt to formalise mathematics and computing.

1956

IPL is created at Carnegie Institute of Technology and could be considered as the first FP language (in assembly), though it has some imperative language features.

1958

MIT professor John McCarthy invents List Processing Language (LISP) as the first implementation of Church's lambda calculus. Common Lisp and Scheme are two popular dialects of LISP. The influence of lambda calculus on Lisp has been challenged.

1973

Programmers at MIT's Artificial Intelligence Lab build a Lisp machine. Thus Lisp got its own native hardware rather than running on von Neumann architecture.

1973

Robin Milner at the University of Edinburgh creates ML (Meta Language). OCaml and Standard ML (SML) are popular dialects of ML.

1977

John Backus publishes a paper describing the proper use of functions and expressions without assignments and storage. Some call this function-level programming but the paper influences FP.

Sample Code

Python

# Source: Metz, David. 2015. Functional Programming in Python. O'Reilly Media, Inc.
def factorialR(N):
    "Recursive factorial function"
    assert isinstance(N, int) and N >= 1
    return 1 if N <= 1 else N * factorialR(N-1)
 
def factorialI(N):
    "Iterative factorial function"
    assert isinstance(N, int) and N >= 1
    product = 1
    while N >= 1:
        product *= N
        N -= 1
    return product
 
from functools import reduce
from operator import mul
def factorialHOF(n):
    "Factorial implemented as a higher-order function"
    return reduce(mul, range(1, n+1), 1)