Lab: Local bindings and recursion

Assigned
Friday, Oct 19, 2018
Due
Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
Summary
In this laboratory, we consider the various techniques for creating local recursive procedures, particularly letrec and named let. We also review related issues, such as husk-and-kernel programming.

Reference

A letrec statement has the form

(letrec ([name-of-recursive-proc-1 body-1]
         [name-of-recursive-proc-2 body-2]
         ...
         [name-of-recursive-proc-n body-n])
  expression
  expression
  ...
  expression)

This statement builds a new environment that maps names to values, adds all of the name/body pairs to the environment, evaluates the expressions, and forgets about the new environment it created. It is useful for temporarily creating local procedures, and for limiting access to kernels.

A named let is an alternative mechanism for defining recursive kernels. It can be used only when you want to define a single recursive kernel and call it immediately, and has the form

(let kernel ([name_1 exp_1]
             ...
             [name_n exp_n])
  body)

The named let tells Scheme to define a new procedure (whose name is kernel), with parameters that correspond to the names and whose body corresponds to body. It then immediately calls the new procedure with the value of the given expressions.

In other words, named let is shorthand for the following:

(letrec ([kernel (lambda (name_1 ... name_2) body)])
   (kernel exp_1 ... exp_n))

Exercises

Exercise 1: Furthest from zero, revisited

As the reading suggests, local kernels are particularly appropriate for checking preconditions. Local kernels are also appropriate for writing recursive helper procedures that take an extra parameter to accumulate a result.

For example, here is a helper-based definition of furthest-from-zero.

(define furthest-from-zero
  (lambda (numbers)
    (furthest-from-zero-helper (car numbers) (cdr numbers))))
(define furthest-from-zero-helper
  (lambda (furthest-so-far remaining-numbers)
    (cond
      [(null? remaining-numbers)
       furthest-so-far]
      [(> (abs (car remaining-numbers)) (abs furthest-so-far))
       (furthest-from-zero-helper (car remaining-numbers) (cdr remaining-numbers))]
      [else
       (furthest-from-zero-helper furthest-so-far (cdr remaining-numbers))])))

a. Rewrite this to make the helper local using letrec and to name the helper kernel.

b. Test your procedure on a few simple lists of numbers. Make sure to use both positive and negative numbers, and to include the furthest from zero at the front, back, and middle of the list.

c. When you are done, you may want to compare your answer to a sample solution contained in the notes on the exercise.

Exercise 2: Safely computing the furthest from zero

The procedure given above and your rewrite of that procedure, will fail miserably if given an inappropriate parameter, such as an empty list, a list that contains values other than real numbers, or a non-list. Rewrite furthest-from-zero so that it checks its preconditions (including that the list contains only real numbers) before calling the kernel.

Exercise 3: Computing the furthest from zero, revisited again

Rewrite furthest-from-zero using a named let rather than letrec. (The goal of this exercise is to give you experience using named let, so you need not check preconditions for this exercise.)

When you are done, you may want to compare your answer to a sample solution contained in the notes on the exercise.

Exercise 4: Tallying odd numbers

Here is the start of a recursive definition of a procedure that tallies the number of odd numbers in a list.

;;; Procedure:
;;;   tally-odd
;;; Parameters:
;;;   ints, a list of integers
;;; Purpose:
;;;   Determine how many values in ints are odd.
;;; Produces:
;;;   tally, an integer
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   tally is the number of odd values in ints.
(define tally-odd
  (lambda (ints)
    (tally-odd-helper 0 ints)))

(define tally-odd-helper
  (lambda (tally remaining)
    ...))

a. Finish the definition.

b. Rewrite the definition of tally-odd to make the helper a local procedure using a named let.

For those with extra time

Extra 1: Tallying odd numbers, revisited

Rewrite tally-odd (from Exercise 4) to use whichever of letrec and named let you did not use in that exercise.

Extra 2: Reflection

