CS 1102 (A12) Homework 3: Complex Data Definitions

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

Assignment Goals

Remember to follow the Expectations on Homework when preparing your solutions, including the academic honesty policy.

The Assignment

You need to use Intermediate Student with Lambda language level for this 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.

[Optional] If you want to test your filesystem functions 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!

Hint: You may also find the ormap function useful (look it up in the DrRacket Help Desk). It is a kind of map and thus satisfies the requirement above.

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 functions -- 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 functions over filesystems.

  3. Write a function 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 function 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 and that it has no subdirectories. You do not need to use these assumptions if you don't want to (i.e., no loss of points for not optimizing your code around this assumption).

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

    Assume that the given filename is only in the system once.

  6. Write a function 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 Racket values for equality using the primitive equal?.

Hints and Guidelines

What to Turn In

Grade your own homework according to General Grading Guidelines before you hand it in!

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

Back to the Assignments page