CSC151.02 2016S, Class 33: Naming Local Procedures ================================================== * New Partners! (Duh!) * Food-like substance! _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Questions. * Topical overview. * Lab. Preliminaries ------------- ### Admin * I hope you had a great break! * Grading is still not done. Hopefully I'll get through everything by Wednesday. ### Reminders * Office hours this week * See http://rebelsky.youcanbook.me. * Teaching TEC 154 at 10, so office hours are moving around * Ask me about other available times. * Tutor hours * Sunday, 3-5 p.m. * Sunday-Thursday, 7-10 p.m. * Weekly review sessions: * Wednesday at 8pm in the CS Commons with Evan. * Thursday 10 am review session with Sam. * Thursday at 8pm in the CS Commons with Someone. ### Upcoming Work: * Reading for Tuesday: * [Turtle Graphics](../readings/turtle-graphics-reading.html) * Lab Writeup: * Send email titled __CSC 151 Lab Writeup 33 (Your Names)__ * Do not include the underscores. * Send to * Due before class on Wednesday. ### Extra Credit * Send your reports to with subject "CSC 151 Extra Credit". (Do not include the quotation marks.) * Send opportunities to me before class with subject "CSC 151 EXTRA CREDIT OPPORTUNITY!" #### Academic / Artistic * Cafe Ta'amon on April 6 at 6pm, in JRC 101 (I think). * Cinderella on April 6 at 7pm, somewhere in Bucksbaum (I think). * Roxane Gay Convocation on Thursday (11 a.m., JRC 101). #### Peer * Post-break ExCo on British Politics Wednesdays at 8:00 in JRC 203. Starts this week (I think). Just show up; you don't need to sign up. * Meet with your clambassador all day Tuesday JRC by dhall. * Fun Japanese Spring Festival Friday at 7pm. Origami food! #### Miscellaneous * Pioneer weekend * Scarlet and Give Back Day Thursday (I will fund your donation of $5 if you find that to be an economic burden) * HOST A PROSPIE! #### Regular Peer * Social Dance Workshop Tuesdays 7:00-8:00 in Bucksbaum Dance Studio * Pun club Saturdays at 4pm in Younker * Electronic Potpourri on KDIC Fridays at Five * Space Odyssey KDIC Fridays at Six * Bollywood, Fridays, 7:30-8:30, Younker * Effective Altruism club, 2:30-3:30 Sundays in JRC 226. #### Misc #### Far in the Future * Lords of the Flies, April twentysomething. * Early in May: Adaptation of Rushdie's East West. ### Questions Topical Overview ---------------- We've been looking at recursion, particularly recursion over lists. In writing recursive procedures, we often find it helpful to write recursive helper procedures. * It makes certain types of problems easier to read or understand. Maybe a filter procedure. * Sometimes we want to check preconditions only once, and then do the real recursive work. (Check preconditions: Husk; doing the real work: kernel). The kernel is effectively a helpe procedure. * Sometimes leads us to more efficient solutions. Detour: Which is more efficient? (define sum (lambda (lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))) vs. (define sum (lambda (lst) (sum-helper 0 lst))) (define sum-helper (lambda (so-far remaining) (if (null? remaining) so-far (sum-helper (+ so-far (car remaining)) (cdr remaining))))) Note: Those two are more-or-less equally efficient. * Sometimes leads us to more efficient solutions. * irgb-brightest, when defined with direct recursion, can have a very inefficient solution because we might keep doubling the number of recursive calls. * In contrast, when defined with helper recursion, this is usually pretty efficient (define irgb-brightest (lambda (colors) (cond ; Only one color [(null? (cdr colors)) (car colors)] ; More than one color, first color is one of the brightest [(>= (irgb-brightness (car colors)) (irgb-brightness (irgb-brightest (cdr colors)))) (car colors)] ; More than one color, first color is not one of the brightest [else (irgb-brightest (cdr colors))]))) * Note: We assume that there is at least one color If we use helper recursion, we can write (define irgb-brightest (lambda (colors) (irgb-brightest-helper (car colors) (cdr colors)))) (define irgb-brighest-helper (lambda (so-far remaining) (cond ; We've looked at all the colors [(null? remaining) so-far] ; The best estimate so far is at least as bright as the ; next available color [(>= (irgb-brightness so-far) (irgb-brightness (car remaining))) (irgb-brightest-helper so-far (cdr remaining))] ] ; The next available color is brighter [else (irgb-brightest-helper (car remaining) (cdr remaining))] ]))) We also use helpers because the "table method" (see the whiteboard) can help us design and implement recursive procedures. And it's a lot easier to print out the status of your procedure. Our past experience tells us that helpers should be local. We'd like to write (define irgb-brightest (let ([irgb-brighest-helper (lambda (so-far remaining) (cond ; We've looked at all the colors [(null? remaining) so-far] ; The best estimate so far is at least as bright as the ; next available color [(>= (irgb-brightness so-far) (irgb-brightness (car remaining))) (irgb-brightest-helper so-far (cdr remaining))] ] ; The next available color is brighter [else (irgb-brightest-helper (car remaining) (cdr remaining))] ]))) (lambda (colors) (irgb-brightest-helper (car colors) (cdr colors))))) Problem: `let` doesn't work for recursive procedures. Solution one: Use `letrec` instead. Solution two: Use something that matches our table model: named let. (define irgb-brightest (lambda (colors) (let irgb-brightest-helper ([so-far (car colors)] [remaining (cdr colors)]) (cond ; We've looked at all the colors [(null? remaining) so-far] ; The best estimate so far is at least as bright as the ; next available color [(>= (irgb-brightness so-far) (irgb-brightness (car remaining))) (irgb-brightest-helper so-far (cdr remaining))] ] ; The next available color is brighter [else (irgb-brightest-helper (car remaining) (cdr remaining))] ]))) Lab --- Start looking at the lab.