CS124 - Programming Language - Statement-Level Control Struc

Statement-Level Control Structures

Overview

•Control Statements

–Allow selecting among alternative control flow paths (of statement execution).

–Means of causing the repeated execution of statements or sequences of statements.

•The control statements of the first successful programming language, Fortran, were, in effect, designed by the architects of IBM 704.

•A control structure is a control statement and the collection of statements whose execution it controls.

–Selection Statements

–Iterative Statements

•There is only one design issue that is relevant to all of the selection and iteration control statements:

–Should a control structure have multiple entries?

Selection Statements

•A selection statement provides the means of choosing between two or more paths of execution.

•Selection statement fall into two general categories:

–Two-way selection

–Multiple-way selection

Selection Statements:

Two-Way Selection Statements

•The general form of a two-way selector is as follows:

if control_expression

 then clause

 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?

Two-Way Selection Statements

The Control Expression

•Control expressions are specified in parenthesis if the then reserved word is not used to introduce the then clause, as in the C-based languages.

•In C89, which did not have a Boolean data type, arithmetic expressions were used as control expressions.

•In contemporary languages, such as Java and C#, only Boolean expressions can be used for control expressions

•In most contemporary languages, the then and else clauses either appear as single statements or compound statements.

•C-based languages use braces to form compound statements.

•One exception is Perl, in which all then and else clauses must be compound statements, even if they contain single statements.

•In Python and Ruby, clauses are statement sequences.

•Python uses indentation to define clauses

if x > y :

 x = y

 print " x was greater than y"

'rather than using then, colon is introduced.

Fill in the Blank

What symbol is used to denote a compound statement?

Fill in the Blank

What programming language must let all then and else clause be in compound statements?

Two-Way Selection Statements

Clause Form: Nesting Selectors

•In Java and contemporary languages, the static semantics of the language specify that the else clause is always paired with the nearest unpaired then clause.

 if (sum == 0)

  if (count == 0)

 result = 0;

 else

 result = 1;

Two-Way Selection Statements

Clause Form: Nesting Selectors

cont...

•A rule, rather than a syntactic entity, is used to provide the disambiguation (distinguish which if is paired to the else)

•So, in the example, the else clause would be the alternative to the second then clause

•To force the alternative semantics in Java, a different syntactic form is required, in which the inner if is put in a compound, as in

 if (sum == 0) {

 if (count == 0)

 result = 0;

 }

 else

 result = 1;

Two-Way Selection Statements

Clause Form: Nesting Selectors

•C, C++, and C# have the same problem as Java with selection statement nesting

•Ruby, statement sequences as clauses

 if sum == 0 then

 if count == 0 then

  result = 0

  else

  result = 1

 end

 end

- The if-else statement in Ruby avoids the problem with the end clause.

Selection Statements:

Multiple Selection Constructs

•The multiple selection construct allows the selection of one of any number of statements or statement groups.

Design Issues

– What is the form and type of the control expression?

– How are the selectable segments specified?

– Is execution flow through the structure restricted to include just a single selectable

segment?

– How are case values specified?

– What is done about unrepresented expression values?

Selection Statements:

Multiple Selection Constructs

•In C, C++, Java, and JavaScript switch

switch (expression) {

case constant_expression1 : statement1;

 ...

 case constant_expressionn : statementn;

 [default: statementn+1]

}

– The control expression and the constant expressions some discrete type including integer types as well as character and enumeration types

– The selectable statements can be statement sequences, blocks, or compound statements

– Any number of segments can be executed in one execution of the construct (there is no implicit branch at the end of selectable segments)

Selection Statements:

Multiple Selection Constructs

cont...

– default clause is for unrepresented values (if there is no default, the whole statement does nothing)

– Any number of segments can be executed in one execution of the construct (a trade-off between reliability and flexibility—convenience.)

– To avoid it, the programmer must supply a break statement for each segment

Selection Statements:

