PRINCIPLES OF PROGRAM DESIGN
PRINCIPLES OF PROGRAM DESIGN COMP 211
Popular in Course
Popular in ComputerScienence
This 17 page Class Notes was uploaded by Cleora Stiedemann on Monday October 19, 2015. The Class Notes belongs to COMP 211 at Rice University taught by Robert Cartwright in Fall. Since its upload, it has received 18 views. For similar materials see /class/224953/comp-211-rice-university in ComputerScienence at Rice University.
Reviews for PRINCIPLES OF PROGRAM DESIGN
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/19/15
Accumulators and Tail Calls Corky Cartwright Department of Computer Science Rice University Plan for today Provide a more precise technical motivation for accumulator concepts Recognizing the need for accumulators Avoiding non tail recursive calls Avoiding unnecessary traversals of a list Which often correlates With non tail recursive calls The book inexplicably does not discuss tail callstail recursion Which was a major focus of the pre book Comp 210 course Tail recursion is extremely important because it corresponds to iteration loops COMP 210 Fall 2007 2 Last Class Accumulators Looked at three examples Computing the partial sums for a sequence o Flattening a general list o Reversing a list COMP 210 Fall 2007 3 5 Last class Accumulators Three key things to remember HOW to use the accumulated value to produce the final answer HOW to update the accumulated value When we make a recursvie call HOW to initialize the accumulated value COMP 210 Fall 2007 4 Design Recipe When do we need an accumulator We pointed out some tell tail signs We miss some context or history information The result of the recursive call is processed by another function a non tail call Difficulty in ensuring termination uncommon because setting a ag in each node structure as it is Visited is usually preferable This list is not exhaustive COMP 210 Fall 2007 5 Factorial Even factorial could benefit from an accumulator Why The recursive call on fact is embedded inside another call on gtk Which means the computer must maintain a calling stack to manage the recursion Call stack maintenance is NOT free Which one is faster COMP 210 Fall 2007 6 ueling Factorials 5D define fact n cond n 0 1 else n fact sub1 n define facthelp n ans cond n 0 ans else facthelp sub 1 n ans define fastfact n facthelp n 1 The recursive call on facthelp is in tail position in COMP 210 Fall 2007 the function body meaning that no subsequent processing is performed on the result of the call in evaluating the body ail Position 5T Consider our laW for evaluating Scheme expressions When a function call application embedded in the body of a function definition for 1 must be the last form to be reduced in evaluating a call fv1 Vn that call is in tail position Note that a function definition may have several COMP 210 Fall 2007 different embedded calls that are in tail position Why because conditionals create multiple control paths through the function Think about our reduction rules for cond Examples Which function calls are in tail position define fact n cond n O 1 no function call in result else n fact sub1 n define facthelp n ans cond n 0 ans no function call in result else facthelp sub 1 n ans define fastfact n facthelp n 1 COMP 210 Fall 2007 9 Reduction pattern factorial fact3 3fact 2 32fact1 3 2 1 fact 0 3211 321 32 6 COMP 210 Fall 2007 10 Reduction pattern fast fact fastfact 3 facthelp 3 1 facthelp 2 3 1 facthelp 2 3 facthelp 1 2 3 facthelp 1 6 facthelp O 1 6 factace O 6 6 COMP 210 Fall 2007 11 Why are non tail calls expensive Tail calls compile to jumps branches Tail recursive calls compile to loop backwards branches Branches are only slightly more expensive than ordinary instructions In fact they can actually be cheaper with the right hardware support Non tail calls compile translate to expensive quotjump to subroutinequot instructions which are covered in both Elec 220 and Comp 221 A quotjump to subroutinequot instruction allocates space in the control stack a chunk of memory reserved by the OS for each computation to save information about the machine state at the point of the call saves critical information and then jumps to the subroutine The saved information enables a subsequent quotsubroutine returnquot instruction to restore the machine state at the the point of call with the returned value in a designated register In contrast a tail call never needs to return to the point of call It simply stores the result in the appropriate register and follows the control dictated by the context of the point of call COMP 210 Fall 2007 12 Naive Reverse define rev I cond empty I empty else append rev rest I list first The subcomputation in red must be performed after the call on rev completes COMP 210 Fall 2007 13 Tail recursive Reverse define revhelp I ans cond empty I ans else revhelp rest I cons first I ans define fastrev I revhelp I empty The recursive call on revhelp can be implemented by branching back to the code for the enclosing cond operation reusing the stack frame for the calling invocation of revhelp The initial call on revhelp in reverse can be quotinlinedquot So the optimized machine translation of this call looks just like it does for corresponding loop code COMP 210 Fall 2007 14 Example reductions Show reverse 39a b c using the DrSCheme stepper Show fastrev 39a b c using the DrSCheme stepper COMP 210 Fall 2007 15 Conversion to tail form Al ways possible Always profitable Always possible but requires passing closures functions as arguments which requires heap allocation Called conversion to continuation passing style CPS May or may not be profitable Covered in depth in Comp 311 What about our examples They did not use closures We COMP 210 Fall 2007 relied on associativity of conversion of append to cons Tail calls are very profitable when they substitute a cheap operation like cons for an expensive one like append They can potentially produce a huge space improvement if no closure allocation is required and significant time improvement if the cost of corresponding operations is unchanged 16 For Next Class Homework correct version on Wiki due Monday Midterm distributed next Friday Future reading my notes on object oriented design COMP 210 Fall 2007 17