WRITING STRUCTURED PROGRAMS

Since most of the SPARKS programs will be read many more times than

they will be executed, we have tried to make our code readable. This is a

goal which should be aimed at by everyone who writes programs. The SPARKS

language is rich enough so that one can create a good looking program by

applying some simple rules of style. Some of the commonly accepted rules

of style are:

(i)

Every procedure should carefully specify its input and output variables.

(ii)

(iii)

(iv)

(v)

(vi)

The meaning of all local variables should be defined.

The flow of the program should generally be forward except for

normal looping or unavoidable instances.

Indentation rules should be established and fol!owed so that com

putational units of program text can more easily be identified.

Documentation should be short, but meaningful. Avoid comments

like "i is increased by one."

Use subroutines where appropriate.

See the book The Elements of Programming Style by Kernighan and Plauger

(McGraw-Hill) for more examples of good rules of programming.

Which iteration statement to use

Since SPARKS contains four different ways for getting a set of statements

to be repeatedly executed, it is natural to ask under what circumstances

we prefer to use one way rather than another. The four iteration statements

are the (i) loop-repeat, (ii) while-repeat, (iii) loop-until-repeat, and (iv)

for-repeat. Suppose we want to read a set of values until their sum exceeds

a predefined limit, say n. This would naturally be expressed using the while
loop as:

y-0

while y ::5 n do

read(x)

y -y + x

repeat

Wridng structured programs

15

On the other hand suppose we want to read in n values and process each

one in some way. Using the while loop we might write:

i-1

while i :s n do

read(x)

call PROCESS(x)

i-i+1

repeat

But in this case it is preferable to employ a for loop, as for example

for i - 1 to n do

read(x)

callPROCESS(x)

repeat

The reason for favoring the for loop in this context is not so much because

we save two statements (i - 1 and i - i + 1) but because the number of

iterations was fixed by n and independent of the data being read. When

we know exactly how many times we want to iterate a group of statements

then the for statement should be used. When we want to iterate some state

ments until a certain condition becomes true or false then the while loop is

favored.

Now suppose we want to read a set of values and process them until we

read an end-of-file marker. Using the while loop we can express this as:

read(x)
while x #- eof do

call PROCESS(x)

read(x)

repeat

However a better way would be using the loop-repeat:

loop

read(x)

if x = eof then exit endif

call PROCESS(x)

repeat

16

Introducdon

Now we have only one occurrence of the read statement which may prove

useful if we have to modify this program segment. In fact suppose we now

want to modify this program to test the result of call PROCESS(x), say

PROCESS(xJI) and terminate processing if y = 0. Then the loop-until

repeat can be fruitfully used:

loop

read(x)

if x = eof then exit endif

call PROCESS(x,y)

until y = 0 repeat

if x #- eofthen ...

The Case for CASE

There are two statements in SP ARKS for discriminating between alter

natives: the if-then-else and the case. We could have gotten by with either

one of these statements since we can simulate the case, as defined in Figure

1.3, using the nested sequence of if-then-else's

if condl then SJ

else if cond2 then S2

else if condJ then SJ

else Sn + 1

endif endif . . . endif

The virtue of the case is that it eliminates the nesting of alternatives and

brings the conditions out to the same level. The amount of syntax is reduced

if many conditions are involved and the resulting program segment is easier

to read.

Functions versus Subroutines

Most programming languages including SP ARKS permit the definition

of both functions and subroutines. But very few language primers discuss

when one is preferable to the other. Before we can get close to answering

this question, let us first reconsider the way variables get used in a proce

dure. In section 1.2 we noted that variables could be classified as either

local, global, or parameter. There is another three category classification

that pertains only to parameters and global variables. In one instance a

variable may carry a value in to a procedure, but it remains unchanged ------------------~-----~----

Writing structured programs

17

throughout execution. A second possibility is that a variable is undefined

upon entry but it is assigned a value which is carried out when the proce

dure ends. The third possibility is a variable which both brings a value in

and (a possibly changed value) out. A language designer might even go

