Programming Languages andCompilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa06/cs421/Based in part on slides by Mattox Beckman, as updatedby Vikram Adve and Gul AghaElsa L. GunterClasses of Control FlowSelection• Structured: if/then/else,continue,switch,case• Unstructured: GOTO, computed GOTO,labelled entryIteration• Precomputed iteration space: do,foreach(range)• Dynamic iteration space: for,while, recursionElsa L. GunterClasses of Control FlowInvocation• Direct calls: function,subroutine• Indirect calls: func. pointer, methods ofa class, closureTermination of scope• Structured: break, break label,exceptions, CPS• Unstructured: GOTO, setjmp/longjmp,exitElsa L. GunterClasses of Control FlowConcurrency• Manual: processes, threads, futures,(coroutines)• Automatic: doall, doacross, directives (e.g.,OpenMP)• Communication and synchronizationtechniques are critical.• You should be familiar with if/then/else,switch/case, do, for, while, foreach (range),GOTO, break, exit.Elsa L. GunterWhat is an exception?Exception :• A runtime event that causes control tobe transferred from the current programpoint to a separate code fragment thatdoes not follow the current point in theprogram’s control flow.Exception handler :• Code fragment that receives controlwhen exception occurs.Elsa L. GunterWhat is an exception?Internal exception :• An exception generated explicitly by theprogram.External exception :• An exception generated by the runtimesystem.Elsa L. GunterWhy do we need exceptions?• What can cause an external exception?• Why would you use an internalexception?Elsa L. GunterPoor Program to Multiply aListlet rec list_mult list = match list with [ ] -> 1 | x::xs -> x * list_mult xsProblem: Want to avoid all themultiplications in list containing 0Elsa L. GunterSuboptimal Solutionlet rec list_mult list = match list with [ ] -> 1 | x::xs -> if x = 0 then 0 else x * list_mult xsOnce it see 0, it ignores the tail of the listProblem: Still multiplies 0 times eachelement in the list before itEg: list = [7;4;0] then still multiply 4, 7 by 0Elsa L. GunterBetter Solutionexception Zero;;let rec list_mult_aux list = match list with [ ] -> 1 | x :: xs -> if x = 0 then raise Zero else x * list_mult_aux xs;;let list_mult list = try list_mult list with Zero -> 0;;Elsa L. GunterWhat Gets Skipped?• Let list = [7; 4; 0; 5]• First function:list_mult [7; 4; 0; 5] => (7 * result) <- list_mult [4; 0; 5] => (7 * result) <- (4 * result) <- list_mult [0; 5] =>(7 * result) <- (4 * result) <- (0 * result) <-list_mult [5] =>(7 * result) <- (4 * result) <- (0 * result) <-(5 * result) <- list_mult [ ]Elsa L. GunterWhat Gets Skipped? =>(7 * result) <- (4 * result) <- (0 * result)<- (5 * 1) =>(7 * result) <- (4 * result) <- (0 * 5) =>(7 * result) <- (4 * 0) =>(7 * 0) => 0Elsa L. GunterWhat Gets Skipped?• Second function:list_mult [7; 4; 0; 5] => (7 * result) <- list_mult [4; 0; 5] => (7 * result) <- (4 * result) <- list_mult[0; 5] =>(7 * result) <- (4 * 0) =>(7 * 0) => 0Elsa L. GunterWhat Gets Skipped?• Third function:list_mult [7; 4; 0; 5] => list_mult_aux [7; 4; 0; 5] => (7 * result) <- list_mult_aux [4; 0; 5] => (7 * result) <- (4 * result) <-list_mult_aux [0; 5] => 0• Could be big win if * were expensiveElsa L. GunterStructured ExceptionPropagationOn exception e:• Unwind stack to innermost call that handlesexception e• In each stack frame, perform cleanups:– call local object destructors in C++– release locks in Java• In stack frame with handler, execute handler• Handler may rethrow the exception, throw adifferent exception,or continueElsa L. GunterException Data• Exception data (values) are needed tocommunicate what exception occurred,state of computation when it occurred,and perhaps where.• OCAML, Ada: exception is a built-intype• Java, C++: subclasses of an “exceptionclass”• C: int argument to longjmp()Elsa L. GunterCurrent Continuations• Idea: remaining computation to be donewhen given result of most localexpression• Example: if (x && y) then s( ) else t( )• Intuitively: the current continuation of x&& y is s( ) if x && y evaluates to true,and is t ( ) it it evaluates to false insteadElsa L. Guntercallcc• (Will use SML/NJ version, but with Ocamlsyntax)• Built-in type of ‘a cont(SMLofNJ.Cont.callcc)• callcc : (‘a cont -> ‘a) -> ‘a if (callcc (fun k -> not x)) then 5 else 3• k represents the function that will eitherreturn 3 or 5• As given, since k is not used, callcc has noeffectElsa L. GunterThrow• The way to use a continuation“captured” by callcc is with throw:• throw: ‘a cont -> 'a -> 'b• if (callcc (fun k -> (throw k false))) || truethen 3 else 5 = 3• if (callcc (fun k -> (throw k false) || true))then 3 else 5 = 5Elsa L. GunterControl Flow through callcc• Callcc is a powerful control construct• Can implement– Exceptions– Concurrency (done in Concurrent ML)– Other non-local control mechanismsElsa L. GunterList Multiplication Examplelet list_mult list =callcc( fun zerok -> let rec list_mult_aux list = match list with [ ] -> 1 | x :: xs -> if x = 0 then throw zerok 0 else x * list_mult_aux xs in list_mult_aux
View Full Document
Unlocking...