Comp 211 Laboratory 2

Natural Numbers & List Abbreviations

Instructions for students & labbies: Students use DrScheme, following the design recipe, working on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention. Students should feel free to skip the challenge exercises.

Scheme's Built-in Naturals

We already know Scheme has lots of numbers built-in, like 3, 17.83, and -14/3. It is often convenient to limit our attention to a subset of these such as the naturals: 0, 1, 2, 3, ... . We can define the naturals and its template as follows:

...

• Use the stepper on (add 2 2) to see how it works.

Example functions

Exercises

Write each of the functions on N.

...

Chapter 13 of the book introduces some new, compact methods for representing lists, which have already been mentioned in lecture. The following exercises simply let you explore how this notation behaves.

Finger Exercises on

...

List Abbreviations

1. Evaluate he following in the DrScheme interactions pane. You can cut and paste to save time if you want.

   Code Block
   (list 1 2 3) (cons 1 (cons 2 (cons 3 empty))) (list 1 2 3 empty) (cons 1 (cons 2 (cons 3 (cons empty empty)))

1. Rewrite the following using list.

   Code Block
   (cons (cons 1 empty) empty) (cons 1 (cons (cons 2 (cons 3 empty)) (cons 4 (cons (cons 5 empty) empty)))) (cons (cons (cons 'bozo empty) empty) empty)

List

...

Constants

Using ' notation we can abbreviate constant lists even more.

Finger Exercises on list constants

1. Evaluate he following in the DrScheme interactions pane. You can cut and paste to save time if you want. Note that ' produces strange results for embedded references to true, false, (), and empty.

'(1 2 3 4)
(list 1 2 3 4)
'(rabbit bunny)
(list 'rabbit 'bunny)
'(rabbit (2) (3 4 5))
(list 'rabbit (list 2) (list 3 4 5))
'(true)
'(empty)
'(())
(list empty)
(list ())
(list 'empty)
(list '())
'(

...

(cons x y) (1 (+ 1 1) (+ 1 1 1)))

Notice that no expressions within the scope of the ' operator are evaluated.
We can think of the ' operator as distributing over the elements. We apply this rule recursively until there are no more ' operators left. This simple rule makes embedded references to true, false, and empty behave strangely because 'true, 'false, and 'empty reduce to themselves as symbols, not to true, false, and empty. In contrast, 'n for some number n reduces to n.

Trees and Mutually Recursive Data Definitions

...

Exercise

...

Re-write the lists from above using
'
notation.

...

We can think of the
'
as distributing over the elements. We apply this rule recursively (Yes! Recursion strikes again!) until there are no more'(
s left.

'(rabbit (2) (3 4 5)) => (list 'rabbit '(2) '(3 4 5)) (list 'rabbit (list '2) (list '3 '4 '5)) => ... => (cons 'rabbit (cons (cons 2 empty) (cons (cons 3 (cons 4 (cons 5 empty))) empty)))

...

NB:

...

'1
reduces to1
. In general,'<a number>
evaluates to<a number>
.

...

Exercise

...

What do we get in these cases?

'((make-posn 1 2)) '(1 (+ 1 1) (+ 1 1 1))

...

You cannot use list abbreviation one nested in another. For example
'(1 '(+ 1 1)) (will be treated in DrScheme as (list 1 (list 'quote (list '+ 1 1)))

If we want to apply functions, we have to use eitherconsorlist. (Not exactly true. There is another abbreviation,quasiquote, that we won't talk about in this course.)

...

Trees & Mutually Recursive Data Definitions

...

Instructions for students & labbies:

...

Students use DrScheme, following the design recipe,
working on the exercises at their own pace,
while labbies wander among the students, answering questions,
bringing the more important ones to the lab's attention.
Students should feel free to skip the challenge exercises.

Trees

In class, we used ancestor family trees as an example form of treesinductively defined tree data.
In ancestor family trees, each person (a
make-child
structure)
has 0, 1, or 2 two ancestors (alsomakealso make-child
structures) which may be empty.
Here In this lab, we'll use a similar, but slightly different, form of trees for
more experiencetree as an example.

In mathematics, we can model formalized arithmetic expressions as trees. For
example,

5+(1-8)×(7+1)

or equivalently, the Scheme code

(+ 5 (* (- 1 8) (+ 7 1)))

is pictorially

+ / \ 5 × / \ - + / \ / \ 1 8 7 1

...