Multiple Selection Constructs

•C# switch

•C# switch statement differs from C-based in that C# has static semantic rule disallows the implicit execution of more than one segment

– The rule is that every selectable segment must end with an explicit unconditional branch statement either a break, which transfers control out of the switch construct, or a goto, which can transfer control to on of the selectable segments.

Selection Statements:

Multiple Selection Constructs

C# switch statement example:

switch (value) {

 case -1: Negatives++;

 break;

 case 0: Zeros++;

 goto case 1;

 case 1: Positives ++;

 default: Console.WriteLine(“Error in switch \n”);

}

Selection Statements:

Multiple Selection Constructs

•Multiple Selection Using if

•Multiple Selectors can appear as direct extensions to two-way selectors, using else-if clauses

– Ex, Python selector statement (note that else-if is spelled elif in Python):

if count < 10 :

 bag1 = True

elif count < 100 :

 bag2 = True

elif count < 1000 :

 bag3 = True

Fill in the Blank

What programming language must end with an explicit unconditional branch statement either a break or goto statement?

Multiple Choice

What type of multiple selection constructs is used as direct extensions to two-way selectors?

• If statement

• Switch statement

• else-if Statement

Iterative Statements

•An iterative statement is one that cause a statement or collection of statements to be executed zero, one, or more times

•The repeated execution of a statement or compound statement is accomplished either by iteration or recursion

•An iterative statement is often called loop

•Iteration is the very essence of the power of computer.

•The repeated execution of a statement is often accomplished in a functional language by recursion rather than by iteration

Iterative Statements

-Recursion is when a statement in a function calls itself repeatedly.

-Iteration is when a loop repeatedly executes until the controlling condition becomes false.

Fill in the Blank

____ is when a statement in a function calls itself repeatedly.

Fill in the Blank

When a loop repeatedly executes until the controlling condition becomes false.

Iterative Statements:

Counter-Controlled Loops

•A counting iterative control statement has a variable, called the loop variable, in which the count value is maintained.

•It also includes means of specifying the initial and terminal values of the loop variable, and the difference between sequential loop variable values, called the stepsize.

•The initial, terminal and stepsize are called the loop parameters.

•Design issues:

– What are the type and scope of the loop variable?

– 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?

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

The general form of C’s for statement is

for (expression_1; expression_2; expression_3)

 loop body

The loop body can be a single statement, a compound statement, or a null statement

for (count = 1; count <= 10; count++)

. . .

– All of the expressions of C’s for are optional

– If the second expression is absent, it is an infinite loop

– If the first and third expressions are absent, no assumptions are made

Fill in the Blank

What do you call the difference between sequential loop variable values?

Multiple Select

Which of the following are the loop parameters? (select appropriate answers)

• Initial

• terminal

• stepsize

• expression

Iterative Statements:

Counter-Controlled Loops

• The C-based languages for design choices are:

- There are no explicit loop variable or loop parameters

- All involved variables can be changed in the loop body

- First expression is evaluated once, but the other two are evaluated with each iteration

- It is legal to branch into the body of a for loop in C

Iterative Statements:

Counter-Controlled Loops

•C’s for is more flexible than the counting loop statements of Fortran and Ada, because each of the expressions can comprise multiple statements, which in turn allow multiple loop variables that can be of any type

– Consider the following for statement:

for (count1 = 0, count2 = 1.0; count1 <= 10 && count2 <= 100.0;

sum = ++count1 + count2, count2 *= 2.5)

;

Iterative Statements:

Counter-Controlled Loops

Cont…

The operational semantics description of this is:

count1 = 0

count2 = 1.0

loop:

 if count1 > 10 goto out

 if count2 > 100.0 goto out

 count1 = count1 + 1

 sum = count1 + count2

 count2 = count2 * 2.5

 goto loop

out:

. . .

The example C for statement above does not need and thus does not have a loop body. All the desired actions are part of the for statement itself, rather than in its body

