Control FlowCOMS W4115Prof. Stephen A. EdwardsSpring 2002Columbia UniversityDepartment of Computer ScienceControl Flow“Time is Nature’s way of preventing everything fromhappening 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 ExpressionsWhat code does a compiler generate fora = b + c + d;Most likely something liketmp = b + c;a = tmp + d;(Assumes left-to-right evaluation of expressions.)Order of EvaluationWhy would you care?Expression evaluation can have side-effects.Floating-point numbers don’t behave like numbers.Side-effectsint x = 0;int foo() { x += 5; return x; }int a = foo() + x + foo();What’s the final value of a?Side-effectsint 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 isimplementation-dependent.Side-effectsJava 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 BehaviorBasic number axioms:a + x = a if and only if x = 0 Additive identity(a + b) + c = a + (b + c) Associativea(b + c) = ab + ac DistributiveMisbehaving Floating-Point Numbers1e20 + 1e-20 = 1e201e-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 largeenough1.00001(1.000001 − 1) 6= 1.00001 · 1.000001 − 1.00001 · 11.00001 · 1.000001 = 1.00001100001 requires too muchintermediate precision.What’s Going On?Floating-point numbers are represented using anexponent/significand format:1 10000001| {z }8-bit exponent01100000000000000000000| {z }23-bit significand= −1.0112× 2129−127= −1.375 × 4 = −5.5.What to remember:1363.4568| {z }represented46353963456293| {z }roundedWhat’s Going On?Results are often rounded:1.00001000000×1.000001000001.000011 00001|{z}roundedWhen 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 whenwriting complex expressions.Short-Circuit EvaluationWhen you writeif (disaster_could_happen)avoid_it();elsecause_a_disaster();cause_a_disaster() is not called whendisaster_could_happen is true.The if statement evaluates its bodies lazily: only whennecessary.Short-Circuit EvaluationThe section operator ? : does this, too.cost =disaster_possible ? avoid_it() : cause_it();cause_it is not called if disaster_possible is true.Logical OperatorsIn Java and C, Boolean logical operators “short-circuit” toprovide this facility:if (disaster_possible || case_it()) { ... }cause_it() only called if disaster_possible isfalse.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 OperatorsNot all languages provide short-circuit operators. Pascaldoes not.C and Java have two sets:Logical operators || && short-circuit.Boolean (bitwise) operators | & do not.Short-Circuit Operators in TigerFrom the LRM:The logical operators & and | are lazy logical operators.They do not evaluate their right argument if evaluatingthe left determines the result. Zero is considered false;everything else is considered true.We will dismantle these operators into conditionalbranches in the next assignment.Unstructured Control-FlowAssembly languages usually provide three types ofinstructions:Pass control to next instruction:add, sub, mov, cmpPass control to another instruction:jmp rtsConditionally pass control next or elsewhere:beq bne bltUnstructured Control-FlowSo-called because it’s easy to create spaghetti:beq AB:jmp CA:beq DC:beq BD:bne BStructured Control-FlowThe “object-oriented languages” of the 1960s and 70s.Structured programming replaces the evil goto withstructured (nested) constructs such asif-then-elseforwhiledo .. whilebreakcontinuereturnGotos vs. Structured ProgrammingA typical use of a goto is building a loop. In BASIC:10 print I20 I = I + 130 IF I < 10 GOTO 10A cleaner version in C using structured control flow:do {printf("%d\n", i);i = i + 1;} while ( i < 10 )An even better versionfor (i = 0 ; i < 10 ; i++) printf("%d\n", i);Gotos vs. Structured ProgrammingBreak 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 LoopsJava 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 ProgrammingPascal has no “return” statement for escaping fromfunctions/procedures early, so goto was necessary:procedure consume_line(var line : string);beginif line[i] = ’%’ then goto 100;(* .... *)100:endIn C and many others, return does this for you:void consume_line(char *line) {if (line[0] == ’%’) return;}LoopsA modern processor can execute something like 1 billioninstructions/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: loopsThis insight is critical for optimization: only botheroptimizing the loops since everything else is of vanishingimportance.Enumeration-Controlled Loops inFORTRANdo 10 i = 1, 10, 2...10: continueExecutes body of the loop with i=1, 3, 5, ..., 9Tricky 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 thelower one?Changing Loop IndicesMost 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 ModificationOptimizing the behavior of loops is often very worthwhile.Some processors have explicit looping instructions.Some compilers transform loop index variables for speedor safety.Letting the program do whatever it wants usually preventsoptimizations.Loops in TigerThe Tiger LRM:The for expression, for id :=
View Full Document
Unlocking...