Held: Monday, 4 April 2016

Back to Outline 32 - Numeric Recursion. On to Outline 34 - Turtle Graphics.

Summary

We explore why and how one writes local recursive procedures.

Related Pages

• Reading: Local Procedure Bindings
• Lab: Local Procedure Bindings
• EBoard 33 (Source 33)

Overview

• Why have local procedures.
• Creating local procedures with letrec.
• Creating local procedures with named let.

Administrivia

• New Partners! (Duh!)
• Food-like substance!
• 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.
  • 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
  • Thursday 10 am review session with Sam.
  • Thursday at 8pm in the CS Commons with

Upcoming Work:

• Reading for Tuesday:
  • Turtle Graphics
• Lab Writeup:
  • Send email titled CSC 151 Lab Writeup 33 (Your Names)
  • Do not include the underscores.
  • Send to CSC151-02-grader@grinnell.edu
  • Due before class on Wednesday.

Extra Credit

• Send your reports to rebelsky@grinnell.edu 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

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)

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.
• Post-break ExCo on British Politics Wednesdays at 8:00 in JRC 203. Starts this week (I think).

Local Procedure Bindings

• Today's class will focus not on something new, but on a better way to do something old: Define helper procedures.
• We frequently want to define procedures that are only available to certain other procedures (typically to one or two other procedures).
• We call such procedures local procedures
• Most local procedures can be done with let and let*.
• However, neither let nor let* works for recursive procedures.
• When you want to define a recursive local procedure, use letrec.
• When you want to define only one, you can use a variant of let called "named let".

letrec

• A letrec expression has the format

(letrec ([*name1* *exp1*]
         [*name2* *exp2*]
         ...
         [*namen* *expn*])
  *body*)

• A letrec is evaluated using the following series of steps.
  • First, enter *name<sub>1</sub>* through *name<sub>n</sub>* into the binding table. (Note that no corresponding values are entered.)
  • Next, evaluate *exp<sub>1</sub>* through *exp<sub>n</sub>*, giving you results *result<sub>1</sub>* through *result<sub>n</sub>*.
  • Finally, update the binding table (associating *name<sub>i</sub>* and *result<sub>i</sub>* for each reasonable i.
• Not that its meaning is fairly similar to that of let, except that the order of entry into the binding table is changed.

Named let

• Named let is somewhat stranger, but is handy for some problems.
• Named let has the format

(let *name* 
  ((*param1* *exp1*)
   (*param2* *exp2*)
   ...
   (*paramn* *expn*))
  *body*)

• The meaning is as follows:
  • Create a procedure with formal parameters *param<sub>1</sub>* ... *param<sub>n</sub>* and body *body*.
  • Name that procedure *name*.
  • Call that procedure with actual parameters *exp<sub>1</sub>* through *exp<sub>n</sub>* .
• Yes, that's right, we've packaged together the procedure definition and the procedure call.
• In effect, we're just doing

(letrec ((*name* (lambda (*param1* ...
*paramn
*)
                  *body*)))
   (*name* *val1* ... *valn*))

An Example

• As an example, let's consider the problem of writing reverse.
• A first version, without local procedures

(define reverse
  (lambda (lst)
    (reverse-kernel lst null)))
(define reverse-kernel
  (lambda (remaining so-far)
    (if (null? remaining)
        so-far
        (reverse-kernel (cdr remaining) (cons (car remaining) so-far)))))

The principle of encapsulation suggests that we should make reverse-kernel a local procedure.

(define reverse
  (letrec [(kernel
            (lambda (remaining so-far)
              (if (null? remaining)
                  so-far
                  (kernel (cdr remaining) (cons (car remaining) so-far)))))]
    (lambda (lst)
      (kernel lst null))))

The pattern of "create a kernel and call it" is so common that the named let exists simply as a way to write that more concisely.

(define reverse
  (lambda (lst)
    (let kernel [(remaining lst)
                 (so-far null)]
      (if (null? remaining)
          so-far
          (kernel (cdr remaining) (cons (car remaining) so-far))))))

Lab

• Work on the the lab.