GIML: Introduction to Functional Programming
The functional language community
The functional language community is excessively dour. The functional
ascetics forbid themselves facilities which less pious programmers regard as
When using functional languages we do away with notions such as variables and
reassignments. This allows us to define programs which may be subjected to
analysis much more easily. When a value is assigned it does not change during
the execution of the program. This property is referential transparency.
There is no state corresponding to the global
variables of a traditional
language or the instances of objects in an object oriented language. When a
definition is made it sticks.
Reassignment does not take place. Getting used to this and finding alternatives
the traditional structures such as loops which require reassignment is one of
the hardest tasks for a programmer "converting" from a traditional language.
x := x+1;
may appear in a 3rd generation language and is understood to indicate
that 'box' or 'location' referred to as 'x' has its contents incremented
at this stage. We do not admit such concepts. 'x' is 'x' and 'x+1' is one
more than x; the one may not be changed into the other. A program without
a state is a simpler thing - it is easier to write the code and easier
to reason about the code once written. It is harder to write poor code.
Functional languages are considered, by their devotees, to be higher
level than third generation languages. Functional languages are regarded
as declarative rather than imperative. Ordinary third generation languages
such as Pascal, C (including flavours such as C++) and assembly instruct
the computer on how to solve a problem. A declarative language is one
which the programmer declares what the problem is; the execution of
the program is a low level concern. This is an attitude shared with
the logic language community (Prolog people).
Towards Correct Programs
There has been a great deal of progress in recent years in defining
methodologies and design techniques which allow programs to be constructed
more reliably. Some would claim that object orientation for example builds
on and improves on structured programming which undoubtedly contributes to
a better process of software construction. Using a rational methodology
software engineers can produce better code faster - this is to be applauded,
however it does not bring us any closer to the goal of correct programs.
A correct program is not just more reliable - it is reliable. It does
not just rarely go wrong - it cannot go wrong. The correct program should
be the philosophers stone for the programmer, the pole star of our efforts.
Software engineering may allow the intellectual effort of the programmer to be
used "more efficiently" however it does not necessarily give us accurate
Away from testing
Testing is usually regarded as an important stage of the software
development cycle. Testing will never be a substitute for reasoning.
Testing may not be used as evidence of correctness for any but the most
trivial of programs. Software engineers some times refer to "exhaustive"
testing when in fact they mean "exhausting" testing. Tests are almost never
exhaustive. Having lots of tests which give the right results may be
reassuring but it can never be convincing.
Rather than relying on testing we should be relying in reasoning. We should
be relying on arguments which can convince the reader using logic.
The benefits and costs of correct programs
If correct programs were cheap and easy then we would all use them. In
fact the intellectual effort involved in proving the correctness of even the
simplest of programs is immense. However the potential benefits of a cast
iron guarantee on a program would be attractive in many situations.
Certainly in the field of "safety-critical" systems formal methods may have
a role to play. It must however be admitted that the safety of many such systems
cannot be ensured by software - no amount of mathematics is going to make a
weapons system or a complex chemical plant safe.
Formal methods may have a useful part to play in systems where there is a
high cost of failure - examples such as power stations, air traffic control
and military systems come to mind. The cost of failure in any of these cases
may be in terms of human life. The really important market for such
systems is in fact in financial systems where the cost of failure is
Why functional programming
Functional languages such as ML, Hope and Lisp allow us to develop
programs which will submit logical analysis relatively easily. Using a
functional language we can make assertions about programs and prove these
assertions to be correct.
It is possible to do the same for traditional, imperative programs - just
It is also possible to write programs in ML which defy logic - just much
A functional language like ML offers all of the features that we have come to
expect from a modern programming language. Objects may be packaged with
details hidden. Input and output tend to be rather more primitive then
we might expect, however there are packages which allow ML to interface
with front ends such as X-windows.
Functional languages are particularly well suited to parallel processing -
several research projects have demonstrated superior performance on parallel
We compare Formal Methods and Functional Programming with some
Programming and traditional software engineering:
|Imperative Programming & Traditional Software Engineering
||Functional Programming & Formal Methods
|The Development Cycle
||Using informal language a specification may be open to interpretation.
Using appropriate testing strategies we can improve confidence - but not in any
Mistakes/bugs are common and difficult to spot and correct.
|Using logic we can state the specification exactly.
Using mathematics we may be able to prove useful properties of our programs.
Mistakes/bugs are common and difficult to spot and correct.
|The Development Language
||Using structured programming or object oriented techniques we can reuse
Using structured programming or object orientation we can partition the problem
into more manageable chunks.
||Using structured programming or object oriented techniques we can reuse code.
We can partition the problem into easy to use chunks - plus there are often
"higher-level" abstractions which can be made ML which would be difficult or
impossible in a traditional language.
|The Run-time System
||The compiler can produce fast compact code taking a fixed amount of
Parallel processing is not possible (in general).
Fancy GUI's may be added.
Code is usually interpreted, the memory requirements are large and unpredicatable.
Parallel processing is possible.
Fancy GUI's may be added, with difficulty.