CSC 151.01, Class 25: Pairs and pair structures

Overview

• Preliminaries
  • Notes and news
  • Upcoming work
  • Extra credit
  • Questions
• Representing lists with pairs and cons cells
• Why care about the underlying representation
• Printing lists
• Lab
• Debrief

Preliminaries

Moment of silence.

News / Etc.

• New partners!
• Welcome back from spring break.
• We’re switching topics/themes post break, from recursion to ways of structuring data.
• I’ve returned exam 2 and provided an answer key.
  • There was an academic honesty issue on the exam that I needed to report.
  • Please don’t let the stress of the next exam lead you to make poor choices!

Upcoming work

• Exam 3 will be distributed on Wednesday.
• Lab writeup for class 25: Exercises 1 and 3. (Hardcopy lab!) Due before class Wednesday.
• Reading for Wednesday
  • Vectors
• Flash Cards due Wednesday.

Dealing with grief

• I will do what I can to support you.
• Let me know if you need adjustments in workload to help.

Extra credit (Academic/Artistic)

• CS Table Tuesday: Unknown topic
• 4pm Tuesday in DLab: “Updating Close Reading for the 21st Century”
• CS Extras Thursday: Unknown topic
• Danforth lecture on Thursday at 11 am in JRC 101. Robert G. Bergman. “Irreproducibility in the Scientific Literature or: How Often do Scientists Tell the Truth, the Whole Truth and Nothing but the Truth?”
• Visit the two exhibits at the Faulconer Gallery. (Are there still two exhibits in the Faulconer gallery?)
• Roxanne Gay talk Friday noon (?).

Extra credit (Peer)

• Men’s Tennis, April 14, 21, and 22.

Extra credit (Recurring peer)

• Listen to KDIC Wednesdays at 6pm - Witty banter with other personalities and/or co-host. Also Indian, Arabic, and Farsi music.
  (Up to two units of extra credit.)
• Peer editing with SS. Talk to SS about the details. Make your English Lit more literate.

Extra credit (Misc)

• Donate on Scarlet and Give Back day. (If donating is a financial burden, I will bring cash on Wednesday to give you to donate.)
• Blood drive tomorrow.
  • Or write to me about why giving blood is important.
• Host one or more prospective students.

Other good things

Questions

I’ve been incredibly behind in submitting extra credit writeups, even though they are due within TWO DAYS of the event. Can I still get extra credit?

I suppose so.

Representing lists with pairs and cons cells

• The computer stores data in memory.
• We will be looking at an abstraction of how it stores data.
• Behind the scenes, everything is just a series of 0’s and 1’s. There is then some interpretation of the 0’s and 1’s.
  • We can’t access the underlying representation, so we’re going to look at a higher level.
• When you call cons, it builds a “cons cell” or “pair” with spaces for two things.
  • The things are not the values you’ve cons’ed, they are references to elsewhere in memory where the values reside.
• When you build a list, you get a sequence of pairs.
  • They are likely scattered about
  • But we will generally draw them in a line.
• When you build a new list from an old list, they likely share memory.

(define lst1 (list 1 2 3))
(define lst2 (cons 'a (cdr lst1)))

• Naming
  • car - Contents of address register
  • cdr - Contents of data (decrement?) register
  • cons - Short for “construct”
• Even if we change what lst1 is, the shared memory sticks around. define builds the rhs and then associates with the left.
• Note: Scheme has some interesting policies on when it does and does not build new (copies of) values.
  • All symbols with the same name are in the same place. (Okay, refer to the same place)
  • The same string may be in different locations.
  • eq? lets you compare memory locations.

Questions

• If I have a list of five symbols, how many pairs do you expect to see?
• If I have a list of four numbers, how many pairs do you expect to see?
• Observation: The number of cons cells corresponds to the number of elements in the list.
  • Each cons cell can hold only one value.

Why care about the underlying representation

Your answers

• Thinking about memory can help us write more efficient code.
• Helps us understand complex list structures.
• Many of us think better visually, can help think about all sorts of issues.

My answers

• Helps with thinking about costs. If you have to recurse through until the end, that’s a lot of work.
• Helps us understand the stupid period we get for (cons 'a 'b).

Printing lists

When Scheme is printing a value and it enounters a pair, it optimistically says “It’s a list” and prints the open paren and the first value. Then it prints the values as it goes. When it hits a null, it prints a right paren.

What if it doesn’t hit a null? It’s already done a lot of work that’s hard to erase, so … it prints a period to say “Whoops” and then the cdr and a right paren.

Lab

• You’ll find it useful to draw lists horizontally.

• If you have a null as the value, you also draw a slash. (cons null null) (or (list null)) looks something like the following.

  +—+—+ | / | / | +—+—+

Debrief

Observations:

• The list of the empty list is not the same as the empty list.
• (cons null 'a) is not a list, even though it has a null

Questions:

• Is there a pair that’s not a list? Sure (cons 'a 'a) is not a list. For the pair to be a list, the second element must be a list.
• Is there a list that’s not a pair? null is a list, but not a pair.

Problem 5

A list is either

• null or
• Cons (a pair) of anything and a list

Translate to code

(define listp?
  (lambda (val)
    (or (null? val)
        (and (pair? val)
             (listp? (cdr val))))))