The Imperative Programming Paradigm

Imperative programming is characterized by programming with a state and commands which modify the state.
Imperative:
a command or order
Procedure:
  1. the act, method or manner of proceeding in some process or course of action
  2. a particular course of action or way of doing something.
When imperative programming is combined with subprograms it is called procedural programming. In either case the implication is clear. Programs are directions or orders for performing an action.
Keywords and phrases: Assignment, goto, structured programming, command, statement, procedure, control-flow, imperative language, assertions, axiomatic semantics. state, variables, instructions, control structures.


The imperative programming paradigm is an abstraction of real computers which in turn are based on the Turing machine and the Von Neumann machine with its registers and store (memory). At the heart of these machines is the concept of a modifiable store. Variables and assignments are the programming language analog of the modifiable store. The store is the object that is manipulated by the program. Imperative programming languages provide a variety of commands to provide structure to code and to manipulate the store. Each imperative programming language defines a particular view of hardware. These views are so distinct that it is common to speak of a Pascal machine, C machine or a Java machine. A compiler implements the virtual machine defined by the programming language in the language supported by the actual hardware and operating system.

In imperative programming, a name may be assigned to a value and later reassigned to another value. The collection of names and the associated values and the location of control in the program constitute the state. The state is a logical model of storage which is an association between memory locations and values. A program in execution generates a sequence of states(See Figure N.1). The transition from one state to the next is determined by assignment operations and sequencing commands.



 
Figure N.1: State Sequence 
S0 -- O0 -> S1 - ... -> Sn-1 -- On-1-> Sn

Unless carefully written, an imperative program can only be understood in terms of its execution behavior. The reason is that during the execution of the code, any variable may be referenced, control may be transferred to any arbitrary point, and any variable binding may be changed. Thus, the whole program may need to be examined in order to understand even a small portion of code.

Since the syntax of C, C++ and Java are similar, in what follows, comments made about C apply also to C++ and Java.

Variables and Assignment

Imperative programs are characterized by sequences of bindings (state changes) in which a name may be bound to a value at one point in the program and later bound to a different value. Since the order of the bindings affects the value of expressions, an important issue is the proper sequencing of bindings.
Aside. Most descriptions of imperative programming languages are tied to hardware and implementation considerations where a name is bound to an address, a variable to a storage cell, and a value to a bit pattern. Thus, a name is tied to two bindings, a binding to a location and to a value. The location is called the l-value and the value is called the r-value. The necessity for this distinction follows from the implementation of the assignment. For example,
X := X+2

the X on the left of the assignment denotes a location while the X on the right hand side denotes the value. Assignment changes the value at a location.

A variable may be bound to a hardware location at various times. It may be bound at compile time (rarely), at load time (for languages with static allocation) or at run time (for languages with dynamic allocation). From the implementation point of view, variable declarations are used to determine the amount of storage required by the program.

The following examples illustrate the general form for variable declarations in imperative programming languages.
Pascal style declaration: var name : Type;
C style declaration:  Type name;
A variable and a value are bound by an assignment. A variety of notations is used to indicate the binding of a variable and the value of an expression E.
 
Pascal V := E
C V = E
APL V <-- E
Scheme (setq V E)
 
Aside. The use of the assignment symbol, =, in C confuses the distinction between definition, equality and assignment. The equal symbol, =, is used in mathematics in two distinct ways. It is used to define and to assert the equality between two values. In C it neither means define nor equality but assign. In C the double equality symbol, ==, is used for equality, while the form: type variable; is used for definitions.
The assignment command is what distinguishes imperative programming languages from other programming languages. The assignment typically has the form:
V := E.

The command is read ``assign the name V to the value of the expression E until the name V is reassigned to another value''. The assignment binds a name and a value.

Aside. The word ``assign'' is used in accordance with its English meaning; a name is assigned to an object, not the reverse. The name then stands for the object. The name is the assignee. This is in contrast to wide spread programming usage in which a value assigned to a variable.
The assignment is not the same as a constant definition because it permits redefinition. For example, the two assignments:
 
