Class 15: Pairs and pair structures

Held Tuesday, September 19, 2000

Summary

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

Notes

• Today's lab: Pairs
• Reading for tomorrow: Association lists
• A few of you asked whether you should finish yesterday's lab outside of class. In general, the policy is that you should finish labs outside of class. I'll do my best to tell you when we have extra in-class time for labs.
• Please email me when you find that a page is not available (after trying www.math.grin.edu instead of www.cs.grinnell.edu).
• No homework this week. Please spend the time you would have spent on homework on finishing up the labs.
• You will receive a take-home exam on Friday. What fun!
• This weekend is the Planned Parenthood booksale in Des Moines. Go see a huge hall full of books!

Overview

• Behind the scenes: Memory usage in Scheme
• Cons cells
• Dotted pairs

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.

Dotted Pairs

• Although we've used lists as the second parts of each cons cell, you can use other values. In this case, you get what is called a dotted pair.
• The shorthand for a dotted pair is (x . y).

Lab

Any questions?

Do the work.

Reflect.

Have a nice lunch.