Lecture 10: Directories and Files, Refining Models (Mon.Wed)

###
Lecture 10: Directories and Files, Refining Models (Mon.Wed)

(quick reminder in q & a session)

1. Given:

       ;; pi : list-of-numbers -> number
       ;; compute the product of the numbers on alon
       (define (pi alon) ...)

   1. What does this compute:

          (pi (list 1 2 3))

   2. What does this compute:

          (define alon (list 1 2 3))

          (pi alon)

   3. What does this compute:

          (define alon (list 1 2 3))

          (pi (rest alon))

   4. What does this compute:

          (define alon ...)

          (pi (rest alon))

   So why should it compute anything different in this contex:

       ;; pi : list-of-numbers -> number
       ;; compute the product of the numbers on alon
       (define (pi alon)
         (cond
           [(empty? alon) ...]
           [else ... (first alon) ...
             ... (pi (rest alon)) ...]))

   That's why natural recursion works!

   Directories and Files
2. On Windows, folders contain folders, which may contain folders and so on. At the bottom we have plain files. On Unix, folders are called directories. A file is a file. Let's model directories and files.

   Like general scientists, we start with a simple model and refine it later:

                [The Ptolemaeus Model of File Systems]

                  _______________________
                 |                       |
                 v                       |
       A directory is either             |
         - empty                         |
         - (cons fyle directory)         |
                       |                 |
                        -----------------
         - (cons directory directory)    |
                       |       |         |
                        -----------------

       A fyle is a symbol (its name).

   This data def has three self-references, but so what.

   Now let's develop the function

       ;; exists? : dir symbol -> boolean
       ;; does name occur in a-dir?
       (define (exists? name a-dir) ...)

3. Okay this model is pretty simple. Let's turn files into things that have structure:

                [The Newton Model of File Systems]

       (define-struct fyle (name size))

       A directory is either
         - empty
         - (cons fyle directory)
         - (cons directory directory)

       A fyle is (make-fyle symbol number)

       ;; du : dir name -> number
       ;; du computes the disk usage of all the files in a-dir and its
       ;; subdirectories
       (define (du a-dir) ...)

   ... the usual: examples, template, definitions ...

4. For a moment, we step back and ignore files completely, and we refine directory into structures with size etc.

                [The Einstein Model of File Systems]

       (define-struct dir (name size subs))

             ____________________________________________________________________
            |                                                                    |
            v                                                                    |
       A directory is (make-dir symbol number list-of-directories)               |
                 __________________________________________________              |
                |                                                  |             |
                v                                                  |             |
       A list-of-directories is either                             |             |
         - empty                                                   |             |
         - (cons d lod)                                            |             |
         where d is a directory and lod is a list-of-directories.  |             |
                       |                          |                |             |
                       |                           ----------------              |
                        ---------------------------------------------------------

   This is the first set of data definitions with mutual references (and self references). This is complicated. Let's make some examples. Let's make some examples:

       (define MS (make-directory 'win3.1 300 empty))
       (define Nxt (make-directory 'win 1 empty)
       (define Sys (make-directory 'sys 2 (cons Nxt (cons MS empty))))

   [Continued]

Matthias Felleisen | This page was generated on Fri Mar 5 09:04:41 CST 1999.