2. Some Fundamental Notions
In this section a number of notions will be introduced, because they are fundamental to the whole activity of programming. They are so fundamental that they will not be dissected into more primitive concepts. As a result, this section will be a very informal one, analogy, metaphor and natural language (poetry, if I were able!) being the only available vehicles to convey their contents and connotations.
It is not unusual —although a mistake— to consider the programmer's task to be the production of programs. (One finds terms such as "software manufacturing", proposals to measure programmer productivity by the number of lines of code produced per month etc., although I have never seen the suggestion to measure composer productivity by the number of notes, monthly scribbled on his score!) This mistake may be at the heart of the management failure which is so apparent in many large software efforts. It is a mistake because the true subject matter of the programmer's activity is not the program he composes, but the class of possible computations that may be evoked by it, the "production" of which he delegates to the machine. It seems more fruitful to describe the programmer's activity as "designing a class of computations", rather than as "making a program". In this connection it should be borne in mind that the more relevant assertions about programs —e.g. about the correctness of their resource demands— indeed pertain to the computations, rather than to the last thing that leaves the programmer's hands, viz. the program text. It is for this reason that, when introducing fundamental notions, I will start at the side of the computations, with the "happenings in time".
The first notion is that of an action. An action is a happening, taking place in a finite period of time and establishing a well-defined, intended net effect. In this description, we have included the requirement that the action's should be "intended", thereby stressing the purposefulness. If we are interested in action at all, it will be by virtue of its net effect.
The requirement that the action should take place in a finite period of time is most essential: it implies that we can talk about the moment T0, when the action begins, and the later moment T1, when the action ends. We assume that the net effect of the action can be described by comparing "the state at moment T0" with the "state at moment T1".
An example of an action would be a housewife peeling the potatoes for the evening dinner. The net effect is that the potatoes for the evening dinner are at moment T0 still unpeeled, say in the potato basket in the cellar, while at moment T1 they will be peeled and, say, in the pan they are to be cooked in.
When we dissect such a happening as a time sequence of (sub)actions, the cumulative effect of which then equals the net effect of the total happening, then we say that we regard the happening as a sequential process, or process for short.
Whenever such a dissection is permissible, we can regard the same happening either as an action, or as a sequential process. When our interest is confined to the net effect, to the states "before and after", then we regard it as an action. If, however, we are interested in one or more intermediate states as well, then we regard it as a process. In the latter case the moment T0 coincides with the beginning of the first subaction and the end of each subaction coincides with the beginning of the next one, with the exception of the last subaction, whose end coincides with T1, the end of the whole happening.
I must stress, that whether some happening is regarded as an action or as a process is not so much an inherent property of the happening as an expression of our mood, of the way in which we prefer to look at it. (Why we should want to look at it in different ways will be left for later discussion.) Similarly, if we have chosen to regard the happening as a process, the way in which it has been dissected is also not so much an inherent property of the happening as a result of which of its distinguishable intermediate states (for some reason or another) we wish to take into consideration.
The happening of the potato-peeling housewife could, for instance, be described by the time-succession of the following subactions of the housewife:
"fetches the basket from the cellar;
fetches the pan from the cupboard;
peels the potatoes;
returns the basket to the cellar" .
Here the total happening has been described as a time-succession of four subactions. In order to stress that we have given the description of a happening, we have phrased it in the form of an eye-witness account. Note, that if the eye-witness did not bother to describe that the basket was fetched from the cellar before the pan was fetched from the cupboard, the first two lines would have been condensed into a single subaction "fetches the basket from the cellar and the pan from the cupboard".
We postulate that in each happening we can recognize a pattern of behaviour, or pattern for short; the happening occurs when this pattern is followed. The net effect of the happening is fully determined by the pattern and (possibly) by the initial state (i.e. the state at moment T0). Different happenings may follow the same pattern; if these happenings establish different net effects, the net effect must have been dependent on the initial state as well, and the corresponding initial states must have been different.
How we can recognize the same pattern in different happenings falls outside the scope of this text. If we meet a friend, we can recognize his face, no matter what facial expression he shows: it may be an expression we have never seen on is face before! Similarly with different happenings: we recognize the same pattern, abstracting from the possibly different initial states and net effects.
We return for a moment to the housewife. On a certain day she has peeled the potatoes for the evening dinner and we have an eye-witness account of this happening. The next day, again, she peels the potatoes for the evening dinner and the second happening gives rise to an eye-witness account equal to the previous one. Can we say, without further ado: "Obviously, the two accounts are equal to each other for on both occasions, she has done exactly the same thing."?
How correct or incorrect this last statement is depends on what we mean by "doing the same thing". We must be careful not to make the mistake of the journalist who, covering a marriage ceremony, reported that the four bridesmaids wore the same dress. What he meant to say was that the four dresses were made from material of the same design and —apart from possible differences in size— according to the same pattern.
The two actions of the housewife are as different from each other as the dresses are: they have, as happenings, at least a different identity: one took place yesterday, one today. As each potato can only be peeled once, the potatoes involved in the two happenings have different identities as well; the first time the basket may have been fuller than the second time; the number of potatoes peeled may differ, etc.
Yet the two happenings are so similar that the same eye-witness account is accepted as adequate for both occasions and that we are willing to apply the same name to both actions (e.g. "peeling the potatoes for the evening dinner").
An algorithm is the description of a pattern of behaviour, expressed in terms of a well-understood, finite repertoire of named (so-called "primitive") actions of which it is assumed a priori that they can be done (i.e. can be caused to happen).
In writing down an algorithm, we start by considering the happening to take place as a process, dissected into a sequence of subactions to be done in succession. If such a subaction occurs in the well-understood, finite repertoire of named actions, the algorithm refers to it by its name. If such a subaction does not occur in the finite repertoire, the algorithm eventually refers to it by means of a subalgorithm in which the subaction, in its turn, is regarded as a process, etc. until at the end all has been reduced to actions from the well-understood, finite repertoire.
The notion of an algorithm, of an executable precept for the establishing of a certain net effect, is very well known from daily life: knitting patterns, directions for use, recipes and musical scores are all algorithms. And if one asks the way to the railway station in an unfamiliar town, one asks essentially for an algorithm, for the description of a pattern of behaviour which, when followed, will lead to the desired goal.
In our definition of an algorithm we have stressed that the primitive actions should be executable, that they should be done. "Go to the other side of the square." is perfectly acceptable, "Go to hell.", however, is not an algorithm but a curse, because it cannot be done.
Besides that we have stressed that the repertoire should be well-understood: between the one who composed the algorithm and the one who intends to follow it there should be no misunderstanding about this repertoire. (In this respect knitting patterns are, as a rule, excellent, recipes are of moderate quality while the instructions one gets when asking the way are usually incredibly bad!) How essential this lack of understanding is may perhaps best be demonstrated by a recipe for jugged hare as it occurs in an old Dutch cookery-book; translated into English the recipe runs as follows: "One taketh a hare and prepareth jugged hare from it.". The recipe is not exactly wrong, but it is hardly helpful!
Let us now contrast the eye-witness account of the potato peeling session:
"fetches the basket from the cellar;
fetches the pan from the cupboard;
peels the potatoes;
returns the basket to the cellar"
with the corresponding algorithm —the set of instructions, say, the housewife might give to a new maid—:
"fetch the basket from the cellar;
fetch the pan from the cupboard;
peel the potatoes;
return the basket to the cellar" .
Comparing the two, we may well ask what we have gained, for it seems a roundabout way of doing things: describing a pattern of behaviour which, when followed, will evoke the happening, while in the eye-witness account we had an excellent way of describing the happening itself.
What have we gained? Well, nothing as long as we restrict ourselves to algorithms that can be given —as in our example— by a concatenation of names of actions, to be done in the given order. Under that restriction an eye-witness account of the actions "as they take place" is equally good. But the behaviour of the housewife (or the maid) could be a little bit more complicated: let us suppose that after the pan had been fetched, she puts on an apron if necessary, i.e. when she wears a light-coloured skirt and that on one day she uses the apron while on the other day she doesn't.
On a rather abstract level —i.e. without explicit mentioning of the apron and the condition under which it is used, a uniform eye-witness account would still do (in some fashion) for both sessions, e.g.:
"fetches the basket from the cellar;
fetches the pan from the cupboard;
takes preparation with regard to clothing;
peels the potatoes;
returns the basket to the cellar"
with the implicit understanding that "takes preparation with regard to clothing" covers the empty action when her skirt is not light-coloured and covers putting on an apron when her skirt is light-coloured.
If, however, we want to go into more detail and want to mention the apron explicitly, then "takes preparation with regard to clothing" has to be replaced in the eye-witness account of the one day's session by
"sees that her skirt is light-coloured and therefore puts on an apron"
and in the other day's session by
"sees that her skirt is not light-coloured and therefore omits putting on an apron" .
The trouble is, that the eye-witness account cannot contain the single sentence:
"puts on an apron if her skirt is light-coloured"
for then the audience justly asks "does she do it or not?". In other words: in that degree of details we cannot cover the two happenings by the same eye-witness account, for in that degree of detail the two happenings differ!
It is here that the potential power of the algorithm becomes apparent, for we can recognize the same pattern of behaviour in the two happenings and by describing that pattern of behaviour we give something that is applicable under both circumstances, light- as well as dark-coloured skirt. This is possible thanks to the fact that what actually happens when a certain pattern of behaviour is followed may be co-determined by the state of affairs which is current when the action begins.
We see two things: the inspection of whether the skirt is light-coloured or not and, depending on the outcome of this inspection, the action "put on an apron" is to take place or not. In order to express this conditional execution we need in our algorithm another connective besides the semicolon. In our example of the algorithm (I refer to the instructions to the new maid) the semicolon had a double function: in the text it separates one action name from the next action name, but besides that it implied for the happening a certain amount of what is technically called "sequencing control", i.e. it was meant to imply that the end moment of the preceding action should co-incide with the beginning of the following action. We now need another connective, indicating whether or not the inspection should be followed by the next action in the text. We write for instance the following algorithm:
"fetch the basket from the cellar;
fetch the pan from the cupboard;
if skirt is light-coloured do put on an apron;
peel the potatoes;
return the basket to the cellar" .
(for historical reasons the so-called conditional connective "if...do" is split into two symbols "if" and "do", enclosing the inspection.)
The conditional connective connects two actions, the first of which must be a so-called "inspection". This inspection describes a state of affairs, which may be true or false ("false" is the technical term for "not true"). The happening which is to take place corresponding to the conditional compound
"if inspection do action"
may take one of two mutually exclusive forms: either the inspection gives the result true and it is followed by the action, or the inspection delivers the result false and thereby the whole compound action has been completed. The algorithm derives its superiority over the eye-witness account from the fact that it may contain connectives (such as the conditional connective) that imply a more elaborate sequencing control than the semicolon.
We need a further connective before we can see the full superiority of the algorithm over the eye-witness account, viz. a repetitive connective.
Suppose that we want to express that "peeling the potatoes" is in itself a process that deals with one potato at a time and that, correspondingly, our primitive action is named "peel a next potato". If the number of potatoes to be peeled is a fixed constant, say always 25, then we can replace "peel the potatoes" by 25 times "peel a next potato", separated from each other by in toto 24 semicolons. But we now assume that the number of potatoes to be peeled may differ from one day to the next; yet we want to recognize in each peeling session the same pattern of behaviour. We suppose the housewife capable of looking into the pan and judging whether the amount of peeled potatoes is sufficient or not.
If we know a priori that in the worst case (i.e. many guests and very small potatoes) she will never have to peel more than 500 potatoes, we can give a general algorithm describing the actual peeling by repeating in the text of our algorithm 500 times (separated by in toto 499 semicolons) the conditional compound:
if number of peeled potatoes is insufficient do peel a next potato" .
Several objections can be made to this solution. There is the practical objection that it would reduce the construction of algorithms to doing lines. Furthermore we had to make the fundamental assumption that we know in advance a maximum number. Often it is very hard to give such an upper bound a priori and if it can be given, such an upper bound is usually many times larger than the average value. And if in actual fact 25 potatoes have to be peeled, the 26th inspection "number of peeled potatoes insufficient" —i.e. the first to deliver the result "false"— gives fresh information, the following 474 inspections (which are prescribed by the algorithm as suggested) give no new information. Once the housewife has established that the number of peeled potatoes is no longer insufficient, she should not be forced to look into the pan another 474 times in order to convince herself!
In order to meet these objections, we introduce a repetitive connective which, again for historical reasons, is written in two parts "while...do". Using this connective we can write the algorithm:
"fetch the basket from the cellar;
fetch the pan from the cupboard;
if skirt is light-coloured do put on an apron;
while number of peeled potatoes is insufficient do
peel a next potato;
return the basket to the cellar" .
The process corresponding to
"while inspection do action"
consists of one or more executions of the conditional compound
"if inspection do action"
viz. up to and including the first time that the inspections gives the result "false".
We can also describe the semantics of the repetitive connective in terms of the conditional one recursively:
"while inspection do action"
is semantically equivalent to
"if inspection do
begin action; while inspection do action end"
Here the symbols "begin" and "end" are used as opening and closing bracket respectively; they are a syntactical device to indicate that the conditional connective connects the inspection (from the first line) to the whole of the second line: the value delivered by the first inspection decides whether what is described on the second line (from begin until end) will be done in its entirety or will be skipped in its entirety.
Note. In the above I have approached the idea of an algorithm starting my considerations from the class of happenings in which we wanted to discern the same pattern of behavior. In addition to the semicolon as connective in the text of the algorithm this led to other connectives such as the conditional connective "if...do" and the repetitive connective "while...do". It is not unusual to approach the relation between algorithm and computations from the side of the algorithm; such an approach leads in a very early stage to syntactical considerations, as a result of which the connectives are introduced in a somewhat different terminology. Instead of
"if inspection do action"
people write
"if condition do statement" .
The part of the text denoted by "if condition do" is then described as "conditional clause" which is regarded as a prefix attached to the "statement", the whole construction comprising clause and statement together is then called "a conditional statement". Similarly, in
"while condition do statement" ,
"while condition do" is called "a repetitive clause" and the statement is called "the repeatable statement". This terminology is so widely used that —in spite of its syntactical origin— I shall not refrain from using it whenever I see fit to do so.
As a final exercise I shall describe the pattern of behaviour of a housewife who —for some obscure reason— is so conditioned that she can only peel an even number of potatoes for the evening dinner:
"fetch the basket from the cellar;
fetch the pan from the cupboard;
if skirt is light-coloured do put on an apron;
while number of peeled potatoes is insufficient do
begin peel a next potato; peel a next potato end;
return the basket to the cellar" .
This example is included to show that the same set of primitive actions allows different patterns of behaviour.
The notion of an algorithm is a very powerful one, for a single algorithm "extracts" what a large number of different happenings may have in common. And it does not do so by ignoring details, on the contrary, a single algorithm covers a whole class of happenings to the very degree of detail in which the corresponding eye-witness accounts would differ from each other. The possible large number of different corresponding happenings is generated by the different ways of sequencing as might be controlled by the conditional, the repetitive (and similar, see later) connectives.
On the one hand we have the algorithm, a finite text, a timeless, static concept; on the other hand we have the corresponding happenings that may be evoked by it, dynamic concepts, happenings evolving in time. The intimate relation between the two —to which we refer by the term "sequencing"— lies at the heart of the algorithmic notion. (It is to this intimate relation that I refer whenever I stress that the programmer's true activity is "The design of classes of computations".) The notion of an algorithm is admittedly a very powerful one; before going on, however, I shall allow myself a little detour in order to indicate what "price" we have paid for its introduction.
We have stated that we restrict ourselves to happenings taking place in a finite period of time. Whenever an algorithm is followed, a happening is taking place, eventually as a time-succession of primitive actions. It is only realistic to postulate that each primitive action will take a finite period of time, unequal to zero: no action will take place "infinitely fast". This implies that we confine our attention to happenings that are taking place as a time-succession of a finite number of primitive actions.
And now we are beginning to see the price: it is very easy to write down a text that looks like an algorithm but that is not an algorithm in our sense of the word, because the effort to follow it turns out to be a never-ending task, e.g.
"while skirt is light-coloured do peel a next potato" .
When we assume that the peeling of a next potato does not influence the colour of the skirt, we have just two cases: either the shirt is not light-coloured and the only action taking place is the inspection establishing this fact, or the skirt is light-coloured and will remain so and what the pattern could be interpreted to describe is the peeling of an infinite number of next potatoes. This is usually called "an improper algorithm".
The question of whether a text that looks like an algorithm is indeed a proper algorithm or not, is far from trivial. As a matter of fact Alan M. Turing has proved that there cannot exist an algorithm capable of inspecting any text and establishing whether it is a proper algorithm or not. The assumption if the existence of such an algorithm leads to a contradiction which will be sketched below. Suppose that we have such an algotithm, an inspection
"proper(L)"
which delivers the result true when the text named L is a proper algorithm and the result false when it is improper. Consider now the following text, named L:
L: "while proper(L) do whistle once"
(in which "whistle once" is assumed to be an available primitive). If we start to follow this algorithm, how many times will a whistle sound? The assumption that "proper(L)" delivers the result true will cause the algorithm to be improper and vice versa! The conclusion is that no algorithm for the inspection "proper" can exist. (Marvin Minsky concludes in "Computation, Finite and Infinite Machines", Prentice Hall, 1967 a formal treatment of this proof with the sentence: "We have only the deepest sympathy for those readers who have not encountered this type of simple yet mind-boggling argument before.".)
The moral of this story is that it is an intrinsic part of the duty of everyone who professes to compose algorithms to supply a proof that his text indeed represents a proper algorithm.
Our next fundamental notion is a machine (or a "computer"). A machine is a mechanism capable of causing actions to take place following a pattern of behaviour such as can be described by algorithms expressed in terms of a repertoire of primitive actions belonging to this machine.
Above we have given two algorithms for peeling potatoes, one for a natural number of potatoes and one only for even numbers of potatoes. Both algorithms have been expressed in the same repertoire of primitive actions. They were introduced in the realm of "observing happenings"; the one could describe the pattern of behaviour of my left-hand neighbour, the other the one of my right-hand neighbour. Suppose that my own wife
| 1) | is also capable of performing those primitive actions |
| 2) | will accept from me algorithms expressed in these primitives and will follow such an algorithm obediently. |
Then I can make her peel either as my left-hand neighbour or as my right-hand neighbour, depending on the algorithm I have supplied to her. Then she is an example of a machine.
A mechanism that can do only one thing (such as one of the most widely-spread automata, the toilet flusher), is not called a machine. Essential for us is the associated repertoire of actions, the ability to accept patterns if behaviour and to behave accordingly.
Machines are mechanical algorithm followers. The fact that in the last decennia increasingly powerful machines have become available to mankind is directly responsible for the increased importance of and interest in algorithms and their composition.
Note. It is a trivial matter to compose an algorithm for the fastest machine in the world, a proper algorithm in the theoretical sense of the word but somewhat impractical, as it would take the machine a million years to carry out the corresponding process to completion. The claim that "the machine is capable of causing the process to take place" is then somewhat subject to doubt: in actual fact it cannot. In what follows we shalln't be bothered by the distinction between "theoretically possible" and "practically feasible". Not because we are impractical, on the contrary! The point is that in the meantime computers are so powerful that the class of practically feasible computations is by now sufficiently large —to put it mildly!— to make machines very useful and intriguing pieces of equipment, fully worthy of our attention.
We call an algorithm intended to control the behaviour of a machine, a program. In other words, we reserve the name program for those algorithms that are intended for mechanical execution. In the general notion of an algorithm we have only required that the repertoire should be "well-understood", without bothering how this understanding is established: if a composer indicates "Andante" (= "going") for a composition in three-four time, he may do so, because, remarkably enough, we may expect this indication to be somehow meaningful even for a player with two legs. In the case of a machine, the situation is drastically different, for a machine is a finite piece of equipment which, by its very construction, has associated with it a finite, very well defined repertoire and whenever it is fed with a program it shall behave exactly as prescribed.
The fact that machines are completely obedient slaves has caused complaints from many beginning programmers. Their obedience, they felt, makes programming cruelly difficult, for a trivial mistake in the program is sure to lead to entirely unintended behaviour. The programmer's inability to appeal to "the common sense of the machine" has been experienced as one of its major shortcomings. The more experienced programmer learns to appreciate its servile, strict obedience; thanks to it we can instruct it to do something "uncommon"! And this is something you cannot do with a servant who "rounds off" his instructions to the nearest probable interpretation.
In the preceding paragraphs I have introduced programming as an important activity because now we have machines that can be controlled by programs and for which we have to compose programs when we want to use them, i.e. when we want to convert them into the tool solving our problem. But this is not the whole story. A computer is a many-sided thing. For its manufacturer it is primarily a product that he can (hopefully) produce and sell with profit. For many institutional buyers the computer is probably primarily a status symbol. For many years it is either a source of endless worries or, as the case may be, a highly useful tool. In University surroundings, the view of the computer as a tool to be used tends to be the predominant one. And there is no denying it: in their capacity of tools the computers are changing the face of the earth (and of the moon as well!). Yet I am convinced that we underestimate the computer's significance if we confine our appreciation of it to the aspects mentioned. They may cause shocks to the basis of our society, but I believe in the longer run these will turn out to be but ripples on the surface of our culture. I expect a much more profound influence from the advent of the modern computer, viz. in its capacity of a gigantic intellectual challenge, unprecedented in the history of mankind.
The computer as a piece of equipment presents us with an entirely new combination of simplicity and power, which makes the programming task a unique challenge. When the electronic engineers have done their job properly, they present to the programmer a mathematically trivial piece of equipment. Its instruction code (its "repertoire") can be described perfectly well on a modest number of pages, everything is finite and discrete, there is just no place for conceptually difficult mathematical notions, such as continuity, infinity, limits, irrational numbers and whatnots. The mathematical basis of programming is just very, very simple. So simple that programming should be easy: it should be easy to conceive programs, it should be easy to convince oneself that a program is correct and that the machine working under its control will indeed produce the desired result. From its basic simplicity one derives the intuitive feeling that it should be a trivial matter to keep the happening evoked by one's program firmly within one's intellectual grip.
But its basic simplicity is only one side of the coin: the other side presents the extreme power (both as regards capacity and speed) of currently available computers. As a result of its extreme power, both the amount of information playing a role in the computations as well as the number of operations performed in the course of a computation, escape our unaided imagination by several orders of magnitude. Due to the limited size of our skull we are absolutely unable to visualize to any appreciable degree of detail what we are going to set in motion, and programming thereby comes an activity facing us with conceptual problems that have risen far, far above the original level of triviality.
It is the possibility of considering realistically effective solutions of any degree of sophistication, combined with our complete intellectual grip on what we are considering, which will deeply influence our ways of thinking and our appreciation of our own thought processes. It has no precedent, for whenever in the past we were faced with something powerful (a storm or an army) we never had effective control over it. (This for a long time, used to be the definition of "powerful", viz. that we were "powerless" in the face of it!)
Next chapter: 3. Programming Languages and their Implementation