COMP 210, Spring 2001
Homework 5 : Mutual Recursion
Due Oct.03 (wed), in class

All problems will require all (applicable) steps from the design recipe, including a template. Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.


An xexpr ("xml-expression") is either: An xlist (list of xexpr) is:

Do the following:

  1. For context, read over xml and xexpr background.

    If you want, there is a provided teachpack (see below), which will let you read an xml file (giving you the corresponding xexpr), and similarly let you write an xexpr to a file (it will be written as an xml file, which may happen to be an html file (see wrap-into-html below)). However, this assignment is purely about manipulating and transforming xexprs; no knowledge of xml or html is needed, and any html files you create are entirely optional.

  2. Make some further examples of xexprs, for testing our later functions. Build them up from the above definition. (What are the simplest examples of each type?)
  3. Write the function is-this-a?, which takes in a symbol and an xexpr, and returns whether the xexpr is a list whose first item is the indicated symbol. (An easy function, but handy.)
  4. Make templates for xexpr and xlist.
  5. Often people comment out parts of their file. For instance, they might comment out one caption and use an alternate one. Or they might comment out an entire stretch of several pictures (which might themselves contain commented-out sections). Commenting out is easy, with xexprs: we simply declare anything occurring between <comment> and its matching </comment> as being commented out.

    Make sure you have examples of xexprs containing comments, including some nested comments.

    Of course, programs which interpret the data don't want to even see anything which has been commented out. Write strip-comments: Given an xlist, return a corresponding xlist, except w/ any 'comment sub-xexprs removed, no matter how deeply nested.
    (This will include a helper function for individual xexprs, of course; what if this helper is itself given a comment xexpr? You can either mention in the contract/purpose that your function only works on non-comment xexprs, or you can return the empty string, "".)

    Hint: compare with functions we've written before, which (say) remove each occurrence of 7 from a list of numbers. You might want to quickly write that function, you you can discuss the exact analogy here. What does the template suggest for the first and the rest of your xlist?

  6. Write xexpr=?, which takes two xexpressions and determines whether they're equal. (This wil be helpful when doing your test cases.) Note: include a template for functions-processing-two-xexprs, Be sure your template explicitly lists all possible cases of the input. Note 2: You may want to defer this problem until you've done a couple of the following, since it's harder to process two xexprs simultaneously, than functions which just process one.

    Do not use the built-in function equal? for this homework. Essentially, you are writing that function yourself. After this homework, you will be allowed to use equal?.

  7. collect-captions: Given an xlist, -- no symbol -- return a list of those xexprs which are tagged 'caption, in the immediate list only. (That is, if your list contains a tagged xexpr 'table, don't look inside the table to see if it contains (anything that contains) a caption.)
  8. collect-pictures: As collect-captions, but looking for xexprs tagged with 'pictures. Hint: generalize collect-caption and collect-pictures so that you only have one general version of the function, which can handle either case.
  9. verify-1-tag: Given a xlist and a symbol, return true if there is exactly one tagged-xexpr with the indicated tag in the immediate list (non-nested). This is useful in checking that, say, a picture contains at exactly one 'caption tag.
  10. wrap-into-html: xlist --> xexpr. Given a list of xexpr Xs return the xexpr
    (list 'html 
          (list 'head (list 'title "my html page"))
          (list 'body ...))
    
    where the ... should be replaced by the elements of Xs.
    (Note: this involves taking the list Xs and tacking 'body on to the front of it: should you use the function list, or the function cons? How many items are (immediately) in the list that you return? Will calling list work in this situation?)
    Optional: If you want to, you can also take in a title-string, and use that in the header. And perhaps even include (list 'h1 title-string) inside the body.

    By the way, .html files happen to always consists of exactly two elements: a head (containing just the title, usually displayed in the title-bar of a browser window), and the body (which is the actual contents). (Coincidence ?-)
    Correction: In the original version, I forgot that the title is itself an element of the head (according to html). This version fixes that, but of course we'll accept either the old or new for the homework.

  11. frame-picture: picture --> xexpr. A picture is a particular type of xexpr: it is of the form (list 'picture (list 'caption ..) (list 'filename ..)), except that the filename and caption can come in any order (but there is only one of each). Your function should take in such an xexpr, and output

    (list 'li (list 'img (list 'attr 'src filename))
              (list 'p (list 'attr 'align "center") ..caption))
    
    where filename is a string, and ..caption is the contents of an xlist.

    Why this particular mumbo-jumbo? It's html for a (single) list-item, whose contents are an 'img, and a paragraph. These elements each contain some attributes: The image contains an attribute saying what the image's source-file is, and the paragraph contains an attribute suggesting that it's centered. The rest of the paragraph is of course the caption.

    Notes: You may return the same info in different html, if you like; the details are up to you. Also, you do not need to check that each picture has exactly one caption and filename. (If you want to for fun, that's fine; check out the scheme's functions error and format functions. E.g., (error 'frame-picture (format "Only one caption should be in ~s." the-pict)))

  12. process-gallery: xexpr --> xlist. (If you already wrote a version which returned a single xexpr with reasonable contents, that's fine too.) Given a gallery (an xexpr which contains a title xexpr and (any number of) pictures), return an xlist of the form:
    (list 
      ('p ..title)
      ('ol ..framed-pictures))
    
    That is, a paragraph whose contents are the gallery's title, and then an ordered-list, containing the results of frame-picture on each of the gallery's pictures.
For an larger example of the last few functions: The sample gallery, after being processed and then further wrapped in html (and then written as an xml file, with a couple of aptly-name jpeg files sitting in the same directory. (Use your broswer to "view-source")). For fun: Load the teachpack /home/comp210/Homeworks/Hw05/xexpr210.ss. You then have access to the functions: