Filesystem
1 Attribution
This assignment is borrowed directly from How to Design Programs. Please note that it would be a violation of the Academic Code to look at the corresponding material in that book and use any content associated with it there (not that it will necessarily help you).
2 Theme Song
リサフランク420 / 現代のコンピュー by MACINTOSH PLUS
3 Background
The goal of this assignment is to model a filesystem. A filesystem is that part of the computer that remembers programs and data when the computer is turned off (i.e., it makes the data persistent).
On most computer systems, the collection of files is organized in directories. Roughly speaking, a directory contains some files and some more directories. The latter are called subdirectories and may contain yet more subdirectories and files, and so on. The entire collection is collectively called the filesystem.
This figure shows a small filesystem. Each box has one of two annotations. A directory is annotated with DIR, and a file is annotated with a number, which signifies the file’s size. The tree’s root directory is TS. It contains one file, read!, and two subdirectories, Text and Libs. The Text subdirectory contains three files; Libs contains two subdirectories, each of which contains at least one file. Altogether, TS contains seven files and consists of five (sub)directories.
4 Data Representation
data File:
| file(name :: String, content :: String)
end
f = file("tester", "filecontent")
check:
f.size() = 11
end
data Dir:
| dir(name :: String, ds :: List<Dir>, fs :: List<File>)
end
This models a typical filesystem. Based on this model we can create functions that approximate the behavior of an actual computer.
5 Exercises
Develop the function
how-many :: Dir -> Number
which consumes a Dir and produces the number of files in the directory tree.
Develop the function
du-dir :: Dir -> Number
The function consumes a directory and computes the total size of all the files and subdirectories. Assume that storing a file and a directory in a dir structure costs 1 storage unit. The size of a directory is the sum of its files and directories, the length of its files list, and the length of its dirs list. For example, in the figure, the size of the TS directory is 218, and the size of the Code is 12.
Develop the function
can-find :: Dir, String -> Boolean
which consumes a Dir and a file name and determines whether or not a file with this name occurs anywhere in that directory tree.
Develop the function
fynd :: Dir, String -> List<Path>
(so-named because Pyret has a function called find built in). It consumes a Dir d and a file name f, and produces a list of all the paths to all the files named f in d. (That means, if can-find(d, f) is false, it produces empty.)
A path is a list of directory names. The first one is that of the given directory; the last one is that of the subdirectory that contains f. Each path should lead to a different occurrence, and there should be a path for each occurrence. To make this easier for you, we have defined the data type Path to be a list of strings (directory names), so fynd should return List<Path>.
For example, in the figure:
check:
fynd(TS, "part3") is
[list: [list: "TS", "Text"]]
fynd(TS, "read!") is
[list: [list: "TS"], [list: "TS", "Libs", "Docs"]]
end
6 Clarifications
- The paths output by fynd can be in any order, so you cannot hard code your test cases. We are providing you with the following two functions to compare the list generated by fynd with a hard-coded solution:
fun count<A>(target :: A, a :: List<A>) -> Number:
el-checker = lam(el, cnt):
if el == target:
cnt + 1
else:
cnt
end
end
a.foldl(el-checker, 0)
end
fun lst-same-els<A>(a :: List<A>, b :: List<A>) -> Boolean:
fun same-count(el, acc):
acc and (count(el, a) == count(el, b))
end
(a.length() == b.length()) and a.foldl(same-count, true)
end
If you wish, you are welcome to copy and paste these two functions exactly into your test suites. You do not need to write test cases for these functions provided that you do not modify them.
Now you can write your tests as follows:lst-same-els([list: path1, path2], [list: path2, path1]) is true
Within a single directory, all file names will be unique.
You may use == to check whether two Strings are equal, but no other String functions.
You may not use any List or Set functions other than higher-order ones (map, filter, various folds, etc.).