Iterative Statements:

Counter-Controlled Loops

•The for statement of C99 and C++ differs from earlier version of C in two ways:

▪ It can use an arithmetic expression or a Boolean expression for loop control

▪ The first expression can include variable definitions (scope is from the definition to the end of the loop body), for example

for (int count = 0; count <= 10; count++) { . . . }

– The for statement of Java and C# is like that of C++, except that the loop control expression is restricted to Boolean

Multiple Choice

TRUE OR FALSE

In the for statement of Java and C#, the loop control expression is restricted to Boolean.

• True

• False

Iterative Statements:

Counter-Controlled Loops

•The for statement of Python

•– The general form of Python’s for is:

for loop_variable in object:

 - loop body

[else:

 - else clause]

Iterative Statements:

Counter-Controlled Loops

cont...

– The object is often range, which is either a list of values in brackets ([2, 4, 6]), or a call to the range function (range(5), which returns 0, 1, 2, 3, 4)

– The loop variable takes on the values specified in the given range, one for each iteration

– The else clause, which is optional, is executed if the loop terminates normally

– Consider the following example:

for count in [2, 4, 6] :

 print count

Iterative Statements:

Counter-Controlled Loops

•The for statement of C99 and C++ differs from earlier version of C in two ways:

▪ It can use an arithmetic expression or a Boolean expression for loop control

▪ The first expression can include variable definitions (scope is from the definition to the end of the loop body), for example

for (int count = 0; count <= 10; count++) { . . . }

– The for statement of Java and C# is like that of C++, except that the loop control expression is restricted to Boolean

Multiple Choice

TRUE OR FALSE:

The for statement of C99 and C++ differ from the earler version of C is that It can use an arithmetic expression or a Boolean expression for loop control

• True

• False

Iterative Statements:

Counter-Controlled Loops

•The for statement of Python

•– The general form of Python’s for is:

for loop_variable in object:

 - loop body

[else:

 - else clause]

Iterative Statements:

Counter-Controlled Loops

– The object is often range, which is either a list of values in brackets ([2, 4, 6]), or a call to the range function (range(5), which returns 0, 1, 2, 3, 4)

– The loop variable takes on the values specified in the given range, one for each iteration

– The else clause, which is optional, is executed if the loop terminates normally

– Consider the following example:

for count in [2, 4, 6] :

 print count

Multiple Select

In Python;s for loop. the syntax is:

for loop_variable in object:

- loop body

What are often objects used in range? (select appropriate answers)

• list of values

• a call to the range function

• boolean expression

Iterative Statements:

Logically Controlled Loops 

•Repetition control is based on a Boolean expression rather than a counter

•Design Issues:

– Should the control be pretest or posttest?

– Should the logically controlled loop be a special form of a counting loop or a separate statement?

•The C-based programming languages include both pretest and posttest logically controlled loops that are not special forms of their counter-controlled iterative statements

•The pretest and posttest logical loops have the following forms (while and do-while):

Iterative Statements:

Logically Controlled Loops 

•The only real difference between the do and the while is that the do always causes the loop body to be executed at least once

•Java’s while and do statements are similar to those of C and C++, except the control expression must be Boolean type, and because Java does not have a goto, the loop bodies cannot be entered anywhere but at their beginning.

Fill in the Blank

A pretest is in a form of what type of statement/repetitive control structure?

Fill in the Blank

A loop statement that causes the loop body to be executed at least once.

Iterative Statements:

User-Located Loop Control Mechanisms

•It is sometimes convenient for a programmer to choose a location for loop control other than the top or bottom of the loop

•Design issues:

– Should the conditional mechanism be an integral part of the exit?

– Should only one control body be exited, or can enclosing loops also be exited?

Iterative Statements:

User-Located Loop Control Mechanisms

C and C++ have unconditional unlabeled exits (break)

