What is  a Function ?
---------------------
"A relation between two sets that associate a unique element (the
VALUE) of the second (the CODOMAIN) with each element, or n-tuple, of
elements (the ARGUMENTS) of the first (DOMAIN)." Dictionary of
Mathematics, Borowski and Borwein

"Informally, a function is seen as a correspondence between argument
values (the SOURCE set) and result values (the TARGET set). ... 

A function is called TOTAL if it associates exactly one element in the 
target with each element in its source. A PARTIAL function may or may not 
associate an element in the target with each element in the source,
and is said to be undefined for those arguments which it does not map
to a result. ....

A function can be defined "intensionally" by a rule describing the
association, or can be defined "extensionally" as a set of associated
pairs (argment,result). An intensional description of a function
emphasizes the process by which the result is found for given
arguments."  Elements of Functional Programming, Reade.


Why Functional Programming?
--------------------------

                         LANGUAGES


               EXPRESSIONS         STATEMENTS


Expression: "yield a value through the process of evaluation"
Statement: "alter the flow of control, alter the state (memory) of the
            computer"

Statements: alter something. The order in which things are done is
            significant.

    z:= (2*a*y+b)*(2*a*y+c)  {common sub-expression 2*a*y}
    t:= 2*a*y                {eliminate redundancy}
    z:= (t+b)*(t+c)


    y:= 2*a*y+b
    z:= 2*a*y+c              {common sub-expression 2*a*y}

What happens if we factor out 2*a*y?
Common sub-expression elimination is difficult in statements.
Expressions allow an ease of reasoning over programs.

To "evaluate" something, means to extract its value.
The evaluation of an expression, for example (2ax + b)(2ax + c), is
dependent on its "context of evaluation".  Assume a=3, b=2, c=-1, x=2.
Draw expression as a tree.






                      (page 9 MacLennan)





Observations
------------
Each operation depends only on those directly below it. 
In evaluation, begin at the leaves, evaluate the nodes in ANY order,
so long as the inputs to a node have already been evaluated.
Whenever all nodes below a given node have been "decorated" with
values, we can "decorate" the given node with a value. This terminates
when the root node has been decorated., that is the value of the
entire expression has been computed. So what?

No matter what the order of decoration, as long as the above rule is
obeyed, the same value will be delivered. So what?

This property of "pure" expressions, that is independence of
evaluation order, is called the "Church-Rosser property".

Impure: function f(x:integer):integer;
         begin
          a:=a+1;
          f:=x*x
         end;

        a:=0
        z:= a + f(3);  {does (a + f(3)) = (f(3) + a) ?}

Pure:   function f(x:integer):integer;
         begin
          f:=x*x
         end;


Referential Transparency
------------------------
In evaluating the expression (2ax + b)(2ax + c) no person (in their
right mind) would evaluate the sub-expression 2ax twice. Having
evaluated 2ax, the value could be substituted in place of all
occurrences of 2ax. Therefore we can represent the expression 
(2ax + b)(2ax + c), not just as a tree but as an "acyclic graph".

Referential transparency means that, in a fixed context the
replacement of sub-expression by its value is completely independent
of the surrounding expression. More generally, referential
transparency can be defined as the universal ability to substitute
equals for equals. This permits optimisation. This also permits the
derivation of new equations/expressions from given
equations/expressions, and ultimately allows proof of expressions. 
That is it facilitates reasoning.


A History of Functional Programming
-----------------------------------
Maclennan, page 23-26