Control Flow COMS W4115 Prof Stephen A Edwards Spring 2003 Columbia University Department of Computer Science Control Flow Time is Nature s way of preventing everything from happening at once Scott identifies seven manifestations of this 1 Sequencing foo bar 2 Selection if a foo 3 Iteration while i 10 foo i 4 Procedures foo 10 20 5 Recursion foo int i foo i 1 6 Concurrency foo bar 7 Nondeterminism do a foo b bar Ordering Within Expressions What code does a compiler generate for a b c d Most likely something like tmp b c a tmp d Assumes left to right evaluation of expressions Order of Evaluation Why would you care Expression evaluation can have side effects Floating point numbers don t behave like numbers Side effects int x 0 int foo x 5 return x int a foo x foo What s the final value of a Side effects int x 0 int foo x 5 return x int a foo x foo GCC sets a 25 Sun s C compiler gave a 20 C says expression evaluation order is implementation dependent Side effects Java prescribes left to right evaluation class Foo static int x static int foo x 5 return x public static void main String args int a foo x foo System out println a Always prints 20 Number Behavior Basic number axioms a x a if and only if x 0 Additive identity a b c a b c Associative a b c ab ac Distributive Misbehaving Floating Point Numbers 1e20 1e 20 1e20 1e 20 1e20 1 9e 7 9e 7 6 1 9e 7 9e 7 9e 7 1 so it is discarded however 1 8e 6 is large enough 1 00001 1 000001 1 6 1 00001 1 000001 1 00001 1 1 00001 1 000001 1 00001100001 requires too much intermediate precision What s Going On Floating point numbers are represented using an exponent significand format 1 z 01100000000000000000000 z 10000001 8 bit exponent 23 bit significand 1 0112 2129 127 1 375 4 5 5 What to remember 1363 4568 46353963456293 z represented z rounded What s Going On Results are often rounded 1 00001000000 1 00000100000 1 000011 00001 z rounded When b c b c is small so ab ac 6 a b c because precision is lost when ab is calculated Moral Be aware of floating point number properties when writing complex expressions Short Circuit Evaluation When you write if disaster could happen avoid it else cause a disaster cause a disaster is not called when disaster could happen is true The if statement evaluates its bodies lazily only when necessary Short Circuit Evaluation The section operator does this too cost disaster possible avoid it cause it cause it is not called if disaster possible is true Logical Operators In Java and C Boolean logical operators short circuit to provide this facility if disaster possible case it cause it only called if disaster possible is false The operator does the same thing Useful when a later test could cause an error int a 10 if i 0 i 10 a i 0 Short Circuit Operators Not all languages provide short circuit operators Pascal does not C and Java have two sets Logical operators short circuit Boolean bitwise operators do not Unstructured Control Flow Assembly languages usually provide three types of instructions Pass control to next instruction add sub mov cmp Pass control to another instruction jmp rts Conditionally pass control next or elsewhere beq bne blt Unstructured Control Flow So called because it s easy to create spaghetti beq A B jmp C A beq D C beq B D bne B Structured Control Flow The object oriented languages of the 1960s and 70s Structured programming replaces the evil goto with structured nested constructs such as if then else for while do while break continue return Gotos vs Structured Programming A typical use of a goto is building a loop In BASIC 10 print I 20 I I 1 30 IF I 10 GOTO 10 A cleaner version in C using structured control flow do printf d n i i i 1 while i 10 An even better version for i 0 i 10 i printf d n i Gotos vs Structured Programming Break and continue leave loops prematurely for i 0 i 10 i if i 5 continue if i 8 break printf d n i Again if i 10 goto Break if i 5 goto Continue if i 8 goto Break printf d n i Continue i goto Again Break Escaping from Loops Java allows you to escape from labeled loops a for int i 0 i 10 i for int j 0 j 10 j System out println i j if i 2 j 8 continue a if i 8 j 4 break a Gotos vs Structured Programming Pascal has no return statement for escaping from functions procedures early so goto was necessary procedure consume line var line string begin if line i then goto 100 100 end In C and many others return does this for you void consume line char line if line 0 return Loops A modern processor can execute something like 1 billion instructions second How many instructions are there in a typical program Perhaps a million Why do programs take more than 1 s to run then Answer loops This insight is critical for optimization only bother optimizing the loops since everything else is of vanishing importance Enumeration Controlled Loops in FORTRAN 10 do 10 i 1 10 2 continue Executes body of the loop with i 1 3 5 9 Tricky things What happens if the body changes the value of i What happens if gotos jump into or out of the loop What is the value of i upon exit What happens if the upper bound is less than the lower one Changing Loop Indices Most languages prohibit changing the index within a loop Algol 68 Pascal Ada FORTRAN 77 and 90 Modula 3 But C C and Java allow it Why would a language bother to restrict this Prohibiting Index Modification Optimizing the behavior of loops is often very worthwhile Some processors have explicit looping instructions Some compilers transform loop index variables for speed or safety Letting the program do whatever it wants usually prevents optimizations Empty Bounds In FORTRAN 10 the body of this loop is executed once do 10 i 10 1 1 continue for i 10 to 1 by 1 Test is done after the body Empty Bounds Modern languages place the test before the loop Does the right thing when the bounds are empty Slightly less efficient one extra test Scope of Loop Index What happens to the loop index when the loop terminates Index is undefined FORTRAN IV Index is its last value FORTRAN Pascal 77 Algol 60 Index is just a variable C C Java Tricky when iterating over subranges What s next var c a z for c a to z do begin end what s c Scope of Loop Index Originally in C a locally defined index variable s scope extended beyond the loop for int …
View Full Document
Unlocking...