Comp 210 Lab 5: Mutual recursion

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.

This example should be relatively familiar because it is very similar to the in-class example of family trees, where each parent could have children. Here we basically replace parents with directories, and children with files, and observe that directories are just a special kind of files.

We use the definitions of files and directories given in the course notes packet and the library ~comp210/lib/teach/dir-lib.ss.

Every directory or file has a name, e.g., comp210 or dir-lib.ss. A directory can contain any number of other directories or files. A file can contain any number of symbols; it also contains a number counting the number of symbols in it. Thus, we use

(define-struct dir (name dirs files)
(define-struct fil (name size contents)

• each name is a symbol,
• dirs is list of directories (list of dirs),
• files is a list of files (list of fils),
• size is a number, and
• contents is a list of symbols.

Where is recursion involved?

How many program templates do you need for these data definitions? Write some of them.

Create some example files and directories, possibly modeling your own Unix files and directories.

1. Write a program grep, which takes a file and a symbol as inputs, and returns a boolean indicating whether that symbol occurs in the file.

   This sort of models the Unix command grep symbol file.

2. Write a program grep*, which takes a directory and a symbol as inputs, and returns a boolean indicating whether that symbol occurs in any file in that directory.

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

3. Write a program grepr*, which takes a directory and a symbol as inputs, and returns a boolean indicating whether than symbol occurs in any file in any subdirectory of that directory (including the given directory).

   The Unix command grep, by itself, cannot do something like this.

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.

Last week's lab sessions didn't end up covering Unix basics much, so this week we'll try again: Unix basics.

Note that now you should have a better idea of what Unix files and directories look like because of the example above.