Thank you to the students who showed up so that we'll have notes that that other students can read over later.

Finding This Page

• Go to http://www.cs.grinnell.edu/~rebelsky/
• Click on "CSC 151" at the top of the page
• Click on "EBoard" in the "Current" row

Notes

• Happy Scarlet and Give Back day
• I did not pre-prepare sample questions today, so I'll generate questions a bit more "on the fly".

Overview

• About the quiz
• Your questions.
• Sample quiz questions.
• More of your questions.

The Quiz

Topics

• Numeric recursion
• Helper recursion with local helpers (letrec and named let)
• Turtles
• Maybe a little bit of iteration

Types of questions

• Given this code, what is the output? (E.g., what figure does the turtle draw?)
• What code might generate this output? (I.e., write the appropriate series of turtle operations.)
• Show steps.
• Write a procedure.
• Write a pattern.
• Document this procedure
• Fill in the blanks.
• Identify errors.
• Convert between kinds of helper recursion (external, letrec, named let)

Your Questions

Can we compare list recursion and numeric recursion?

When we think about list recursion, we have two basic parts to every recursive function. (There may be multiple versions of each part.)

"Base case": Empty list, singleton list, identified value if we're just looking for the first one, etc.

"Simplify for recursive case": Take the cdr.

For numeric recursion, we also have base cases and recursive cases.

"Base case": 0, 1, n (if counting up), "close enough to some goal" (e.g., if we are approximating the square root of 2 with successive approximations)

"Simplify for the recursive case": Subtract 1 (counting down to 0 or 1), add 1 (counting up to n), divide by 2 (counting down to a small number), ...

Can we practice switching through the different kinds of local procedure bindings?

Sure. We'll do that as part of the sample quiz questions.

Do turtles always start at (0,0), facing to the right?

If the turtle is created with turtle-new, then yes.

If the turtle is created with turtle-clone, then no. (The goal in turtle-clone is to maintain image, position, and direction.)

When we use turtle-turn!, what direction does it turn?

Clockwise (to the right from the direction facing, assuming that you are turning a positive amount).

Also, the opposite of what experience would lead you to expect, since everything tends to be upside-down in GIMP coordinates.

Angles are "upside-down" from what you expect. 90 degrees is "down", not "up".

Can you turn a negative amount?

Yes. That's counter-clockwise (or left)

Sample Quiz Questions

Draw this picture (hexagon)

Write a series of instructions to draw a hexagon with side-length 20.

Draw this picture (star)

Write a series of instructions to draw a five-pointed star.

Draw this picture (abstract)

"It looks like California, but with sharp edges."

Interpret this Scheme code

    (define canvas (image-show (image-new 200 200)))
    (define trop (turtle-new canvas))
    (turtle-teleport! trop 100 100)
    (for-each
      (lambda (x)
        (turtle-forward! trop (* 10 x))
        (turtle-turn! trop (* 45 x)))
       (cdr (iota 7)))

Interpret this Scheme code

    (define canvas (image-show (image-new 200 200)))
    (define trop (turtle-new canvas))
    (turtle-teleport! trop 100 100)
    (repeat 8
      (lambda ()
        (turtle-forward! trop 10)
        (turtle-turn! trop 45)))

Convert from external helper to letrec

    (define tally-odds
      (lambda (lst)
        (tally-odds-helper 0 lst)))

    (define tally-odds-helper
      (lambda (tally remaining)
        (cond
          ([null? remaining]
           tally)
          [(odd? (car remaining))
           (tally-odds-helper (+ 1 tally) (cdr remaining))]
          [else
           (tally-odds-helper tally (cdr remaining))])))

A Solution

"Just add a letrec before the lambda and shove the definition of tally-odds-helper into that letrec."

    (define tally-odds
      (letrec ([tally-odds-helper
                (lambda (tally remaining)
                  (cond
                    ([null? remaining]
                     tally)
                    [(odd? (car remaining))
                     (tally-odds-helper (+ 1 tally) (cdr remaining))]
                    [else
                     (tally-odds-helper tally (cdr remaining))]))])
        (lambda (lst)
          (tally-odds-helper 0 lst))))

Convert from external helper to named let

    (define tally-odds
      (lambda (lst)
        (tally-odds-helper 0 lst)))

    (define tally-odds-helper
      (lambda (tally remaining)
        (cond
          ([null? remaining]
           tally)
          [(odd? (car remaining))
           (tally-odds-helper (+ 1 tally) (cdr remaining))]
          [else
           (tally-odds-helper tally (cdr remaining))])))

A Solution

• "Put in a let and the name".
• "Put in the parameter names in square brackets."
• "Put in the intital value.s"

• "Copy and paste the body."

  (define tally-odds
    (lambda (lst)
      (let tally-odds-helper ([tally 0]
                              [remaining lst])
        (cond
          ([null? remaining]
           tally)
          [(odd? (car remaining))
           (tally-odds-helper (+ 1 tally) (cdr remaining))]
          [else
           (tally-odds-helper tally (cdr remaining))]))))
  

• It's weird. There's no explicit call. You learn to deal with this for named let.

Generalize

Write a generalized tally pattern that we can easily turn into something that can tally any type of value.

Fix Code

The aforementioned tally-odds will fail miserably if the list contains "a" or others "odd to ask whether they are odd" values. Fix the code.

Convert from letrec to named let

    (define iota
      (lambda (n)
        (letrec ([kernel (lambda (so-far i)
                           (if (= i 0)
                               so-far
                               (kernel (cons i so-far) (- i 1))))])
          (kernel null n))))

Print results

Consider the following procedure

    (define r
      (lambda (lst)
        (let kernel ([a null]
                     [b lst])
          (display (list 'kernel a b)) (newline)
          (if (null? b)
              a
              (kernel (cons (car b) a) (cdr b))))))

What is the output when we do (r (iota 5))?

Solution

    (kernel '() '(0 1 2 3 4))
    (kernel '(0) '(1 2 3 4))
    (kernel '(1 0) '(2 3 4))
    (kernel '(2 1 0) '(3 4))
    (kernel '(3 2 1 0) '(4))
    (kernel '(4 3 2 1 0) '())

Evil print results

    (define r
      (lambda (lst)
        (let kernel ([a null]
                     [b null]
                     [remaining lst])
          (display (list 'kernel a b remaining)) (newline)
          (if (null? remaining)
              (list a b)
              (kernel b (cons (car remaining) a) (cdr remaining))))))

What is the output for (r (iota 5))?

How would you describe what this procedure does?

Why would anyone ever want to use this procedure?

A Solution

    (kernel '() '() '(0 1 2 3 4))
    (kernel '() '(0) '(1 2 3 4))
    (kernel '(0) '(1) '(2 3 4))
    (kernel '(1) '(2 0) '(3 4))
    (kernel '(2 0) '(3 1) '(4))
    (kernel '(3 1) '(4 2 0) '())

A claim: This separates the values at even and odd positions, giving you back in .

    (r (list "a" "b" q" 3 1 2))