Control Structures Any mechanism that departs from straight line execution Selection if statements Multiway selection case statements Unbounded iteration while loops Definite iteration for loops Iterations over collections transfer of control gotos unbounded transfer of control exceptions backtracking Selection if Condition then Statement Pascal Ada if Condition Statement C C Java All you need for a universal machine increment decrement branch on zero All the rest is programmer convenience To avoid ambiguities use end marker end if To deal with alternatives use keyword or bracketing if Condition then Statements elsif Condition then Statements else Statements end if if Condition Statements else if Condition Statements else Statements Nesting if Condition then if Condition then Statements end if else Statements end if if Condition if Condition Statements else Statements Statement Grouping Pascal introduces begin end pair to mark sequence C C Java abbreviate keywords to Ada dispenses with brackets for sequences because keywords for the enclosing control structure are sufficient for J in 1 N loop end loop More writing more readable The use of grouping in C a reminder that it is an expression language The use of grouping in C Java is just syntactic tradition Another possibility ABC Python make indentation significant Short Circuit Evaluation If x is more than five times greater than y compute z if x y 5 then z but what if y is 0 If y 0 and x y 5then z but operators evaluate their arguments Solutions a lazy evaluation rule for logical operators LISP C etc a control structure with a different syntax C1 C2 if C1 and then C2 then C1 C2 if C1 or else C2 then does not evaluate C2 if C1 is false ditto does not evaluate C2 if C1 is true ditto Multiway selection The case statement is the most useful control structure because most programs are interpreters Can be simulated with a sequence of if statements but logic become obscured case Next Char is when I Val 1 when V Val 5 when X Val 10 when C Val 100 when D Val 500 when M Val 1000 when others raise Illegal Numeral end case The well structured case statement Type of expression must be discrete an enumerable set of values floating point numbers not acceptable each choice is independent of the others no flow through There are no duplicate choices All possible choices are covered There is mechanism to specify a default outcome for choices not given explicitly Implementation Finite set of possibilities can build a table of addresses and convert expression into table index compute value transform into index retrieve address of corresponding code fragment branch to code fragment and execute branch to end of case statement All cases have the same execution cost All choices must be static computable at compile time Complications case X 1 is any integer value discrete but large when integer first 0 Put Line negative when 1 Put Line unit when 3 5 7 11 Put Line smal prime when 2 4 6 8 10 Put Line small even when 21 Put Line the house wins when 12 20 22 99 Put Line manageable when others Put Line Irrelevant end case Implementation must be combination of tables and if statements Unstructured flow Duff s device void send int to int from int count int n count 7 8 switch count 8 case 0 do to from case 7 to from case 6 to from case 5 to from case 4 to from case 3 to from case 2 to from case 1 to from while n 0 What does this do Why bother Indefinite loops All loops can be expressed as while loops Condition is evaluated at each iteration If condition is initially false loop is never executed while Condition loop end loop equivalent to if Condition then while Condition loop end loop end if provided Condition has no side effects What if we want to execute at least once Pascal introduces until loop C C use different syntax with while while Condition do while Condition While form is most common Can always simulate with a boolean variable first True while Condition or else first loop first False end loop Breaking out More common is the need for an indefinite loop that terminates in the middle of an iteration C C Java break Ada exit statement loop infinite loop compute first part exit when got it compute some more end loop Multiple exits Within nested loops useful to specify exit from several of them Ada solution give names to loops Otherwise use a counter Modula or use a goto Outer while C1 loop Inner while C2 loop Innermost while C3 loop exit Outer when Major Failure exit Inner when Small Annoyance end loop Innermost end loop Inner end loop Outer Definite loops Counting loops are iterators over discrete domains for J in 1 10 loop for int I 0 I N I Design issues Evaluation of bounds only once ever since Algol60 Scope of loop variable Empty loops Increments other than one Backwards iteration non numeric domains Evaluation of bounds for J in 1 N loop N N 1 end loop terminates In Ada bounds are evaluated once before iteration starts The above always terminates and is abominable style The C C Java loop has hybrid semantics for int J 0 J last J last does not terminate The loop variable Best if local to loop and treated as constant Avoids issue of value at termination and value on abrupt exit counter integer 17 outer declaration for counter in 1 10 loop do something 1 counter 10 end loop counter is still 17 Different increments The universal Algol60 form for J from Exp1 to Exp2 by Exp3 do Too rich for most cases Exp3 is most often 1 1 What is meaning if Exp1 Exp2 and Exp3 0 In C C for int J Exp1 J Exp2 J J Exp3 In Ada for J in 1 N loop for J in reverse 1 N loop increment is 1 increment is 1 Everything else can be programmed with while loop Non numeric domains Ada form generalizes to discrete types for M in months loop Basic pattern on other data types define primitive operations first next more elements Iterator Collection Iterate build an iterator over a collection of elements element thing iterator first define loop variable while iterator more elements thing iterator next value is each successive element How do we know it s right Pre Conditions and Post conditions P S Q means if Proposition P holds before executing S and the execution of S terminates then proposition Q holds afterwards Need to formulate pre and post conditions for all statement forms and syntax directed rules of inference P and C S P P and C while C do S end loop P and not C i e on exit from a while loop we know the condition is false Efficient exponentiation function Exp Base Integer Expon Integer