CSC151, Class 26: Pairs

Overview:
* Memory
* Pairs and Cons cells
* Dotted pairs
* Lab

Notes:
* Mr. Stone teaches on Friday, 7 March 2003.  
  Sam goes to conference on recruiting and retaining majors.
* No class on Friday, 14 March 2003.
* Questions on randomness and simulation?
* Questions on homework 3?
* Two solutions to the approximation problem.

(define approx
  (lambda (num digits)
; Key idea 1: We know how to chop off at the decimal point
;    Move the decimal point, chop, move it back
    (exact->inexact
      (/ (round (* num (expt 10 digits))) (expt 10 digits)))))

; Key idea 2: Work with strings instead of numbers.
  (substring
    (append (number->string num) "00000000000000")
    0 (+ ... DIGITs))

----------------------------------------

Behind the scenes, Scheme must store everything in memory.
You can think of memory as a big series of boxes

+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+

We can naturally store values in boxes (or sequences of
boxes)

  0   1   2   3   4   5   6   7   8   9   10  11  12
+---+---+---+---+---+---+---+---+---+---+---+---+---+
| a |   | " | H | i | ! | " |   |123|   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+

Question: How do you know what type of thing is stored
  in each box?
Answer: Take CSC201.

Question: How much fits in one box?
Answer: Not much; some values require multiple boxes
  (like the string above).

Design Problem: How do you store compound values, like
  lists?

Strategy one:
  Put the values in adjacent memory locations.
  For example, store the list (4 5 6) starting at
    memory lcoation 9.

  0   1   2   3   4   5   6   7   8   9   10  11  12
+---+---+---+---+---+---+---+---+---+---+---+---+---+
| a |   | " | H | i | ! | " |   |123| 4 | 5 | 6 |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+

  A Problem: How do you know you've hit the end?
  A similar problem: How do you know that the list 
    (123 4 5 6) doesn't start at location 8?
  The biggest problem: How do you cons 3 on to the
     front of that list?
     IT WOULD OVERWRITE THE 123

The common solution to "I want something that's easy to
add to the front" is to use "pairs" (or cons cells or "nodes")

Each pair stores two addresses of boxes.
  The first address gives the box that holds the value.
  The second address gives the box or boxes that holds
     the rest.

Since the particlar arrangement doesn't matter, we tend to
draw seprate pairs, as in

  +---+---+     +---+---+     +---+---+
  | * | *-----> | * | *-----> | * | / |
  +-|-+---+     +-|-+---+     +-|-+---+
    v             v             v
    3             4             5

The model Scheme uses for printing things is fairly
simple:

  When I see a cons cell, assume it's a list
    print the open paren
    print each value in turn and then move on to
      the next cons cell
    when you hit the null at the end, print a close paren

Unfortunately, the next thing isn't always a pair or null.

  +---+---+     +---+---+
  | * | *-----> | * | * |
  +-|-+---+     +-|-+-|-+
    v             v   v  
    3             4   5  

In this case, Scheme puts a dot to represent
  "HEY, IT'S NOT A LIST.  IT JUST LOOKS A LOT LIKE ONE!"

----------------------------------------

Reflection

* Next class: listp?