Statement-Level Control Structures Notes

Introduction and Evolution of Control Flow

Levels of Control Flow * Within Expressions: Covered in Chapter 7. * Among Program Units: Covered in Chapter 9. * Among Program Statements: The primary focus of this chapter (Chapter 8).
Evolution of Control Statements * FORTRAN I: The control statements in this early language were based directly on the hardware of the $IBM\,704$ . * Research in the 1960s: Significant research and debate centered on control flow. * Key Theoretical Result: It was proven that all algorithms represented by flowcharts can be coded using only two types of control structures: * Two-way selection. * Pretest logical loops.

Fundamental Concepts of Control Structures

Definition: A control structure consists of a control statement and the set of statements whose execution it governs.
Design Question: A major design consideration is whether a control structure should allow multiple entry points.

Selection Statements

Purpose: Provides a mechanism for choosing between two or more execution paths.
General Categories: * Two-way selectors. * Multiple-way selectors.

Two-Way Selection Statements

General Form: if control_expression then clause else clause.
Design Issues: * What are the form and data type of the control expression? * How are the then and else clauses specified? * How is the meaning of nested selectors defined?
The Control Expression: * If a syntactic marker like the reserved word then is not used, the control expression is typically enclosed in parentheses. * Arithmetic Expressions: In $C89$ , $C99$ , Python, and $C++$ , control expressions can be arithmetic. * Boolean Expressions: Most other modern languages require the control expression to be strictly Boolean.
Clause Form: * Most contemporary languages allow clauses to be single statements or compound statements. * Perl: Requires all clauses to be delimited by braces (making them compound statements). * Python/Ruby: Use statement sequences. Python specifically uses indentation to define clauses. Example: python if x > y : x = y print " x was greater than y"         
Nesting Selectors (The Dangling Else Problem): * Example in Java: java if (sum == 0) if (count == 0) result = 0; else result = 1;          * Java Static Semantics: The else is matched with the nearest previous if that does not have an else. * Manual Control: Braces/compound statements can force alternative semantics. This is the common solution in $C$ , $C++$ , and C#. * Ruby: Uses the end keyword to explicitly terminate blocks. * Python: Uses indentation levels to associate else clauses with the correct if level.
Selector Expressions: * In languages like ML, F#, and Lisp, the selector is an expression rather than a statement. * Example in F#: let y = if x > 0 then x else 2 * x. * Rules for Expressions: 1. If the if expression returns a value, the else clause is mandatory (unless it produces a unit type). 2. The types of the values returned by the then and else clauses must be identical.

Multiple-Way Selection Statements

Purpose: Allows the program to select one out of any number of statements or groups of statements.
Design Issues: * Form and type of the control expression. * Specification of selectable segments. * Restriction of execution flow (e.g., does it only execute one segment or fall through?). * Specification of case values. * Handling of unrepresented expression values.
C, C++, Java, and JavaScript Switch: * Form: switch (expression) { case const_expr1: stmt1; ... default: stmtn+1 }. * C Design Choices: 1. Control expression must be an integer type. 2. Segments can be sequences, blocks, or compound statements. 3. No implicit branch; any number of segments can execute (fall-through) unless a break is used. 4. The default clause handles unrepresented values; without it, the statement does nothing.
C# Switch: * Disallows implicit execution of multiple segments (no fall-through). * Every segment must end with an unconditional branch like goto or break. * Allows strings as control expressions and case constants.
Ruby Case Statements: example of using case as an expression: ruby leap = case when year % 400 == 0 then true when year % 100 == 0 then false else year % 4 == 0 end     
Implementation Approaches: * Multiple conditional branches. * Linear search of a case value table. * Hash tables for more than $10$ cases. * Jump tables (arrays of labels) if the range of values is small and dense (more than half of the range is represented).
Multiple-Way Selection Using if: * Can be implemented using else-if or Python's elif structure.
Scheme COND: * General Form: (COND (predicate1 expression1) ... (ELSE expressionn+1)). * ELSE is a synonym for true. * Evaluates to the value of the expression associated with the first true predicate.

Iterative Statements

General Concepts: Accomplished via iteration or recursion.
Design Issues: How is iteration controlled? Where is the control mechanism located (top or bottom)?

Counter-Controlled Loops

