CSE399: Advanced ProgrammingHandout 20Tail RecursionRecall...Ordinary factorial function:fact n = if n==0 then 1 else fact(n-1)Recall...Tail-recursive factorial:fact’ n a = if n==0 then aelse fact (n-1 ) (a*n)fact’’ n = fact’ n 1The second one will be compiled to much more efficientcode, because the compiler can se e that the recursive callto fact’ is in tail position—i.e., its result is the result of thewhole body of fact’.This means that the stack frame for the current call tofact’ is not needed any more, so the recursive call can justre-use the same stack frame. (The “call” instructionbecomes a “jump.”)I.e., fact’ will be compiled to a loop.Tail PositionBut what, exactly, is this notion of “tail position”?Not “rightmost subexpression,” because this also describesthe (non-tail) recursive call in the original fact.And conversely, tail calls may also occur in non-rightmostpositions, textually:fact4 n a = if n/=0 then fact (n-1) (a*n)else aWe can make the notion precise by introd ucing the idea ofcontinuati ons.ContinuationsContinuationsAt each point during a computation, we can think of (1)some subcomputation that i s eventually going to yield avalue and, (2) some context that is waiting for this value andis going to use it to finish computing the final value of thewhole program.(2) is called the continuation of (1).E.g., the continuation of the subexpression fac t 3 in thecomputation of fact 6 is.6 * (5 * (4 * )),where indicates the place whe re the value of fact 3 willbe used.Making Continuations ExplicitA continuation can be thought of as a function from theresult of the subexpression to the final result of the wholecomputation. I.e., we can write the continuation from theprevious slide as\x -> 6 * (5 * (4 * x))Making Continuations ExplicitWe can use this observation to write another version of factthat makes these continuations explicit:fact_cps n k =if n==0then k 1else fact_cps (n-1) (\x -> k (n*x))Note that all call s i n fact_cps are in tail position. I.e., everycall can be compiled as a jump. (A continuati on can b edescribed as a “goto w ith arguments.”)Q: So when does the stack grow?CPSThis programming style is called continuati on-passing style:every function is explicitly passed its continuation—i.e.,another function to which it should send its re sult.Another ExampleHere’s a CPS variant of another familiar function:length_cps [] k = k 0length_cps (x:xs) k = length_cps xs (\x -> k (x+1))Q: What is the type of length_cps?Continuations in WASHMany WASH programs are written in continuation-passingstyle: the “callback” argument to ask never returns—it justkeeps (often recursively) making new calls to ask until theinteraction is finished.Continuations for BacktrackingIt is sometimes useful to define functions taking multiplecontinuati ons.For example, programs that perform some kind of searchcan often be express ed very naturally using continuations. Asearching functi on is passed two continuations:•a success continuation that tells it what is the nextsubgoal to try if this one works, and•a failure continuation that tells it how to “unwind” to aprevious choice point, if something fails.Example: Se a rching in CPSdata Tree a b = Le af a b | Node (Tree a b) (Tree a b)myTree = Node (Leaf 5 3) (Leaf 2 4)findk :: Eq a => a -> (Tree a b) -> (Maybe b -> r) -> r -> rfindk a t sk fk =case t ofLeaf a’ b | a= =a’ -> sk ( Just b)| a/=a’ -> fkNode t1 t2 -> findk a t1 sk (findk a t2 s k fk)find a t = fin dk a t (\b -> b) Not hingmain =do print (find 1 myTree)print (find 2 myTree)Example: Se a rching in CPSTo make the failure continuation more interesting, let’s keeptrack of how many nodes had to b e s earched to find thegiven key.findk :: Eq a => a -> (Tree a b) -> Int ->(Maybe (b,Int) -> r) -> (Int->r) ->rfindk a t count sk fk =case t ofLeaf a’ b | a= =a’ -> sk ( Just (b,count))| a/=a’ -> fk countNode t1 t2 -> findk a t1 (count+1)sk (\c -> findk a t2 c sk fk)find a t = fin dk a t 1 (\b -> b) (\c -> Nothing)main =do print (find 1 myTree)print (find 2 myTree)CPS TransformIt is poss ible to re write any program i n continuation-passingstyle.Indeed, there is a mechanical procedure (called a CPStransform) that will take an arbitrary program and producean equivalent CPS program.This transformation plays a critical role in some compilers forfunctional languages.Call/CCMany functional languages (including Scheme, Standard ML,and Haskell’s Cont monad) provide an operator for gainingexplicit access to the “current continuati on” at any point in aprogram.This operator is traditionally called call/cc.It can be used for many amazing and mind-bendingprogramming