EBoard 16: Recursion

This class will be recorded! Its use is limited to members of the class. Please do not share with others.

Approximate overview

• Administrative stuff [~10 min]
• Q&A [~10 min]
• Quiz [~10 min]
• Discussion of mini-project 3 [~30 min]
• Discussion of recursion [~30 min]

Administrative stuff

Notes and News

• Happy Monday!
• I’m back in my campus office.
  • But not particularly competent at using photos I’ve taken as backdrops.
• Apologies on delays in grading; this is one of those semesters in which my workload seems higher than my available time.
  • Admittedly, that’s the case almost every semester.
• The Registrar’s office wants me to remind you that Friday is the S/D/F deadline and also the Withdraw deadline.
• You know the drill on evening tutoring. Please use the evening tutors. Please consider visiting them in person (if you are on campus).
• Today is a “talk class”; there is no lab.
• Note: The new lab policy is that you can turn in what you’ve done when you reach 4:30 p.m. (I’d recommend that you do the rest at some point, to make sure you understand, but I want to respect your time.)
  • This does not apply to today’s class.
• Tomorrow’s reading is the same as today’s. There is no new reading writeup. You might just skim, you might review.
• Thank you once again to those who are actvely posting questions and helping each other (within reason) on Teams.
• I’m intrigued to see that you are encountering very different issues with this mini-project than last term’s students encountered.
• “afk” = “away from keyboard”. That is, I’m not at my computer.

Upcoming activities and other token earning things

Events

• Mentor session Wednesday at 7 pm. Practice for the SoLA 2! Learn recursion from someone who teachers better than Sam.
• CS major declaration information session Thursday at 5pm.
• 4+1 BA/MS in CS Program info session Friday at noon.
• CS Table Monday, 1 March 2021 at noon.
• Journalism Ethics Workshop, 7:00-8:30 pm, Thursday, March 4 and Tuesday, March 9

Upcoming work

I’m not sure if all of these links are correct. Let me know if any are not.

• Mini-project 3 is due TONIGHT.
• No reading response for Tuesday. But review anyway.
  • Recursion
• No lab writeup.
• Quiz today: Unit testing with RackUnit
• SoLA 2 will be on Thursday
  • Review session Wednesday night
  • Class Thursday: Sam answers questions about sample SoLA questions and the exam topics.

Q&A

We’ll be talking about the mini-project after the quiz, so no questions on the mini-project until then.

We’ll be talking about recursion after we talk about MP3, so no questions on recursion.

Is the SoLA really Thursday?

Yes. But I’ll give you two days because of the confusion.

How do we sign up for visiting the drop-in-tutors in person?

Step 1: Go to the CS Team

Step 2: Go to the Evening Tutoring Channel

Step 3: Click on “Files”

Step 4: Click on “Sign Up For Lab Space”

Make sure to Self-Gov the signup.

What are the approximate answers to this quiz?

(test-equal? message something something-else)

Do we have to make a test suite?

No.

Do we have to add a message to each test-equal?

Yes.

Do we need to have a message for test-equal?

You need something for the message argument. It could “”.

It’s nice to have something so that you can tell which test failed.

What will the style problem on the second SoLA look like?

Easier.

We’ll probably add let to the mix.

What’s the difference between test-equal? and check-equal?? Are there situations we should use the latter?

For what we know, they are equivalent, except for parameter order.

I prefer that you use test-equal?

You might use check-equal? in a test suite where you don’t want to have to write the message.

What is the epsilon in check=?

Inexact numbers are approximated in Racket.

So when we do computations that should return the same numeric value, but might instead return something close.

(test-= (sqr (sqrt 2)) 2.0 ...)

They won’t be equal, but they are pretty close.

We should specify what answers are close enough.

(test-= (sqr (sqrt 2)) 2.0 0.00001) says “It’s okay as long the two numbers are within 1/10000 of each other.”

If we were dealing with something like (test-= (sqr (sqrt (expt 2 -100))) (expt 2 -100) (expt 1 -103))

