EBoard 21: Tail recursion

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

Approximate overview

• General administrative stuff + More [~20 min]
  • Some comments on SoLA 2
  • Some comments on reading from files
  • Some comments on recursion
• Q&A [~10 min]
• Quiz [~10 min]
• Lab [~50 min]

Administrative stuff

Notes and news

• I’ve posted notes on The Zen of Booleans
• I’ve posted A Racket Style Guide
• You can find links to both on the handouts page.
• It makes me incredibly unhappy to see nearly identical answers on multiple LAs from the same pair of students. Please do not cheat!
  • I am currently debating turning some students in to the Committee on Academic Standing. (I’d rather spend time grading and writing resources for the other students than writing up evidence.)
  • Thanks for ruining my Thanksgiving break.
• Please read the comments we leave on your work. I’ve heard too many “Why did I get a zero on this?” or “How do I do better?” in which students had not read the comments.
  • You should also read the comments on good work; we often include suggestions for improvement and, once in a while, a compliment.
• Late due dates on quizzes and SoLAs are only for students who prearranged to use them. (Usually it’s because a student has a reasonable conflict with that class day.) Please don’t use the late extensions unless you’ve been approved for them.
  • You can use them for lab writeups, reading self-checks, and mini-projects. I just need tokens.
• I’m working my way through the questions I received after 9pm last night.
• Bonus for finding a good mnemonic or equivalent for “Document Test Design Implement” (which is how you should approach the writing of procedures).

Tutoring reminders

• Please use our tutors! They like to work.
• Evening tutoring will be available
  • 8-10 p.m. Sundays through Thursdays
  • 3-5 p.m. Sundays
  • In the “Drop in tutoring” channel on the CS team.
  • Sam will generally not be available during these times.
• Individual tutors are temporarily unavailable. We’re recruiting more.
  • Don’t let this stop you from requesting one.
  • If you’re willing to share your individual tutor (as in, to do pair tutoring), let me know.

Upcoming activities

Attend (or watch recording) and send a one-paragraph reflection.

• None currently scheduled.

Other SoLA notes

• For the product-of-positives, many of you ignored the case in which numbers were zero. I still gave you credit for that.
• Please don’t say “characters in a list”. Perhaps “elements”.
• Please don’t refer to the symbol 'a or the string “a” as a character.
  It’s a symbol or a string.
  • Getting types right is important!
• Please plan meetings with me if you struggled.
  • But leave time for other students!

Upcoming work

• Redo of Mini-project 2 (due Monday the 30th (TONIGHT) at 10:30 p.m. CST)
• Redo of quizzes 18 (Recursion) and 20 (List Recursion) (due Tuesday am)
• Redo of Mini-project 3 (due Sunday the 6th at 10:30 p.m. CST)
• Mini-project 4 (due Wednesday, December 2 at 10:30 p.m. CST)
  • Now posted.
• Reading for Tuesday
  • Higher-order recursive design
• Quiz today: Numeric recursion
• Quiz Tuesday: Tail recursion

Some comments on reading from files

Reading from files is expensive. If you can reduce the number of times you call, say file->words, you will make your program much faster.

Different approaches to counting words

(define count-word-1
  (lambda (word filename)
    (list word (tally-value (file->words filename)))))

(define count-word-2
  (lambda (word list-of-words)
    (list word (tally-value list-of-words))))

(define count-words-1
  (lambda (words filename)
    (map (section count-word-1 <> filename) words)))

(define count-words-2
  (lambda (words filename)
    (let ([file-words (file->words filename)])
      (map (section count-word-2 <> file-words) words))))

What’s the difference in design between the -1 procedures and the -2 procedures?

• count-word-1 does (file->words filename) for each word in the list.
• count-word-2 assumes that we’ve already called file->words.

How does count-words-2 ensure that that we’ve already called file->words? (That is, how does it meet the goal of count-word-2?)

• There’s that nice local binding.

