Sequence Control

1. Sequence control

Sequence control : the control of the order of execution of the operations both primitive and user defined.
Implicit: determined by the order of the statements in the source program
or by the built-in execution model
Explicit: the programmer uses statements to change the order of execution
(e.g. uses If statement)

1. Levels of sequence control

Expressions: computing expressions using precedence rules and parentheses.
Statements: sequential execution, conditional and iteration statements.
Declarative programming: an execution model that does not depend on the order
of the statements in the source program.
Subprograms: transfer control from one program to another.

1. Sequencing with expressions

The issue: given a set of operations and an expression involving these operations,
what is the sequence of performing the operations?
How is the sequence defined, and how is it represented?
An operation is defined in terms of an operator and operands.
The number of operands determines the arity of the operator.
Basic sequence-control mechanism: functional compositionGiven an operation with its operands, the operands may be:

• Constants

• Data objects

• Other operations

Example 1: 3 * (var1 + 5)

operation - multiplication, operator: *, arity - 2

operand 1: constant (3)

operand 2: operation addition

operand1: data object (var1)

operand 2: constant (5)

Functional compositions imposes a tree structure on the expression,
where we have one main operation, decomposable into an operator and operands.
In a parenthesized expression the main operation is clearly indicated.
However we may have expressions without parentheses.
Example 2: 3* var1 +5
Question: is the example equivalent to the above one?
Example 3: 3 + var1 +5
Question: is this equivalent to (3 + var1) + 5, or to 3 + (var1 + 5) ?
In order to answer the questions we need to know:

• Operator's precedence

• Operator's associativity

Precedence concerns the order of applying operations, associativity deals with the order of operations of same precedence.
Precedence and associativity are defined when the language is defined - within the semantic rules for expressions.
3. 1. Arithmetic operations / expressionsIn arithmetic expressions the standard precedence and associativity of operations
are applied to obtain the tree structure of the expression.
Linear representation of the expression tree:

• Prefix notation

• Postfix notation

• Infix notation

Prefix and postfix notations are parentheses-free.
There are algorithms to evaluate prefix and postfix expressions and algorithms to convert an infix expression into prefix/postfix notation, according to the operators' precedence and associativity.
3. 2. Other expressionsLanguages may have some specific operations, e.g. for processing arrays and vectors, built-in or user defined. Precedence and associativity still need to be defined - explicitly in the language definition or implicitly in the language implementation.
3. 3. Execution-time representation of expressions

• Machine code sequence

• Tree structures - software simulation

• Prefix or postfix form - requires stack, executed by an interpreter.

3. 4. Evaluation of tree representationEager evaluation - evaluate all operands before applying operators.
Lazy evaluation - first evaluate all operands and then apply operations
Problems:

• Side effects - some operations may change operands of other operations.

• Error conditions - may depend on the evaluation strategy (eager or lazy evaluation)

• Boolean expressions - results may differ depending on the evaluation strategy.

1. Statement level sequence control

4. 1. Forms of statement-level control

• Composition – Statements are executed in the order they appear on the page.

• Alternation – Two sequences form alternatives so one sequence or the other 

• sequence is executed but not both. (conditionals)

• Iteration – A sequence of statements that are executed repeatedly.

• Explicit Sequence Control

goto Xif Y goto X – transfer control to the statement labeled X if Y is true.
break4. 2. Structured programming design

1. Hierarchical design of program structures

1. Representation of hierarchical design directly in the program text 

1. using "structured" control statements.

1. The textual sequence corresponds to the execution sequence

1. Use of single-purpose groups of statements

4. 3. "Structured" control statements

1. Compound statements

Typical syntax:
begin

statement1;

statement2;

...

end;

Execute each statement in sequence.
Sometimes (e.g., C) { ... } used instead of begin ... end

1. Conditional statements

if expression then statement1 else statement2
if expression then statement1
If we need to make a choice among many alternatives
nested if statements
case statements
Example :
case Tag is

when 0 => begin

statement0

  end;

when 1 => begin

statement1

  end;

when 2 => begin

statement2

  end;

when others => begin

statement3

   end;

end case
Implementation: jump and branch machine instructions, jump table implementation for case statements (see fig. 8.7)

1. Iteration statements

Simple repetition (for loop) Specify a count of the number of times to execute a loop:
Examples:
perform statement K times;
for I=1 to 10 do statement;
for(I=0;  I<10;  I++) statement;
Repetition while condition holds
while expression do statement; - Evaluate expression and if true execute statement. then repeat process.
repeat statement until expression; - Execute statement and then evaluate expression. Quit if expression is true.
C++ for loop functionally is equivalent to repetition while condition holds
by T. Pratt and M. ZelkowitzProblems with structured sequence control:Multiple exit loops
Exceptional conditions
Do-while-do structure