---------------------------------------
Tutorial notes #5 for 3/12 or 3/13/2007

TA:       Stephen McCamant
Email:    smcc@mit.edu
Location: 36-113A or 36-115
http://people.csail.mit.edu/smcc/6.001-sp07/
----------------------------------------
Quiz 1 hand-back

Median for my students: 92/100

Go over tricky problems?

----------------------------------------
Project 1 work time statistics

Mean: 9.5 hrs
Quartiles: 5, 7, 12 hrs
Standard deviation: 6.35 hrs

How to make future projects go faster?

- You get less efficient if try to work
  for too long at once: start early, but
  do a bit every day.

- Talk through project with others (but
  list them as collaborators)

- Ask for help when you need it, not at
  the last minute

----------------------------------------
Project 1 hand-back

Comments in red are things I took off
points for.

Comments in green are things I didn't, but
they're still important.

----------------------------------------
Project 1 common mistakes

- Easiest way to lose lots of points:
  start late, turn in late, and skip the
  last couple of problems

- You need to write your own test cases
  (took off one point per problem, up to
   5, for this)

- Be sure to answer all the parts of all
  the questions.

- Problems in key generation:
  - Need to check that p*q is big enough
  - When retrying, need to pick new p,q

- random-prime can fail in many ways
  (you needed to give at least two)

- Procedures not running fast enough
  - "louis-mult" problem
  - Don't delay moding in exptmod

- We wanted you to do RSA on single,
  large numbers representing strings
  not sequences of small ones. (RSA on
  small numbers isn't secure.)

- I tested your code by actually running it
  - So make sure to use the right
    procedure names
  - And argument lists
  - And comment out all your test cases

- Make sure your test cases match your
  code
  - Rerun tests when you change the code,
    even if "this can't break anything"
  - The only legitimate way to get test
    results is by running the code you've
    written. Anything else is cheating.

- Be sure to list your collaborators
  - Collaboration is good, we encourage it
  - But, you *must* acknowledge your
    collaborators
  - And, you must write up your work
    yourself.
  - Having submissions online makes it
    easy for us to catch cheating, and
    we have.

----------------------------------------
Office-hours style open questions


----------------------------------------
All you need is HOPs

In my continuing quest to prove that
pairs don't need to be a primitive data
type, I started to write an
implementation of booleans using
higher-order procedures:

(define (my-if cond then else)
  (cond then else))

What definitions of my-true and my-false
go with this?


(define (my-true  then else) then)
(define (my-false then else) else)

Also, I want to get rid of pairs.


(define (my-car p) (p my-true))
(define (my-cdr p) (p my-false))

How should I write my-cons?



(define (my-cons a b)
  (lambda (selector)
    (if selector a b)))

While I'm at it, it would be nice to
replace numbers too. One idea is to
represent "n" by a higher-order function
that repeats its argument n times.
("Church numerals")

Write zero, one, zero?
(define (zero f) identity)
(define (one f) (lambda (x) (f x)))
(define one identity) ; equivalently
(define (zero? n)
  ((n (lambda (x) my-false)) my-true))

Write plus-one
(define (plus-one n)
  (lambda (f)
    (lambda (x)
      (f ((n f) x)))))

Write plus
(define (plus m n)
  (lambda (f)
    (lambda (x)
      ((m f) ((n f) x)))))

Write times
(define (times m n)
  (compose m n))

Write to-the
(define (to-the m n)
  (n m))

Write minus-one
;; Solution apparently due to Norman Ramsey
; (lag (cons m n)) -> (n+1 . n)
(define (lag p)
  (my-cons (plus-one (my-car p)) (my-car p)))
(define (minus-one n)
  (my-cdr ((n lag) (my-cons zero zero))))


Without a special form for if, it's hard to
write recursive procedures. But we can use
numerals to implement loops.

Are there any loops you can't do with
numbers?

You can't do a loop where you don't know at the beginning how long it
will run for, including things like interactive programs, as well as
evaluators for other programming languages. Also, there are some
functions that get so big, you won't be able to compute how many
iterations they'll take to compute.