It’s supposed to be “how close is ‘close enough’”?

> (test-= "small number" (sqr (sqrt (expt 2 -100))) (expt 2 -100) (expt 10 -103))
> (test-= "medium number" (sqr (sqrt 2)) 2 (expt 10 -103))
--------------------
medium number
. FAILURE
name:       check-=
location:   interactions from an unsaved editor:56:2
params:
  '(2.0000000000000004
    2
    1/10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)
--------------------

What if we don’t get credit on a LA?

Take it again on the next SoLA.

There are five SoLAs all together.

The fifth one has no new material.

You should also talk to an evening tutor or an individual tutor or SamR or … about the problem to understand the topic and the particulars.

Quiz

• Students should hang out here after class.

Notes for/from mini-project 3

An important lesson …

• Don’t bang your head against the wall for more than five or ten minutes.
• Ask for help!
• Sam seems to reply more quickly to Teams messages.

Document -> Test -> Implement -> Test

I am serious that you should use the “document, then write tests, then implement, then write more tests” approach. There are multiple reasons to do so.

Why document?

• Documentation helps make sure that you kno what you want your procedure to do. If you don’t have a clear idea of what it should do, you’ll have trouble writing it.
• Documentation makes it easier for others to help you because they can tell what you want to do.
• Documentation tells us parameter types, which lets us catch parameter-type errors.

Why write tests before code?

• Tests make concrete what the documentation means. They help you codify in your head (and in bits) what the code should do.
• They help others help you.
• They let you think about issues before you are biased by what you have written.
• It’s okay to start with just two or three.

Why write tests after code?

• Returns you to the question of “Am I sure it works in the edge/corner cases?”
• Lets you think about issues raised by the implementation.
• Encourages you to think more broadly about the procedure again.

Intervening questions

Where should I document?

Everywhere!

Broadly in acknowledgements.

Particuarly in particular places.

Should we turn in one mini-project as a group?

No.

You should not be working that closely together.

Do we have to credential people?

No. “I know this person is smart because the second and third letters of their name are A.”

What if we don’t know someone’s name.

Explain context. “I got help from the Sunday evening tutor.”

Decompose, decompose, decompose

I see many of you writing long, complex, hard-to-read expressions. Remember, other human beings are supposed to be able to read your code. So decompose!

How?

• Write helper procedures.
• Use let or let*.

Why?

• More readable.
• You can test the individual parts.
• You better understand the relationships between parts.

Questions

Do we have to document each variable in the let?

It’s just good practice. Good names may suffice.

An example

Goal: Write (count-words words filename).

Decompose: I know how to read a string from a file, so I should implement count-words with (count-words-in-string words str).

;;; (count-words-in-string words str) -> listof (listof word/number)
;;;    words : listof string?
;;;    str : string?
;;; Count how many times each word in words appears as a separate
;;; word in str.  Return something of the form 
;;;    '(("word" count) ...)

Hmmm … Giant strings are hard to think about. So perhaps I should think about breaking count-words in string into: (a) separate a string into a second list of words and (b) (count-words-in-list words list-of-words).

Can I separate a string into a list of words? I think I did that on the rex lab. I’ll cite my partner.

Or “I seem to recall Sam posting that somewhere. I’ll copy it and cite him.”

;;; (count-words-in-list words list-of-strings) -> listof (listof string/number)
;;;    words : listof string?
;;;    list-of-strings :  listof string?
;;; Count how many times each word in words appears as an element of
;;; list-of-strings.  Return something of the form 
;;;    '(("word" count) ...)

I’ll need to count each word separately, so I should write a count-word procedure and then I’ll map it over my list of words.

;;; (count-one-word word list-of-strings) -> listof word/number
;;;    words : listof string?
;;;    list-of-strings :  listof string?
;;; Count how many times word appears as an element of list-of-strings.  
;;; Returns something of the form '(word count)

