• Continue Partners!

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Debrief from yesterday.
• The listp? predicate.
• How Scheme prints lists.
• Drawing trees vs. drawing lists.
• Lab.

Preliminaries

Admin

• Lab 35 returned.

Upcoming Work

• Lab writeup (optional): Exercises 2 and 4a. http://bit.ly/151-2015S-lab37
• Reading for Wednesday: Vectors
• HW7 due tonight at 10:30 p.m.
• Exam 3 available now, officially distributed tomorrow.

Extra Credit Opportunities

Academic

• Joe Palca talk Tuesday at 7:30 p.m. in Sebring-Lewis.
• Scholars Convocation Wednesday at noon: Alison Bechdel.
• CS Extras Thursday: ???
• CS Table Friday: Design for User Empowerment http://interactions.acm.org/archive/view/march-april-2015/design-for-user-empowerment

Peer Support (Morning Section)

• KY's radio show, "We Think We're Funny", 9-10pm Mondays.
• Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m.
• How an admitted student this coming Sunday night (or the following Sunday night)! Contact JMU for info.
• ISO Show, Saturday night 7-9 pm at Harris. Many live performances.
• Salsa Showcase Seventeenth

Miscellaneous

Nothing at present

Other Good Things (no extra credit)

• Student research seminar this week.

Questions

Debrief from yesterday

What should we take from yesterday's lab?

• We build things with pairs.
  • Lists
  • As well as some weird things that aren't lists.
  • These are somewhat "dynamic" - You can always add something at the front with cons.
• There is a close relationship between lists and pairs.
  • All NON-EMPTY lists are pairs
    • null is not a pair.
  • Not all pairs are lists
    • (cons 'a 'b)
    • For a pair to be a list, the cdr has to be a list.
• We can provide unambiguous drawings of pair structures using a simple process.
  • For any cons, draw this pair thing with two boxes
  • When a parameter to cons is null, draw a slash
  • When a parameter to cons is not null, draw an arrow to that element
• We can turn these drawings back into code.
• A list with N elements has a "spine" of N pairs.
  • One box for each element in a list, the boxes are spread out in a line.

Why are we studying this?

• There is some value in understanding what a program or langauge does "behind the scenes".
• Understanding the underlying representation can help you better explain some phenomena.
• We will start building some pair structures that aren't lists, so you should know more about those structures.
• Linked structures are a fundamental idea in CS.

How Scheme prints lists

We see our first pair Print a single quotation mark and an open paren Print the car Look at the remaining pairs Print a space Print the car When you hit null, print a close paren When you hit something other than null, print the profanity symbol (.) and the cdr

(define print-something (lambda (thing) (cond [(pair? thing) (display "'(") (print-something (car thing)) (let kernel ([remaining (cdr thing)]) (cond [(null? remaining) (display ")")] [(pair? remaining) (display " ") (print-something (car remaining)) (kernel (cdr remaining)]

Writing listp?

A list is a collection of values.

In Scheme, we can build lists with pair structures.

• cons a value onto the front of a list
• build the empty list with null

"A list is either null or (cons VALUE LIST)".

 (define listp?
   (lambda (val)
     (or ; is it null?
         (null? val) 
         ; is it a pair whose cdr is a list
         (and (pair? val) 
              (listp? (cdr val))))))

"Structural recursion" -> Recurse over the parts of a structure (e.g., built with pairs)

Lab

Writeup is cancelled.