This class will be recorded! Its use is limited to members of the class. Please do not share with others.
Approximate overview
(when ((close-to-finishing-during-class students conditionals-lab) < 1/2)
(announce "We will continue this lab tomorrow")
(note "This won't always happen")
(re-jigger! syllabus))
When appropriate, I will post details to the Announcements channel.
I’m not sure if all of these links are correct. Let me know if any are not.
Rules for tracing conditionals
(if TEST CONSEQUENT ALTERNATE): Evaluate TEST.
TEST evaluates to something truish, replace the if expression
with CONSEQUENT and continue evaluating the consequent.TEST evaluates to something false, replace the if expression
with ALTERNATE and continue.(and EXP1 EXP2 ...): First, evaluate EXP1.
EXP1 is false, stop and return false.EXP1 is truish, evaluate (and EXP2 ...).(and EXP1) is the value of EXP1.(and) is true. Because and returns false
if any of its parameters is false.(or EXP1 EXP2 ...): First, evaluate EXP1.
EXP1 is false, evaluate (or EXP2 ...).EXP1 is truish, return the value of EXP1.(or) is false.Like all tracing, we take it a step at a time.
(define fun
(lambda (x)
(if (integer? x)
(if (odd? x)
'oi
'ei)
'ov)))
For convenience, let’s write it like this. (Don’t do so in practice.)
(define fun
(lambda (x)
(if (integer? x) (if (odd? x) 'oi 'ei) 'ov)
))
Why the evaluation order?
(fun 2.4)
; Make sure the parameter is evaluated. Check.
; Replace the procedure call with the body of the procedure
; while subtituting in the actual argument for the formal parameter. --> (if (integer? 2.4) (if (odd? 2.4) 'oi 'ei) 'ov)
; If we follow the normal order of replacement/tracing, we'd
; evaluate the (odd? 2.4), which gives us a crash.
; Real order: Evaluate the (integer? 2.4) --> (if #f (if (odd? 2.4) 'oi 'ei) 'ov)
; Order: Keep only the alternate because the test return false --> 'ov ```
Real practice
(fun (fun 4))
; Rule: Find the procedure.
; Find the parameter for the inner call. (We need to evalaute
; the parameter to the outer call before we apply the outer proc.)
; That parameter is 4.
; Substitute
--> (fun (if (integer? 4) (if (odd? 4) 'oi 'ei) 'ov))
; Evaluate the test (integer? 4)
--> (fun (if #t (if (odd? 4) 'oi 'ei) 'ov))
; Replace by consequent
--> (fun (if (odd? 4) 'oi 'ei))
; Evaluate test
--> (fun (if #f 'oi 'ei))
; Take alternate
--> (fun 'ei)
; Substitute (body for proc, arg for param)
--> (if (integer? 'ei) (if (odd? 'ei) 'oi 'ei) 'ov)
; Evaluate the test
--> (if #f (if (odd? 'ei) 'oi 'ei) 'ov)
; Take the alternate
--> 'ov
; We're done
Tracing and
(define poi
(lambda (val)
(and (integer? val) (positive? val) (odd? val))))
Why order of evaluation matters.
(poi 2.4)
; Substitute body of procedure, substitute arg for param
--> (and (integer? 2.4) (positive? 2.4) (odd? 2.4))
; Suppose we evaluate all of the parameters to and
--> (and #f (positive? 2.4) (odd? 2.4))
--> (and #f #t (odd? 2.4))
BOOM!
Evaluating that correctly
(poi 2.4)
; Substitute body of procedure, substitute arg for param
--> (and (integer? 2.4) (positive? 2.4) (odd? 2.4))
; Evaluate first parameter
--> (and #f (positive? 2.4) (odd? 2.4))
; And stop with #f
--> #f
Another example
(poi -5)
--> (and (integer? -5) (positive? -5) (odd? -5))
--> (and #t (positive? -5) (odd? -5))
--> (and (positive? -5) (odd? -5))
--> (and #f (odd? -5))
--> #f
And another
(poi 4)
-->
And another
(poi 5)
-->
Option: List all the cases
(define median-of-three-a
(lambda (x y z)
(cond
[(<= x y z)
y]
[(<= x z y)
z]
[(<= y x z)
x]
[(<= y z x)
z]
[(<= z x y)
x]
[(<= z y x)
y]
[else
(error "Math makes no sense")])))
Note: If you use < rather than <=, you may get some strange issues
if two values are the same.
Option: Decision tree
(define median-of-three-b
(lambda (x y z)
(if (<= x y)
(if (<= y z)
y
(if (<= x z)
z
x))
(if (<= x z)
x
(if (<= y z)
y
z)))))
Option: Math!
Idea: “Chop off the smallest and largest.”
(define median-of-three-c
(lambda (x y z)
(- (+ x y z)
(min x y z)
(max x y z))))
Option: Some weird hybrid
Done live!
(define median-of-three-d
(lambda (x y z)
(if (<= x y)
(if (<= y z)
y
(max x z))
(if (<= x z)
x
(in y z)))))
Question: Which do you prefer? Why?
Which of a and b is likely to be faster / more efficient?
I did not write this problem, so I’m not completely certain what my colleague was thinking. But I’d like to talk about it and the possible issues you might encounter.
In a particular company, employees are given IDs that consist of a string of 6 digits, e.g., “419109”.
Write a procedure,
(employee-id? str), that takes a string as input and determines whether the string is a valid employee id. You need not check thatstris a string.
(You’re not expected to do that yet, but you will be soon.)
;;; (employee-id? str) -> boolean?
;;; str : string?
;;; Determine if str is a valid id, in this case, a length-six
;;; string all of whose characters are digits.
What are some inputs you might try and what answers do you expect?
"123456" -> #t [“normal” case]"419109" -> #t [“normal” case]"1" -> #f [too few digits]"000659" -> #t [leading zeros]"65432x" -> #f [right length, non-digit]Spend a few minutes writing the procedure (or thinking about how you would write the procedure).
Hint: string->number may help.
Sam’s first solution.
(define employee-id?
(lambda (str)
(and (string->number str)
(= (string-length str) 6))))
What are some stranger inputs that might cause problems? (“Edge cases” “Corner cases”)
Black box: Without knowing the implementation.
White box: If we do know the implementation.
Inputs / expectations / explanations
(define employee-id?
(lambda (str)
(and (string? str)
(string->number str)
(= (string-length str) 6))))
string->number and string-length(string->number str) returns false if it cannot convert
the string to a number. (This can be a good strategy for procedure
design; instead of crashing, return false.)How might you fix that?
What other potential problems are there?
You don’t have to deal with them in the lab, but you should think.
Please try to ask questions on the Q&A channel and leave this section for (a) things I am unclear about in that channel and (b) things that came up while you were listening to me this a.m.
Why isn’t the schedule fixed?
Um. It will be.
Can you tell me more about the string->number procedure.
> (string->number "000111")
111
But we are checking the string length of the original number.
Same partners! Switch who starts.
Please make sure to title your group correctly.