Note on Imperative and Functional programming

 

What does computing mean?
Roughly, to transform information from an implicit into an explicit form.

But this notion means nothing unless we make it precise, formal, by defining a computational model.
What is a Computational model?
A particular formalization of the notions connected to the concept of "computing".
The rather vague concept of computing can be formalized in several different ways, that is by means of several different computational models:
the Lambda-calculus, the Turing machine, etc.
"To program" means to specify a particular computation process, in a language based on a particular computational model.

Functional programming languages are based on the Lambda-calculus computational model.
Imperative programming languages are based on imperative computational models like the Turing-machines or the URM.

The fundamental concepts in imperative programming languages (coming from the Turing Machines or URM models) are:

  • store
  • variable - something it is possible to modify ("memory cell")
  • assignment
  • instruction
  • iteration

In functional programming these concepts are absent (or, in case they are present, have a different meaning).
Instead, in it we find:

  • expression
  • recursion - different from the notion of iteration
  • evaluation - different from the notion of execution:
    • when we evaluate a mathematical expression we do not modify anything.
  • variable - intended in a mathematical sense:
    • unknown entity
    • abstraction from a concrete value



 Functional programming

A program in a functional language  consists in a set of function definitions and an expression (usually formed using the defined functions). The Interpreter of the language evaluates this expression by means of a discrete number of computation steps, making its meaning explicit (as pointed out before, during a computation, nothing is actually created, but - a fact extremely clear in functional programming - the representation of the information is "transformed".)

A function definition in functional programming is not simply a means to uniquely identify a mathematical function on a domain of objects.

Example: a mathematical definition of two functions

f: R -> R ,   g: R -> R
f '' - 6g' = 6 sen x
6g'' + a2 f ' = 6 cos x
f(0) = 0,  f '(0) = 0,  g(0) = 1,  g'(0) = 1

This set of equations precisely identify two precise  f and g.

In the above example f and g are uniquely identified by the set of differential equation, but such a definition is not useful from a computational point of view.
A function definition in a functional programming language, instead, has also to show how to compute (evaluate) the defined function on a given argument.

Example: function definition in Scheme and in Haskell

            (define Inctwo (lambda (n) (+ n 2)))

             Inctwo  n = n + 2

The evaluation of the application of a (user-defined) function to an argument consists in evaluating the expression consisting in the body of the function in which the formal parameter is replaced by the actual parameter (the argument).
To evaluate an expression means to first look for a sub-expression which is the application of a function to some arguments and then to evaluate such an application. In this way, in a sense, the meaning of the whole expression is made more and more explicit.

Example: evaluating (Inctwo 3)

   Inctwo is a user defined function, and it is applied to an argument, so  we take the body of the function, replace the formal parameter n by the actual parameter 3, obtaining
 3+2, and then we evaluate 3+2 obtaining 5

In the example above we have seen two kinds of computational steps from Inc 3 to 5. In the first one we have simply substituted in the body of the function the formal parameter by the actual parameter, the argument, and in the second one we have computed a  predefined function. The essence of the notion of computation in functional programming is indeed embodied by the first type of computational step. The simple operation of replacing the arguments of a function for its formal parameters in its body contains all the computing power of functional programming. Any sort of computation in functional programming could indeed be defined in terms of this one. This sort of computational step is formalized by the beta-reduction rule in the lambda calculus and we shall see that, if one wish, any possible computation can be defined in terms of this beta-rule.

When we evaluate an expression there are sometimes more than one sub-expression one can choose  and hence different possible evaluation paths can be followed. An evaluation strategy is a policy enabling to decide on which sub-expression we shall perform the next evaluation step. Some evaluation strategies could lead me in a never-ending path (this fact is unavoidable); but I would like to be sure that all finite path do lead me to the very same value (this will be guaranteed by the Confluence Theorem of the Lambda-calculus).

Example: In Haskell

     inf n = inf n                // definition of the value inf
    alwayseven x = 7  // definition of the function alwayseven
    alwayseven (inf 3)     // expression to be evaluated

Two possible choices in the evaluation of alwayseven (Inf 3):

  1. We evaluate (inf 3)  first (the evaluation strategy of Scheme).
  2. We evaluate (alwayseven (inf 3))  first (the evaluation strategy of Haskell, a lazy language).

case 1. Replace (inf 3) by (inf 3)    =>  we go on endlessly
case 2. Replace (alwayseven (inf 3)) by 7   =>   we terminate in a single step.

One of the distinguishing features in a programming language is the evaluation strategy it uses.

We know how to define the function  factorial in a recursive way:

            fac n = if (n=0) then 1 else n*fac(n-1)

    Let us see how an interpreter using an evaluation strategy like the one of Scheme would evaluate the expression (fac 2).

(fac 2)
→ (if (2 = 0) then 1 else (2 * (fac (2 - 1))))
→ (if FALSE then 1 else (2 * (fac (2 - 1))))
→ (2 * (fac (2 - 1)))
→ (2 * (fac 1))
→ (2 * (if (1 = 0) then 1 else (1 * (fac (1 - 1)))))
→ (2 * (if FALSE then 1 else (1 * (fac (1 - 1))))))
→ (2 * (1 * (fac 0)))
→ (2 * (1 * (if (= 0 0) then 1 else (0 * (fac (0 - 1)))))))
→ (2 * (1 * (if TRUE then 1 else (0 * (fac (0 * 1)))))))
→ (2 * (1 * 1)))
→ (2 * 1) → 2

Notice how, also in languages like Scheme, the arguments of the conditional operator if, are not both evaluated before the application of if, since otherwise the computation would never stop. (exercise: why?).

Let us give now an example of mutually recursive functions.

even x=if x=0 then true
                        else odd(x-1)
odd x=if x=0 then false
                        else even(x-1)

With our recursive definitions we do not only specify functions, but we also provide a method to compute them: a recursive definition definition says that the left-hand side part of the equation is equivalent (has the same "meaning") of the right-hand side. The right-hand side, however, has its meaning expressed in a more explicit way. We can replace the left-hand side part with the right-hand one in any expression without modifying its meaning.
We can notice that in order to evaluate "even 3" we can follow different evaluation strategies. It is also possible to perform more reductions in parallel, that is to replace two or more sub-expressions with equivalent sub-expression (reduction step) at the same time. A similar thing is not possible in imperative languages since we need to take into account the problem of side effects:
running in parallel the instructions of the subprograms computing two functions F1 and F2 can produce strange results, since the two subprograms could use (and modify) the value of global variables which can affect the results produced by the two functions. Of course, because of the presence of global variables, the value of a function can depend on time and on how many times we have computed it before (in general in imperative languages it is difficult to be sure that we are programming actual mathematical functions.) We have not the above mentioned problems in functional programming languages, since there not exists side effects (there are no global modifyable variables). What we define are therefore actual mathematical functions; hence in an expression the value of any sub-expression does not depend on the way we evaluate it or other ones, that is the same expression always denotes the same value (a property called referential transparency).