If I use the following list: (list "moo" "baa" "the" "cow" "says"), how many times will I call file->words in the -1 case and how many times in the -2 case?

• Five for the first, one for the second.

Let’s check

(define file2words
  (lambda (filename)
    (display "Calling file->words") (newline)
    (file->words filename)))

> (count-words-1 sample-words "DaleChallEasyWordList.txt")
Calling file->words
Calling file->words
Calling file->words
Calling file->words
Calling file->words
'(("moo" 1) ("baa" 1) ("the" 1) ("cow" 1) ("says" 0))
> (count-words-2 sample-words "DaleChallEasyWordList.txt")
Calling file->words
'(("moo" 1) ("baa" 1) ("the" 1) ("cow" 1) ("says" 0))

Let’s check the difference in performance. (Your compute speed may vary.)

(define sample-words
  (list "moo" "baa" "the" "cow" "says"))

(define long-list-of-words
  (apply append (make-list 50 sample-words)))

> (time (count-words-1 sample-words "DaleChallEasyWordList.txt"))
cpu time: 53 real time: 58 gc time: 34
'(("moo" 1) ("baa" 1) ("the" 1) ("cow" 1) ("says" 0))
> (time (count-words-2 sample-words "DaleChallEasyWordList.txt"))
cpu time: 4 real time: 4 gc time: 0
'(("moo" 1) ("baa" 1) ("the" 1) ("cow" 1) ("says" 0))
> (time (take (count-words-1 long-list-of-words "DaleChallEasyWordList.txt") 5))
cpu time: 1047 real time: 1174 gc time: 283
'(("moo" 1) ("baa" 1) ("the" 1) ("cow" 1) ("says" 0))
> (time (take (count-words-2 long-list-of-words "DaleChallEasyWordList.txt") 5))
cpu time: 41 real time: 41 gc time: 0
'(("moo" 1) ("baa" 1) ("the" 1) ("cow" 1) ("says" 0))

Wow! That was much faster. This is a factor of ten faster. We only expected a factor of five.

• There’s the weird Grinnell College (Garbage Collection) time. We’re seeing some effects of building too much lists for the computer to handle.

Can we speed up count-words-2 any more?

• Never mind.

Different kinds of anonymous procedures

(map (lambda (word) (count-word word (file->words filename))) list-of-words)

vs.

(map (section count-word <> (file->words filename)) list-of-words)

The former should read the file for each element of list-of-words. The latter should read the file once. (Experiments ssuggest that I’m mistaken.)

Some comments on list lengths

Please do not use (= (length lst) 1) to check for a list with one value. And definitely don’t use (= (length lst) 0) to look for an empty list.

• Why? It’s expensive. It’s needlessly expensive.
• Options for length-one list:
  • pattern matching with (list x) ;
  • use (and (not (null? lst)) (null? (cdr lst)));
  • use (null? (cdr lst)) (if you know it’s nonempty).
• Options for a length-zero list:
  • pattern matching with (list).
  • pattern matching with '().
  • Use (null? lst).

Some notes on recursion

• Two key issues of recursion:
  • Each time we do a recursive call, we simplify the parameter (e.g., remove an element from a list, subtract one from an integer).
  • We must eventually reach a simple-enough case that we can solve without recursion. We call that a base case.
  • Simplification gets you closer to the base case.
• Note: After reaching the base case, we likely have built up additional work to do.
• In designing recursive procedures, we often design by assuming that we correctly designed our procedure and going from there. “Suppose we know the recursive call will succeed … Then what?”
  • We tend to say “Trust the magic recursion fairy”.
  • During debugging / experimenting /development, you can try the recursive call to make sure.
• Tracing recursion can be hard, particularly when you use let or something similar.
  • In tracing recursive procedures, it’s sometimes best to just assume that the recursive call succeeds and returns the expected value, particularly if you’re using a let.

Q&A

Mini-Project 2 Redo

Can we use things we’ve learned since MP2?

Yes.

