Held: Monday, 30 March 2015

Back to Outline 31 - Numeric Recursion. On to Outline 33 - Turtle Graphics.

Summary

We explore why and how one writes local recursive procedures.

Related Pages

• Reading: Local Procedure Bindings
• Lab: Local Procedure Bindings
• Morning EBoard 32 (Source a.m. 32)
• Afternoon EBoard 32 (Source p.m. 32)

Overview

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

Administrivia

• New Partners!
• Welcome back! I hope that your breaks were spectacular.
• Quizzes 6-8 returned. More graded work coming soon.

Upcoming Work

• Lab Writeup: Problem 4. http://bit.ly/151-2015S-lab32
• Reading for Tuesday:
  • Turtle Graphics

Extra Credit Opportunities

Academic

• Wedneday, April 1 Scholars Convocation on Implicit Bias.
• CS Table Friday: Therac 25 (readings coming soon)

Peer Support (Morning Section)

• Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m.

Peer Support (Afternoon Section)

• 7:30 p.m. on April 2: Gender as a Process. EE talks afterwards

Miscellaneous

• Wednesday evening discussion. (Terrifyingly enough, I get to facilitate one of the discussions.)

Notes on Exam 2

• Exam 2 is graded but will not be returned until Wednesday because a few people have extensions until Tuesday night.
• Academic honesty issue 1: Many students were careless in citing code from readings/labs/homework.
  • You are expected to cite anything that's not the exam.
  • The College does expect me to report failure to cite to the Committee on Academic Standing. Neither you nor I want that to happen.
  • If you neglected to cite because of misunderstanding of polices, please get citations to me by 5pm today.
• Academic honesty issue 2: I received reports of students collaborating on the exam.
  • "I saw some of your students talking about the exam."
  • "I heard the following conversation: 'How do you make the code faster?' 'Use a let.'" (Conversation simulated.)
  • "I don't feel comfortable signing the second statement."
  • Let's treat this in an exercise in self governance. I'll work with both classes on deciding what to do. But you need some time to reflect, so at the start of class on Tuesday, we will discuss how I might handle this issue.

Husk and Kernel Programming

• Particularly for recursive procedures, it is inefficient to check preconditions at every recursive call
  • If the preconditions were met for the first call, they should be met for every subsequent call.
• Hence, programmers tend to use what I refer to as "Iowa's Great Contribution to Programming": The Husk-and-Kernel approach
  • The husk checks the preconditions and, if all preconditions are met, calls the kernel.
  • The kernel does the real work.
• Corn serves as the metaphor: The husk protects the kernel, and the kernel is the valuable part.
  • And no, Husk-and-Kernel programming was not invented in Iowa.

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 thate 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.