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 standard . 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. The line 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 programs.

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 money itself.

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 much harder. It is also possible to write programs in ML which defy logic - just much harder. 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 machines.

Summary

We compare Formal Methods and Functional Programming with some traditional Imperative 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 measurable way. 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 code. 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 memory. 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.