New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Cleora Stiedemann


Marketplace > Rice University > ComputerScienence > COMP 211 > PRINCIPLES OF PROGRAM DESIGN
Cleora Stiedemann
Rice University
GPA 3.72

Robert Cartwright

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Robert Cartwright
Class Notes
25 ?




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.

Similar to COMP 211 at Rice University

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.