Bob's Corner  / Programming  
Pseudo code
Home Issues Pseudo code Publications People

Typical programming constructs

We show some typical programming constructs, using only pseudo code, by designing / sketching a few small programs.

Basic Elements

We start of with a very typical program that is commonly used in books on programming languages (it takes after the program from the book The C Programming Language, but the first version is probably older). 

write 'Hello, World!'
which only outputs the text 
Hello, World!
The write instruction is our very own version for output that can be implemented by a version in a typical programming language (or one that is provided by a library for that particular programming language). We expect this instruction to write a line of text with everything between quotes that follow this instruction as literal text.
Spacing !!!

We can use this to write a program that outputs the multiplication table for the number 4. 

write '1 x 4 = 4'
write '2 x 4 = 8'
write '3 x 4 = 12'
write '4 x 4 = 16'
write '5 x 4 = 20'
write '6 x 4 = 24'
write '7 x 4 = 28'
write '8 x 4 = 32'
write '9 x 4 = 36'
write '10 x 4 = 40'

Now, instead of giving the results of the multiplication ourselves, we want to calculate these values. 

write '1 x 4 = ' 1*4
write '2 x 4 = ' 2*4
write '3 x 4 = ' 3*4
write '4 x 4 = ' 4*4
write '5 x 4 = ' 5*4
write '6 x 4 = ' 6*4
write '7 x 4 = ' 7*4
write '8 x 4 = ' 8*4
write '9 x 4 = ' 9*4
write '10 x 4 = ' 10*4
We assume that it is possible to calculate arithmetic expressions containing a set of common operations. Furthermore, we changed the instruction write. We expect it to write everything that follows on the same line. The text between quotes must be written as literal text and the rest it must compute.
Note: with most programming languages the arguments that follow the instruction must be separated by a ,, but we have chosen for just some spacing (but the arguments must be on the same line).

Generalization

We generalize this code. We introduce a placeholder i that represent a certain value given by a definition in the form i = .... This placeholder must be replaced everywhere it is used in the code by its definition, except when it appears between quotes. 

i = 1
write i '  x 4 = ' 1*4
i = 2
write i '  x 4 = ' i*4
i = 3
write i '  x 4 = ' i*4
i = 4
write i '  x 4 = ' i*4
i = 5
write i '  x 4 = ' i*4
i = 6
write i '  x 4 = ' i*4
i = 7
write i '  x 4 = ' i*4
i = 8
write i '  x 4 = ' i*4
i = 9
write i '  x 4 = ' i*4
i = 10
write i '  x 4 = ' i*4

We can make use of this generalization to write a shorter program which does the same thing. We introduce a new instruction that does a repetition (loop). 

for i = 1 2 3 4 5 6 7 8 9 10
    write i ' x 4 = ' i*4
The for instruction repeats all the following indented instructions where in each repetition the placeholder gets defined with a particular value.
Note: We use indentation to denote that the instruction is part of another instruction. In most programming languages these must be enclosed by a { } pair or if it is just one instruction no enclosing is necessary. But it is still recommended to use some indentation for readability.

We can generalize this code to write the multiplication table for a particular number. We use the placeholder N for this. 

for i = 1 2 3 4 5 6 7 8 9 10
    write i ' x ' N ' = ' i*N

Abstraction

We can make up our own instructions (which are usually called procedures, functions, or subroutines, in programming languages). In fact, we already did that with the write instruction. We can at a later time program / design the code for this instruction, or perhaps the programming language we are going to use to implement our program has some support for this.

We can also do this for existing code. For instance, we can define the instruction table, like this. 

define table
    for i = 1 2 3 4 5 6 7 8 9 10
	write i ' x ' N ' = ' i*N
And when we use it like this, 
table
it is to be replaced by our code for multiplication tables.

