--------------------------------------- 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.