X := 3;
X := X + 1
are understood as follows: assign X to three and then reassign X to the value of the expression X+1 which is four. Thus, after the sequence of assignments, the value of X is four.

Several kinds of assignments are possible. Because of the frequent occurrence of assignments of the form: X := X op E, C provides an alternative notation of the form: X op= E. A multiple assignment of the form:

V0 := V1 := ... := Vn := E

causes several names to be assigned to the same value. This form of the assignment is found in C. A simultaneous assignment of the form:

V0,...,Vn := E0,...,En c

causes several assignments of names to values to occur simultaneously. The simultaneous assignment permits the swapping of values without the explicit use of an auxiliary variable.

From the point of view of axiomatic semantics, the assignment is a predicate transformer. It is a function from predicates to predicates. From the point of view of denotational semantics, the assignment is a function from states to states. From the point of view of operational semantics, the assignment changes the state of an abstract machine.

Unstructured Commands

Given the importance of sequence control, it is not surprising that considerable effort has been given to finding appropriate control structures. Figure N.M gives a minimal set of basic control structures.


 
Figure N.M: A set of unstructured commands
command ::= identifier := expression
| command; command
| label : command 
| GOTO label 
| IF boo_exp THEN GOTO label 
 

The unstructured commands contain the assignment command, sequential composition of commands, a provision to identify a command with a label, and unconditional and conditional GOTO commands.  The unstructured commands have the advantage, they have direct hardware support and are completely general purpose. However, the programs are flat without hierarchical structure with the result that the code may be difficult to read and understand. The set of unstructured commands contains one of the most powerful commands, the GOTO. It is also the most criticized.  The GOTO can make it difficult to understand a program by producing `spaghetti' like code. So named because the control seems to wander around in the code like strands of spaghetti.

The GOTO commands are explicit transfer of control from one point in a program to another program point. These jump commads come in unconditional and conditional forms:

goto label 
if conditional expression goto label
At the machine level alternation and iteration may be implemented using labels and goto commands. Goto commands often take two forms:
  1. Unconditional goto. The unconditional goto command has the form:
  2. goto LABELi

    The sequence of instructions next executed begin with the command labeled with LABELi.

  3. Conditional goto. The conditional goto command has the form:
  4. if conditional expression then goto LABELi

    If the conditional expression is true then execution transfers to the sequence of commands headed by the command labeled with LABELi otherwise it continues with the command following the conditional goto.

Structured Programming

The term structured programming was coined to describe a style of programming that emphasizes hierarchical program structures in which each command has one entry point and one exit point. The goal of structured programming is to provide control structures that make it easier to reason about imperative programs. Figure M.N gives a minimal set of structured commands.

 
Figure N.M: A set of structured commands
command ::= SKIP 
| identifier:= expression 
| IF guarded_command [ []guarded_command ]+ FI 
| DO guarded_command [ []guarded_command ]+ OD 
| command ;command 
guarded_command ::= guard --> command 
guard ::= boolean expression 
 

The IF and DO commands which are defined in terms of guarded commands require some explanation.   The IF command allows for a choice between alternatives while the DO command provides for iteration.  In their simplest forms, an IF statement corresponds to an If condition then command and a DO statement corresponds to a While condition Do command.
 

IF guard --> command FI = if guard then command
DO guard --> command OD = while guard do command 
A command proceded by a guard can only be executed if the guard is true.  In the general case, the semantics of the IF - FI and DO - OD commands requires that only one command corresponding to a guard that is true be selected for execution.  The selection is nondeterministic..

Control structures are syntactic structures that define the order in which assignments are performed. Imperative programming languages provide a rich assortment of sequence control mechanisms. Three control structures are found in traditional imperative langauges: sequential composition, alternation, and iteration.

Sequential Composition. Sequential composition specifies a linear ordering for the execution of commands. It is usually indicated by placing commands in textual sequence and either line separation or a special symbol (such as the semicolon) is used to indicate termination point of a command. In C the semicolon is used as a terminator, in Pascal it is a command separator. At a more abstract level, composition of commands is indicated by using a composition operator such as the semicolon (C0;C1).

Selection: Selection permits the specification of a sequence of commands by cases. The selection of a particular sequence is based on the value of an expression. The if and case commands are the most common representatives of alternation.

Iteration: Iteration specifies that a sequence of commands may be executed zero or more times. At run time the sequence is repeatedly composed with itself. There is an expression whose value at run time determines the number of compositions. The while, repeat and for commands are the most common representatives of iteration.

Abstraction: A sequence of commands may be named and the name used to invoke the sequence of commands.  Subprograms, procedures, and functions are the most common representatives of abstration.

Skips

The simplest kind of command is the skip command. It has no effect.

Composition

The most common sequence is the sequential composition of two or (more) commands (often written `S0;S1'). Sequential composition is available in every imperative programming language.

