Unformatted text preview:

Control StructuresSelectionNestingStatement GroupingShort-Circuit EvaluationMultiway selectionThe well-structured case statementImplementationComplicationsUnstructured flow (Duff’s device)Indefinite loopsWhat if we want to execute at least once?Breaking outMultiple exitsDefinite loopsEvaluation of boundsThe loop variableDifferent incrementsNon-numeric domainsHow do we know it’s right?Efficient exponentiationAdding invariantsControl 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, backtrackingSelection•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 if (Condition) { Statements Statements }elsif Condition then else if (Condition) { Statements Statements}else else { Statements Statements}end if;Nestingif Condition then if (Condition) if Condition then if (Condition) { Statements Statements end if; }else else { Statements Statementsend if; }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 significantShort-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 does not evaluate C2 if C1 is false •if C1 and then C2 then ditto•C1 || C2 does not evaluate C2 if C1 is true•if C1 or else C2 then dittoMultiway 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-timeComplicationscase (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 statementloop -- 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


View Full Document

NYU CSCI-GA 2110 - Control Structures

Download Control Structures
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Control Structures and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Control Structures 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?