Comp 210 Lab 5: Mutual recursion, UNIX basics

Files example, Odd/even example, UNIX basics

On most computer systems, information and programs are stored in files, which are then organized into directories. These directories can also contain other directories. In this example, we will show a way to model files and directories based on UNIX.

UNIX considers a directory to be just a special case of a file. Every file has a name, e.g., comp210 or dir-lib.ss. A directory can contain any number of other files. A file can contain any number of symbols.

A file is one of

• (make-simple symbol list_of_symbol), where the first symbol is the name of the file and the list is the file's contents, or
• (make-dir symbol list_of_file), where the first symbol is the name of the file (a directory) and the list is the files in this directory.

Of course, a list_of_symbol is one of

• empty, or
• (cons symbol list_of_symbol)

• empty, or
• (cons file list_of_file)

Note the mutual recursion between files and lists of files.

To do

1. What are the appropriate uses of define-struct?

2. Create some example data, possibly modeling your own UNIX files and directories. Start by making examples of simple files, then a list of simple files, then a directory of these. We'll provide one large Example.

3. Since there are three data definitions, you need three templates. If you provide the template for files, we'll provide templates for list_of_symbol and list_of_file. Also, we'll happen to include the code for contains?, which is essentially the same as contains-mike? as seen in lecture. (Provided templates, contains?)

4. Beware: In the functions you are about to write, do not put more code into the function than the template suggests! In particular, the code for (say) a list_of-file suggests calling a file-handling function on the first element. Good. Your list_of_file handler should not go any further, trying to determine which case of file that first element is, etc. This is file-specific code has no business in a list_of_file handler; pass the buck to a more appropriate function. If you try to do everything all in one function, you'll end up with an awful mess (which doesn't work).
5. Write a function grep, which takes a symbol and a file as inputs, and returns a boolean indicating whether that symbol occurs in the contents of the file. It does not look in directories.

   This sort of models the UNIX command grep symbol file.

6. Write a function grep*, which takes a symbol and a list of files as inputs, and returns a boolean indicating whether that symbol occurs in any of the files. Again, this does not look in directories.

   This sort of models the UNIX command grep symbol directory/*.

7. Write a function grepr, which takes a symbol and a file as inputs, and returns a boolean indicating whether that symbol occurs in that file, or any subdirectory of that file. (including the file itself).
   Hint: Write a mutually-recursive function grepr*, which is like grep* except that it recursively descends into any directories. In fact, the naming scheme becomes clearer: the r is for "recursive", and * means that it takes a list instead of a single file. (But where in heck did the name grep come from?)

   The UNIX command grep, by itself, cannot do something like this. But, you could combine grep with find (the mother-of-all UNIX directory traversing programs).

(Labbies: Skip this if you lack time.)

Mutual recursion isn't always based on recursion in data definitions. As an example, we will define the two functions odd? and even?. Each takes a natural number as input and returns a boolean indicating whether that number was odd or even, as appropriate.

For the purposes of this example, we rely only on our basic knowledge of natural numbers, starting with its data definition and program template. (I.e., we temporarily forget about other ways to write these function using division, equality tests, and other "complicated" functions.)

A natural-number is

• 0 or
• (add1 n), where n is a natural-number.

(define natnumfun
   (lambda (n)
      (cond [(zero? n) ...]
            [else      ...(sub1 n)...])))

Following only this template, write odd? and even?. Assume that zero is even. When writing odd?, assume you will have a working version of even?, and when writing even?, assume you will have a working version of odd?.

Note that we could have defined two mutually recursive data types, odd-natural-numbers and even-natural-numbers. Then, the mutual recursion in odd? and even? would have been based on the mutual recursion of the data definitions. However, we usually don't describe these and similar definitions in that way.

Note that now you have an idea of what UNIX files and directories look like because of the example above.

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). (For consistency, the root also has a parent -- itself.)

• pwd prints the path (see below) of your current working directory.
• cd path changes your working directory to that specified. If no path is given, it changes to your home directory.
• 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. In UNIX, evaluation means variables (indicated with ``$'') are expanded and special characters like ``*'' and leading ``~''s are expanded. For example, the command

more h*.ss

more hw1.ss hw2-attempt.ss hw19.ss

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.