Monitoring_System

Statement Level Control Structures Chapter 8 Overview • • • • Selection Statements Iterative Statements Unconditional Branching Guarded Commands 2 Statement Level Control Structures' • Constructs that allow the program to select from alternative control flow paths (if else construct) • Allow repeated execution of statements (loops) 3 Control Statements • Research on control statements during the 1960s and 1970s • ‘goto’ statements are sufficient • A language without goto statements really only needs a few other controls • All algorithms that can be expressed by flowcharts can be coded using just two control structures 4 What Do They Look Like' • Number of control statements used expanded by writability • • • • While For If – else Switch • Restricted by readability • On the other hand, too few control statements can be harmful to readability 5 Selection Statements • Means of choosing between two or more execution paths • Two categories • Two-way • n-way (multiple selection) 6 Two-way Selection • What we know as if-else constructs • Variations in their evolution can be seen in their diverse syntax in different languages Basic construct is: if control_expression then clause else clause 7 The Control Expression • In C-based languages – usually in parentheses • If the language has a then reserved word, then parentheses not necessary (Ada) • Usually a Boolean expression if 5 == 7 then print “Your compiler is broken” else print “Your compiler works!” 8 The Clause • In modern languages the then clause and else clause can be single or compound • Perl forces all clauses to be compound • In Fortran 95 and Ada , the clauses are just statement sequences – must be ended with keyword end 9 Nesting Selectors • Problems with Nesting Selectors Java: if (sum == 0) if (count == 0) result = 0; else result = 1; Python: if (sum == 0): if (count == 0): result = 0 else: result = 1 10 Nested Selectors Continued • No syntactic indicator to specify a matching of the else clause • In many imperative languages, the static semantics specify that the else is paired with the nearest unpaired then clause The correct way would of course be: if (sum == 0){ if (count == 0) result = 0; } else result = 1; 11 Nested Selectors Continued • To avoid confusion Fortran 95 and Ada had a special keyword Ada Example: if A > B then Sum := Sum + A; else Sum := Sum + B; end if; • Perl forces all clauses to be compound, so: if (1 == 1) print “One”; would not compile. 12 Concluding Two-Way Selectors • The control_expression is not necessarily boolean – it can be of integer type • Fortran has a 3-way arithmetic if and decides on whether the control expression evaluates to positive integer, negative integer, or 0. • In Perl, if (“*” == “+”){ print “This should not print”; } is valid, and in fact is true. 13 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' 14 Multiple Selection Constructs • Generalization of a two-way selector • Allows a choice between several different control flow paths • Can be built using two-way selectors and goto statements – but this hurts both readibility and writability 15 Multiple Selectors Continued • C-based languages use the switch construct Basic form: switch(control_expression) { case constant_expression_1: statement_1; case constant_expression_2: statement_2; … case constant_expression_n: statement_n; default: statement_n+1; } 16 Multiple Selectors Continued • Rules for the switch construct • The control expression and constant expressions are of the same type • The selectable statements can be statement sequences or compound statements • The default segment is optional and is the fallback case • No implicit branches provided – allows flow through any number of code segments 17 Switch Construct Example: switch(index) { case 1: printf(“Case 1\n”); case 2: printf(“Case 2\n”); case 3: printf(“Case 3\n”); case 4: printf(“Case 4\n”); default: printf(“Error”); } 18 Switch Construct Example: switch(index) { case 1: printf(“Case 1\n”); break; case 2: printf(“Case 2\n”); break; … default: printf(“Error”); } 19 Switch Construct Continued • Convenient to allow code flow through several segments • However, it causes a decrease in reliability • C design choice to allow more power at cost of reliability • C# forces all branches to end in an unconditional branch statement • break • goto 20 Multiple Selectors Continued Ada example: case control_expression is when choice list => statement_sequence; … when choice list => statement_sequence; when others => statement_sequence; end case; 21 Multiple Selectors Using If • Used in cases when a boolean expression must be evaluated Example: if (Count < 10){ Bag1 = true; } else { if (Count < 100){ Bag2 = true; } else { if (Count < 1000) { Bag3 = true; } } } 22 Multiple Selectors Using If • Some languages have recognized the use of if-else-if constructs and cleaned up the syntax Python Example: if count < 10: bag1 = true elif count < 100: bag2 = true elif count < 1000: bag3 = true else: bag4 = true 23 Design Issues • What is the type and form of the control expression' • How are the selectable statements specified' (Single, Compound, Sequences) • Is the execution flow restricted' • How should unrepresented selector expression values be handled, if at all' 24 Iterative Statements • Causes a statement of collection of statements to be executed one or more times • One of the basic units of programming languages - and the most powerful • Without it, programmers would be forced to write out all their statements – or even worse, use recursion 25 Iterative Statements • Basically defined by how designers answered the following questions: • How is the iteration controlled' • Logical • Counting • Both • Where should the control mechanism appear in the loop' • Before the code segment • After the code segment 26 Counter Controlled Loops • Has a variable called the loop variable that contains the count value • The initial and terminal values of the loop variable are also specified in some way, along with the stepsize • The initial, terminal and stepsize are called loop parameters 27 The Do Statement • Fortran 95 Do statement Do label variable = initial, terminal [,stepsize] • label is the location of the last statement in the loop body • stepsize defaults to 1 if not specified • variable is an Integer that is the loop variable, though the iteration count is inaccessible to the user 28 The Do Statement • Can only be entered through the initial do statement • The loop variable is altered regardless of how the loop terminates Another form of the Fortran 95 Do: [name:] Do variable = initial, terminal … End Do [name] Uses special ending word End Do – and an optional name, which helps in nesting 29 The C For Statement General form in C: for (expression1; expression2; expression3) loop_body • The loop body can be a single, compound or null statement • expression1 is for initialization and evaluated only once • expression2 is the loop control and is evaluated before each execution 30 The C For Statement • In C, all expression are also statements, so: for (k = 0; k < 10; k++) printf(“%d”, k); can be expressed using operational symantics as: int k = 0; loop: if (k < 10) == false goto out printf(“%d”, k); k++; goto loop out: … 31 The C For Statement • All expressions in the C for loop are optional • If expression2 is absent, it is considered true, and it is an infinite loop • There are no explicit loop variables – they can all be manipulated in the loop body • The C for is quite flexible as • The expressions need not be just one statement • It allows loop variables to be any type 32 The C For Statement • Consider the following for (count1 = 0, count2 = 1.0; count1 100) break count; } } 41 User Located Control Mechanisms • Similarly, C and C++ have an unlabeled continue statement, while Java, Perl and C# have labeled continue statements • Allow the flow to skip the rest of the loop body and continue with the next iteration • As glorified goto statements, these statements reduce readability – but they are severely restricted gotos and are used widely 42 Iteration Based on Data Structures • Perl, JavaScript, PHP, and C# have a foreach construct that allows iteration by collections of elements A PHP Example: $arr = array(1, 2, 3, 4); foreach ($arr as $value) { print “value is $value”; } 43 Iteration Based on Data Structures • Java 5 added a foreach construct to Java Example: int [] numbers = {1,2,3,4}; for (int x : numbers){ System.out.println(x); } 44 Iteration Based on Data Structures • An iterator is a function that allows going through a user-defined data structure • Because of the power of the for statement is C-based languages it is possible to simulate an iterator Example of a tree traversal: for (ptr = root; ptr == null; traverse(ptr)); 45 Iterators • Important in object-oriented programming • In C++, an iterator is usually implemented with any user-defined types or classes • In Java, any object that implements the Collection interface can be visited using the built in Iterator class • C# uses the foreach statement as an iteration interface 46 Unconditional Branching • An unconditional branch statement transfers control to a specific place in the program • Well known as the goto statement • Has been a target of criticism, as it is known to produce “spaghetti code” • Restrictions usually placed by programming language design and standards 47 Unconditional Branching • Most modern languages include a goto statement • Karnighan and Ritchie called the goto statement “infinitely abusable” but still included it in C • Some notable exceptions are Modula-2, Java, Python • The break and continue statements are disguised gotos with severely limited power 48 Unconditional Branching • Example of code that works better with goto statements: for (i = 0; i < n; i++){ for (j = 1; j < n; j++) if (x[i][j] != 0) goto reject; print “First all-zero row is:”, i; break; reject: } Finds first row of a matrix which has nothing but 0 values. 49 Guarded Commands • Suggested by Dijkstra in 1975 • Alternate and different forms of selection and loop structures • Motivation was to create a methodology that proved correctness during development – instead of testing • Used for concurrent programming in CSP (Communicating Sequential Processes) 50 Guarded Commands Basic form of Dijkstra’s selection construct: if -> [] < boolean expression> -> … [] < boolean expression> -> fi fatbars 51 Guarded Commands • All of the boolean expressions are evaluated each time • If none of the boolean expressions are true, it is considered a runtime error • Forces programmer to think of all cases • If more than one boolean statement is true, any one of the associated statements can be chosen 52 Guarded Selectors • Example: if k = 0 -> sum += k [] k > j -> sum += j [] j > k -> sum += k fi • If k = 0 and j > k, the construct can choose non-deterministically between both statement 1 and 3 • If k = j and k != 0, then a runtime error occurs 53 Guarded Selectors • Allows programmer to state that the order of execution is irrelevant • Example: if x >= y -> max := x [] y >= x -> max := y fi • If x and y are equal, it does not matter which statement is executed 54 Guarded Loops • Basic form: do -> [] -> .. [] -> od • Exits loop if all boolean expressions are false • Picks one true expression and executes its statement 55 Guarded Loops • Example do q1 > q2 -> swap (q1, q2); [] q2 > q3 -> swap (q2, q3); [] q3 > q4 -> swap (q3, q4); od Bubble sort 56 Guarded Commands • Show how semantics and syntax can have an impact on program verification • Implementation of guarded commands is complex • Increase reliability of programs – at the cost of writability and possibly readability 57 Design Issues - Overall • How is the control expression defined' • C and C++ allow boolean and arithmetic expressions • Java allows only booleans • Is the structure restricted to single statements' • Most languages today allow compound and single statements, as well as sequences 58 Design Issues - Overall • How is nesting specified' • Are else clauses paired with closest unpaired then clauses' • Most imperative languages do it this way • Is it possible to use labeled breaks and continues for nested structures' • C and C++ do not allow it • Java, Perl, C# allow it, but loops have to be given a name • How is the syntax of the structure specified' • Modern languages use {} to specify the structure body • Python simply uses indentation 59 Design Issues - Selection statements • How is the if-else syntax specificied' • Fortran 95 and Ada had a special keyword end if • Unix scripting uses ‘fi’ to end an if • Is the execution flow restricted within a multiple selector' • In C-based switch it isn’t, have to specifically break out • C# requires the code to break out • How should the default option be specified in multiple selectors' • Optional in C-based switch as well as Ada’s case statement 60 Design Issues – Iteration Statements • How are the loop variable and parameter specificied' • Can they be changed during execution of the loop' • Fortran and Ada do not allow changing the loop variable in the loop • C allows this, gives more power to the programmer • Are the loops pretest or posttest' • C-based languages include both • Posttest loops being faded out 61 Conclusion • Only sequence, selection and logical pretest loops are required to express algorithms • Goto statements have been regarded as abusable, and only appear in languages today as breaks and continues • The diversity of control structures seen in languages today shows how different language designers can combine their design choices 62