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?