Chapter 8: Statement-Level Control Structures

Topics Overview

Introduction
Selection Statements
Iterative Statements
Unconditional Branching
Guarded Commands
Conclusions

Levels of Control Flow

Control flow can be categorized into three levels:
- Within expressions (discussed in Chapter 7)
- Among program units (discussed in Chapter 9)
- Among program statements (focus of this chapter)

Control Statements: Evolution

Historical Context:
- The control statements in FORTRAN I were closely tied to the hardware of IBM 704.
- The 1960s saw significant research and debate regarding control structures leading to a significant conclusion:
- All algorithms depicted by flowcharts can be coded using only two-way selection and pretest logical loops.

Control Structure Definition

A control structure is defined as a control statement along with the statements it controls for execution.
Design Question: Should a control structure allow for multiple entries?

Selection Statements

Purpose: A selection statement facilitates the choice between multiple paths of execution.
Categories:
- Two-way selectors
- Multiple-way selectors

Two-Way Selection Statements

General Form:

  if control_expression then clause else clause

Design Issues:
- Form and type of the control expression?
- Specification method of the then and else clauses?
- Clarity in meaning for nested selectors?

The Control Expression

If neither the then keyword nor any syntactic marker introduces the then clause, the control expression must be enclosed in parentheses.
In languages like C89, C99, Python, and C++, the control expression can be an arithmetic expression; most others require it to be Boolean.

Clause Form

In several modern languages, the then and else clauses may either be single statements or compound statements.
Perl: All clauses are required to be defined by braces (denoting they must be compound).
Python and Ruby: Clauses are statements sequences, with Python using indentation for clause definition.

  if x > y:  
      x = y  
      print "x was greater than y"

Nesting Selectors Examples

Java Example:

  if (sum == 0)  
      if (count == 0)  
          result = 0;  
      else  
          result = 1;

In Java, the else associates with the nearest preceding if due to static semantics rules.
To enforce different semantics, one can use compound statements:

  if (sum == 0) {  
      if (count == 0)  
          result = 0;  
      } else  
          result = 1;  
  }

Python Example:

  if sum == 0:  
      if count == 0:  
          result = 0  
      else:  
          result = 1

Selector Expressions

In languages such as ML, F#, and Lisp, a selector can be formulated as an expression.
Example in F#:

  let y =  
      if x > 0 then x  
      else 2 * x

An else clause is essential if the if expression is expected to yield a value, ensuring that the types of values returned by the then and else clauses are consistent.

Multiple-Way Selection Statements

These statements enable the selection of one from many statements or statement groups, with several design issues:
- Control expression type and form?
- Definition of selectable segments?
- Execution flow limitations: is it restricted to a single selectable segment?
- Specification of case values?
- Handling of unrepresented expression values?

Examples of Multiple-Way Selection

C, C++, Java, and JavaScript: The switch statement is used.

  switch (expression) {  
      case const_expr1: stmt1;  
      ...  
      case const_exprn: stmtn;  
      [default: stmtn+1]  
  }

C Language Design Choices:
- The control expression is limited to integer types.
- Selectable segments can be statements or compound statements.
- There's the possibility of executing multiple segments in a single execution without an implicit branching at segment end.
- The default clause addresses any unrepresented cases (without a default, no execution occurs).
C#:
- The switch differs from C as it prohibits implicit multisegment execution.
- Each segment must close with an unconditional branch (either goto or break).
- The control expression can also use strings as case constants.

Ruby Case Statement Example

Ruby includes two forms for case statements, one defined as:

  leap = case  
      when year % 400 == 0 then true  
      when year % 100 == 0 then false  
      else year % 4 == 0  
  end

Implementing Multiple Selectors

Strategies for implementation may include:
- Utilizing multiple conditional branches.
- Storing case values within a table and employing linear table searching.
- Using a hash table when there are more than ten cases.
- If most of the overall range of case values are represented (over half), one can implement an array indexed by case values with associated case labels.

Multiple-Way Selection Using if Statements

