Chapter 8Chapter 8 TopicsLevels of Control FlowControl Statements: EvolutionControl StructureSelection StatementsTwo-Way Selection StatementsNesting SelectorsNesting Selectors (continued)Slide 10Selector ExpressionsMultiple-Way Selection StatementsMultiple-Way Selection: ExamplesSlide 14Slide 15Implementing Multiple SelectorsMultiple-Way Selection Using ifSlide 18Lisp or Scheme’s Multiple SelectorIterative StatementsCounter-Controlled LoopsCounter-Controlled Loops: ExamplesSlide 23Slide 24Slide 25Logically-Controlled LoopsLogically-Controlled Loops: ExamplesUser-Located Loop Control MechanismsSlide 29Iteration Based on Data StructuresIteration Based on Data Structures (continued)PowerPoint PresentationUnconditional BranchingGuarded CommandsSelection Guarded CommandLoop Guarded CommandGuarded Commands: RationaleConclusionsChapter 8Statement-Level Control StructuresCopyright © 2012 Addison-Wesley. All rights reserved. 1-2Chapter 8 Topics•Introduction•Selection Statements•Iterative Statements•Unconditional Branching•Guarded Commands•ConclusionsCopyright © 2012 Addison-Wesley. All rights reserved. 1-3Levels of Control Flow–Within expressions (Chapter 7)–Among program units (Chapter 9)–Among program statements (this chapter)Copyright © 2012 Addison-Wesley. All rights reserved. 1-4Control 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 loopsCopyright © 2012 Addison-Wesley. All rights reserved. 1-5Control Structure•A control structure is a control statement and the statements whose execution it controls •Design question–Should a control structure have multiple entries?Copyright © 2012 Addison-Wesley. All rights reserved. 1-6Selection Statements•A selection statement provides the means of choosing between two or more paths of execution•Two general categories:–Two-way selectors (for example, if then else)–Multiple-way selectors (for example, switch)Copyright © 2012 Addison-Wesley. All rights reserved. 1-7Two-Way Selection Statements•General form:if control_expressionthen clauseelse 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?•In many contemporary languages, the then and else clauses can be single statements or compound statementsCopyright © 2012 Addison-Wesley. All rights reserved. 1-8Nesting Selectors•Java example if (sum == 0) if (count == 0) result = 0; else result = 1;•Which if gets the else? •Java's static semantics rule: else matches with the nearest previous ifCopyright © 2012 Addison-Wesley. All rights reserved. 1-9Nesting Selectors (continued)•To force an alternative semantics, compound statements may be used:if (sum == 0) { if (count == 0) result = 0;} else result = 1;•The above solution is used in C, C++, and C#Copyright © 2012 Addison-Wesley. All rights reserved. 1-10Nesting Selectors (continued)•Statement sequences as clauses: Ruby if sum == 0 then if count == 0 then result = 0 else result = 1 end endSelector Expressions•In ML, F#, and LISP, the selector is an expression•F# let y = if x > 0 then x else 2 * x- If the if expression returns a value, there must be an else clause (the expression could produce output, rather than a value)Copyright © 2012 Addison-Wesley. All rights reserved. 1-11Copyright © 2012 Addison-Wesley. All rights reserved. 1-12Multiple-Way Selection Statements•Allow the selection of one of any number of statements or statement groups(e.g. switch statement in C or C++)•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 are case values specified?5.What is done about unrepresented expression values?Copyright © 2012 Addison-Wesley. All rights reserved. 1-13Multiple-Way Selection: Examples•C, C++, Java, and JavaScriptswitch (expression) { case const_expr1: stmt1; … case const_exprn: stmtn; [default: stmtn+1]}Copyright © 2012 Addison-Wesley. All rights reserved. 1-14Multiple-Way Selection: Examples•Design choices for C’s switch statement1. Control expression can be only an integer type2. Selectable segments can be statement sequences, blocks, or compound statements3. Any number of segments can be executed in one execution of the construct (there is no implicit branch at the end of selectable segments)4. default clause is for unrepresented values (if there is no default, the whole statement does nothing)Copyright © 2012 Addison-Wesley. All rights reserved. 1-15Multiple-Way Selection: Examples•C#–Differs from C in that it has a static semantics rule that disallows the implicit execution of more than one segment–Each selectable segment must end with an unconditional branch (goto or break)–Also, in C# the control expression and the case constants can be stringsImplementing Multiple Selectors•Approaches:–Multiple conditional branches–Store case values in a table and use a linear search of the table–When there are more than ten cases, a hash table of case values can be used–If the number of cases is small and more than half of the whole range of case values are represented, an array whose indices are the case values and whose values are the case labels can be usedCopyright © 2012 Addison-Wesley. All rights reserved. 1-16Copyright © 2012 Addison-Wesley. All rights reserved. 1-17Multiple-Way Selection Using if•Multiple Selectors can appear as direct extensions to two-way selectors, using else-if clauses, for example in Python:if count < 10 : bag1 = Trueelif count < 100 : bag2 = Trueelif count < 1000 : bag3 = TrueCopyright © 2012 Addison-Wesley. All rights reserved. 1-18Multiple-Way Selection Using if•The Python example can be written as a Ruby case case when count < 10 then bag1 = true when count < 100 then bag2 = true when count < 1000 then bag3 = true endLisp or Scheme’s Multiple Selector•General form of a call to COND: (COND (predicate1 expression1) … (predicaten expressionn) [(ELSE expressionn+1)] )-The ELSE clause is optional; ELSE is a synonym for true-Each