Components: Loop variable, initial value, terminal value, and stepsize.
General Design Issues: * Type and scope of the loop variable. * Legality of changing the loop variable or parameters within the body and its effect on control. * Frequency of parameter evaluation (once vs. every iteration). * The value of the variable after the loop terminates.
C-Based Languages: * for ([expr_1] ; [expr_2] ; [expr_3]) statement. * Expressions can be statement sequences separated by commas; the value is the last statement's value. * If expr_2 is absent, the loop is infinite. * No explicit loop variable required; everything can be changed in the body. * Branching into the body is permissible in $C$ .
C++ Differences: Control expression can be Boolean. Variables defined in the initial expression have scope until the end of the loop.
Java and C# Differences: The control expression MUST be Boolean.
Python: * for loop_variable in object:. * object is usually a range (e.g., [2, 4, 6] or range(5) which is $0, 1, 2, 3, 4$ ). * Loop variable retains its last assigned value upon termination. * An optional else clause executes if the loop terminates normally.
F# Simulation: Functional languages simulate counter loops with recursion: fsharp let rec forLoop loopBody reps = if reps <= 0 then () else loopBody() forLoop loopBody (reps - 1)

Logically-Controlled Loops

Control: Based on a Boolean expression.
Design Issues: Pretest (check before body) or posttest (check after body)? Should it be a separate statement type?
Examples: * C/C++: Both while (pretest) and do-while (posttest) exist. Control expressions can be arithmetic. Branching into the body is legal. * Java: Similar to $C$ , but expressions must be Boolean and the body can only be entered at the start. * F#: Simulated with recursion using functions for test and body.

User-Located Loop Control

Mechanisms: Allow programmers to decide where the loop should break (not just top or bottom).
Design Issues: Is the exit conditional? Can it exit multiple nested loops?
Keywords: * break: Unconditional unlabeled exit in $C$ , $C++$ , Python, Ruby, and C#. * break (Java) / last (Perl): Unconditional labeled exits for nested structures. * continue: Unlabeled statement to skip the remainder of the current iteration ( $C$ , $C++$ , Python). * Java and Perl also provide labeled versions of continue (Perl uses next).

Iteration Based on Data Structures

Concept: The number of elements in a data structure controls the iteration.
Mechanism: An iterator function returns the next element or terminates the loop.
PHP: Uses internal pointers: current, next, and reset functions.
Java 5.0 (foreach): Works for arrays and any class implementing the Iterable interface.
C# and F#: Iterate over generic library classes (lists, stacks, queues) using foreach. Uses the IEnumerator interface.
Ruby: * Uses blocks delimited by braces {} or do...end. * Predefined methods: times, each, upto. * Example: 3.times {puts "Hey!"}. * Iterators use the yield statement to execute the attached block.
Python yield: * Functions containing yield are called generators. * yield is similar to return but maintains the state of the function. * The function runs in its own thread of control; subsequent calls act like a "resume," making it history-sensitive.

Unconditional Branching and Guarded Commands

Unconditional Branching (goto)

Transfers control to a specific location.
Sparked intense debate in the 1960s/70s over concerns regarding readability.
Java: Does not support goto.
C#: Supports goto (often used in switch statements).
Loop exit statements are essentially restricted, "camouflaged" goto statements.

Guarded Commands

Origins: Designed by Edsger Dijkstra to support program verification (correctness) during development.
Rationale: To allow concurrent programming (CSP) and to avoid specifying an execution order when the order is unimportant.
Selection Guarded Command: * if <Boolean expr> -> <statement> [] ... fi. * Semantics: Evaluate all Booleans. If multiple are true, pick one non-deterministically. If none are true, runtime error occurs.
Loop Guarded Command: * do <Boolean> -> <statement> [] ... od. * Semantics: Evaluate all Booleans. If any are true, pick one non-deterministically and repeat the loop. If none are true, exit the loop.
Verification: Guarded commands facilitate simpler program verification. Dijkstra argued that verification is impossible with goto but relatively simple with guarded commands.

Conclusions

There is a wide variety of statement-level control structures across languages.
Adding more control statements beyond basic selection and pretest loops is a trade-off between the size/complexity of the language and the "writability" for the programmer.
Functional and logic programming languages typically employ significantly different control structures than procedural languages.