Extensions to two-way selectors utilizing else-if clauses.
Example in Python:

  if count < 10:  
      bag1 = True  
  elif count < 100:  
      bag2 = True  
  elif count < 1000:  
      bag3 = True

The above Python logic is convertible to a Ruby case:

  case    
      when count < 10 then bag1 = true  
      when count < 100 then bag2 = true  
      when count < 1000 then bag3 = true  
  end

Scheme’s Multiple Selector Example

General structure of a call to COND:

  (COND  
      (predicate1 expression1)  
      ...  
      (predicaten expressionn)  
      [(ELSE expressionn+1)]  
  )

The ELSE clause is optional and synonymous with true. Each predicate-expression pair acts as a parameter.
Semantics: The value of the evaluation of COND corresponds to the expression linked with the first true predicate expression.

Iterative Statements

Iteration allows repeated execution of statements or compound statements, achieved via either iteration or recursion.
General design issues for iteration control statements root from:
1. How iteration is governed?
2. The position of the control mechanism within the loop.

Counter-Controlled Loops

A counting iterative statement features a loop variable along with specifications for the initial value, terminal value, and stepsize.
Design Issues:
- Type and scope considerations for the loop variable?
- Is modification of the loop variable or parameters within the loop body allowed?
- Should loop parameters only evaluate once or with each iteration?
- The value of the loop variable post-termination?

Examples of Counter-Controlled Loops

C-Based Languages Syntax:

  for ([expr_1]; [expr_2]; [expr_3]) statement

Here: expressions can encompass whole statements or sequences segmented by commas, with the last statement's value acting as the expression’s evaluation.
If the second expression is absent, it defaults to an infinite loop.
Design Choices in C include: no explicit loop variable, all variables are mutable in the loop, the first expression evaluates once, while the second condition repeats across iterations, and branching into the body of the loop is sanctioned.
C++ Differences from C:
- Control expressions can also be Boolean.
- Initial expressions may define variables (scope from definition through loop body end).
Java and C#:
- Control expressions must strictly be Boolean.
Python For Loop Syntax:

  for loop_variable in object:  
      loop body  
      [else:  
          - else clause]

Typical object: a range defined either as a list or calling the range function.
The loop variable adopts the values from the specified range per iteration, and at termination, it retains the last assigned value. The optional else clause executes if the loop concludes without a break.
F# Counter-Controlled Loops:
- Lacking variables, counter-controlled loops are simulated through recursive functions:

  let rec forLoop loopBody reps =  
      if reps <= 0 then ()  
      else  
          loopBody();  
          forLoop loopBody (reps - 1)

The above syntax defines a recursive function with parameters for the loop body and repetition count, where () signifies no output or return value.

Logically-Controlled Loops

For these loops, repetition control hinges on a Boolean expression.
Design Issues:
- Pretest versus posttest nature?
- Should logically controlled loops be a specific case of counting loops or stand as a separate statement?

Examples of Logically-Controlled Loops

C/C++ Syntax: Two forms exist for pretest and posttest iterations, where control expressions can be arithmetic:

  while (control_expr) do loop body  
  loop body while (control_expr)

Valid to branch into a logically controlled loop body; Java mimics this but mandates Boolean types for control expressions, entering the body exclusively at the start.
F# Simulated Logically-Controlled Loops:

  let rec whileLoop test body =  
      if test() then  
          body();  
          whileLoop test body  
      else ()

The function whileLoop is recursively defined with parameters for the control check and loop body, where test defines the control condition.

User-Located Loop Control Mechanisms

Programmers may prefer defining loop control locations distinct from the loop's top or bottom.
Design considerations for nested loops include:
- Should the exit condition form part of the exit?
- Is it permissible to transfer control out of multiple loops?

Examples of User-Located Loop Control

Languages enabling unconditional unlabeled exits (e.g., break): C, C++, Python, Ruby.
Languages with unconditional labeled exits: Java and Perl (using break in Java, and last in Perl).
Language paradigms like C, C++, and Python providing an unlabeled control statement (e.g., continue) can skip current iteration while remaining within the loop. Java and Perl offer labeled alternatives.

