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:

Write the appropriate uses of define-struct.

List the functions that these uses of define-struct make.

Create all the program templates for functions of one input on these data types.

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.

Create test data for this 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.

Create test data for this function.

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.

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

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

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.

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.

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: