A functional model of computation

In this chapter we will introduce the basics of a functional model of computation. The functional model is very close to mathematics; hence functional algorithms are easy to analyze in terms of correctness and efficiency. We will use the ML interactive environment to write and execute functional programs. This will provide an interactive mode of development and testing of our early algorithms. In the later chapters we will see how a functional algorithm can serve as a specification for development of algorithms in other models of computation.

In the functional model of computation every problem is viewed as an evaluation of a function. The solution to a given problem is specified by a complete and unambiguous functional description. Every reasonable model of computation must have the following facilities:

Primitive expressions

which represent the simplest objects with which the model is concerned.

Methods of combination

which specify how the primitive expressions can be combined with one another to obtain compound expressions.

Methods of abstraction

which specify how compound objects can be named and manipulated as units.

In what follows we introduce the following features of our functional model:

1. The Primitive expressions.
2. Definition of one function in terms of another (substitution).
3. Definition of functions using conditionals.
4. Inductive definition of functions.

We will introduce the more advanced concepts in our functional model later in these notes.