That’s easy enough for me to write based on things I know, such as tally (or tally-value) and one or two other things.

Questions

Does it ever hurt to write too many procedures?

In some cases, it takes you more time.

In some cases, it makes your code slower.

But it’s a good first step in many cases.

Could you explain using let outside of lambda?

(define proc
  (let ([binding one]
        [bind two]
        ...)
    (lambda (...)
      ...)))

Idea: We are generating a bunch of names that we can use within the lambda.

We can think of DrRacket as evaluating the let and plugging everything in.

Could you explain about using lambda within the let?

;;; (add-to-all val lst) -> listof number?
;;;    val : number?
;;;    lst : listof number?
;;; Adds val to each element of lst, producing a new list.
(define add-to-all
  (lambda (val lst)
    (let ([helper (lambda (x) (+ val x))])
      (map helper lst))))

Efficiency

Some of you asked why your code runs so slowly. The most common reasons are

• You are repeating work.
• You are repeating computationally expensive or slow work.
• You are doing unnecessary work. For example, I’ve seen people use string->list and then list->string in quick succession.
• You are using comparatively expensive procedures that you don’t realize are expensive. For example, you should avoid repeated use of list-ref
• All of the above.

Here’s one easy thing to fix: Reading from a file is slow. Really slow. So try not to read from the same file multiple times. Here are some changes you might make.

If you’ve written (tally-word-in-file word filename) which counts how often word appears in filename, you might to use (tally-word-in-list word lst) or (tally-word-in-string word str) instead.

If you find yourself repeatedly reading the Dale-Chall list, name it.

;;; dale-chall-words : listof string?
;;; All the Dale-Chall easy words, in a convenient list.
(define dale-chall-words (file->lines "DaleChall.txt"))

Or perhaps

(define easy-word?
  (let ([dale-chall-words (file->lines "DaleChall.txt")])
    (lambda (word)
      ...)))

Some tips on debugging

I’ll ask you to add some of your own.

• Reindent your code with Ctrl-i. Amazingly, some errors are just mis-parenthesization.
  • That’s one of the reasons I am so critical about style. Following stylistic guidelines helps you identify/avoid errors.
• Check parameter types! Some errors are just due to us calling a procedure with the wrong kind of parameter or the parameters in the wrong order.
  • That’s another reason I encourage you to document early.
• Find the smallest/simplest case in which your code does not work and trace it by hand or at least think through the steps. Or just trace any non-working input.
• Try small parts of your code to make sure they work as you expect. That may involve decomposing your procedure or just copying parts from the definitions pane, pasting them in the interactions pane, and editing them.
• Record your expectations in tests. That helps ensure that once you fix something, you don’t break it again later.
• Ask others for help. Evening tutors are great. And they’ll help you not go too far off the path.
• Use a rubber plant or teddy bear or CS person or non-CS person or ….
• Explain as if you’re the teacher and they are the student.
• Take a break and come back to the problem later. Sometimes you are too close to the problem to see the error; a break helps.
• Explain what your problem is.
• Draw pictures of what’s happening.
• Work on a similar problem / another problem.
• Go to Teams and answer other people’s questions.

On section

Many of you are confused by section. I posted this in the Q&A channel, but it’s long, so I’m rewriting it here. It also gives you a chance to ask questions.

Section is one of those things that don’t make sense until something clicks. Let me try to see what I can do to help.

• Think of section as “another way to write procedures as an alternative to lambda”.
• We use it for limited situations: Procedures that do little more than call another procedure with “canned” values and of their own parameters.
• Consider (define add2 (lambda (x) (+ 2 x))). All add2 does is call + with a “canned” value (2) and add2’s parameter (x).
• That’s an opportunity for section. So we could also write (define add2 (section + 2 <>)).

But when does the <> (“diamond”) get filled in?

• Just as you don’t fill in a parameter for a procedure until you apply the procedure, you don’t fill in the diamond until you apply the procedure.
  • You might fill it in by just applying it directly.
  • You might fill it in by using it with map or filter or …
  • See the tracing example below.