• Java, Perl, and C# have unconditional labeled exits (break in Java and C#, last in Perl)

• The following is an example of nested loops in C#:

outerLoop:

 for (row = 0; row < numRows; row++)

  for (col = 0; col < numCols; col++) {

 sum += mat[row][col];

 if (sum > 1000.0)

  break outerLoop; //break

 }

Iterative Statements:

User-Located Loop Control Mechanisms

•C and C++ include an unlabeled control statement, continue, that transfers control to the control mechanism of the smallest enclosing loop

• This is not an exit but rather a way to skip the rest of the loop statements on the current iteration without terminating the loop structure. Ex:

while (sum < 1000) {

getnext(value);

if (value < 0) continue; //if value is less than 0 then go back to top of loop

sum += value;

}

A negative value causes the assignment statement to be skipped, and control is transferred instead to the conditional at the top of the loop

Fill in the Blank

What is the unconditional label exit in Java and C#?

Fill in the Blank

What is the unlabeled control statement in C and C++ that transfers control to the control mechanism of the smallest enclosing loop?

Iterative Statements:

User-Located Loop Control Mechanisms

•On the other hand, in

while (sum < 1000) {

 getnext(value);

 if (value < 0) break; //A negative value terminates the loop

 sum += value;

}

•Java, Perl, and C# have statements similar to continue, except they can include labels that specify which loop is to be continued.

• The motivation for user-located loop exits is simple: They fulfill a common need for goto statements through a highly restricted branch statement

• The target of a goto can be many places in the program, both above and below the goto itself

• However, the targets of user-located loop exits must be below the exit and can only follow immediately the end of a compound statement.

Fill in the Blank

In a loop statement, what does Java, Perl and C# include in an unconditional control statement (break, continue, goto) to specify what part of the program should be executed?

Iterative Statements:

Iteration Based on Data Structures

•A general data-based iteration statement uses a user-defined data structure and a user-defined function (the iterator) to go through the structure’s elements

•The iterator is called at the beginning of each iteration, and each time it is called, the iterator

•return an element from a particular data structure in some specific order

•C's for can be used to build a user-defined iterator:

for (ptr=root; ptr==NULL; ptr = traverse(ptr)) {

. . .

}//In this statement, traverse is the iterator.

Iterative Statements:

Iteration Based on Data Structures

•User-defined iteration statements are more important in object-oriented programming than they were in earlier software development paradigms because users of object-oriented programming routinely use abstract data types for data structures, especially collections.

•In such cases, a user-defined iteration statement and its iterator must be provided by the author of the data abstraction because the representation of the objects of the type is not known to the user.

Iterative Statements:

Iteration Based on Data Structures

•Java 5.0 uses for, although it is called foreach

•The following statement would iterate though all of its elements, setting each to myElement:

for (String myElement : myList) { . . . }

•The new statement is referred to as “foreach,” although is reserved word is for

Iterative Statements:

Iteration Based on Data Structures

•C#’s foreach statement iterates on the elements of array and other collections

•C# and F# (and the other .NET languages) have generic library classes, like Java 5.0 (for arrays, lists, stacks, and queues)

•For example, there are generic collection classes for lists, which are dynamic length array, stacks, queues, and dictionaries (has table)

•All of these predefined generic collections have built-in iterator that are used implicitly with the foreach statement

Furthermore, users can define their own collections and write their own iterators, implement the IEnumerator interface, which enables the use of use foreach on these collections

Multiple Choice

What loop statement in Java or in C# is used to iterate through all its elements in an collection such as an array?

• for loop

• while loop

• do-while loop

• foreach

Unconditional Branching

•An unconditional branch statement transfers execution control to a specified place in the program

•The unconditional branch, or goto, is the most powerful statement for controlling the flow of execution of a program’s statements

•However, using the goto carelessly can lead to serious problems

•Without restrictions on use, imposed by either language design or programming standards, goto statements can make programs very difficult to read, and as a result, highly unreliable and costly to maintain.

