Computer Science

Chapter 8

Statement-Level

Control Structures

Chapter 8

Topics

Introduction

Selection Statements

Iterative Statements

Unconditional Branching

Guarded Commands

Conclusions

Levels of Control Flow

Within expressions

Among program statements

Among program units

Control Statements
Evolution

FORTRAN I control statements were based directly on IBM 704 hardware
Much research and argument in the 1960s about the issue
One important result:
It was proven that all algorithms

represented by flowcharts

can be coded with only

two-way selection and pretest logical loops

Control Statements

Selection among several alternative control flow paths

Repeated execution of collections of statements

Overall Design Issue

What control statements should a language have, beyond selection and pretest logical loops?

Introduction

Definition: A control structure is a control statement and the statements whose execution it controls

Introduction

Categories of Control Structures

Compound statements
Selection statements
Iteration statements
Unconditional branching
Compound Statements

Definition: A block is a compound statement, including data declarations, defining a new scope

Some languages have specially delimited compound statements:

begin … end

{ … }

Some control constructs have built-in delimiters:

repeat … until

Python uses indentation!

Selection Statements

A selection statement provides the means of choosing between two or more paths of execution
Two general categories:
Two-way selectors
Multiple-way selectors
Two-Way Selection Statements

Design Issues

The Control Expression

Clause Form

Nesting Selectors

Multiple Selection Constructs

Design Issues

Examples of Multiple Selectors

Multiple Selection Using if

Selection Statements

Two-Way Selection

General form:
if <control_expression>

then <then_clause>

else <else_clause>

Design Issues:
What is the form and type of the control expression?
How are the then and else clauses specified?
How should the meaning of nested selectors be specified?
Design Issues

What is the form and type of the control expression?
How are the then and else clauses specified?
How should the meaning of nested selectors be specified?
Control Expressions

Syntax: Parentheses?

Data type?

Two-Way Selection

Single statements or compound statements?

Single statement example: (FORTRAN)

IF (<boolean_expr>) statement

IF (.NOT.<condition>) GOTO 20

20 CONTINUE

Compound statement example: (ALGOL 60)

if (<boolean_expr>)

then <statement>

else <statement>

Two-Way Selection

Clause Form

Example (Java)

if …

if …

else …

Which if gets the else?

Java’s static semantics rule:

else goes with the nearest if

Two-Way Selection

Nested Selectors

Fortran 95, Ada – closing special words

Examples (Ada)

if … then if … then

if … then if … then

… …

else end if

… else

end if …

end if end if

Advantages: flexibility and readability

Modula-2 uses the same closing special word

for all control structures: END

This results in poor readability

Two-Way Selection

Nested Selectors

Design Issues

1. What is the form and type of the control expression?

2. How are the selectable segments specified?

3. Is execution flow through the structure restricted to include just a single selectable segment?

4. How should unrepresented selector expression values be handled, if at all?

These questions are answered for each example

Multiple Selection

FORTRAN arithmetic IF (a three-way selector)

IF (<arithmetic-expression>) 10,20,30

10 …

GO TO 40

20 …

GO TO 40

30 …

40 …

Multiple Selection

Early Multiple Selectors

case <expression> of

<constant_list_1> : <statement_1>;

<constant_list_n> : <statement_n>

end

Design choices

1. <expression> is any ordinal type

int, boolean, char, enum

2. <statement_i> can be either single or compound

3. Only one segment can be executed per construct execution

4. Unrepresented <expression> not defined

Modern Multiple Selectors

Pascal case

switch (<expression>) {

case <const_expr_1> : <statement_1>;

case <const_expr_n> : <statement_n>;

[default: <statement_n+1>]

}

Design Choices

1. <expression> can be an integer type only

2. <statement_i> can be sequences

3. Many segments can be executed in one construct execution

4. The default clause is for unrepresented values

(without it, the whole statement may do nothing)

Modern Multiple Selectors

The C Langauges switch

Modern Multiple Selectors
The Ada case statement

case <expression> is

when <choice list> => <stmt_sequence>;

when <choice list> => <stmt_sequence>;

when others => <stmt_sequence>;]

end case;

More reliable than C’s switch

Once a <stmt_sequence> execution is completed, control is passed to the first statement after the case statement

Some languages specifically extend the if statement, allowing some of the special words to be left out

else-if sequences are replaced with a single special word elsif and the closing special word on the nested if is dropped

Ada

if Count < 10 then Bag1 := True;

elsif Count < 100 then Bag2 := True;

elsif Count < 1000 then Bag3 := True;

end if;

This is not easily modeled with a case statement, since each selector is a Boolean expression

