AMAZON multi-meters discounts AMAZON oscilloscope discounts
3. Structured programming
3.1 Primitives Assignment
Variables are distinct, named items within the memory subsystem of a computer.
The name of a variable is a symbol which denotes its location. A variable is said to have a value which must be chosen from a set known as its range. Two variables with ranges which differ in size or content are said to be of different data type.
Variables of a process constitute its state. Values of variables may change while the process to which they belong runs.
Constants are symbols which denote a value which remains unchanged while the process to which they belong runs. Their type must be chosen from those of the variables belonging to the same process. Each is then said to be compatible with variables of that type.
Binary operators are primitive functions which take two arguments and evaluate a result. A simple example is the add operator, which when applied to the arguments {3, 4} evaluates to 7. The set of operators supplied in a programming language will depend on the applications for which it is designed. For instance, a language used to develop mathematical applications must have, at very least, a full set of algebraic operators. One used to develop graphics or image processing applications will need (at least) a full set of logical operators.
Expressions are combinations of operators, variables and constants which are evaluated by first evaluating each operator in turn. The arguments of each binary operator are considered to be expressions. A variable or constant is just a primitive expression.
The order in which expressions must be evaluated will be dictated by the syntax (rules) of the language. It is common to use parenthesis to allow the programmer to indicate any particular meaning. In order to reduce ambiguity the language usually defines an operator precedence which defines the order in which operators are evaluated. Responsibility for removing all ambiguity usually rests with the programmer.
Assignment means the assignment of a value to a variable. In procedural programming an assignment statement commands the assignment to occur at a specific point in the procedure. The variable to which the value is assigned appears on the left hand side of a symbol denoting assignment. On the right hand side is an expression, e.g.… answer:=42
In a purely sequential programming language assignment is the only available primitive.
Input
See Section 1 for a discussion of the process model of computation.
An input command causes the assignment of a value input (over a channel) to a variable. In the Occam programming language (see 2.4.2) the variable name appears on the right hand side, the channel name on the left and a symbol denoting input lies in between, e.g.…
Hence this means…"input a value over channel 'c.keyboard' into variable 'key.pressed'
Output
Point-to-point communication is the most fundamental within any network. It is that between just two nodes and in one direction only. It constitutes a single event for the network but one event each for sender and receiver (output and input).
Out of this, many-to-one (multiplexing) and one-to-many (demultiplexing or broadcast) communication can be achieved.
An output command causes the output of the value of an expression onto a channel. Consequently the channel name and expression must be stated. In Occam the expression appears on the right hand side, the channel name on the left and a symbol denoting output lies in between, e.g. … c.screen!6*7
Hence this means "output the value of '6*7' onto channel 'c.screen'"
3.2 Constructs
Sequence
The SEQ construct is used to directly define an event sequence. Each statement is a command causing one or more events to occur (see Fig. 7).
Each statement may be a primitive or a procedure name and may be regarded as a process which must terminate before the next starts.
Parallel
The PAR construct is the means by which the programmer specifies which processes are to run concurrently. It must itself be considered a sequential process whose event order will depend upon communication between the component processes.
The events of a process defined by a parallel construct are the assignments belonging to each component process and each communication (i.e. input
+output) between them, (see Fig. 8).
Once again, each statement within the construct is either a primitive or a procedure name.
Fig. 7: Sequence construct
Iteration
A WHILE construct specifies the iteration of a process while a condition (expression of Boolean type) remains true. The body will never run if the condition is false initially. Strictly speaking, only one iteration construct is necessary to program any process. WHILE would do nicely! A REPEAT construct specifies the iteration of a process until a condition becomes true. The body will always run once regardless of whether the condition is true when it starts (unlike WHILE).
A FOR construct specifies iteration of a process a number of times equal to the value of an expression. If this has value zero initially then the body will never run.
Fig. 8: Parallel construct
Selection
Selection means choosing one process from a number of stated possibilities. The choice is made immediately before the one chosen is to start. There are three ways in which the choice may be made…
• Expression value (CASE)
• Condition (IF)
• Guard (ALT)
Selection by either expression or condition is sufficient in a programming language to program any process. Selection by guard is used to define efficient behavior given multiple input channels. The guards used are the input events on each channel. Hence each associated process is the one which uses that channel.
The process which has input and thus can run is selected and allowed to do so.
It is quite possible to program input from multiple channels without selection by channel input guard. It is not however possible to do it efficiently. Input could be taken from each channel alternately. In any real system this would result in serious underuse of the processor, which would spend most of its time idle, waiting for input.
For instance a word processor used by a single typist spends most of its time waiting for the next key to be pressed since it operates much faster than any typist. One which is shared by a number of typists, and which is able to activate the process appropriate to whichever keyboard on which a key is pressed, will make much more efficient use of the processor, which itself then becomes a guarded shared resource.
CASE selects between a number of processes by the value of an expression.
The expression is thus restricted to ordinal types. There is no ambiguity since the expression can only possess a single value. It may be thought of as a multiway switch between the various processes specified.
IF…THEN…ELSE selects between two processes by the success of a condition. It may be regarded as a subset of case, since a condition is just a Boolean expression, and selects between just two processes. As with CASE, no ambiguity is possible since the condition may only take a single value at a time.
It may be thought of as a two-way switch.
Fig. 9: While construct
Occam, however, extends the construct to have an arbitrary number of conditions. On entry, a process is selected by the success of its associated condition. Ambiguity thus arises, should more than one succeed, which is overcome by prioritization of entries by their listed order.
ALT selects between a number of processes, each guarded by an input primitive.
The process selected is the one for which the corresponding input is ready.
Obviously this construct is only needed in a language which supports synchronous communication between concurrent processes. If more than one input is ready, the selection is nondeterminate. A condition may be appended to a guard to effectively allow inhibiting of the input.
3.3 Partitions
Modules
Modules are simply a means of partitioning software for human benefit. They do not reflect any partition relevant to execution. The whole point of a module is that an individual (or team) may take responsibility for its separate development and separate test. They have the added advantages of reusability between applications (like hardware chips) and maintainability. To facilitate reusability, there should ideally be no difficulty in interfacing modules when they are designed, implemented or run.
Fig. 10: Module content
Modules of a procedural language contain the following…
• Interface (exports and imports to parent and child modules respectively)
• Data type definitions
• Data declarations
• Procedure definitions
Each of these should have their own, clearly delineated, section in the source module, see Fig. 10.
Procedures
Procedures offer a means of further partitioning software. Once again they exist to ease development, maintenance and modification. They do not enhance performance but if anything reduce it. Like modules they are to some extent reusable. They should be thought of as implementing a single task. Neither the task nor the procedure should be bigger than a single human can understand easily at one time. A guideline recommended by the author is that the procedure source should all fit on the screen of a terminal at once. All statements of a program should be thought of as belonging to one or other procedure.
Procedure parameters are variables on whose value the precise action of the procedure depends. Value parameters are variables whose current value is passed to the procedure. These variables thus remain unaltered after procedure execution. Reference parameters are variables whose location is passed, allowing the procedure to alter their value.
The scope of a variable is the software partition in which it is visible.
Variables declared within a procedure are called local variables hence their scope is that procedure only. The same goes for constants. Parameters are said to have local scope only. Local scope usually includes any procedures declared locally, although this is not true of Occam.
Recursive definition of a procedure is possible. This may be understood from the following…
Something is said to possess a recursive definition if it may be defined in terms of itself.
Recursion must terminate and hence must be subject to selection. A commonly quoted example is the definition of the factorial function of a number…
factorial(x)= IF x>0 THEN factorial:= x * factorial(x-1) ELSE factorial:=1 END
…where recursion terminates when x is zero.
4. Standard programming languages
4.1 Modula 2
Primitives
There is only assignment in Modula 2. There is no support for concurrent or parallel processing at the primitive level. Expression evaluation is well supported with operators to support mathematical, graphics and text processing applications.
Constructs
All the purely sequential constructs discussed above are available. A sequence is defined as any set of statements separated by ";". There is no support at the construct level either for concurrency or parallel processing. (No PAR or ALT.) In addition to WHILE, REPEAT and FOR constructs Modula 2 has another iteration construct… LOOP. Multiple exits are possible using a command EXIT which may be conditionally selected. Use of the LOOP construct is not recommended for the inexperienced programmer!
Partitions
Software partitions are the strength of Modula 2! Procedures and modules are fully supported. Functions are not quite the same as in other languages. They occur in Modula 2 in the guise of function procedures which are able to take reference as well as value parameters (caution!) and unfortunately are unable to return structured data objects. The effect of this can be simulated by using a reference parameter (although it will lead to less readable source code) or by returning a pointer to the structured data.
The procedure data type is provided allowing procedures to be passed as parameters. This is a powerful feature which should be used with great care.
Modula 2 was the first language to provide modules as an explicit, readable part of the language. It is possible to clearly delineate between all four sections listed above.
Concurrency
It is at this level that support is found for concurrent processing though not for parallel processing. A special module, guaranteed always available, called "System" exports two procedures and one data type which facilitate extra processes called co-routines to run quasi-concurrently with a procedure defined in the usual way. These are…
• New Process: A procedure which creates, but does not start, a new process. It must be passed a parameter of procedure type which defines the new process and returns a variable of process type
• Transfer: A procedure which transfers control between two processes specified by their descriptors which are passed as value parameters
• Process: A data type used for process descriptors
Procedures are provided, exported from module "Processes", to support inter process communication. The technique used is based on the use of shared resources which are protected by semaphores, see [Deitel 84] or [Lister 84].
(Channels are not provided.)
Considerable expertise and care is required of the programmer to ensure…
• Secure communication
• Mutual exclusion (of processes from shared resources)
• Synchronization
It is certainly for experts only. Unfortunately, even experts make mistakes which in this area can be disastrous.
Support for concurrent processing in a programming language should be provided at the primitive level. The same facilities should also (transparently) support parallel processing and be simple to use. This is only possible if the idea of shared resources is abandoned and each process has its own private memory.
Computer architects must provide support for both concurrent processing (scheduling, soft channels) and parallel processing (hard channels).
Applicability
Modula 2 is especially recommended for large projects. It renders large projects manageable because of the availability of modules for design, specification and implementation. The high degree of the source readability eases its maintenance.
Development costs may be cut by exploitation of module reusability.
The range of operators available make it appropriate to mathematical, textual and graphics applications. Not discussed above are facilities for systems level programming which are reasonable.
As a vehicle for applications requiring concurrent processing it is usable (with great care) by experts only. It is not equipped for parallel processing at all.
Further reading
The purpose of this brief summary is to set the background for subsequent discussion of hardware architectural support of modular, procedural programming. It is not the intent to be thorough.
The discussion should be enough for a student who has successfully traversed a course in procedural programming using any fully block-structured language (e.g. Pascal).
[Knepley & Platt 85] is recommended as a readable tutorial, accessible to any student, with a fair amount of example code. [Wirth 85] is the official summary given by the author of the language, Niklaus Wirth, and is recommended as a tutorial and reference text for those experienced in at least one other programming language. Modula 2 is now well established. Many good texts are thus available.
4.2 Occam
Primitives
Probably the most important and novel feature of Occam is that it supports concurrency at the primitive level. There are three main primitives…
• Assignment
• Input
• Output
Communication is synchronized via a mailbox form of rendezvous. The first process to arrive at the rendezvous leaves its identity and suspends itself. The second completes the communication and causes the first to resume. Note that either process may be the one suspended. One cannot determine which prior to their running.
A second novel feature of Occam is that everything is a process. Recall (from Section 1) that a process is a sequence of events which starts, runs then terminates. In addition to the three above, two extra primitives are defined…
• STOP which starts but never terminates
• SKIP which starts and immediately terminates
All five are fully fledged processes in their own right but, from the point of view of the programmer, are indivisible.
Data types available unfortunately differ between variable and channel. For instance, variable length strings and records are supported as channel protocols but not as the data types of variables.
Constructs Occam succeeds beautifully in being at once both simple and extremely expressive in its facilities to construct sequential processes. Construction of a sequence of subordinate processes, i.e. where the event ordering is explicitly stated, is made possible using a SEQ construct. Iteration is provided via a WHILE construct, conditionally terminated in the usual way.
Construction of a single sequential process from a number of concurrent ones is enabled with the PAR construct. All specified processes start together. The PAR itself terminates only when all the subordinate processes have terminated.
If just one of them STOPs so does the PAR. It is essential to understand that, although its subordinate processes run concurrently, the PAR itself forms a single process which is sequential like any other.
All three forms of selection (mentioned earlier) are available. CASE selects a process from a list by expression value. IF selects from a list by the truth of an associated condition. Care is required here! Should no condition evaluate true the process STOPs. A wise programmer thus adds the condition TRUE and an associated SKIP process to the list. There exists a second problem with IF. Given more than one condition succeeding in the list specified, which process is run? In Occam it is the one following the first successful condition. Nothing is gained by nesting IF constructs in Occam. All conditions may simply be entered in the list of a single construct. This has the effect of improving readability.
Selection by channel is supported by the ALT (ALTernative) construct. A list of input guards is specified each with an associated process. The process associated with the first ready guard is the one which runs. If no guard is able to terminate the ALT is suspended until one can.
Each guard may be supplemented with a condition to selectively exclude inputs from consideration. A guard may be an input from a timer process, which outputs time. The AFTER qualifier may be used to prevent the guard from succeeding until after a stated time thus effectively allowing a "timeout" process to be triggered if no other input arrives.
Replication
Replication of SEQ, IF, PAR and ALT construct level processes is supported. If the design calls for a number of procedurally identical processes, which differ only in elements chosen from arrays of either channels (PAR, ALT) or variables (SEQ, IF), extremely concise elegant programs may be written. Replication renders Occam very expressive.
Partitions
We have already met one of the weaknesses of Occam in its limited set of data types for variables. A second weakness is arguably in its support of partitions to benefit software design. There are no modules which can encapsulate packages of procedures for reuse between applications. The effect can, of course, be achieved by shuffling text between files using an appropriate editor. Occam does however go part way towards the concept of a module. Individual procedures may be separately compiled and then linked into any number of applications.
Procedures in Occam are well supported as named processes which take reference parameters by default. Value parameters are also supported. If invoked as a subordinate of a SEQ, a procedure must be passed variables with which to communicate with its neighbors. If that of a PAR it needs the appropriate channels.
Functions also form part of Occam. Only value parameters are allowed. All parameters must be variables and not channels. Hence functions which communicate together must communicate via variable sharing and hence must run successively. Neither may they contain any non-determinacy in the form of ALT or PAR constructs.
Neither procedures nor functions may be recursively defined. This constitutes a third weakness in that it places a limit on its expressivity, especially for mathematical applications.
Applicability
Concurrent functions or procedures cannot share variables and thus cannot inflict side effects upon each other. A newcomer to Occam might well start off with the notion of it as "Pascal with no shared variables". The idea of doing away with the sharing of any state between processes is central and responsible for Occam being able to offer simple yet unrestricted access to the power of parallel processing.
Event processing is the essence of creating systems which effect real time control over automation (e.g. production lines, robots, washing machines, watches, kettles etc). Such systems are known as embedded systems and now account for the greatest and fastest growing number of computers. Languages such as Ada and Occam were originally designed for real time control and embedded systems.
Problems in the real world almost always possess a high degree of concurrency. It is the exception which is purely composed of successive processes. Occam is the simplest programming language with which to adequately describe such problems. It is much simpler to describe a problem composed of concurrent, communicating sequential processes with a language which is equipped for it than to mentally transform it into a purely sequential form. Unfortunately the majority of practicing software engineers are firmly rooted in thinking sequentially and thus often find Occam difficult and natural concurrency obscure.
The simplicity of Occam, together with its expressive power over the behavior of both natural and machine systems, give it an accessible range of applications limited only perhaps by their scale due to its limited modularity.
Further reading
We can only afford a brief summary of Occam here, enough to serve subsequent discussion of hardware architectures which support the process model of computation. [Burns 88] is an excellent tutorial which includes a comparison with Ada. [Fountain & May 87] offers an alternative introduction. [Inmos 88#1] is the official language definition and manual which also contains many useful examples. It is absolutely indispensable.
Exercises
Question 1
i. Define in your own words the meaning of the following terms and how they may be used in the engineering of software…
• Module
• Top-down task diagram
• Data flow diagram
Question 2
i. Explain the evolution of a software project in terms of the various phases of its life.
ii. Identify the phase at which the following must be specified…
• Definition modules
• Pseudocode
Question 3
i. What are library modules and why are they commercially important to software engineering?
ii. In what form would you expect to use library modules?
Question 4
If neither procedures nor modules should affect the machine execution of a program, why should a machine language support them?
Related Articles -- Top of Page -- Home