Comp 210 Lab 4: More define-struct,
Unix basics
More define-struct,
list vs. cons,
Unix basics
More define-struct
Consider the following data definition, which describes the structure of
a medieval kingdom:
<regent> := (general aide)
where general is a <knight>, and aide is a <serf>.
<knight> := (private salary)
| (officer fellow squire servant salary)
where fellow is a <knight>, and squire and servant are <serf>s.
salary is a number of potatoes.
<serf> := (simpleton potatoes)
| (idiot)
where potatoes is a number, and rebel is a <regent>.
I.e., in English:
- A regent has a general and an aide,
where the general is a knight, and
the aide is a serf.
- A knight is either
- a private,
who has a salary,
where the salary is a number, or
- an officer,
who has a fellow, a square,
a servant, and a salary,
where ...(see above)....
- A serf is either
- a simpleton, who has potatoes,
where potatoes is a number, or
- an idiot.
- Q: Is there any recursion in this?
- A: Sure, a kind of knight, officer,
is defined in terms of knight.
Write the appropriate uses of define-struct.
- Q: How many uses do we need?
- A: 5. One for regent,
two for knight, and
two for serf.
List the functions that these uses of define-struct make.
- Q: How many constructors, predicates, and selectors are there?
- A: 5 constructors, one for each define-struct.
5 predicates, one for each define-struct.
8 selectors: 2 for regent, 1+4 for knight,
and 1+0 for serf.
Create all the program templates for functions of one input on these
data types.
- Q: How many templates do we need?
- A: 3. One that takes a regent as input,
one for a knight as input, and
one for a serf as input.
Write a function that counts the number of potatoes grown in a kingdom.
(simpletons generate potatoes,
idiots are too stupid to raise potatoes.
knights and regents are too important to farm
themselves.)
The function should take a regent as its argument and
return a number.
- Q: How many functions should you write in total for this?
- A: 3, one for each relevant data type. To write a function
potatoes-of-regent, we need helper functions
potatoes-of-knight and potatoes-of-serf.
Create test data for this function.
- Q: To be thorough, how many pieces of test data do we need?
- A1: Assume we test each of the three functions separately.
We need at least two different serfs, one of each kind.
We need at least two knights, one of each kind.
We need at least one regent, of the only kind.
- A2: Assume we test only the main function
potatoes-of-regent. We still need to test each of the
cases of the helper functions.
We could easily use four regents
(= 2 * 2 * 1, or all combinations of the previous test cases).
We could get away with fewer.
Since an officer has two serfs,
one regent with a general who is an
officer could have two different kinds of
serfs, thus testing multiple cases
of potatoes-of-serfs at once.
It is much easier to test each function separately,
because it is easier to generate the test cases, and for larger
examples, you need more test data to test all cases if you are
only testing the main function.
With either answer, be sure to pick each serf's number of
potatoes well.
E.g., it's not very helpful if each serf generates zero potatoes:
you can't tell if you're adding all the numbers up properly.
E.g., if you pick the numbers 1, 10, 100, ..., you'd be able to check not
only whether your sum is correct, but if it isn't, you should be able to
tell which number wasn't being added correctly.
In the real world, understanding all of the relevant test cases is very
important for checking software products. This is part of the area of
Quality Assurance, or QA.
A hint of mutual recursion
You haven't seen this in lecture yet, but here's something to think about.
Let's add to our data definition:
<serf> := ...
| (spy potatoes rebel)
This introduces mutual recursion:
There is a loop in the dependencies: regent is defined
in terms of knight, which is defined in terms of
serf, which is defined in terms of regent.
How would we change our potato-counting program?
(Spies steal potatoes.)
Write a function that checks if a kingdom has any spys
working against it.
The function should take a regent as its argument and
return a boolean.
- Q: Do we need to write templates for this function?
- A: No, each function doesn't require a template, just each input
data type, and we've already written templates for these datatypes.
- Q: How many functions should you write in total for this?
- A: 3, like before.
To write a function
has-spies-regent?, we need helper functions
has-spies-knight? and is-spy-serf?.
Create test data for this function.
- Q: How many pieces of test data do we need?
- A: Assume we test each function separately since we know that
is easier than testing just the main function.
We need at least three different serfs, one of each kind.
We need at least two knights, one of each kind.
For completeness, we need nine
(a private plus eight officers,
each combination of his fellow possibly
having a spy and his squire and
servant possibly being spies).
We need at least one regent, of the only kind.
For completeness, we need four (each combination of
his general possibly having a spy and his
aide possibly being a spy).
This would test all the cases of any reasonable implementation.
This example requires a lot of test data to be fully complete.
list vs. cons
Let's look at some different uses of list and cons,
so that we make sure we never confuse the two.
- Q: What's the difference between
(cons 1 null) and (list 1 null)?
- A: The former creates a list containing one element, 1.
The latter creates a list containing two elements, 1 and
null, i.e., the list
(cons 1 (cons null null)).
- Q: What's the difference between
(cons 1 2) and (list 1 2)?
- A1: The former is an error -- cons's second argument must
be a list.
The latter creates a list containing two elements, 1 and
2, i.e., the list
(cons 1 (cons 2 null)).
- A2: There is another answer if we consider all of Scheme.
However, we won't be talking about that in this course.
- Q: What's the difference between
(cons 1) and (list 1)?
- A: The former is an error -- cons requires two arguments.
The latter creates a list containing one element, 1.
- Q: What's the difference between
(cons 1 2 null) and (list 1 2 null)?
- A: The former is an error -- cons requires two arguments.
The latter creates a list containing three elements.
- Q: What is (list)?
- A: null.
In short, cons and null are the constructors of lists.
list is another function which makes lists, and is convenient
shorthand for combinations of the constructors.
Unix basics
Now for a quick intro to a handful of Unix basics.
This isn't part of the course material, but will be generally helpful
when you are working on the computer.
Unix keeps each of your files in a directory.
Directories may themselves be contained in other directories.
(Directories are just special kinds of files.)
Directories are just the same thing as Windows/Mac folders.
In other words, directories and files form a tree, similar to
the family tree you've seen in class.
At any point, you (or more accurately, each xterm) is in a specific
directory, your working directory.
Each directory contains itself, always named . (a period)
and its parent, always named .. (two periods).
The top root directory is called / (a slash).
- pwd prints the path (see below) of your current working
directory.
- cd path changes your working directory
to that specified.
- ls path lists the files in the the specified
directory. If no path is given, it lists the files in the current
working directory.
A path is a name for a file. A path can be relative
or absolute. A relative path names a file relative to your
current working directory; an absolute path give the total name for
the file, starting from the root directory, /.
- foo.ss is a relative path to a file in your current directory.
- ../foo.ss is a relative path to a file in the parent of your
current directory.
- /home/comp210/public_html is an absolute path
to a subdirectory of the root directory.
- ~comp210/public_html is a path to a subdirectory of the
home directory of comp210. The first character, twiddle (``~''),
is pronounced ``home of'' in the context of filenames.
When you type a command, e.g., drscheme, Unix searches
a variable (PATH)
that contains a list of paths to look in to find that program.
One of the things that register comp210 did for you was to
add things to your PATH.
- echo $PATH prints your PATH.
Commands/programs take arguments telling them what to do.
E.g., register comp210 told the register program to add you to
this course. Some of you have also used the program to register for other
courses using a different argument.
You will need to manipulate files in various ways.
- mv oldpath newpath moves a file
from one location to a new one.
- cp oldpath newpath copies (duplicates) a file
from one location to a new one.
- rm path removes (deletes) a file.
Careful -- deleted files are forever gone!
- more path displays the contents of a file,
a screenful at a time.
The syntax of Calling UNIX programs is similar to calling
Scheme functions:
The first word is the name of the program to call,
and successive words are arguments to that program.
Moreover, as in Scheme, before the program is actually called,
the other arguments are evaluated.
For example,
-- in Unix, this means
variables (indicated with ``$'') are expanded and
special characters like ``*'' and leading ``~''s are expanded.
For example, the command
more h*.ss
first evaluates the argument to mean all of
the files in the current directory whose name ends
start with h and end in .ss.
I.e., this could be equivalent to typing something like
more hw1.ss hw2-attempt.ss hw19.ss
if those are the Scheme files in
this directory.
(Note that more received three arguments -- not one.)
In Unix-terminology, we say that the wildcard pattern h*.ss
was expanded.
(There are other ways to provide wildcards and patterns.)
We will occasionally cover more Unix basics. For more info,
refer to Owlnet handouts available in Mudd or just ask around.
Also use the online (terse) manual pages:
- man program gives information about the specified
Unix program.
- man -k keyword looks for a manual page related to
the keyword.