10. Functional Programming

10.1. What is functional programming language?

Common features of functional programming languages are as follows:

• A program is a set of functions.

• A function is a first class object.

• There is no such thing as statements or commands. Evaluating expressions is the only way to execute a program.

• There is referential transparency.

10.2. referential transparency

A language has referential transparency if literally same expressions always result in the same value as long as the environment is the same.

10.2.1. Variable

Since a single variable is an expression, referential transparency implies that the value of the variable is always the same.

In other words, a variable name is directly bound to a value (cf. Bindings). Note that the same name may be bound to another value in another environment.

You may think switching environments is virtually same as assigning new values. However, there are differences as follows:

• Environments are usually associated with syntactic structures while assignments are non-structured and hard to predict their influence.

• Since creation of a new environment does not affect existing environments, there is no side-effect.

10.2.2. Loop

With referential transparency, it is impossible to have a loop structure such as while because the value of its condition never changes.

Instead, recursive functions are usually used for iterations in functional languages. Each time a function is called, a new environment is created so that a condition may have another value.

10.2.3. Data structure

When we have a complex data, referential transparency implies that its structure never changes. It is also called persistent data structure or immutable data structure.

Although it is called persistent, it may be removed by the garbage collector.

Note

Whereas the most prominent feature of functional languages is referential transparency, not so many languages strictly follow the policy. For example, Lisp has setq (assignment to variables) which breaks referential transparency. However, many people say Lisp is a functional language because it is possible to write a program with only features that keep referential transparency.

When we want to emphasize that every feature of a language keeps referential transparency, we say the language is pure functional.

10.3. Theoretical basis

Lambda calculus is a formal system used for research of theoretical computer science. See Wikipedia for detail.

10.3.1. Reduction

In mathematics, the right side of \(1+2=\) may be \(4-1\) or \(\sqrt{9}\). However, we expect the value of 1+2 is 3 in computer programs. Reduction is, intuitively speaking, a procedure to convert an expression into a simpler equivalent expression.

• \(\beta\)-reduction in lambda calculus corresponds to applying a function to its arguments in programming languages.

• Given a lambda expression, we can repeatedly apply \(\beta\)-reduction until it is irreducible any more. The final expression is called the normal form of the given expression.

• Normal form may not exist because \(\beta\)-reduction may be applicable infinitely many times.

10.3.2. Reduction strategy

A lambda expression may have more than one part for which \(\beta\)-reduction is applicable. A reduction strategy is a rule to choose the next reduction step.

applicative order

Select the innermost part for which \(\beta\)-reduction is applicable. There is a possibility that reduction continues forever even if the expression has a normal form.

normal order

Select the outermost part for which \(\beta\)-reduction is applicable. Reduction always reach the normal form if it exists.

Reduction strategies correspond to evaluation strategies in programming languages (cf. Evaluation strategy of parameters, Lazy evaluation).

applicative order	normal order
strict evaluation	non-strict evaluation
eager evaluation	lazy evaluation
pass by value	pass by name

Reduction steps that do not reach the normal form corresponds to an infinite loop in programming languages.

Strictness and infinite loop

JavaScript is a strict language. bar(foo("a")) goes into an infinite loop.

function foo(x) {
  return foo(x)
}

function bar(x) {
  return "b"
}

console.log(bar(foo("a")))

Haskell is a non-strict language. bar(foo("a")) returns "b".

foo :: String -> String
foo x = foo x

bar :: String -> String
bar x = "b"

main = putStrLn (bar (foo "a"))

10.4. Monad

There are several cases where referential transparency obstacles practical use of the language.

• Random number: It is nonsense that the function random returns the same value every time.

• Input/Output: The function getLine should return strings typed by humans.

Haskell, a pure functional language, has introduced monad to solve the problems above.

• Monad is a simple mechanism that generates a new type from an existing type by adding auxiliary information.

• IO monad is somewhat special.

  • It encapsulates input/output operation as auxiliary information.

  • For example, getLine always returns the same value whose type is IO string.

  • Actual input/output operations are done by Haskell runtime.

• cf. You Could Have Invented Monads! (And Maybe You Already Have.)