so far as to insist that a programmer declare his variables in this way, as

to whether they are in, out, or inout as this adds another measure of relia

bility. However we will refrain from adding this declaration feature to

SPARKS, at least for now.

The reason for introducing these categories is to help us understand the

notion of side effect. The words subroutine or pure procedure are used to

denote a procedure which returns no function value but may alter either its

parameters or global variables or both. A procedure which does alter one

of its parameters or global variables is said to have a side effect. This is

Pure procedures work solely through side effects. A procedure which is a

function may also have side effects. But in the interests of reliability SPARKS

insists that one uses either functions without side effects or pure proce

dures.

In general we write a function when the value it returns will be used once

in an expression. For example if we needed a procedure to determine

whether two trees are equal we should create a function, say EQUAL(S, T),

which returns either true or false (a Boolean function). Then in a program

we could say

[Link](S,T) then ...

Or we might create a function for computing the greatest common divisor

and use it in the assignment

z - x *ylgcd(x,y)

However if we need the gcd(x,y) more than once we can either assign its

value to a variable (t - gcd(x,y)) or we can make it a subroutine with a

side effect (callgcd(x,y,t)).

Recursion

Recursion is a powerful programming technique which unfortunately is

not employed to the extent it should. There are at least two reasons for this.

One is the fact that FORTRAN does not permit recursion. Thousands of

people who have learned the art of programming using FORTRAN have

thus been unable to experience its benefits. Two is the fact that there is

18

Introducdon

often a heavy penalty in terms of execution time when one uses recursion

on some compilers. We shall be running some experiments later to see if

we can quantify this penalty.

Let's take a look at some examples, both good and bad, which make use

of recursion.

Example 1.1 The Fibonacci sequence l,1,2,3,S,8,l3,21,34, ... is defined

Fo = 0, Fi = 1, F; = F;-1 + F;-2, i >

This mathematical definition might naturally lead to the recursive SPARKS

procedure:

procedure F(n)

I !returns the nth Fibonacci number! I

integern

ifn :s 1 thenretum(n)

else retum(F(n - 1) + F(n - 2))

endif

endF

Algorithm 1.2 Fibonacci numbers

The virtue of this program is that it is almost syntactically identical to

the mathematical definition. However it is atrociously inefficient from the

standpoint of computing time. But the major source of the inefficiency

does not arise because recursion is used. Rather it is because of the way

the computation proceeds. Many values are recomputed many times; for

example F(n - 2) is computed twice, F(n - 3) is computed three times,

and F(n - 4) is computed five times. Other recursive versions can be con

structed which are far more efficient (see the exercises).

Example 1.2 Perhaps the oldest recorded nontrivial algorithm is due to

Euclid. This algorithm is for computing the greatest common divisor of

two nonnegative integers. The essential step which guarantees the validity

of his method consists of showing that the greatest common divisor of a and

b (a > b =:::: 0) is equal to a if b is zero and is equal to the greatest common

divisor of band the remainder of a divided by b if bis nonzero. For exam

ple:

Writing structured programs

gcd(22,8) = gcd(8,6) = gcd(6,2) = gcd(2,0) = 2

and

gcd(21,13) = gcd(13,8) = gcd(S,S) = gcd(S,3) = gcd(3,2) = gcd(2,1)

Expressing this process as a recursive procedure one gets

procedure GCD(a,b)

I I assume a > b <::: 0/ I

if b = 0 then retum(a)

else retum(GCD(b, a mod b))

endif

endGCD

Algorithm 1.3 Greatest common divisor

19

Example 1.3 One often gets the mistaken impression that recursion is

only appropriate for computing "mathematical" functions. Here is a pro

cedure which searches for x in A(l:n).

procedure SEARCH(i)

I /if there exists an index k such that A (k) = x in A (i: n )/I

I !then the first such k is returned else zero is returned.I I

global n,x,A(l:n)

case

: i > n : retum(O)

: A (i) = x : retum(i)

: else : retum(SEARCH (i + 1))

end case

end SEARCH