CSC 151.01, Class 24: Randomness and simulation
Overview
- Preliminaries
- Notes and news
- Upcoming work
- Extra credit
- Friday PSA
- Questions
- Quiz
- Debrief from prior class
- Lab
- Debrief
Preliminaries
News / Etc.
- New partners!
- You are still awesome.
- I know that some of you were planning to look at last semester’s
exam 3 to study for the coming exam 3. Unfortunately, that exam
depends on some material we haven’t studied yet.
- Problems 1, 2, and 4 are of the style that might appear on the exam.
- You are not yet ready to do problem 4. I am not yet certain whether or not we will choose to include vectors on the exam.
- Have a great spring break!
Upcoming work
- There is no writeup for today’s class.
- Reading for Monday after break
- No homework over break.
- Exam 3 will be distributed after break.
- Yes, you will get exam 2 (and an answer key) back first.
Extra credit (Academic/Artistic)
- Visit the two exhibits at the Faulconer Gallery.
Extra credit (Peer)
Extra credit (Recurring peer)
- Listen to KDIC Wednesdays at 6pm - Witty banter with other
personalities and/or co-host. Also Indian, Arabic, and Farsi music.
(Up to two units of extra credit.) - Peer editing with SS. Talk to SS about the details. Make your English Lit more literate.
Extra credit (Misc)
- Host one or more prospective students.
Other good things
Friday / Spring Break PSA
- Please take care of yourselves.
- If you imbibe substances, do so in moderation (and, preferably, legally)
- If you cohabit, consent is absolutely positively necessary
- It’s the right thing
Questions
It feels like it would be easier to use a define in the body of
the procedure, rather than named let or letrec. Can’t I just do
that?
There are some semantic confusions with using
definein the body of a procedure. So we do not permit it. (We do discuss the idea of usingdefinerather thanletevery few years. We always decide to do without it.)
Could you go over named let? I find it confusing.
Sure.
Named let is intended to provide a “more natural” syntax for something that you do a lot of. (a) Define a recursive (helper) procedure; (b) call that procedure.
When we think about solving problems with helpers and tail recursion, a table helps us think.
When we design the table, we often name columns and think about their initial values.
Named let is intended to mimic that, but in Scheme syntax.
(let NAME ([PARAM1 VAL1]
[PARAM2 VAL2]
...)
BODY)
The other important issue about table-based solutions is that we say “Do it all again, updating each parameter as follows.” Amazingly, a procedure call makes sense for that.
(NAME (INSTRUCTIONS-FOR-UPDATING-COLUMN-1)
(INSTRUCTIONS-FOR-UPDATING-COLUMN-2)
...)
What do I put in for val1 and val2 and …
Answer one: If you think in terms of our traditionally way of writing a recursive helper.
(define helper
(lambda (PARAM1 PARAM2 ...)
BODY))
(define primary-procedure
(lambda (...)
(helper EXP1 EXP2 ...)))
If you can write that, it translates directly to
(define primary-procedure
(lambda(...)
(let helper ([PARAM1 EXP1]
[PARAM2 EXP2]
...)
BODY))
But if you want to think about it more directly, think in terms of the table. VAL1 etc. are what I put in the first row of the table.
What is the relationship between the body of the primary procedure and the body of the named-let procedure?
There is none. Each is independent. (Although the body of the primary procedure likely depends on the implementation of the named-let.)
Where is the first call to the procedure defined in the named let?
It is implicit.
If we don’t check preconditions, can we still use named let and is there anything else there?
Yes, you can still used named let. Often, you’ll see nothing else.
(define tally-odds
(lambda (lst)
(let table ([tally-so-far 0]
[remaining lst])
(cond
[(null? remaining)
tally-so-far]
[(and (integer? (car remaining))
(odd? (car remaining)))
(table (+ 1 tally-so-far)
(cdr remaining))]
[else
(table tally-so-far
(cdr remaining))]))))
What if we’re checking preconditions?
(define tally-odds
(lambda (lst)
(cond
[(not (list? lst))
(error "You are listless!")]
[(not (all integer? lst))
(error "You lack integrity")]
[else
(let table ([tally-so-far 0]
[remaining lst])
(cond
[(null? remaining)
tally-so-far]
[(odd? (car remaining))
(table (+ 1 tally-so-far)
(cdr remaining))]
[else
(table tally-so-far
(cdr remaining))]))])))
Can I use the parameters of the primary procedure in the body of the let?
Yes. Sometimes, it even helps you shrink your code. Consider our normal approach to iota, which involves counting up to n. Since the n doesn’t change, it doesn’t need to be a parameter to the (local) kernel.
(define iota
(lambda (n)
(let kernel ([i 0])
(if (= i n)
null
(cons i (kernel (+ i 1)))))))
Does named let do anything fancy other than let you define a procedure and call it immediately?
Nope. But “define a procedure and call it immediately” is a really common task.
Quiz
Wow, Sam screwed up a lot.
- Two missing names.
- One misspelled name.
- Two missing students. [+1 for that student]
- [+1 for everyone for Sam’s screwups; this may be the highest scoring quiz in history]
Debrief from prior class
We spent enough time on preliminary questions that I’m skipping this one.
Let’s look at the different ways people approached problem 2 (finding the furthest from zero using a local kernel), particularly the different places they put the kernel.
(define ff0
(letrec ([kernel ...])
(lambda (lst)
(cond
...))))
(define ff0
(lambda (lst)
(letrec ([kernel ...])
(cond
...))))
(define ff0
(lambda (lst)
(cond
...
[else
(letrec ([kernel ...])
...)])))
Which do you prefer? Why?
Which is easiest to change to named let?
Lab
It is hard to test random procedures, since they don’t have predictable output. (We could do a lot of calls and see if they meet a reasonable statistical distribution.)
Yes, we really do want you to use direct recursion on the first procedure.
These are zero-parameter procedures. They are procedures because we are encapsulating a series of steps. They have no parameters because they need no inputs.
When you see “Rolling … Rolling … Rolling …”, do you think
- “on the river”?
- “Rawhide”?
- None of the above?
If this question does not make sense, look for a YouTube Video of Ike and Tina Turner singing “Proud Mary” and the Blues Brothers singing “Rawhide”.
Debrief
The problem with tally-7-11? We have two calls to (pair-a-dice).
Sometimes both are called. Sometimes only one.
Lots of ways to write tally-sevens-elevens.
(define tally-7-11
(lambda (n)
(let ([this-roll (pair-a-dice)])
(cond
[(zero? n)
0]
[(or (= 7 this-roll) (= 11 this-roll))
(+ 1 (tally-7-11 (- n 1)))]
[else
(tally-7-11 (- n 1))]))))
; That first version does one extra roll. We should make sure that `n`
; is not zero before rolling.
(define tally-7-11
(lambda (n)
(cond
[(zero? n)
0]
[(let ([this-roll (pair-a-dice)])
(or (= 7 this-roll) (= 11 this-roll)))
(+ 1 (tally-7-11 (- n 1)))]
[else
(tally-7-11 (- n 1))])))
; That second version is kind of ugly. The old `count-odd-rolls?` was much
; nicer. Can we follow that model? We can if we write a helper procedure.
(define seven-or-eleven?
(lambda (roll)
(or (= 7 roll) (= 11 roll))))
(define tally-7-11
(lambda (n)
(cond
[(zero? n)
0]
[(seven-or-eleven? (pair-a-dice))
(+ 1 (tally-7-11 (- n 1)))]
[else
(tally-7-11 (- n 1))])))
; Can we do without a new procedure?
(define tally-7-11
(lambda (n)
(cond
[(zero? n)
0]
[(member? (pair-a-dice) '(7 11))
(+ 1 (tally-7-11 (-n 1)))]
[else
(tally-7-11 (- n 1))])))
; Or if we love section
(define tally-7-11
(lambda (n)
(cond
[(zero? n)
0]
[((disjoin (section = 7 <>) (section = 11 <>)) (pair-a-dice))
(+ 1 (tally-7-11 (-n 1)))]
[else
(tally-7-11 (- n 1))])))