If you have not done so already, please read the reading on pairs.
Draw box-and-pointer diagrams for each of the following lists:
((x) y z)
(x (y z))
((a) b (c ()))
Enter each of the following expressions into Scheme. In each case, explain why Scheme does or does not use the dot notation when displaying the value.
(cons 'a "Walker")
(cons 'a null)
(cons null 'a)
(cons null (cons null null))
Draw a box-and-pointer representation of the value of each expression in the previous exercise.
What do you think that
pair? will return for each of
the following? How about
list?. Confirm you answer
experimentally and explain any that you found particularly tricky.
(cons 'a 'b)
(cons 'a (cons 'b 'c))
(cons 'a null)
(list 'a 'b 'c)
Define and test a procedure named
cons-cell-count that takes
any Scheme value and determines how many boxes would appear in its
box-and-pointer diagram. (The data structure that is represented by such a
box, or the region of a computer's memory in which such a structure is
stored is called a cons cell. Every time the
procedure is used, explicitly or implicitly, in the construction of a
Scheme value, a new cons cell is allocated, to store information about the
car and the cdr. Thus
cons-cell-count also tallies the number
cons was invoked during the construction of its
For example, the structure in the following box-and-pointer diagram
contains seven cons-cells, so when you apply
to that structure, it should return 7. On the other hand, the string
"sample" contains no cons-cells, so the value of
(cons-cell-count "sample") is 0.
cons-cell-count to find out how many cons cells are needed
to construct the list
(0 (1 (2 (3 (4))))). Draw a
box-and-pointer diagram of this list to check the answer.
Monday, 18 September 2000
http://www.math.grin.edu/~stone/courses/scheme/pairs.xhtml(by Henry Walker and John Stone).
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/pairs.html
Source text last modified Mon Sep 18 10:30:47 2000.
This page generated on Tue Sep 19 10:27:09 2000 by Siteweaver. Validate this page's HTML.
Contact our webmaster at firstname.lastname@example.org