• Continue Partners!

Overview

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

Preliminaries

Admin

• Random sugar.
• Homework grades coming soon!

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 (Afternoon Section)

• Wednesday at 4:30 in ???. Psychology Alumni Job Talk Series, Alum '##, a Senior Research Analyst from ACT.
• Womens Tennis Sunday against Central.
• ISO Show, Saturday night 7-9 pm at Harris. Many live performances.
• How an admitted student this coming Sunday night (or the following Sunday night)! Contact JMU for info.
• Many things the following weeks.

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
  • Trees (two-dimensional lists?)
  • Other things that have no clear name.
• There is a close relationship between lists and pairs.
  • All non-empty lists are pairs
    • Null is a list, but not a pair
  • Not all pairs are lists; only a pair whose cdr is a list is a list
  • Sequences of pairs don't need to end with a null, but sequences of pairs that represent a list do need to end with a null.
• We can provide unambiguous drawings of pair structures using a simple process.
  • For each cons, draw a pair of boxes
  • If an element is not null, draw that element separately and draw an arrow to it. Traditionally, the arrow from the left box goes downward and the arrow from the right box goes to the right
  • If an element is null, draw a slash in the box
• We can turn these drawings back into code.
• A list with N elements has a "spine" of N pairs.
  • N elements means N boxpairs
  • One boxpair per element

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

Print
  If you have a pair
    print a single quotation mark
    print an open parentheis
    print the car
    move on to the cdr
    ^ if the cdr is null
    |   print a close paren and stop
    | if the cdr is a pair
    |   print a space
    |   print the car
    +---+ loop back and do it all over again
    | otherwise
    |   print a space
    |   print a curse
    |   print a space
    |   print the cdr
    |   print a right paren

Writing listp?

Write a procedure, (listp? val) that returns #t if val is a list and

f otherwise.

Reminder: A list is null or (cons VAL LIST)

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

Drawing trees vs. drawing lists

Lab