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.

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 n)
; where n is a Natural
(define-struct next (nat))
; 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))

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

Exercises 

• Use the stepper on (add-Nat Two Two)to see how it works.

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

Exercise

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

Example functions

Exercises

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.

#Factorial, which is defined as

0! = 1, and
(

n

+1)! = ( n +1) × (

...

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:

; A natural (N) is either:
; - 0
; - (add1 n)
; where n is a natural

; Template
; nat-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 most data definitions, we are not defining new Scheme values here (i.e., there's no define-struct), but we are defining (identifying) a subset of Scheme numbers. The definition and template use some built-in Scheme functions (add1, sub1, zero?) that may be unfamiliar, but which mean just what their names suggest.

Exercises

Write each of the following functions on N.

1. The factorial function !, which is defined by the equations:

   Code Block
   (! 0) = 1 (! (add1 n)) = (* (add1 n) (! n))

2. The function down that takes an input n in N and returns the list of N (n ... 1 0).
3. The function up that takes an input n in N and returns the list of N (0 1 ... n). Hint: define an auxiliary function upfrom: N N -> list of N such that (upfrom m n) returns (m (add1 m) ... n). Assume that m is less than or equal to n.

List Abbreviations

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

2. 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 concisely.

Finger Exercises on list constants

1. Evaluate the 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

Students should feel free to skip the challenge exercises.

Trees

In class, we used ancestor family trees as an example of inductively defined tree data. In ancestor family trees, each person (a make-child structure) has two ancestors (also make-child structures) which may be empty. In this lab, we'll use a similar, but slightly different, form of tree as an example.

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

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

or equivalently, the Scheme code

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

which encodes expressions as lists revealing their nesting structure.

The string representation for expressions is particularly unattractive for computational purposes because we have to parse the string to understand its structure. The parsing process must understand which symbols are variables, operators incorporate the precedence of infix operators.

We can define a tree formulation of simple Scheme expressions which avoids representing them as list and encodes far more information about their structure. Parsers build tree representations for programs.

To simplify the formulation of Scheme expressions as trees, we will limit each addition, subtraction, multiplication, anddivision operation to exactly two subexpressions. We will limit the atomic elements of expressions to numbers.

;; Given

(define-struct add (left right))
(define-struct sub (left right))
(define-struct mul (left right))
(define-struct div (left right))

;; an Arithmetic-Expression (AExp) is either:
;; - a number ;
;; - (make-add l r) where l,r are AExps;
;; - (make-sub l r) where l,r are AExps;
;; - (make-mul l r) where l,r are AExps; or
;; - (make-div l r) where l,r are AExps,

Using this data definition, the arithmetic expression above corresponds to the structure ae1 defined by

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

A trival AExp is ae2 defined by

(define ae2 16)

Exercises on Arithmetic Expressions

1. Develop the function eval: AExp -> N where (eval ae) returns the number denoted by the expression ae. For example, (eval ae1) should return -51, and (eval ae2) should return 16.
2. [Challenge] Assume that our expression language includes many basic operations, not just the four supported by AExp. We would want a single representation for the application of a binary operator to arguments and use a separate data definition enumerating all of our operations. Rewrite the preceding data definitions, examples, and the function eval using for this. As a further challenge, extend your data definition to accommodate unary operations including negation and absolute value as unary operators.

Files and Directories

The following are data definitions are idealized (for the sake of simplicity) representations of files and directories (

n

...

!).

...

A function returning the list of naturals (or Naturals)

...

n

...

...0 in left-to-right order.

...

Given a base

...

b

...

,
the integral part of the logarithm
log

...

b

...

n

...

,
Compute this by recursively counting the number of times
you can divide the number by the base.

...

Note:

...

Like the in-class examplegeq
,
this doesn't follow the natural's data-defined template.

...

Challenge exercise, this is much tougher at this
point in the course

...

:
A function returning the list of naturals (or Naturals)
0...

...

n

...

in left-to-right order.

...

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 workonly 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 13of the book introduces some new, compact methods for representing lists.

...

NB:

...

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 anempty
. 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.

...

Exercise

...

Play with
list
a bit. Can you write these?

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

Which notation is easier to read?

...

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

...

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 trees.
In ancestor family trees, each person (a
make-child
structure)
has 0, 1, or 2 ancestors (alsomake-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

...

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

...

Exercise

...

Make more example data.

...

Develop the function
evaluate
which takes an
AExp as input and returns the number that the expression
mathematically computes. For example,
(evaluate AExp1)
should result in -51, and
(evaluate AExp2)
should result in 16.

...

Challenge exercise:

...

Let's say we hadmanybasic operations, not just
these four. We would want to have one structure for any
binary operation, using a separate data definition enumerating
all of our operations. Rewrite the data definitions, examples,
andevaluate
for this.
As a further challenge, also allow unary operations.

...

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 in the definition of for a file, which makes the set f definitions more compact but makes it less clear obfuscates 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 either:
; - a symbol (representing a "simple" file's name

...

) or
; - a directory

...

 (make-dir name contents)

...

 where name is a symbol, and contents is

...

 a lof.


; A list-of-files (

...

lof) is one of

...

; - empty

...

 or
; - (cons f lofd)

...

 where f is a file

...

 and lofd is

...

 a lof

This set of definitions

...

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

...

Tree-based data structures are very common!

...

Directory exercises

...

...

1. Create some sample data for the above types.

...

1. Write the templates for the above types.

...

2. Develop a function

   ...

   Code Block
   ; find? : symbol file -> boolean

...

1. ; Returns whether the filename is anywhere in the

...

1. ; tree of files represented by the file. This includes both

...

1. ; simple file names and directory names.

...

...

Aside

...

1. Note that this function is a vast simplification of

...

1. {{find

...

1. }}, the

...

1. mother-of-all everything-but-the-kitchen-

...

1. sink UNIX directory traversing command. If open a terminal window and enter

   Code Block
   man find

   to see what it can do.
   

...

1. 
   

...

1. Use DrScheme's stepper to step through an example use

...

1. of find?.

...

1. Following the templates leads to an overall strategy known as

...

1. depth-first search

...

1. , i.e., it explores each tree branch to the

...

1. end before moving on to the next branch.

...

...

1. Develop the following function:

   ...

   Code Block
   ; any-duplicate-names? : file -> boolean

...

1. ; Returns whether any (sub)directory directly or indirectly contains

...

1. ; another directory or file of the same name. It does NOT check

...

1. ; for duplicated names in separate branches of the tree.

...

1. There

...

1. is a straightforward way to write this function that just follows the

...

1. template.
2. Challenge:

...

1. develop a program to check for duplicated names among

...

1. all directories and files in the given tree, not just

...

1. subdirectories.
   
   Here's a hint.

...

1. Develop the following function:

   ...

   Code Block
   ; flatten-dir-once : symbol file -> (file

...

1. or lof) ; Purpose: returns a structure like the original file, except that any (sub)directory with that name is removed and its

...

1. contents are promoted up one level in the tree.

...

1. Here are two pictorial examples, in both cases removing the directory

...

1. named to-remove. These illustrate why this function can

...

1. return either a file or a list

...

Input

...

Output

...

1. of files.

Example 1:

...

foo
/ | \
bar baz to-remove
/ \
one two

      foo
    / \   \
 bar baz to-remove
          / \
        one two

becomes

      foo
   /  / \  \
bar baz one two

...

Example 2:

...

 to-remove
   / \ \
foo bar baz

becomes

foo bar baz

...

foo
/ / \ \
bar baz one two

...

Example 2:

...

to-remove
/ | \
foo bar baz

...

foo bar baz

Follow the templates and think about a single
case at a time.

...

If you do that, it shouldn't be this exercise is not too difficult. If you don't , you'll
probably have real trouble.

...

Sample solutions.

...

!! Access Permissions

...

follow the templates, you are likely to run into difficulty.