Multiple Selection

Multiple Selection Using if

Iterative Statements

Counter-Controlled Loops
Design Issues
Fortran 95 Do
Ada for
C languages for
Logically Controlled Loops
Design Issues
Examples
User-Located Loop Control Mechanisms
Iteration Based on Data Structures
Repeated execution of a statement or compound statement can be accomplished either by iteration or recursion

Here we look at iteration

— recursion is unit-level control

General Design Issues

for Iteration Control Statements

How is iteration controlled?

Where is the control mechanism in the loop?

Iterative Statements

Design Issues

1. What are the type and scope of the loop variable?

2. What is the value of the loop variable at loop termination?

3. Should it be legal for the loop variable or loop parameters to be changed in the loop body, and if so, does the change affect loop control?

4. Should the loop parameters be evaluated only once, or once for every iteration?

These questions are answered for each example

Counter-Controlled Loops

Do <label> <var>=<start>,<finish>[,<stepsize>]

[<name>:] Do <var>=<start>,<finish>[,<stepsize>] …

End Do [<name>]

Counter-Controlled Loops

Fortran 95

Design Choices

1. <var> must be Integer

2. After execution, <var> has its last value

3. <var> cannot be changed in the loop

4. Loop parameters can be changed in the loop

Notes: – Cannot branch into either Do

– <stepsize> can be any value but zero

– Loop parameters can be expressions

for <var> in [reverse] <discrete_range> loop

end loop

Counter-Controlled Loops

Ada

Design Choices

1. Type of <var> is that of <discrete_range>; its scope is the loop body

2. <var> does not exist outside the loop

3. <var> cannot be changed in the loop,

<discrete_range> can be changed in the loop

4. <discrete_range> is evaluated only once, so changing it does not affect loop control

Note: Cannot branch into the loop body

for ([<exp1>];[<exp2>];[<exp3>])<statement>

Design Choices

1. There is no explicit loop variable

2. The loop variable (if there is one) has its latest value

3. Everything can be changed in the loop

4. <exp1> is evaluated once, but the other two are evaluated with each iteration

Notes: – The expressions can be statements

or statement sequences

for (i=0,j=10;j==i;i++)…

– If the second expression is absent,

it is an infinite loop

Counter-Controlled Loops

C Languages

The loop statement of the C languages is the most flexible, but there are differences mostly based on the while loop

C99,C++ for:

The control expression is coercised Boolean
The initial expression can include variable definitions (scope is from the definition to the end of the loop body)
Can branch into them
Java,C# for:

The control expression must be Boolean
Branching into the loop? Java no
C# yes

Counter-Controlled Loops

Should the language have a pretest loop or a posttest loop or both?
Should this be a special case of the counter-controlled loop or a completely separate statement?
Logically-Controlled Loops

Design Issues

C Languages have both while-do and do-while

Branching into either loop construct?

C,C++,C# yes

Java no

Ada has a pretest version, but no posttest

Fortran 95 has neither

Perl has two pretest logical loops,

while and until,

but no posttest logical loop

Logically-Controlled Loops

Language Examples

Should the conditional be part of the exit?
Should control be transferable, conditionally or unconditionally, out of more than one nested loop?
User-Located Loop Controls

Design Issues

Ada conditional or unconditional,

for any loop, any number of levels

User-Located Loop Controls

Language Examples

for … loop

exit [when …]

end loop

LOOP1: while … loop

LOOP2: for … loop

exit LOOP1 [when …]

end loop LOOP2;

end loop LOOP1;

C Languages

break

Unconditional, for any loop or switch

C,C++ one level only

Java,Perl,C# multiple levels, by labels

continue

Skips the remainder of this iteration,

but does not exit the loop

Fortran 95

Exit, Cycle

Unconditional

for any loop, any number of levels

User-Located Loop Controls

Language Examples

Concept

Use the order and number of elements of some data structure to control iteration

Control Mechanism

A function call (the iterator) that returns either the next element in a chosen order, if there is one, or else exits the loop

Languages

Specific structures: Perl, PHP, JavaScript, C#

Can be modeled in most languages by functions,

easily so in object-oriented languages

Data Structure Iteration

C,C++ traversing a linked list using pointers

for (p=hdr; p; p=next(p)){…}

C#

String[] strList = {″Bob″,″Carol″, …};

foreach (String name in strList)

System.Console.WriteLine(″Name: {0}″,name);

The foreach statement iterates the elements of any collection that implements IEnumerable

Data Structure Iteration

Examples

Perl has a built-in iterator for arrays and hashes

foreach $name (@names) { print $name }