Alternation

An alternative command may contain a number of alternative sequences of commands, from which exactly one is chosen to be executed.   The nondeterministic IF-FI command is unusual.  Traditional programming languages usually have one or more if commands and a case command.
 
-- Ada 
if condition then
   commands
{ elsif condition then
   commands }
[ else
   commands]
endif
case expression is
when choice | choice  => commands
when choice | choice  => commands
[when others => commands]
end case;

Iteration

An iterative command has a body which is to be executed repeatedly and has an expression which determines when the execution will cease.   The three common forms are the while-do,  the repeat-until, and the for-do.
 
while-do while condition do
    body
repeat-until repeat
   body
until condition
for-do for index := lowerBound, upperBound, step do
   body
The while-do command semantics require the testing of the condition before the body is executed.  The semantics of the repeat-until command require the testing of the condition after the body is executed.  The for-do command semantics require testing of the condition before the body is executed.

 The iterative commands are often used to traverse the elements of a data structure - search for a item etc.  This insight leads to the concept of generators and iterators.

The generator concept appears in functional programming languages as functionals.
Definition: An iterator is a generalized looping structure whose iterations are determined by a generator.
An iterator is used with the an extended form of the for loop where the iterator replaces the initial and final values of the loop index. For example, given a binary search tree and a generator which performs inorder tree traversal, an iterator would iterate for each item in the tree following the inorder tree traversal.
 
FOR Item in Tree DO S;

Sequential Expressions

Imperative programming languages with their emphasis on the sequential evaluation of commands often fail to provide a similar sequentiality to the evaluation of expressions. The following code illustrates a common programming situation where there are two or more conditions which must remain true for iteration to occur.
 
i := 0;
while (i < length) and (list[i] <> value) do 
   i := i+1
The code implements a sequential search for a value in a table and terminates when either the entire table has been searched or the value is found. Assuming that the subscript range for list is 0 to length it seems reasonable that the termination of the loop should occur either when the index is out of bounds or when the value is found. That is, the arguments to the and should be evaluated sequentually and if the first argument is false the remaining argument need not be evaluated since the value of the expression cannot be true. Such an evaluation scheme is call short-circuit evaluation.  In languages without short-circuit evaluation, if the value is not in the list, the program aborts with a subscript out of range error.

The Ada language provides the special operators and then and or else so that the programmer can specify short-circuit evaluation.

Subprograms, procedures, and functions

A procedure is an abstraction of a sequence of commands. The procedure call is a reference to the abstraction.   The syntax of procedure definition and invocation (call) is simple.
 
Procedure definition: name( parameter list) { body }
Procedure invocation: name( argument list )

The semantics of the procedure call is determined by the semantics of the procedure body.  For many languages with non-recursive procedures, the semantics may be viewed as simple textual substitution.
 

Parameters and arguments have a simple syntax
 

Parameter list: t0 name1, ..., tn-1 namen-1
Argument list: expression1, ..., expressionn-1

An in parameter designates that the body of the procedure may not modify the value of the argument (often implemented as a copy of the argument).  An out parameter designates that value of the argument is undefined on entry to the procedure and when the procedure terminates, the argument is assigned to a value  (often copied to the argument).  An in-out parameter designates that the value of the parameter may be defined on entry to the procedure and may be modified when the procedure terminates.
 

