Programming langauge help
crazybob3Chapter 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
http://www.considered-harmful.org/
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
*