EBoard 26: Dictionaries, Hashes, and the Ilk

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]
• Sam Q&A to help with MP5 [~10 min]
• Q&A [~10 min]
• Lab [~60 min]

Administrative stuff

Notes and News

• Happy Monday! I hope you have an awesome week.
• When you are starting a lab, make sure the text at the top of the code has the correct term (Spring Term 1 2021). If not, you probably have the wrong version of the lab.
• As you may have noticed, we have a few slots available in CSC-161 next term. To provide equitable access to the Spring Two CSC-161, we did not allow students to pre-register for both CSC-151 in term 1 and CSC-161 in term 2. We will be holding a weighted lottery for the open slots next week. If you would like to be included in the lottery, please send an email to me at rebelsky@grinnell.edu by 5pm on Monday, 8 March 2021.
• I’ve been asked to attend a board meeting of the Richard Tapia Celebration of Diversity in Computing from 2:30-4:00 on Wednesday. Wednesday’s class will start with lab. I’ll assume that the mentors will be able to have things work.
• I’ve been asked to attend a seminar on diversity in computing on Friday starting at 4pm. I’ll assume that the mentors will be able to make things work.

Upcoming activities and other token-earning things

Events

• Visit Grinnell Art Museum, maybe get an art pack https://www.grinnell.edu/campus-life/arts-culture/museum.
• Monday, CS Table at noon
• Thursday, CS Extras at 5pm (program synthesis and such)

Upcoming work

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

• [Reading response for Tuesday]
  • Data abstraction
  • A brand new reading! Let me know when you see flaws.
• Lab writeup
  • Hash tables
  • Forthcoming
• Mini-Project 5 due TONIGHT.
  • Note that the autograder assumes that bindings are in the same order; I’ll try to get that fixed.
• Mini-project 6 due next Monday.
  • We’ll talk about it tomorrow.
  • Our last mini-project.
• SoLA 3 on Thursday

Some notes on MP5

I’m hoping I help many of you with some Q&A about problem 4.

Trust the magic recursion fairy.

That is, you can assume that any recursive procedure you are writing works on any input closer to the base case (e.g., the car of a list, the cdr of a list, a smaller number, etc.).

Warning!

• Those who have solved problem 4 already will be frustrated that I didn’t do this earlier. (That’s okay; you learn from your struggles/failure.)
• Those who have made some progress but are stuck will likely find this useful.
• Those who have not begun MP5 may be confused.

(define evaluate
  (lambda (exp bindings)
    (cond
      [(symbol? exp)
       (simple-evaluate-base exp bindings)]
      [(integer? exp)
       (simple-evaluate-base exp bindings)]
      [else
       ???])))

What else do we have?

• We have a list that begins with mul or add and has a bunch of other expressions.

Broadly, what are the steps we have to do in that else? (We can assume we have a list.) And yes, I’m using random calling.

• Determine the operation (mul or add).
• Evaluate each remaining element of the list (the parameters to mul or add and evaluate them with simple-evaluate-base, at least for the problem 1)
  • Simple evaluate base won’t work for evaluate, since it only works for symbols and integers.
  • We need a procedure that evaluates not only symbols integers, but also lists of operations + symbols and integers, and lists of sympols
    • lists of symbols and integers ….
  • Our evaluate does that. <— TRUST THE MAGIC RECURSION FAIRY
• Apply the operation (multiply for mul, add for add)

Recursion is our friend.

Match is not our friend.

The magic recursion fairy will also help on part 5.

Q&A

Hash tables

Why are they called “hash tables”?

In the implementation, you chop up the key and then convert it to a simpler implementation.

I’m confused on self-check three. Will you explain it?

Nope. Discuss with your partner.

Miscellaneous

If we want to keep things, must we put them in the definitions pane?

Yes.

Or rerun them in the interactions page.

I can’t run car or cdr on the empty list.

Don’t attempt to do so until you make sure the list is not empty.

    (if (empty? lst)
        base-case
        (let ([head (car lst)]
              [tail (cdr lst)])
          whatever-else-you-want-to-do))

MP5

I’m trying to write simple-evaluate-list. I’ve used a let to define mul and add. Why don’t they work as procedures?

Racket isn’t as smart as you think (or doesn’t work like you think).

You probably need to write something more like

    (if (equal? (car lst) 'mul)
        (apply * whatever)
        (apply + whatever))

When you suggest tail recursion, are you saying to use match?

I am not saying that you suggest use match.

I am suggesting that you write a helper procedure that adds an extra parameter, usually called so-far.

Lab

Fun fun fun!