Parameter Argument
Pascal in: 
in-out:
name : type
var name : type
name
expression
Ada in
out
in-out
name : in type
name
: out type
name
: in out type
expression
name
name
C in:
in-out:
type name 
type *name 
(internal reference to the in-out 
parameter must be *name)
expression
&name

Other Control Structures

Other control structures are possible. In simulations, it is often easier to structure a program as a set cooperating tasks. When the task activities are interdependent, they can be structured as a collection of coroutines. Unlike subroutines where control is passed back to the calling routine from the subroutine when the subroutine is finished, control is passed back and forth between the subroutines with control resuming where it left off (right after the resume commands in the following).
 
Coroutine C1 
... 
resume C2 
... 
Coroutine C2 
... 
resume C3 
... 
Coroutine C3 
... 
resume C1 
... 

There is a single thread of control that moves from coroutine to coroutine.  The multiple calls to a coroutine do not necessarily require multiple activation records.

In addition to coroutines there are concurrent or parallel processes

[|| Processo, ... , Processn-1]
with multiple threads of control which communicate either through shared variables or message passing.  Concurrency and parallel programming languages are considered in a later chapter.

Reasoning about Imperative Programs

Imperative constructs jeopardize many of the fundamental techniques for reasoning about mathematical objects. For example, the assignment axiom of axiomatic semantics is valid only for languages without aliasing and side effects. Much of the work on the theory of programming languages is an attempt to explain the ``referentially opaque'' features of programming languages in terms of well-defined mathematical constructs. By providing descriptions of programming language features in terms of standard mathematical concepts, programming language theory makes it possible to manipulate programs and reason about them using precise and rigorous techniques. Unfortunately, the resulting descriptions are complex and the notational machinery is difficult to use in all but small examples. It is this complexity that provides a strong motivativation to provide functional and logic programming as alternatives to the imperative programming paradigm.

Sequencers

There are several common features of imperative programming languages that tend to make reasoning about the program difficult. The goto command \cite{Dijk68} breaks the sequential continuity of the program. When the use of the goto command is undisciplined, the breaks involve abrupt shifts of context.

In Ada, the exit sequencer terminates an enclosing loop. All enclosing loops upto and including the named loop are exited and execution follows with the command following the named loop.

Ada uses the return sequencer to terminate the execution of the body of a procedure or function and in the case of a function, to return the result of the computation.

Exception handers are sequencers that take control when an exception is raised.

A sequencer is a construct that allows more general control flows to be programmed.

