CS 1102 (A08) Homework 3: Complex Data Definitions

Due: September 18 (Thursday) at 11:59pm via turnin (assignment name hwk3).

Assignment Goals

The Assignment

For an operating systems class, you've been asked to implement a simple filesystem. The HTDP text provides three models for filesystems. Use Model 3, the one at the bottom of the page, for these exercises.

If you want to test your filesystems programs on a real filesystem (your own, for example), use the dir.ss teachpack described in HTDP, exercise 16.3.1.

In these exercises, a "filesystem" is a directory (the root directory). Functions over "filesystems" should therefore follow the template for dir (where dir is as defined in the HtDP model).

You should use map and filter whenever appropriate in your solution. This means that if a function matches the structure of map or filter, you should write it using map/filter. You do not need to re-arrange solutions to use map/filter (even if they have one solution that uses them and one that does not). If you are still shaky with map/filter, write the solutions without map/filter first, then look for places where you could rewrite your solutions with them (you'll get more points for a solution that matches the template but misses map/filter calls than for solutions that don't correctly solve the problem.) Map/filter solutions still follow the templates!

Warning: One common error on these problems is mixing up the positions of files and subdirectories when you make your examples of data and test cases. You then spend a lot of time "debugging" code that is correct around buggy examples. Double check your examples carefully to make sure you haven't done this. One indication that you are having this problem is an error about no matching cond clause in one of your programs -- that usually means that you put the wrong type of data somewhere in your data structure.

  1. Write three examples of data created with the filesystem data definition.

  2. Write the template for programs over filesystems.

  3. Write a program any-huge-files? that consumes a filesystem and a number (a file size) and returns a boolean indicating whether any file in the filesystem has size larger than the given size.

  4. Write a program clean-directory that consumes a filesystem and an existing directory name, and returns a filesystem. In the returned filesystem, any files of size 0 in the named directory should have been removed. All other files and directories should be the same between the input and returned filesystems.

    You may assume that the given directory name is only in the system once. You do not need to use this assumption if you don't want to (ie, no loss of points for not optimizing your code around this assumption).

  5. Write a program find-file-path that consumes a filesystem and a filename and returns either the path (a list of directory names, in order from root to the one containing the file) to that filename or false if the filename is not in the filesystem.

    Assume that the given file name is only in the system once.

  6. Write a program file-names-satisfying that consumes a filesystem and a function from file to boolean and returns a list of names of files for which the given function returns true (you don't need to include the whole path, just the filename). You may find it easier to first write this function with a specific criterion (such as a file with a minimum size) instead of the function parameter, then generalize it.

  7. Use file-names-satisfying to write a function files-containing that consumes a filesystem and a value and returns a list of names of files with the given value as its contents. You can compare arbitrary Scheme values for equality using the primitive equal?.

What to Turn In

Turn in a single file hwk3.ss (or hwk3.scm) containing all code and documentation for this assignment. Make sure that both students' names are in a comment at the top of the file.

Hints and Guidelines

Back to the Assignments page