Unconditional Branching

•There problems follow directly from a goto’s ability to force any program statement to follow any other in execution sequence, regardless of whether the statement proceeds or follows previously executed statement in textual order

•Java, Python, and Ruby do not have a goto. However, most currently popular languages include a goto statement

•C# uses goto in the switch statement

Multiple Choice

An ____ statement transfers execution control to a specified place in the program, it has the ability to force any program statement to follow any other in execution sequence, regardless of whether the statement proceeds or follows previously executed statement in textual order.

• unconditional control

• unconditional branch

• unlabeled control

Guarded Commands

•New and quite different forms of selection and loop structures were suggested by Dijkstra (1975)

•His primary motivation was to provide control statements that would support a new program design methodology that ensured correctness (verification) during development rather than when verifying or testing completed programs.

•Basis for two linguistic mechanisms for concurrent programming in CSP (Hoare, 1978)

•Basic idea: if the order of evaluation is not important, the program should not specify one

Guarded Commands

•Dijkstra’s selection guarded command has the form

if <Boolean expr> -> <statement>

[] <Boolean expr> -> <statement>

...

[] <Boolean expr> -> <statement>

fi

•Semantics: when construct is reached,

– Evaluate all Boolean expressions

– If more than one are true, choose one non-deterministically (

– If none are true, it is a runtime error

Guarded Commands

Ex

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

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

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

fi

– If i = 0 and j > i, this statement chooses non-deterministically between the first and third assignment statements

– If i is equal to j and is not zero, a run-time error occurs because none of the condition are true

Guarded Commands

•The loop structure proposed by Dijkstra has the form

do <Boolean> -> <statement>

[] <Boolean> -> <statement>

...

[] <Boolean> -> <statement>

od

•Semantics: for each iteration

– Evaluate all Boolean expressions

– If more than one are true, choose one non-deterministically; then start loop again

– If none are true, exit loop

Guarded Commands

•Ex Consider the following problem: Given four integer variables, q1, q2, q3, and q4, rearrange the values of the four so that q1 ≤ q2 ≤ q3 ≤ q4

•Without guarded commands, one straightforward solution is to put the four values into an array, sort the array, and then assign the values from the array back into the scalar variables q1, q2, q3, and q4. While this solution is not difficult, it requires a good deal of code, especially if the sort process must be included.

Guarded Commands

•Now, uses guarded commands to solve the same problem but in a more concise and elegant way

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

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

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

od

Guarded Commands

•Dijkstra’s guarded command control statements are interesting, in part because they illustrate how the syntax and semantics of statements can have an impact on program verification and vice versa.

•Program verification is impossible when goto statements are used

•Verification is greatly simplified if

– only selection and logical pretest loops

– only guarded commands

Multiple Choice

In a guarded clause, when more than one boolean expression is true, how is the selection of guarded statement(s)?

• only one guarded statement that has a true boolean expression is selected.

• No guarded statement will be selected.

• among the guarded statement one is chosen non-deterministically

• a run-time error occurs.

•Dijkstra’s guarded command control statements are interesting, in part because they illustrate how the syntax and semantics of statements can have an impact on program verification and vice versa.

•Program verification is impossible when goto statements are used

•Verification is greatly simplified if

– only selection and logical pretest loops

– only guarded commands

Multiple Choice

In a guarded clause, when more than one boolean expression is true, how is the selection of guarded statement(s)?

• only one guarded statement that has a true boolean expression is selected.

• No guarded statement will be selected.

• among the guarded statement one is chosen non-deterministically

• a run-time error occurs.

Multiple Choice

In a guarded clause, when more than one boolean expression is true, how is selection of guarded statement(s)?

• only one guarded statement that has a true Boolean expression is selected.

• No guarded statement will be selected.

• among the guarded statement one is chosen non-deterministically

• a run-time error occurs.