• Let’s think about it in terms of the procedures we already know.
• We now know (or at least I hope we do), that (lambda (x) (+ 2 x)) is “a procedure that takes one input, x, and adds 2 and that input”.
• We should read (section + 2 <>) as “a procedure that takes one input and adds 2 and that input”. It’s just a more concise way of writing the lambda expression. And, to many people, it’s easier to read.

Getting to section

We might start by defining a helper procedure that determines whether At this stage of your career, you might find it easier to get to section in a series of steps. For example, consider the following procedure.

;;; (extract-bigger-than lower-bound vals) -> list-of integer?
;;;   lower-bound : integer?
;;;   vals : listof integer?
;;; Extract all the values from vals that are strictly bigger 
;;; than lower-bound.

A starting point

We might start by defining a helper procedure that determines whether a single value is bigger than val and then filter the list using that procedure.

(define extract-bigger-than
  (lambda (lower-bound vals)
    (let ([bigger-than-lower-bound
           (lambda (x) (> x lower-bound))])
      (filter bigger-than-lower-bound vals))))

Let’s verify that it works. (We should use tests, but sometimes it’s nice to see the output.)

> (extract-bigger-than 5 (list 9 1 2 18 3 5 4 -2 7)) 
'(9 18 7)

Yes, that’s what I wanted.

From lambda to section

Looking at bigger-than-val, I see that it takes the form appropriate for section. That is, we’re just filling in one of the two parameters to the > procedure.

I can use section to make the code a little bit shorter.

(define extract-bigger-than
  (lambda (lower-bound vals)
    (let ([bigger-than-lower-bound (section > <> lower-bound)])
      (filter bigger-than-lower-bound vals))))

And I’ve confirmed that it works using the tests I’ve written. (Don’t worry, I’ll include those.)

Eliminating the let

I know that when I have (let ([name val]) exp), I can just substitute val for name in exp. So let’s do that.

(define extract-bigger-than
  (lambda (lower-bound vals)
    (filter (section > <> lower-bound) vals)))

And this passes all my tests.

Detour: Some tests

Here are the tests I wrote. Note that I’ve included some edge cases (all values smaller than the bound, all larger, empty list, negative bound).

