Com S 342 --- Principles of Programming Languages

	    EXERCISE 05: INDUCTIVE DEFINITIONS AND S-LISTS
                 (File $Date: 2004/02/04 02:21:52 $)

The purpose of this exercise is for you to learn some basic ideas
about inductive definitions.

As with all exercises, this is to be done individually.  And it is due
the day this topic is planned to be discussed in class, unless
specified otherwise (see the syllabus at:
http://www.cs.iastate.edu/~cs342/syllabus.shtml).

As with all exercises, you have two choices for doing the work. You
can either:

  - complete it as specified or
  - write down questions or problems that you had in trying to
    complete it.

If you write down questions or problems you have, these should be
detailed enough so that we can tell that you have read the materials
and thought about them.  (Don't just write: "I didn't understand how
to do it".  Instead, say what you tried and what you didn't
understand.)  During the class where this exercise is discussed, you
should ask about these difficulties, and clear them up.  Don't be shy;
there will be other people with the same problem, and everyone can
learn by discussing these issues.  And you'll most likely see similar
things on the homework, so it's best to understand them now.

1. [Inductive Definition of Directory Structures]

Read section 1.1 of "Essentials of Programming Languages" (2nd ed.,
2001) by Friedman, Wand, and Haynes.

Give an inductive specifcation of the set of directory structures in a
file system like Unix or Windows (these are essentially the same
except for the syntax).  We will ignore devices, symbolic links, and
other exotic elements of a file system, and imagine that directories
only contain files and other directories.  The contents of files are
not important, and so don't bother to define them.  What we're looking
for is something like definition 1.1.1 or 1.1.2 that defines the set
"directory structures in a file system".

2. [S-lists and Directory Structures]

Read section 1.1 of "Essentials of Programming Languages" (2nd ed.,
2001) by Friedman, Wand, and Haynes.

Is there any correspondence between directory structures and s-lists
(see p. 5 of EOPL2e) that you can draw?  That is, if you were to set
up an analogy between directory structures and s-lists, what would be
analogous to what?  Explain briefly.

WHAT TO HAND IN

You should have at the beginning of class, written answers to the
above questions (or written out questions and problems you encountered
for each part).  Make sure your name is on these. Attach the
printouts, if any, requested above.

ADDITIONAL THOUGHTS

If you have time, think about what a grammar for directory structures
would look like. 

In a window system (like Java's Swing or AWT), windows can contain
windows.  How are windows like s-lists?

If you're familiar with XML, how is XML like an s-list and how is it
different?