You have now seen two examples in which you’ve employed two different strategies for building local helpers, one that uses letrec and one that uses named let.

Reflect on which of the two strategies you prefer and why.

Extra 3: Alternating lists

A list of numbers is an odd-even-alternator if its elements are alternately odd numbers and even numbers, beginning with on odd numbers. A list of numbers is an even-odd-alternator if its elements are alternately even and odd, beginning with an even number . (We say that the empty list is both a odd-even-alternator and a even-odd-alternator.)

a. Write a predicate, numbers-alternating-parity?, that determines whether a non-empty list of numbers is either a odd-even-alternator or a even-odd-alternator. Your definition should include a a letrec expression in which the identifiers odd-even-alternator? and even-odd-alternator? are bound to mutually recursive predicates, each of which determines whether a given list has the indicated characteristic.

(define numbers-alternating-parity?
  (lambda (numbers)
    (letrec ([odd-even-alternator?
              (lambda (numbers) 
                ...)]
             [even-odd-alternator?
              (lambda (numbers) 
                ...)])
      ...)))

When you are done, you may want to compare your answer to a sample solution contained in the notes on the exercise.

b. Check your procedure on a variety of lists.

Notes

Notes on Exercise 1: Furthest from zero, revisited

Here is one possible solution.

(define furthest-from-zero
  (lambda (numbers)
    (letrec ([kernel
              (lambda (furthest-so-far remaining-numbers)
                (cond 
                  [(null? remaining-numbers)
                   furthest-so-far]
                  [(> (abs (car remaining-numbers)) (abs furthest-so-far))
                   (kernel (car remaining-numbers) 
                           (cdr remaining-numbers))]
                  [else
                   (kernel furthest-so-far 
                           (cdr remaining-numbers))]))])
      (kernel (car numbers) (cdr numbers)))))

Return to the exercise.

Notes on Exercise 3: Furthest from zero, revisited again

Here is one possible solution.

(define furthest-from-zero
  (lambda (numbers)
    (let kernel ([furthest-so-far (car numbers)]
                 [remaining-numbers (cdr numbers)])
            (cond
              [(null? remaining-numbers)
               furthest-so-far]
              [(> (abs (car remaining-numbers)) (abs furthest-so-far))
               (kernel (car remaining-numbers)
                       (cdr remaining-numbers))]
              [else
               (kernel furthest-so-far
                       (cdr remaining-numbers))]))))

Return to the exercise.

Notes on extra 3: Alternating lists

Once odd-even-alternator? and even-odd-alternator? are written, the definition is fairly straightforward. A non-empty list of numbers has alternating oddness/evenness if it’s not empty and it’s either an odd-even-alternator or an odd-even-alternator.

      (and (not (null? numbers))
           (or (odd-even-alternator? numbers)
               (even-odd-alternator? numbers)))

Each definition is also fairly straightforward. A list is a odd-even-alternator if it is empty or if the car is odd and the cdr is a even-odd-alternator.

             (odd-even-alternator?
              (lambda (numbers) 
                (or (null? numbers)
                    (and (odd? (car numbers))
                         (even-odd-alternator? (cdr numbers))))))

The definition of even-odd-alternator? is so similar that we will not provide it separately.

Putting everything together, we get

(define numbers-alternating-parity?
  (lambda (numbers)
    (letrec ([odd-even-alternator?
              (lambda (numbers)
                (or (null? numbers)
                    (and (odd? (car numbers))
                         (even-odd-alternator? (cdr numbers)))))]
             [even-odd-alternator?
              (lambda (numbers)
                (or (null? numbers)
                    (and (even? (car numbers))
                         (odd-even-alternator? (cdr numbers)))))])
      (and (not (null? numbers))
           (or (odd-even-alternator? numbers)
               (even-odd-alternator? numbers))))))

Note that there is a hidden moral here: The procedures defined in a letrec can be mutually recursive.

Return to the exercise.