Iteration Based on Data Structures

Loop iteration is controlled by the element count within a data structure.
The control mechanism may trigger an iterator function that returns the next data structure element until completion, leading to loop termination.

Examples of Iteration Based on Data Structures

C's For Loop as User-defined Iterator:

  for (p=root; p!=NULL; traverse(p)){  
      ...  
  }

PHP Iteration Rights:
- current positions at an array element.
- next advances current to the next element.
- reset moves current back to the first element.
Java 5.0 Iterator Syntax:
- Iteration utilizes the for statement, often referred to as foreach. For classes implementing the Iterable interface, such constructs can be employed, e.g., ArrayList.
C#, F# and .NET Variants:
- Utilize generic library classes, allowing iteration through arrays, lists, stacks, and queues with foreach. User-defined collections may also implement the IEnumerator interface for foreach use.

  List<String> names = new List<String>();  
  names.Add("Bob");  
  names.Add("Carol");  
  names.Add("Ted");  
  foreach (String name in names)

Ruby Iteration With Blocks

Ruby blocks consist of code sequences framed in either braces or do...end.
These blocks can function collaboratively with methods to create iterators.
Predefined Iteration Methods in Ruby:

  3.times {puts "Hey!"}  
  list.each {|value| puts value}  
  1.upto(5) {|x| print x, " "}

Blocks function via attaching method calls and can retain parameters (through vertical bars), executing yield statements when engaged.
Example of Ruby Iterator Utilizing Yield Statement:

  first, second = 1, 1  
  def fibonacci(last)  
      while first <= last  
          yield first  
          first, second = second, first + second  
      end  
  end  
  puts "Fibonacci numbers less than 100 are:"  
  fibonacci(100) {|num| print num, " "}

Ruby has a for statement that translates into upto method calls internally.

Python's Yield Statement

Illustrated with a function that generates nodes within a data structure:

  def traverse(self):  
      yield node

Every call to traverse returns the next node in the structure.
The yield statement functions similarly to return, but alters the function's semantics significantly as it operates in an independent control thread, resuming from its last execution state in subsequent calls, thereby marking it as history-sensitive.

Unconditional Branching

Definition: Unconditional branching entails the transfer of execution control to a specific location within the program code.
Historical Context: The use of this feature was a topic of intense debate through the 1960s and 1970s, primarily concerning readability concerns.
Languages like Java do not support the goto statement, whereas C# permits its use (notably within switch statements).
Other loop exit statements can be regarded as camouflaged forms of goto.

Guarded Commands

Creation: Designed by Edsger Dijkstra to facilitate a new programming methodology aimed at supporting verification (correctness) in program development.
Serve as a foundation for concurrent programming mechanisms introduced in CSP (Communicating Sequential Processes).
Fundamental Principle: The order of evaluation shouldn't hold importance if specified by the program.

Selection Guarded Command

Structure:

  if <Boolean expr> -> <statement> [] <Boolean expr> -> <statement> ... [] <Boolean expr> -> <statement> fi

Semantics: Upon reaching this construct:
- All Boolean expressions are evaluated.
- If multiple conditions hold true, one is chosen non-deterministically.
- If none are true, it results in a runtime error.

Loop Guarded Command

Structure:

  do <Boolean> -> <statement> [] <Boolean> -> <statement> ... [] <Boolean> -> <statement> od

Semantics: During each iteration:
- Evaluate all Boolean expressions.
- If more than one condition is true, select one non-deterministically and repeat the loop.
- If no conditions are valid, the loop exits.

Rationale Behind Guarded Commands

The interplay between control statements and program verification is crucial.
Verification is unfeasible with goto statements.
It's achievable via mechanisms incorporating only selection and logical pretest loops.
Verification simplifies considerably when structured solely around guarded commands.

Conclusions

A diverse range of statement-level structures exists.
Selecting appropriate control statements, beyond simple selections and logical pretest loops, involves balancing language size with usability (writability).
Notably, functional and logic programming languages deploy control structures that diverge markedly from procedural habituations.