Can we get an E without using new things?

Certainly.

Mini-Project 3 Redo

Could we just define the file in Part the First?

No. Our goal was a procedure that would work with any file.

Mini-Project 4

Can I use a token on MPs?

Yes.

???

There’s a FAQ for that. (Or perhaps There an FAQ for that.)

Could you explain rule d?

Rule d says: “The pattern ‘(join P1 P2) matches a list of at least one element if P1 matches the car of the list and P2 matches the cdr of the list. (Sounds like recursion, doesn’t it?) The pattern (join 1 xs) matches nonempty lists that start with 1. The pattern (join x (join y z)) matches lists with at least two elements.”

If we have '(join 1 xs), we should match 1 against the car of the value, and xs against the cdr of the value.

Note that '(xs) is not the same as 'xs.

How do you get the xs out of '(join 1 xs)? Perhaps using list-ref.

(list-ref '(join 1 xs) 2) -> 'xs

Do I need to generalize?

join is always accompanied by two things. You can use list-ref to get each of them, using the right index.

What are join and seq?

They are just symbols to which we’ve assigned meaning.

join is like cons (for our patterns).

seq is like list (for our patterns).

Is it okay if I still use list and cons?

Yes. But I’d prefer that you switch (which wouldn’t take long).

Should I make a procedure for each guard and each consequent?

It’s up to you.

(define match?
  (lambda (pattern value)
    (cond
      ...
      ; Empty list: '(seq)
      ; "If the pattern is '(seq) then check whether the value is an empty list
      [(and (list? pattern) 
            (not (null? pattern)) 
            (null? (cdr pattern))
            (equal? (car pattern) 'seq)
            (null? (cdr pattern)))
       (null? value)]
      
      ; Alternate
      [(empty-list-pattern? pattern)
       (empty-list-value? value)]

      ...)))

...

;;; (empty-list-pattern? pattern) -> boolean
;;;   pattern : a pattern (see MP4 assignment)
;;; Determine if pattern represents the empty list.
(define empty-list-pattern? 
  (lambda (pattern)
    (and (list? pattern) 
         (not (null? pattern)) 
         (null? (cdr pattern))
         (equal? (car pattern) 'seq))))

;;; (empty-list-value? value) -> boolean
;;;   value : a Racket value 
;;; Determine if value represents the empty list.
(define empty-list-value?
  (lambda (value)
    (null? value)))

Can we take this code as long as we credit you?

Sure.

SoLA general questions

Will you explain why I did not get a point on a LA if I ask on Teams?

I will try. Make sure you’ve checked the comments.

What happens if I did an LA late and had not asked for an extension?

You get a zero on it. But you’ll still have a chance to make it up on the next SoLA.

Is it “a LA” or “an LA”?

I say the latter.

Will there really be twenty-one LAs on SoLA three?

There could be as many as twenty-one. But I hope not. I sincerely hope that all of you covered some of the Group 1 LAs with two tries.

You only have to redo the ones you missed!

Is there any way to make up an LA other than doing it again on the next SoLA?

No.

Can I get practice on SoLAs?

Write your own? Ask a classmate to write a variant? Look back at labs and readings.

Other

The reverse fib seemed like magic. The tail recursion helped.

I agree that it’s really weird.

We’ll discuss it tomorrow.

Quiz

• Open the prior lab in your Web browser.
• Open the reading on numeric recursion in your Web browser.
• Open DrRacket.
• Take a deep breath.

Cancelled

Here’s what you would have done.

Write a recursive procedure, (termial n), that takes a list of non-negative integer, n, as a parameter and returns 1 + 2 + 3 + … + n.

> (termial 0)
0
> (termial 1)
1
> (termial 4)
10 ; 4 + 3 + 2 + 1

Note: There is a famous formula for this sum. You may not use it. Your goal is to write a recursive procedure.

Lab

• Make sure to negotiate submission with your partner(s) in advance.
• You should know the rest of the drill.