Class 26: Pairs

Held: Tuesday, 4 March 2003

Summary: Today we visit some of the behind the scenes structures in Scheme, particularly the pairs that cons creates.

Related Pages:

• EBoard.
• Reading on Pairs.
• Lab on Pairs.

Assignments

• Read Association Lists.

Notes:

• No class on Friday, 14 March 2003, so that you can leave earlier for break.
• Are there questions on randomness and simulation?
• Are there questions on homework 3?
• Two solutions to the approximate problem.

Overview:

• Behind the scences in Scheme: Memory.
• Pairs and Cons cells.
• Dotted pairs.
• Lab.

Behind the Scenes

• In Scheme, every value that you create takes up computer memory.
• Typically, the memory allocated to a value includes the type of the value and the contents of the value.
• As you might guess, different values have their contents arranged differently.
• Scheme also keeps a table (or tables) that associates names with values in memory. (Picture to be drawn in class.)
• Why is this important? Because it can help us think about some things.

Cons Cells

• Perhaps the most interesting values are the things that cons creates. We often call these cons cells or pairs
• The first value of a pair is a reference to the first parameter to cons. The second value is a reference to the second parameter.
• Let's look at some examples. (Again, pictures in class.)
  • (cons 3 4)
  • (cons a b)
  • (cons ('a null))

Dotted Pairs

• Although we've used lists as the second parts of each cons cell, you can use other values. If the second part of a cons cell is not a list, you get what is called a dotted pair.
• The shorthand for a dotted pair is (x . y).
• You'll also see the dot at the end of a long sequence of cons cells.

Lab

• Any questions?
• Do the lab.
• Be prepared to reflect.