Please follow the standard start-of-class routine.
Warning! You are being recorded (and transcribed) (provided the technology is working correctly).
Approximate overview
CHANGES.txt that describes what you’ve changed.CHANGES.txt that describes what you’ve changed.(export ...).Scholarly
Artistic/Cultural
Multicultural
Peer
Musical, theatric, sporting, academic, and similar events involving this section’s students are welcome.
Wellness
Misc
These do not earn tokens, but are worth your consideration.
Will Sam give us work over break?
No! But you might want to review stuff.
What is tracing?
Why trace?
Three Basic Rules
define statements.(define sqr (lambda (x) (* x x)))
(define p (lambda (x y) (+ (f x) (g y))))
(define f (lambda (y) (sqr (+ y 1))))
(define g (lambda (a) (+ a a)))
(define a 2)
(define b 3)
(p (- 10 (* a 4)) (+ (* a b) 2))
--> (p (- 10 (* 2 4)) (+ (* 2 3) 2))
--> (p (- 10 8) (+ (* 2 3) 2))
--> (p 2 (+ (* 2 3) 2))
--> (p 2 (+ 6 2))
--> (p 2 8)
; x y
--> (+ (f 2) (g 8))
; y
--> (+ (sqr (+ 2 1)) (g 8))
--> (+ (sqr 3) (g 8))
; x
--> (+ (* 3 3) (g 8))
--> (+ 9 (g 8))
; a
--> (+ 9 (+ 8 8))
--> (+ 9 16)
--> 25
To write algorithms, we need a bunch of tools.
How do we name things in Scheme?
(define NAME EXPRESSION)How do we sequence operations?
(define pb-open (open jar-of-pb)) (define hunk-of-pb (remove-contents pb-open)) (define half-sandwich (spread hunk-of-pb slice-of-bread))(spread (remove-contents (open jar-of-pb)) slice-of-bread)o. (o (r-s spread slice-of-bread) remove-contents open)
(o f g h) applies h then g then f.How do we make functions?
(define FUN
(lambda (PARAMS)
COMPUTATION))
We use conditionals to make choices.
(if TEST CONSEQUENT ALTERNATE) - a bit like a function with a different
evaluation strategy. Evaluate TEST. If the test is true (#t), evaluate
the CONSEQUENT and return its value. If the test is false (#f), evaluate
the ALTERNATE and return its value.(cond [TEST1 CONSEQUENT1] [TEST2 CONSEQUENT2] ... [else ALTERNATE]) -
An extended if. Evaluate TEST1. If it holds, evaluate CONSEQUENT1
and return its value, ignoring the rest. If TEST1 does not hold,
evaluate TEST2. If TEST2 holds, evaluate and return CONSEQUENT2.
If none of the tests hold, evaluate and return the value of ALTERNATE.To make choices, we need to be able to write expressions that return either
#t or #f. We use the term predicate to describe functions that return
#t or #f. We also usually write these ending in a question mark.
even?, char-upper-case?, square?, <=, string<=?, …We also combine the results of such expressions in three basic ways.
(not EXP) - Evaluate EXP and return “the opposite”. If EXP is
true (#t) (“EXP holds”), return #f. If EXP is false (“doesn’t
hold”), return #t.(and EXP1 EXP2 ...) - Evaluate each expression in turn. If one of them
is false, stop immediately and return false. If none of them is false,
return true.(or EXP1 EXP2 ...) - Evaluate each expression in turn. If one of them
is true, stop immediately and return true. If none of them is true,
return false.Write a procedure, (days-in-month month), that takes an integer representing
a month as a parameter and returns the number of days in that month.
1 is January (31 days), 2 is February (28) days …month is not an integer, do whatever you’d like (return a value,
likely a nonsensical value, crash and burn, …)month is an integer outside the range 1 .. 12, return false.We use a cond because there are at least four situations to consider.
(define days-in-month
(lambda (month)
(cond
[(= month 2)
28]
[(or (= month 9) (= month 4) (= month 6) (= month 11))
30]
[(<= 1 month 12)
31]
[else
#f])))
While we usually define procedures with lambda, we can also define them
in a variety of other ways, often for concision.
Composition (o f1 f2 ... fm fn): A function that takes one input and
applies fn, then fm, …, then f2, then f1.
(define make-pb-half (o spread remove-from-jar open-jar))More generally,
(define fun (o f g h))
(define fun
(lambda (x)
(f (g (h x)))))
Section:
(l-s fun ARG1) - Creates a function that takes one parameter
(ARG2), and computes (fun ARG1 ARG2).
(r-s fun ARG2) - Creates a function that takes one parameter
(ARG1), and computes (fun ARG1 ARG2).
(define prependHello (l-s string-append "Hello "))
(define prependHello (lambda (str) (string-append "Hello " str)))
(define subtract10 (r-s - 10))
(define subtract10 (lambda (num) (- num 10)))
We use o, l-s, and r-s primarily when we want to be concise.
We often use them when we don’t want to bother naming a function.
We also use them when we’re told to do so.
Sam likes o, l-s, and r-s for another reason. They change the way
we think about functions.
o, l-s, and r-s, we think about building functions by combining
other function in a few ways.We will frequently use these functions with things like map or pixel-map
or reduce or ….
Oooh! A new type.
(list VAL1 VAL2 ... VALn)
or null.(make-list n val) - Makes a list of n copies of val.(list EXP1 EXP2 ... EXPn) - Evaluate all the expressions and then
shove them together into a list.range
(range n) - Produces the list (0 1 2 ... (- n 1))(range start finish) - Produces the list
(start (+ 1 start) (+ 2 start) ... (- finish 1))(range start finish inc) - Produces the list
(start (+ inc start) (+ inc inc start) ... ?)(SOMETHING->list SOMETHING) - Convert some other type (e.g., string
to a list).(map fun lst)(filter fun lst)(sort may-precede? lst)Next class