Control Flow COMS W4115 Prof Stephen A Edwards Spring 2002 Columbia University Department of Computer Science Control Flow Ordering Within Expressions Time is Nature s way of preventing everything from happening at once What code does a compiler generate for 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 a b c d Most likely something like tmp b c a tmp d Assumes left to right evaluation of expressions 5 Recursion foo int i foo i 1 6 Concurrency foo bar 7 Nondeterminism do a foo b bar Order of Evaluation Side effects Side effects Why would you care int x 0 int x 0 int foo x 5 return x int foo x 5 return x int a foo x foo int a foo x foo Expression evaluation can have side effects Floating point numbers don t behave like numbers What s the final value of a GCC sets a 25 Sun s C compiler gave a 20 C says expression evaluation order is implementation dependent Side effects Number Behavior Misbehaving Floating Point Numbers Java prescribes left to right evaluation Basic number axioms 1e20 1e 20 1e20 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 a x a if and only if x 0 Additive identity a b c a b c Associative a b c ab ac Distributive 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 What s Going On Short Circuit Evaluation Floating point numbers are represented using an exponent significand format Results are often rounded When you write 1 00001000000 1 00000100000 1 10000001 z 01100000000000000000000 z 8 bit exponent 23 bit significand 1 000011 00001 z rounded if disaster could happen avoid it else cause a disaster When b c b c is small so ab ac 6 a b c because precision is lost when ab is calculated cause a disaster is not called when disaster could happen is true Moral Be aware of floating point number properties when writing complex expressions The if statement evaluates its bodies lazily only when necessary Short Circuit Evaluation Logical Operators Short Circuit Operators The section operator does this too In Java and C Boolean logical operators short circuit to provide this facility Not all languages provide short circuit operators Pascal does not if disaster possible case it C and Java have two sets cause it only called if disaster possible is false Boolean bitwise operators do not 1 0112 2129 127 1 375 4 5 5 What to remember 1363 4568 z 46353963456293 z represented rounded cost disaster possible avoid it cause it cause it is not called if disaster possible is true Logical operators short circuit 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 in Tiger Unstructured Control Flow Unstructured Control Flow From the LRM Assembly languages usually provide three types of instructions So called because it s easy to create spaghetti beq A Pass control to next instruction B The logical operators and are lazy logical operators They do not evaluate their right argument if evaluating the left determines the result Zero is considered false everything else is considered true We will dismantle these operators into conditional branches in the next assignment jmp C add sub mov cmp Pass control to another instruction A beq D jmp rts C Conditionally pass control next or elsewhere beq bne blt beq B D bne B Structured Control Flow Gotos vs Structured Programming Gotos vs Structured Programming The object oriented languages of the 1960s and 70s A typical use of a goto is building a loop In BASIC Break and continue leave loops prematurely Structured programming replaces the evil goto with structured nested constructs such as 10 print I 20 I I 1 30 IF I 10 GOTO 10 for i 0 i 10 i if i 5 continue if i 8 break printf d n i if then else for A cleaner version in C using structured control flow while break do printf d n i i i 1 while i 10 continue An even better version return for i 0 i 10 i 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 Gotos vs Structured Programming Loops Java allows you to escape from labeled loops Pascal has no return statement for escaping from functions procedures early so goto was necessary A modern processor can execute something like 1 billion instructions second procedure consume line var line string begin if line i then goto 100 100 end How many instructions are there in a typical program Perhaps a million do while 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 In C and many others return does this for you void consume line char line if line 0 return 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 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 Changing Loop Indices Prohibiting Index Modification Most languages prohibit changing the index within a loop Optimizing the behavior of loops is often very worthwhile Algol 68 Pascal Ada Some processors have explicit looping instructions FORTRAN 77 and 90 Modula 3 But C C and Java allow it Why would a language bother to restrict this Some compilers transform loop index variables for speed or safety Letting the program do whatever it wants usually prevents optimizations Loops in Tiger Empty Bounds Empty Bounds The Tiger LRM In Modern languages place the test before the loop The for expression for id expr to expr do expr evaluates the first and second expressions which are loop bounds Then for each integer value between the values of these two expressions inclusive the third expression is evaluated with the integer variable named by id bound to the loop index The scope of this variable is limited to the third expression and may not be assigned to This …
View Full Document
Unlocking...