Held: Tuesday, 28 October 2014

Back to Outline 30 - Preconditions, Revisited. On to Outline 32 - Characters and Strings.

Summary

We explore why and how one writes local recursive procedures.

Related Pages

• Reading: Local Procedure Bindings
• Lab: Local Procedure Bindings
• EBoard 31 (Source 31) (HTML 31)

Overview

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

Administrivia

• Continue partners.
• Yes, I do care that you follow the standard "pattern" for the six P's.
  • Three semicolons, one space, the word "Procedure", a colon.
  • Three semicolons, three spaces, the name of the procedure.
  • Three semicolons, one space, the word "Parameters", a colon.
  • Three semicolons, three spaces, the name of the first parameter, a comma, the type of the first parameter
  • Etc.

Upcoming Work

• Sign up to meet with me if you had difficulty on the exam (or even if you just want to discuss a few more problems or need help interpreting my scrawls).
• Lab writeup: Problem 4, http://bit.ly/151-2014F-w31.
• Reading for Wednesday: TBD.
• Homework 6 (to be assigned on Wednesday), due a week from Tuesday.
• Exam 3, distributed a week from Wednesday, due two weeks from Tuesday.

Extra Credit Opportunities

Academic

• CS Extra Thursday: Randomness in Computer Science.

Peer Support

• Football (Saturday at 1pm)
• Swimming scrimmage noon on Saturday
• Karan's radio show 11pm Thursday nights on KDIC
• Evan's radio show 5pm Friday nights on KDIC
• Donna's radio show Sunday midnight on KDIC

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.