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.

Natural Numbers

Review: Definition

In class, we defined our own version of natural numbers, its
corresponding template, and example data:

      ; A Natural is one of
      ; - 'Zero
      ; - (make-next <em>n</em>)
      ;   where <em>n</em> is a Natural

      (define-struct next (nat))

      ; f : Natural -&gt; &hellip;

      (define (f n)
         (cond
            [(symbol? n) &hellip;]
            [(next? n)   &hellip;(f (next-nat n))&hellip;]))

      (define Zero  'Zero)
      (define One   (make-next Zero))
      (define Two   (make-next One))
      (define Three (make-next Two))
      (define Four  (make-next Three))

Here is an example function:

      ; add-Nat : Natural Natural -> Natural
      ; Returns the result of adding two Naturals.
      (define (add-Nat n m)
         (cond
            [(symbol? n) m]
            [(next? n)   (make-next (add-Nat (next-nat n) m))]))

We do not suggest actually using this data definition in everyday programs.
There are two reasons for looking at this definition.
First, it is a second example (after lists), of recursively defined
data structures and how we write functions on them.
Second, we can take this idea and apply it to Scheme's built-in numbers.
The lab's examples will explore both of these.

Adapting to 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,
the naturals: 0, 1, 2, 3, ….
We can define the naturals and its template as follows:

      ; A natural is one of
      ; - 0
      ; - (add1 <em>n</em>)
      ;   where <em>n</em> is a natural

      ; f : natural -&gt; &hellip;

      (define (f n)
         (cond
            [(zero? n)      &hellip;]
            [(positive? n)  &hellip;(f (sub1 n))&hellip;]))

Of course, we already know what the example data looks like:
0, 1, 2, 3, …

Unlike for Naturals, we are not defining new Scheme values here
(i.e., there's no

define-struct

), but we are defining
a subset of all Scheme numbers that we are interested in.
The definition and template use some built-in Scheme functions that
we haven't seen before (

add1

,

sub1

,

zero?

), but which mean just what their names imply.

If we choose to ignore that Scheme has a built-in function

+

,
we could define it ourselves, just like the above

add-Nat

on
Naturals:

      ; add-nat : natural natural -> natural
      ; Returns the result of adding two naturals.
      (define (add-nat n m)
         (cond
            [(zero? n)      m]
            [(positive? n)  (add1 (add-nat (sub1 n) m))]))

(add-nat 2 2)

Example functions

Built-in Natural Numbers and Templates

At the beginning of the course, we wrote lots of functions on numbers
without using templates, and just using mathematical formulae.
In those cases, we were writing functions on numbers
without viewing the number as having any kind of internal structure.

Here, we are considering functions that work only on naturals.
By adopting the recursive definition on naturals, we get a benefit –
the natural's template guides us in writing our functions.

However, as examples like the logarithm above show, not all functions
will follow the template that mimics the data definition.
This is a leading example, as we will soon be
introducing a more flexible template to help in such situations.

List Abbreviations

Chapter 13 of the book introduces some new, compact methods for representing lists.

From now on, we need to use the "Beginning Student with List Abbreviations" language. Change this now. (The chapter in the book lists "Intermediate Student". We'll get to "Intermediate Student" a little later.)

list

Using

list

we can quickly write a list with many fewer

()

s:

      (list 1 2 3) =>
      (cons 1 (cons 2 (cons 3 empty)))

Notice that we did not end the

list

construct with an

empty

. What would happen if we did?:

      (list 1 2 3 empty) =>
      (cons 1 (cons 2 (cons 3 (cons empty empty))))

The last element has become a list of lists.

list

  (cons (cons 1 empty) empty)

  (cons 1 (cons (cons 2 (cons 3 empty)) (cons 4 (cons (cons 5 empty) empty))))
      

'

abbreviations

Using

'

notation we can abbreviate our lists even more.

'

notation is especially useful when we have nested lists.

      '(1 2 3 4) =>
      (list 1 2 3 4) =>
      (cons 1 (cons 2 (cons 3 (cons 4 empty))))

     '(rabbit bunny) =>
     (list 'rabbit 'bunny) =>
     (cons 'rabbit (cons 'bunny empty))

     '(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)))

'

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)))

'1

reduces to

1

. In general,

'<a number>

evaluates to

<a number>

.

  '((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 either cons or list . (Not exactly true. There is another abbreviation, quasiquote, that we won't talk about in this course.)

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 trees.
In ancestor family trees, each person (a

make-child

structure)
has 0, 1, or 2 ancestors (also

make-child

structures).
Here, we'll use a similar, but slightly different, form of trees for
more experience.

In mathematics, we can model 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

This tree form has some advantages. To understand the more familiar
linear form, you must know about the order of operator precedence,
whereas that is unnecessary in the tree form. The tree also eliminates
the need for parentheses. The tree also gets us away from the relatively
minor concerns of the precise details of mathematical or Scheme
notation, like infix vs. prefix operators.

Consider if you were developing a computer program like DrScheme
(or, similarly, a "compiler," if you know what that is).
Such a program would take the linear form, which is convenient for
a person to type in, but then convert or

it to the tree form
for internal use.
Since parsing is beyond the scope of this course, let's just skip straight
to the tree form.

We'll require that each addition, subtraction, multiplication, and
division has exactly two subexpressions. Of course, recursively,
each subexpression can be another addition, subtraction, multiplication,
or division. As a base case, an expression can also be a number.

      (define-struct add (m n))
      (define-struct sub (m n))
      (define-struct mul (m n))
      (define-struct div (m n))

      ; An Arithmetic-Expression (AExp) is one of
      ; - a number
      ; - (make-add <var>m</var> <var>n</var>)
      ;   where <var>m</var>,<var>n</var> are AExps
      ; - (make-sub <var>m</var> <var>n</var>)
      ;   where <var>m</var>,<var>n</var> are AExps
      ; - (make-mul <var>m</var> <var>n</var>)
      ;   where <var>m</var>,<var>n</var> are AExps
      ; - (make-div <var>m</var> <var>n</var>)
      ;   where <var>m</var>,<var>n</var> are AExps

With this data definition, the above tree is modeled by the structure

      (define AExp1 (make-add 5
                              (make-mul (make-sub 1 8)
                                        (make-add 7 1))))

Another sample AExp is

      (define AExp2 16)

As always, we distinguish between the information (the mathematical
expression or its corresponding tree) and its data representation
(this AExp).
Just writing this piece of data doesn't mean we can do anything with it
yet, such as compute the intended result.

Files and Directories

The following are data definitions for one possible (simplified) representation
of files and directories (a.k.a. folders). These definitions follow the Windows convention of attaching a name to a file. They also collapse the definition of the directory type into a clause of the definition of for file, which makes the definitions more compact but makes it less clear how to write functions that process directories (instead of files). For this reason, none of the following exercises uses a directory as the primary input to a function.

Observe the mutual recursion between files and list-of-files.

      (define-struct dir (name contents))

      ; A file is one of

      ;   - a symbol

      ;     representing a "simple" file's name

      ;   - a directory

      ;     (make-dir name contents)

      ;     where name is a symbol, and contents is a l-o-f.

      ; A list-of-files (l-o-f) is one of

      ;   - empty

      ;   - (cons f lofd)

      ;     where f is a file, and lofd is a l-o-f

This is very similar to the descendant trees data structure seen in class.