Approximate overview
Token Events
Will the evening tutors be available during Finals week?
No.
Do we need to get full credit from the autograder to get full credit on labs?
No, not if you turn them in on time.
The only thing that matters is the human grader.
What’s the “mostly” mean?
Images used without citations.
Too-long presentations.
What is SoLA 5?
A chance to make up anything you didn’t get on SoLAs 1-4.
Will all the mini-projects be graded by Monday?
We hope so. I’m chatting with graders tomorrow.
How many labs were made optional?
Two (2), I think. That’s getting updated soon, too.
Guidelines: About five minutes plus about 3 min for Q&A.
Ordering
I’ll gather questions and then answer them in some order.
You may not ask “How do you implement match?”
For running times, where do you put the code to count?
Traditionally, we do two things to count.
First, define a counter.
(define MY-COUNTER (counter "agh"))
It depends a bit on what you want to count, but typically, you add the
(increment-counter! MY-COUNTER 'proc)immediately after the lambda for either (a) the main procedure or (b) any recursive helper.
We normally put displays in the same place.
Can we use your counter procedures?
Yes.
Will we be given code in which a counter is the only viable option?
Probably not. Usually, we say “Figure it out in whichever way you think is best (tracing, adding
writeln, adding counters, memory of related procedures and comparison to them).
What will “applicability to your goals look like”?
See the sample SoLA.
Can you go over writing higher-order procedures?
A higher-order procedure is a procedure that (a) takes another procedure as a parameter (e.g., the first parameter to
map), (b) returns a new procedure (e.g., compose and section), or (c) both.
To take a procedure as a parameter, there’s not much special. It looks like any other parameter, and you apply it as you would apply any other procedure.
E.g., Here’s a quick and dirty definition of
map.
(define my-map
(lambda (proc lst)
(if (null? lst)
null
(cons (proc (car lst)) (my-map proc (cdr lst))))))
Returning a new procedure can take two forms. You can just return a lambda expression. You can name the new procedure with
letorletrecand the just return the name.
;;; (make-multiplier n) -> procedure?
;;; n : number?
;;; Make a procedure that takes one parameter, x, and
;;; multiplies x by n.
(define make-multiplier
(lambda (n)
(lambda (x) (* n x))))
(define make-multiplier
(lambda (n)
(let ([multiplier (lambda (x) (* n x))])
multiplier)))
Here’s an example of doing both
;;; (apply-twice proc) -> procedure?
;;; proc : procedure?
;;; Create a procedure that takes one input, and
;;; returns (proc (proc (x)))
(define apply-twice
(lambda (proc)
(lambda (x)
(proc (proc (x))))))
Can you go over tail recursion?
Often, we do someting with the result of a recursive call. “Magic recursion fairy, make the recursive case work, and I’ll do a little bit more.” E.g., to sum a list, we have the magic recursion fairy sum the cdr of the list, and then we add the first element.
(sum '(1 2 3))
--> (+ 1 (sum '(2 3)))
--> (+ 1 (+ 2 (sum '(3))))
--> (+ 1 (+ 2 (+ 3 (sum '()))))
Bulding up the delayed work to do involves computing resources.
In tail recursion, as soon as the recursive call finishes, we’re done. We can return the same value that the recursive call returned.
We almost always achieve tail recursion by adding an extra parameter to a helper procedure.a Instead of “sum this list”, we say “sum the list and add it to the running sum; give me back the final result”
(sum '(1 2 3))
--> (helper 0 '(1 2 3))
--> (helper 1 '(2 3))
--> (helper 3 '(3))
--> (helper 6 '())
---> 6
To convert a regular recursive function to a tail recursive function, we normally write a helper, add the extra parameter, and move the “after recursive call” into “this is what we do to the extra paraemter”
Can we look at recursive cases for tree recursion?
Tree recursion should be much like direct recursion. Assume that when you recurse on the left subtree and the right subtree, the recursive call works correctly. You then combine one or both of those with any information at the “top” of the current tree.
Stupid example: Summing a tree.
(define sum-tree
(lambda (tree)
(if (empty-tree? tree)
0
(+ (bt/t tree)
(sum-tree (bt/l tree))
(sum-tree (bt/r tree))))))
Sample example: Finding in an arbitrary tree
(define tree-find
(lambda (str tree)
(cond
[(empty-tree? tree)
#f]
[(string-ci=? (bt/t tree) str)
(bt/t tree)]
[(tree-find str (bt/l tree))]
[else
(tree-find str (bt/r tree))])))