Fundamentals of CS I (CS151 2001S)
[Current]
[Discussions]
[Glance]
[Honesty]
[Instructions]
[Links]
[News]
[Search]
[Syllabus]
Primary
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Quizzes]
[Readings]
[Reference]
Sets
[Blackboard]
[Scheme Report]
[SamR's Schedule]
[Rebelsky/Fall 2000]
[Walker/Fall2000]
[Stone/Spring2000]
Links
Start DrScheme.
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)
null
(list 'a 'b 'c)
(list 'a)
(list)
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 cons
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
of times cons
was invoked during the construction of its
argument.)
For example, the structure in the following box-and-pointer diagram
contains seven cons-cells, so when you apply cons-cell-count
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.
Use 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.
If, for some reason, you are having troulbe creating the list
(0 (1 (2 (3 (4)))))
, try
(list 0 (list 1 (list 2 (list 3 (list 4)))))
Monday, 18 September 2000
http://www.math.grin.edu/~stone/courses/scheme/pairs.xhtml
(by Henry Walker and John Stone).
Wednesday, 21 February 2001
[Current]
[Discussions]
[Glance]
[Honesty]
[Instructions]
[Links]
[News]
[Search]
[Syllabus]
Primary
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Quizzes]
[Readings]
[Reference]
Sets
[Blackboard]
[Scheme Report]
[SamR's Schedule]
[Rebelsky/Fall 2000]
[Walker/Fall2000]
[Stone/Spring2000]
Links
Disclaimer: I usually create these pages on the fly. This means that they are rarely proofread and may contain bad grammar and incorrect details. It also means that I may update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.
This page was generated by Siteweaver on Thu May 3 23:07:56 2001.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/pairs.html
.
You may validate
this page's HTML.
The source was last modified Wed Feb 21 05:20:04 2001.