The machine language of a typical computer includes instructions which allow any instruction to be selected as the next instruction. A sequencer is a construct that is provided to give high-level programming languages some of this flexibility. We consider three sequencers, jumps, escapes, and exceptions. The most powerful sequencer (the goto) is also the most criticized. Sequencers can make it difficult to understand a program by producing `spaghetti' like code. So named because the control seems to wander around in the code like the strands of spaghetti.

Escape

An escape is a command which terminates the execution of a textually enclosing construct. An escape of the form:
return expr

is used in C to exit a function call and return the value computed by the function.

An escape of the form:

exit(n)

is used to exit n enclosing constructs. The exit command can be used in conjunction with a general loop command to produce while and repeat as well as more general looping constructs.

In C a break command sends control out of the enclosing loop to the command following the loop while the continue command transfers control to the beginning of the enclosing loop.

Exceptions

There are many ``exception'' conditions that can arise in program execution. Some exception conditions are normal for example, the end of an input file marks the end of the input phase of a program. Other exception conditions are genuine errors for example, division by zero. Exception handlers of various forms can be found in PL/1, ML, CLU, Ada, Scheme and other languages.

There are two basic types of exceptions which arise during program execution. They are domain failure, and range failure.

Domain failure
occurs when the input parameters of an operation do not satisfy the requirements of the operation. For example, end of file on a read instruction, division by zero.
Range failure
occurs when an operation is unable to produce a result for values which are in the range. For example, division by numbers within an epsilon of zero.
Definition: An exception condition is a condition that prevents the completion of an operation. The recognition of the exception is called raising the exception.
Once an exception is raised it must be handled. Handling exceptions is important for the construction of robust programs. A program is said to be robust if it recovers from exceptional conditions.
Definition: The action to resolve the exception is called handling the exception. The propagation of an exception is the passing of the exception to the context where it can be handled.
The simplest method of handling exceptions is to ignore it and continue execution with the next instruction. This prevents programmer from learning about the exception and may lead to erroneous results.

The most common method of handling exceptions is to abort execution. This is not exceptable for file I/O but may be acceptable for an array index being out of bounds or for division by zero.

The next level of error handling is to return a value outside the range of the operation. This could be a global variable, a result parameter or a function result. This approach requires explicit checking by the programmer for the error values. For example, the eof boolean is set to true when the program has read the last item in a file. The eof condition can then be checked before attempting to read from a file. The disadvantage of this approach is that a program tends to get cluttered with code to test the results. A more serious consequence is that a programmer may forget to include a test with the result that the exception is ignored.

Responses to an Exception
Return a label and execute a goto -- Fortran
Issues
Resumption of Program Execution
Once an exception has been detected, control is passed to the handler that defines the action to be taken when the exception is raised. The question remains, what happens after handling the exception?

One approach is to treat exception handlers as subroutines to which control is passed and after the execution of the handler control returns to the point following the call to the handler. This is the approach taken in PL/1. It implies that the handler ``fixed'' the state that raised the condition.

Another approach is that the exception handler's function is to provide a clean-up operation prior to termination. This is the approach taken in Ada. The unit in which the exception occurred terminates and control passes to the calling unit. Exceptions are propagated until an exception handler is found.

Suppression of the Exception
Some exceptions are inefficient to implement (for example, run time range checks on array bounds). The such exceptions are usually implemented in software and may require considerable implementation overhead. Some languages give the programmer control over whether such checks and the raising of the corresponding exception will be performed. This permits the checks to be turned on during program development and testing and then turned off for normal execution.
  1. Handler Specification
  2. Default Handlers

  3. Propagation of Exception

Side effects

Side effects are a feature of imperative programming languages that make reasoning about the program difficult. Side effects are used to provide communication among program units. When undisciplined access to global variables is permitted, the program becomes difficult to understand. The entire program must be scanned to determine which program units access and modify the global variables since the call command does not reveal what variables may be affected by the call.

At the root of differences between mathematical notations and imperative programs is the notion of referential transparency (substitutivity of equals for equals). Manipulation of formulas in algebra, arithmetic, and logic rely on the principle of referential transparency. Imperative programming languages violate the principle. For example:
 

integer f(x:integer)
  {
     y := y+1; 
     f := y + x 
   }
This ``function'' in addition to computing a value also changes the value of the global variable y. This change to a global variable is called a side effect. In addition to modifying a global variable, it is difficult to reason with the function itself.  For example, if at some point in the program it is known that y = z = 0 then f(z) = 1 in the sense that after the call f(z) will return 1. But, should the following expression occur at that point in the program, it will be false.
1 + f(z) = f(z) + f(z)

I/O functions of necessity involve side effects.  The following expressions involving the C function getint may return different values even though algebraically they appear to have the same value.
 

2 * getint()
getint() + getint()
The first multiplies the next integer read from the input file by two while the second expression denotes the sum of the next two successive integers read from the input file.

Aliasing and dangling references

Two names are aliases if they denote (share) the same data object during a unit activation. Aliasing is another feature of imperative programming languages that makes programs harder to understand and harder to reason about.

One way aliases occur is when two or more arguments to a subprogram are the same.  When a data object is passed by ``reference'' it is referenced both by its name in the calling environment and its parameter name in the called environment.  In the following subprogram, the parameters are  in-out parameters.
 

aliasingExample (m, n : in out integer);
   {
      n := 1; 
      n := m + n
   }
The two parameters are used as different names for the same object in the call aliasingExample( i, i).  In this example, the result is that i is set to 2.  In the call aliasingExample( a[i], a[j] ) the result depends on the values of i and j with aliasing occuring when they are equal.  This second call illustrates that aliasing can occur at run time so the detection of aliasing may be delayed until run time and so compilers cannot be relied on to detect aliasing.

Aliasing interferes with optimizing phase of a compiler.   Optimization sometimes requires the reordering of  steps or the deletion of unnecessary steps. The following assignments which appear to be independent of each other illustrate an order depencency.
 

x := a + b
y := c + d
If x and c are aliases for the same object, the assignments are interdependent and the order of evaluation is important.

The purpose of the equivalence command in FORTRAN is the creation of aliases. It permits the efficient use of memory (historically a scarce commodity) and can be used as a crude form of a variant record.  Another way in which aliasing can occur is when a data object may be a component of several data objects (referenced through pointer linkages).

Pointers are intrinsically generators of aliasing.
 
var p, q : ^T;
...
new(p);
q := p
When a programming language requires programmers to manage memory for dynamically allocated objects and the language permits aliasing, an object returned to memory may still be accessible though an alias and the value may be changed if the memory manager allocates the same storage area to another object. In the following code,
 
type pointer = ^Integer
var p : Pointer;

procedure Dangling;
var q : Pointer;
begin;
   new(q);  q^ := 23;  p := q;  dispose(q)
end;

begin
   new(p); Dangling(p)
end;
the pointer p is left pointing to a non-existent value.

The problem of aliasing arises as soon as a language supports variables and assignment. If more than one assignment is permitted on the same variable x, the fact that x=a cannot be used at any other point in the program to infer a property of x from a property of a. Aliasing and global variables only magnify the issue.

Historical Perspectives and Further Reading

Imperative languages have a rich and varied history. The first imperative programming languages were machine languages.  Machine instructions were soon replaced with assembly languages which are essentially transliterations of machine code.

Early Imperative Languages

FORTRAN (FORmula TRANslation) was the first high level language to gain wide acceptance. It was designed for scientific applications and featured an algebraic notation, types, subprograms, and formatted input/output. It was implemented in 1956 by John Backus at IBM specifically for the IBM 704 machine. Efficient execution was a major concern consequently, its structure and commands have much in common with assembly languages. FORTRAN won wide acceptance and continues to be in wide use in the scientific computing community.

COBOL (COmmon Business Oriented Language) was designed (by a committee of representatives of computer manufactures and the Department of Defense) at the initiative of the U. S. Department of Defense in 1959 and implemented in 1960 to meet the need for business data processing applications. COBOL featured records, files and fixed decimal data. It also provided a ``natural language'' like syntax so that programs would be able to be read and understood by non-programmers. COBOL won wide acceptance in the business data processing community and continues to be in wide use.

ALGOL 60 (ALGorithmic Oriented Language) was designed in 1960 by an international committee for use in scientific problem solving. Unlike FORTRAN it was designed independently of an implementation, a choice which lead to an elegant language. The description of ALGOL 60 introduced the BNF notation for the definition of syntax and is a model of clarity and completeness. Although ALGOL 60 failed to win wide acceptance, it introduced block structure, structured control statements and recursive procedures into the imperative programming paradigm.

Evolutionary Developments

PL/I (Programming Language I) was developed at IBM in the mid 1960s. It was designed as a general purpose language to replace the specific purpose languages like FORTRAN, ALGOL 60, COBOL, LISP, and APL (APL and LISP were considered in the chapter on functional programming. PL/I incorporated block structure, structured control statements, and recursion from ALGOL 60, subprograms and formatted input/output from FORTRAN, file manipulation and the record structure from COBOL, dynamic storage allocation and linked structures from LISP, and some array operations from APL. PL/I introduced exception handling and multitasking for concurrent programming. PL/I was complex, difficult to learn, and difficult to implement. For these and other reasons PL/I failed to win wide acceptance.

ALGOL 68 was designed to be a general purpose language which remedied PL/I's defects by using a small number of constructs and rules for combining any of the constructs with predictable results--orthogonality. The description of ALGOL 68 issued in 1969 was difficult to understand since it introduced a notation and terminology that was foreign to the computing community. ALGOL 68 introduced orthogonality and data extensibility as a way to produce a compact but powerful language. The ``ALGOL 68 Report'' considered to be one of the most unreadable documents ever printed and implementation difficulties prevented ALGOL 68's acceptance.

Pascal was developed by Nicklaus Wirth partly as a reaction to the problems encountered with ALGOL 68 and as an attempt to provide a small and efficient implementation of a language suitable for teaching good programming style. C, which was developed about the same time, was an attempt to provide an efficient language for systems programming.

Modula-2 and Ada extended Pascal with features to support module based program development and abstract data types. Ada was developed as the result of a Department of Defense initiative while Modula-2 was developed by Nicklaus Wirth. Like PL/1 and Algol-68, Ada represents an attempt to produce a complete language representing the full range of programming tasks.

Simula 67 added coroutines and classes to ALGOL 60 to provide a language more suited to solving simulation problems. The concept of classes in object-oriented programming can be traced back to Simula's classes. Small-talk combined classes, inheritance, and ease of use to provide an integrated object-oriented development environment. C++ is an object-oriented programming language derived from C. Java, a simplified C++, is an object-oriented languages designed to dynamically load modules at runtime and to reduce programming errors.

Expression-oriented languages

Expression-oriented languages achieve simplicity and regularity by eliminating the distinction between expressions and commands. This permits a simplification in the syntax in that the language does not need both procedure and function abstractions nor conditional expressions and commands since the evaluation of an expression may both yield a value and have a side effect of updating variables. Since the assignment expression V := E can be defined to both yield the value of the expression E and assign V to the value of E, expressions of the form V0 := ... := Vn := E are possible giving multiple assignment for free. Algol-68, C, Scheme, and ML are examples of expression oriented languages.

Exercises

  1. [Time/Difficulty](section)Give all possible forms of assignment found in the programming language C.
  2. Give axiomatic, denotational and operational semantics for the simultaneous assignment command.
  3. Discuss the relationship between the assignment command and input and output commands.
  4. Give axiomatic, denotational and operational semantics for the goto command.
  5. Find an algorithm which transforms a program containing gotos into an equivalent program without gotos.
  6. Give axiomatic, denotational and operational semantics for the skip command.
  7. What is used to indicate sequential composition in
    1. the Pascal family of languages?
    2. the C family of languages?
  8. Show how to implement the if-then-else command using unstructured commands.
  9. Show how to implement a structured while-do and if-then-else commands using unstructured commands.
  10. Show that case and if commands are equivalent by implementing a case command using if commands and an if command using a case command.
  11. Compare and contrast the if and case/switch commands of Ada and C.
  12. Compare and contrast the looping commands of Ada and C.
  13. Show how to implement the repeat-until and for-do commands in terms of a while-do command.
  14. Show that while and repeat until control structures are equivalent.
  15. Design a generalized looping command and give its axiomatic semantics.
  16. Give axiomatic semantics for the IF-FI and DO-OD commands.
  17. Give axiomatic semantics for the C/C++/Java for command.
  18. Provide recursive definitions of the iterative control structures while, repeat, and for.
  19. Alternative control structures
  20. What is the effect on the semantic descriptions if expressions are permitted to have side effects?
  21. Axiomatic semantics
  22. Denotational semantics
  23. Operational semantics
  24. Classify the following common error/exception conditions as either domain or range errors.
    1. overflow -- value exceeds representational capabilities
    2. undefined value -- variable value is undefined
    3. subscript error -- array subscript out of range
    4. end of input -- attempt to read past end of input file
    5. data error -- data of the wrong type

Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of Anthony A. Aaby. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee.
© 1998 Anthony A. Aaby.  Send comments to aabyan@wwc.edu