CSC151.02 2016S, Review Session 9 (2016-04-07)
==============================================

**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))