1. General Concepts

Functional Programming

Functional programs consist entirely of functions, where a function can be defined in terms of other functions (defined by the programmer, libraries, or language primitives). We focus on what is to be computed, not how it should be computed.

Advantages	Disadvantages
shorter programs	usually slower than imperative programs
easier to understand	arguably less flexible
easier to design, verify, and maintain

Link to original

Modern functional languages are strongly-typed and have built-in memory management.

Syntax

The notation is heavily inspired by mathematical definition of functions, using equations. We can compute the square of a number using a function square defined by the equation:

square x = x * x

Execution

The role of the computer is to evaluate and display the results of the expressions that the programmer writes, using the available functions. When we type an expression such as square 6, the computer will display the result 36.

Evaluation

To evaluate square 6, the computer will use the definition of the function square and replace this expression by 6 * 6. The predefined * operation will compute the result 36.

The process of evaluating an expression is a simplification process, also called a reduction or evaluation, whose goal is to obtain the value or normal form associated with the expression. We will use the notation $e\to e^{\prime }$ to denote a reduction from $e$ to $e^{\prime }$.

Properties of evaluation

1. Unicity of normal forms

   Unicity of normal forms: in (pure) functional languages, the value of an expression is uniquely determined by its components, and is independent of the order of reduction

   Link to original

2. Non-termination: not all reduction sequences lead to a value, some reduction sequences do not terminate

Example

Let us define:

fortytwo x = 42
infinity = infinity + 1

The evaluation of infinity never reaches a normal form. The expression fortytwo infinity has reduction sequences which do not term, but those which do give the value 42 (unicity of normal forms).

Although the normal form is unique, the order of reductions is important. The strategy of evaluation defines the reduction sequences that the language implements.

Popular evaluation strategies

• Call-by-name (normal order): reduce first the application using the definition of the function, then the argument. Always finds the value if there is one.
• Call-by-value (applicative order): evaluate first the argument and then the application using the definition of the function. More efficient but may fail to find a value.

Different strategies require a different number of reduction steps. Haskell uses the lazy evaluation strategy which guarantees that if an expression has a normal form, then the evaluator will find it: $\text{lazy evaluation}=\text{call-by-name}+\text{sharing}$. Lazy evaluation defers the evaluation of expressions until their results are needed for other computations.

Functional values

Functions are also values, even though we cant’t display or print them. A function is a mapping that associates to each element of a given type $A$ (domain), an element of type $B$ (codomain). $f:A\to B$

The syntax to associate a type to a function is:

square   :: Integer -> Integer
fortytwo :: Integer -> Integer

Syntax of function definitions

Functions are defined in terms of equations:

square x = x * x
min x y  = if x <= y then x else y
 
-- we can use conditional equations (or guarded equations)
sign x
    | x < 0  = -1
    | x == 0 =  0
    | x > 0  =  1

Function application

Application is denoted by juxtaposition: (f x) For example:

(square 3)
(sign (-5))
(min 3 (-5))

There are some conventions:

• application has precedence over other operations: square 3 + 1 means (square 3) + 1
• application associates to the left: square square 3 means (square square) 3
• we do not write outer brackets