PHP has predefined iterators to access its arrays

current points at one element of the array

next moves current to the next element

prev moves current to the previous element

reset moves current to the first element

Data Structure Iteration

Examples

C++ iterators are often implemented as friend functions or as separate iterator classes

Java objects of a class implementing the Collection interface can be iterated with an implementation of the Iterator interface

– next() moves the pointer into the collection

– hasNext() is a predicate

– remove() deletes an element

C# can iterate any collection implementing the

IEnumerate interface

– MoveNext() moves the pointer in the collection

– Reset() moves the pointer to the beginning

– Current is the current element

– Can also use foreach to iterate

Data Structure Iteration

User-defined Iteration

General Syntax

goto <Label>

Disadvantage readability

Advantage flexibility

Notes: All control structures can be

built with goto and a selector

Some languages do not have them

Modula-2, Java

Loop exit statements are

camouflaged goto’s

– they are severely restricted

– not harmful to readability

Unconditional Branching

…the quality of programmers is a decreasing function of the density of go to statements in the programs they produce….

…the go to statement should be abolished from all “higher level” programming languages…

The go to statement as it stands is just too primitive; it is too much an invitation to make a mess of one’s program….

Dijkstra, Edsger W., Go To Statement Considered Harmful. Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148.

“Go To Statement

Considered Harmful”

Dijkstra’s remark about the undesirability of the goto statement was not new, and was not final !

1959 Heinz Zemanek expressed doubts

1966 Wirth and Hoare “[multiple selection] mirrors the dynamic structure of a program more clearly than goto statements”

1966 Guiseppe Jacopini proved the (logical) superfluousness of the goto statement

1968 Dijkstra Communications of the ACM

1974 Knuth argued that there were occasions when the efficiency of the goto outweighed its harm to readability

1978 Kernighan and Ritchie called the goto “inifinitely abusable,” but included it in C anyway

“Go To Statement

Considered Harmful”

In computing and related disciplines, considered harmful is a phrase used in the titles of diatribes and other critical essays (there are more than 65 such works).

The March 1987 CACM contained a criticism of Dijkstra’s letter under the title

‘GOTO Considered Harmful’ Considered Harmful.

The May 1987 CACM printed further replies, both for and against, under the title

‘”GOTO Considered Harmful” Considered Harmful’ Considered Harmful?.

Dijkstra’s own response to this controversy was titled

On a somewhat disappointing correspondence.

‘GOTO Considered Harmful’ Considered Harmful

Home

Edsger Dijkstra (1975, 1976)

Purpose

to support a new programming methodology

(verification during program development)

Idea

if the order of evaluation is not important,

the program should not specify one

Used in concurrent programming: CSP, Ada

Used in function definitions: Haskell

Guarded Commands

*

Syntax: if <boolean> -> <statement>

[] <boolean> -> <statement>

[] <boolean> -> <statement>

fi

[] is called a fatbar

Semantics: When this construct is reached:

Evaluate all boolean expressions
If more than one are true,
choose one nondeterministically

If none are true, runtime error
Guarded Commands

Selection

*

Selection Guarded Command
Flow Chart

*

examples (text pp. 367-368)

if i = 0 -> sum := sum + i

[] i > j -> sum := sum + j

[] j > i -> sum := sum + i

fi

if x >= y -> max := x

[] y >= x -> max := y

fi

Guarded Commands

Selection

*

Syntax: do <boolean> -> <statement>

[ ] <boolean> -> <statement>

[ ] <boolean> -> <statement>

od

Semantics: For each iteration:

Evaluate all boolean expressions
If more than one are true,
choose one nondeterministically;

then start loop again

If none are true, exit loop
Guarded Commands

Loop

*

Loop Guarded Command

Flow Chart

*

example (text p. 369)

arrange the values of q1, q2, q3, and q4 so that

q1 <= q2 <= q3 <= q4

do q1 > q2 -> temp := q1; q1 := q2; q2 := temp

[] q2 > q3 -> temp := q2; q2 := q3; q3 := temp

[] q3 > q4 -> temp := q3; q3 := q4; q3 := temp

od

Guarded Commands

Loop

*

Guarded Commands
Rationale

Connection between control statements and program verification is intimate

Verification is impossible with goto statements
Verification is possible with only selection and logical pretest loops
Verification is relatively simple with only guarded commands
*

Conclusions

Choice of control statements beyond selection and logical pretest loops is a trade-off between language size and writability

*

*

*

*

*

*

*

*

*

*

Order now and get 10% discount on all orders above $50 now!!The professional are ready and willing handle your assignment.

ORDER NOW »»