We do not need to know how the code for the our instruction table, and write looks like, but we can still use it.
Note: we only have to know that we have set the placeholder N to the right value before the instruction table and that it uses the placeholder i. So, if we also use the placeholder i elsewhere in our program, it might go wrong.
Later we will see how we can cope with this problem.

Conditionals

Instead of giving a definition for the placholder N for which we like to write a multiplication table, we now ask the user to give a value. We use the command read that we expect to read a value given by the user somehow and that gives the definition for the placeholder that follows the read command. 

read N
table

We can off course run our program for every time we want to write out a multiplication table, but instead we want that our program continues with asking for a value and writing a table. 

read N
table
read N
table
   .
   .
   .

But when to stop. We decide that if the value read is 0, we do not want to continue. We introduce the instruction if expression, that if the expression is true continues with the following indented instructions, and otherwise skips the following indented instructions. 

read N
if N > 0
    table
    read N
    if N > 0
	table
	   .
	   .
	   .
Although our program now is able to stop, it is still infinite. So, we can not even write out the whole program. What we see here is a recursion of part of our program. We introduce a new instruction so that we can write out this program in a finite way. The while expression continues with the indented instructions following it when the expression is true, and skips the indented instruction otherwise. 
read N
while N > 0
    table
    read N

It also possible to combine an if with an else part. 

if expression
    ...
else
    ...
If the expression is true it continues with the following indented instructions and after that skips the else part, and if the expression is false it skips the following indented instructions and continues with the indented instructions after the else.

Scope

If we take a look at our code for printing a mathematical table, we see that it uses a placeholder i in the for-loop. If we use this in a program that also uses a placholder i, the definition of this placeholder has changed after the code for the printing of the table has been performed. To prevent this, we want a different placeholder i in the code for the table. We want to limit the visibility, or scope, of the placeholder i to only the code for the table. Also, we want the definition of another placeholder i from somewhere else in our program unchanged after the code for the table has been performed.

From now on, we expect that the visibility of the placeholders are limited to the part of the code where we introduced them. And when we do want a placeholder to be visible elsewhere that we have to indicate that somehow.

So, the placeholder i for the table is now visible only locally, and it only exists in the code for the table. If there was a placeholder i outside of the code for the table, this placeholder i is not visible in the code for the table.

To indicate that a placeholder is not from the current scope, but from the scope around it, we use the instruction global. So, we have to define our instruction table like this. 

define table
    global N
    for i = 1 2 3 4 5 6 7 8 9 10
	write i ' x ' N ' = ' i*N

Parameters

Although we did not mention it, we have used the instruction of our own with some arguments, as we did with the instructions read and write. Instead of defining the placeholder N with the value we want for printing a table and indicate that we use this placeholder from the outer scope in the definition, we want to do this through an argument for the instruction table.

This is usually done with the use of parameters. In the definition of an instruction with specify the parameters we want our instruction to have and when we use that instruction we provide arguments which are bound to the parameters.

The definition for table becomes 

define table in N
    for i = 1 2 3 4 5 6 7 8 9 10
	write i ' x ' N ' = ' i*N
Which denotes that the instruction now has a placholde N (we can use any other name for this) that is used for input (in) and which is only visible inside this definition. And we can use it like this 
N = 4
table N
or like this 
value = 3
table value
or just this 
table 3

We used here only a parameter for input, but we can use a parameter also for output. For instance 

define add in x in y out sum
    sum = x + y
which we can use like this 
add 3 4 s
a = 4
b = 5
add a b s
We can also use a parameter both as input and as output. 
define addtox inout x in y
    x = x + y
and use it like this 
x = 3
add x 4
y = 5
add x y

Functions

In addition to input and output paramaeters, we can also let an instruction return a specific value, that then can be used in an expression. And if we use only returned values for output, we can leave out the specification of input and output values with the parameters. 

define add x y
    return x + y
and use it like this 
x = 3
z = add x 4
y = 5
x = add x y

Datastructures

Array

