Introduction
The first functional language, Lisp, appeared at the end of the 1950's.
That is, at the same time as Fortran, the first representative of
the imperative languages. These two languages still exist, although both have
evolved greatly. They are used widely for numerical programming (in the case
of Fortran) and symbolic applications in the case of Lisp. Interest
in functional programming arises from the great ease of writing programs
and specifying the values which they manipulate. A program is a function
applied to its arguments. It computes a result which is returned (when the
computation terminates) as the output of the program. In this way it
becomes easy to combine programs: the output of one program becomes an
input argument to another, in the sense of function composition.
Functional programming is based on a simple computation model with
three constructions: variables, function definitions, and applications of
a function to an argument. This model is called the l-calculus and
it was introduced by Alonzo Church in 1932, thus before the first computer.
It was created to offer a general theoretical model of the notion of
computability. In the l-calculus, all functions are values
which can be manipulated. They can be used as arguments to other
functions, or returned as the result of a call to another function. The
theory of l-calculus asserts that everything which is computable
(i.e., programmable) can be written in this formalism. Its syntax
is too limited to make its use as a programming language practical, so
primitive values (such as integers or character
strings), operations on these primitive values, control structures, and
declarations which allow the naming of values or functions and, in
particular, recursive functions, have all been added to the
l-calculus to make it more palatable.
There are several classifications of functional languages. For our part,
we will distinguish them according to two characteristics which seem to us
most salient:
-
Without side effects (pure) or with side effects (impure):
a pure functional language is a language in which there is no change of
state. There everything is simply a computation and the way
it is carried out is unimportant. Impure functional languages, such
as Lisp or ML, integrate imperative traits such as change of state.
They permit the writing of algorithms in a style closer to languages like
Fortran, where the order of evaluation of expressions is significant.
- Dynamically typed or statically typed:
typing permits verification of whether an argument passed to a function is
indeed of the type of the function's formal parameter. This
verification can be made during program execution. In that case this
verification is called dynamic typing. If type errors occur the
program will halt in a consistent state. This is the case in the language
Lisp. This verification can also be done before program execution, that
is, at compilation time. This a priori verification is called
static typing. Having been carried out once and for all, it won't
slow down program execution. This is the case in the ML language and its
dialects such as Objective CAML. Only correctly typed programs, i.e., those
accepted by the type verifier, will be able to be compiled and then
executed.