Com S 342 --- Principles of Programming Languages

	       EXERCISE 05: WRITING RECURSIVE PROGRAMS
                 (File $Date: 2005/02/15 05:02:28 $)

The purpose of this exercise is to have you learn more about writing
recursive programs.

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).

We expect this to help you think about the readings (see below).
If you don't have an answer or an answer that you think is good,
write down what you read, and a question or two that would have helped
you make progress.   Then you can ask that question in class;
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.


READINGS:
Read the "Following the Grammar" handout, which
is available from the course resources web page and also directly at:

   http://www.cs.iastate.edu/~cs342/docs/follow-grammar.pdf

1. [remove-attributes]

   This is an exercise about a grammar for XML data.  This format is an
   abstract syntax representation of the (concrete syntax) normally
   associated with XML.  The particular representation we use, SXML,
   is designed to work with the output of the SSAX XML parser, documented at
   http://okmij.org/ftp/Scheme/xml.html.  The details are contained in
   the following grammar, which is documented in our course library
   file "sxml-helpers.scm"

   Your task is to write, using the helpers in
   sxml-helpers.scm, a procedure:

     remove-attributes : (-> (document) document)

   such that (remove-attributes doc) returns a document that is like doc,
   except that there are no attributes anywhere in the result.

   To give examples, suppose that we first make the following
   definition.

    (define simpledoc
      (document
        (list (PI 'x86 "run; die"))
        (list (comment "those x86s..."))
        (named
         'html
         (list
          (child (attributed 'head
                             (list (name-value 'title "Simple doc"))
                             '()))
          (child
           (named 'body
                  (list (child (named 'p (list (text "First paragraph."))))
                        (child (named 'p (list (text "Second paragraph."))))
                        )))))))

   Then we have the following examples

   (remove-attributes
      (document '() '()
                (attributed
                 'weighings
		 (list (name-value 'units "KGs"))
                 (list (child (named 'weight (list (text "42"))))))))
     ==> (*TOP* (weighings (weight "42")))

   (remove-attributes simpledoc)
     ==> (*TOP* (*PI* x86 "run; die")
                (*COMMENT* "those x86s...")
                (html
                 (head)
                 (body (p "First paragraph.")
                       (p "Second paragraph."))))

    You can test your code using

       (test-ex "remove-attributes")

    For this exercise, you don't need to turn in a printout of your
    testing, just a printout of your code is enough.

WHAT TO HAND IN

You should have at the beginning of class, written answers for 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 READINGS

If you have time, read section 1.2 of "Essentials of Programming
Languages" (2nd ed., 2001), by Friedman, Wand, and Haynes, and chapter
5 of The Little Schemer.