(test-equal? "extract-bigger-than: empty list"
              (extract-bigger-than 5 '())
              '())
(test-equal? "extract-bigger-than: all values <= bound"
              (extract-bigger-than 5 '(4 1 3 5 1 2 -5))
              '())
(test-equal? "extract-bigger-than: assorted values"
              (extract-bigger-than 5 (list 9 1 2 18 3 5 4 -2 7))
              '(9 18 7))       
(test-equal? "extract-bigger-than: min value is negative"
              (extract-bigger-than -10 '(-11 5 -12 -4 -5 20 -10))
              '(5 -4 -5 20))
(test-equal? "extract-bigger-than: really long list"
             (extract-bigger-than 10 (range 11 1000))
             (range 11 1000))

If pressed to do more, I might try lists with values equal to each other and lists consisting of values equal to the bound.

Tracing, once again

Things may make more sense if we look at how to trace section and map (and section+map).

Tracing section

When we encounter an expression of the form ((section proc <> v) exp), we

• Evaluate the exp. (So far, the only times we don’t evaluate the expression is in conditionals and in the body of lambdas.)
• Replace the whole expression by (proc value-of-exp v).

That is

    ((section proc <> v) val-of-exp)
--> (proc val-of-exp v)

Similarly

    ((section proc v <>) val-of-exp)
--> (proc v val-of-exp)

And

    ((section proc <> v <>) val1 val2)
--> (proc val1 v val2)

For example,

(define plus2 (section + <> 2))

    (plus2 (* 3 5))
    ; Evaluate the (* 3 5)
--> (plus2 15)
    ; Replace the plus2 by its definition.
--> ((section + <> 2) 15)
    ; Use the section replacement rule
--> (+ 15 2)
    ; Evaluate as normal
--> 17

Where does the diamond or hole go? Wherever you want the parameter to go.

Tracing map

The basic rule for map is “_Replace (map proc '(v1 v2 ...)) with (list (proc v1) (proc v2) ...). Let’s try a simple example.

    (map sqr (list (+ 1 2) (* 3 5) 8))
    ; Evaluate each elment in the list
--> (map sqr (list 3 (* 3 5) 8))
--> (map sqr (list 3 15 8))
--> (map sqr '(3 15 8))
    ; Apply the map rule
--> (list (sqr 3) (sqr 15) (sqr 8))
    ; Evaluate each element in the list
--> (list 9 (sqr 15) (sqr 8))
--> (list 9 225 (sqr 8))
--> (list 9 225 64)
    ; Finish the list
--> '(9 225 64)

Note that most of you are at the point in which you can evaluate all the elements of the list simultaneously in your traces. I just write it step by step for clarity (and to avoid my own mistakes).

    (map sqr (list (+ 1 2) (* 3 5) 8))
--> (map sqr (list 3 15 8))
--> (list (sqr 3) (sqr 15) (sqr 8))
--> (list 9 225 64)
--> '(9 225 64)

Tracing map + section

What about using map and section together? We just apply the rules for each.

    (map (section - <> 2) '(1 5 3))
    ; Apply the map rule
--> (list ((section - <> 2) 1) ((section - <> 2) 5) (section - <> 2) 3)
    ; Apply the section rule in the first expression
--> (list (- 1 2) ((section - <> 2) 5) (section - <> 2) 3)
    ; Evaluate the first expression
--> (list -1 ((section - <> 2) 5) (section - <> 2) 3)
    ; Apply the section rule in the second expression
--> (list -1 (- 5 2) (section - <> 2) 3)
    ; Evaluate the second expression
--> (list -1 3 ((section - <> 2) 3)
    ; Apply the section rule in the third expression
--> (list -1 3 (- 3 2))
    ; Evaluate the third expression
--> (list -1 3 1)
    ; Wrap up
--> '(-1 3 1)

Exploring Tally

We’re using tally or tally-value a lot on this procedure. Let’s explore how it might work, or at least how we might trace it conceptually. We’ll assume that it has to work step-by-step, looking at each value in turn.

    (tally-value '(b a c a b a) 'a)
    ; The b is not the same as a, so it won't contribute to our overall
    ; tally.  Throw away.
    ; We should go on to the next thing
--> (tally-value '(a c a b a) 'a)
    ; Compare the a to a.  They are the same.
    ; Add 1 to the count
    ; And then move on to the rest of the list
--> (+ 1 (tally-value '(c a b a) 'a))
    ; Compare c to a.  No.  Continue on
--> (+ 1 (tally-value '(a b a) 'a))
    ; Compare a to a.  Same.  Add 1 and continue
--> (+ 1 (+ 1 (tally-value '(b a) 'a)))
    ; Compare b to a.  Different.  Throw away the b and continue
--> (+ 1 (+ 1 (tally-value '(a) 'a)))
    ; Compare a to a.  Same.  Add 1 and continue
--> (+ 1 (+ 1 (+ 1 (tally-value '() 'a))))
    ; There are 0 a's in the empty list.  We're done.
--> (+ 1 (+ 1 (+ 1 0)))
--> (+ 1 (+ 1 1))
--> (+ 1 2)
--> 3

Question: Can we write tally-value?

Stay tuned to our next class?

Reading Responses

Why might I be unhappy with these?

``` => (+ 5 (+ 8 (sum (list 2)))) => (+ 5 (+ 8 (if (null? (list 2))))) 0 (+ (car (list 2)) (sum (cdr (list 2)))))) => (+ 5 (+ 8 #f)) 0 (+ (car (list 2)) (sum (cdr (list 2)))))) => (+ 5 (+ 8 (+ 2 (sum ‘()))))

On recursion