Say we have to read 5 numbers and calculate the average of these numbers. We could do it like this. 
total = 0
i = 0
while i < 5
    read N
    i = i + 1
    total = total + N
average = total / 5
But, if we want to use the numbers for other calculations as well, we want to remember them. We could number our placeholders, and do something like this. 
total = 0
read N1
total = total + N1
read N2
total = total + N2
read N3
total = total + N3
read N4
total = total + N4
read N5
total = total + N5
average = total / 5
But for larger amounts of numbers this is not doable. We like to generalize this into something like this. 
total = 0
i = 0
while i < 5
    read Ni
    total = total + Ni
    i = i + 1
average = total / 5
We use an array for this, that can be used like this. 
array N[5]
total = 0
i = 0
while i < 5
    read N[i]
    total = total + N[i]
    i = i + 1
average = total / 5
In which array N[5] defines an array with the name N and that has 5 elements (numbered from 0 to 4). These elements can be denoted in the forms N[3] or N[i] in which i is a placeholder.

And naturally, we can generalize this into the following. Here, we first read the amount of numbers for which we have to calculate the average. 

read nrN
array N[nrN]
total = 0
i = 0
while i < nrN
    read N[i]
    total = total + N[i]
    i = i + 1
average = total / nrN
We see here that for the calculation of the total and average we need to know the length of the array. We kept that information in the placeholder nrN. On this level of abstraction, this is too much detail. We use N.length to get the length of the array. How we get this information on the array is typically left to an implementation in a particular programming language.

And if we separate the reading of the numbers from calculating the average it becomes this. 

read nrN
array N[nrN]
i = 0
while i < N.length
    read N[i]
    i = i + 1

total = 0
i = 0
while i < N.length
    total = total + N[i]
    i = i + 1
average = total / N.length

array - fast access, small memory, fixed length

List

Say that we do not know in advance how many numbers we have to read, but we have to read until some condition is met (like end of file). Then we do not know how large the array has to be. Instead of an array we use a list. 
list N
N = ()
total = 0
nr = 0
while moretoread
    read v
    total = total + v
    N.append v
    nr = nr + 1
average = total / nr
Here, list N defines the list N, () means the empty list, and append just appends a number to the end of a list. Off course, you can also choose for a different notation, for example append N v. How a list and an append really look like is left to an implementation in a particular programming language.

If we first read all the numbers and then calculate the average, we need some operations that make it possible to access the elements of the list one by one. 

list N
N = ()
nr = 0
while moretoread
    read v
    N.append v

total = 0
for v = N
    total = total + v
average = total / N.length
Again, an implementation in a particular programming language must provide the way to get the length of a list as well as a way to iterate over all the elements of a list. Perhaps we have operations to get the first element of a list, and to get the next element of a list. Or, the language provides arrays of variable sizes, so we can implement a list in that way.

Record

If one wants to store something like a date one could store the day, month, and year separately. But, one can also combine this using a record. 
record date year month day
new date D
D.year = 2020
D.month = 5
D.day = 14
D = 2020 5 14
It is also possible to construct an array or a list of records. 
array A[5] data
new record A[2]
A[2] = 2020 5 14
list L date
L = ()
new date d
d = 2020 5 14
L.append d

Linked List

We can make a list of records that are linked together. 
record item v next
new item L
L = 3 NIL
new item i
i = 4 NIL
L.next = i

write L.next.v
Here, the next field of the record is used to refer to the next record in the list. A special value NIL is used to denote the end of the list.

We can make an append instruction for linked lists as follows. 

define append inout L in i
    if L == NIL
	L = i
    else
	x = L
	while x.next != NIL
	    x = x.next
	x.next = i

Combinations

We can make all sorts of combinations with the above data structures, such as an array of array, an array of lists, a list of arrays, etc.
 \ PG \ Computer Science \ Bob's Last modified: Mon Sep 25 14:25:44 2023