Instructions for students & labbies: Students use DrScheme, following the design recipe, 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:
(define-struct next (nat))
; A Natural is one of
; - 'Zero
; - (make-next n)
; where n is a Natural
; f : Natural -> …
(define (f n)
(cond
[(symbol? n) …]
[(next? n) …(f (next-nat n))…]))
(define Zero 'Zero)
(define One (make-next Zero))
(define Two (make-next One))
(define Three (make-next Two))
(define Four (make-next Three))
The class slides had a number of example functions, including
; 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, …. While these look a bit more familiar to us, the "naturals" and "Naturals" are in a one-to-one correspondence. We can define the naturals and its template as follows:
; A natural is one of
; - 0
; - (add1 n)
; where n is a natural
; f : natural -> …
(define (f n)
(cond
[(zero? n) …]
[(positive? n) …(f (sub1 n))…]))
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))]))
Use the stepper on
(add-nat 2 2)
to see how it works.
|
Example functions
Write each of the functions on both Naturals and naturals.
Once you have successfully written one version, the other
should be a matter of copy-and-paste-and-edit.
Each is described using the naturals, for convenience, with
n as the input.
|
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.
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 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 itself (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 parse 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 m n)
; where m,n are AExps
; - (make-sub m n)
; where m,n are AExps
; - (make-mul m n)
; where m,n are AExps
; - (make-div m n)
; where m,n 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.
|