MASSACHVSETTS INSTITVTE OF TECHNOLOGY Department of Electrical Engineering and Computer Science 6.891 Spring 2006 Problem Set 1 Issued: Wed. 8 Feb. 2006 Due: Wed. 15 Feb. 2006 General instructions for problem sets: A problem set for this class generally asks you to do some programming. We usually give you a short program to read and extend. You should turn in your extensions, in the form of clearly annotated code and executions that demonstrate its effectiveness. We may also ask for short essays explaining an idea. Your answers to these questions must be clear and concise: good logic expressed in good English is required. Also, we need information to calibrate these problem sets, so please record how much time it took you to do each part and put that on your report. Thank you. Reading: Code is in simple-xhtml.scm, attached. Review SICP Chapters 1 and 2. Read SICP section 2.2.4 carefully (Picture Language). This is a nice example of a combinator-structured language embedded in Scheme. We will need these ideas. Documentation: Scan the MIT/GNU Scheme documentation online at http://www.gnu.org/software/mit-scheme/ HTML & XHTML: The Definitive Guide, 5th Edition by Bill Kennedy and Chuck Musciano available online at http://libraries.mit.edu/get/safari (requires MIT certificate) Generating Xhtml Pages Most of us are familiar with the painful construction of web pages. To be well formed, each element of a document is started with a delimiter and must end with a matching delimiter. For example: CORRECT: nested elements.

here is an emphasized paragraph.

INCORRECT: overlapping elements

here is an emphasized paragraph.

The rules for a well-formed document are easy to understand. But it would be nice to have a more abstract means of constructing documents that embodies the rules and automagically builds legal documents. Such abstract methods can be combined to build bigger document pieces from smaller ones. The file simple-xhtml.scm, reproduced below, is a start at producing such easy-to-prepare documents. It defines four elementary xhtml elements: body, paragraph, break, and horizontal-rule. Given these primitive procedures one can write code in Scheme and put them together to output legal xhtml constructions: Evaluating: (display (x-body "Now is the time" (x-paragraph "for all good men") (x-paragraph "to come" (x-break) " to the aid") (x-paragraph "of their country."))) Produces: Now is the time

for all good men

to come
to the aid

of their country.

------------- Problem 1.1: Extend the program by defining a few more simple elements, such as head and title. Demonstrate their action. ------------- The value of a representation of xhtml elements as procedural primitives becomes apparent when we need to automatically generate legal xhtml documents. For example, suppose we want to generate a sequence of paragraphs that is a small table of factorials. Evaluating: (display (x-body "Factorials" (map (lambda (n) (x-paragraph n "! = " (factorial n))) (iota 10)))) Produces: Factorials

0! = 1

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120

6! = 720

7! = 5040

8! = 40320

9! = 362880

So, we see that by building things in this way we inherit the full power of the embedding language (Scheme, in this case). ------------- Problem 1.2: Write a program that makes an interesting piece of xhtml, using even more of the power of the Scheme system. ------------- Of course, xhtml is a much more complex and powerful language than we have mechanisms to deal with so far. Each element in xhtml is allowed to have attributes, which modify its behavior. So, for example, an anchor element may allow us to define a link to some page, for example: Our Web site We have not made any provision for such attributes. We need to extend our primitive system to incorporate attributes. We may wish to notate such an anchor as follows: (x-anchor '((href "http://swiss.csail.mit.edu/users/gjs/6.891/") (name "6.891 Site")) "Our Web site") Here we represent the attributes as elements of an association list: a list of key-value pairs. Every element may have such attributes. If we want to specify an element without attributes, we can do this by supplying #f (false) for the attribute list. So, if we want the words "to come to the aid" to be rendered with the color blue, we can write: (display (x-body #f "Now is the time" (x-paragraph #f "for all good men") (x-paragraph '((style "color:blue")) "to come" (x-break) " to the aid") (x-paragraph #f "of their country."))) Yielding: Now is the time

for all good men

to come
to the aid

of their country.

------------- Problem 1.3: Rewrite our program to allow every element to take a first argument that is a list of key-value pairs. Demonstrate your code by implementing anchors and incorporating them in a nice piece of generated xhtml. ------------- The real power and flexibility of combinator-based programming appears when we have interesting combinators. For example, SICP section 2.2.4 outlines the construction of a combinator-based picture language implemented in Scheme. Here, we will develop combinators for using xhtml tables to make nice arrangements. ------------- Problem 1.4 Make Scheme procedures for implementing the xhtml elements needed for constructing tables. You will need to make element constructors named x-table, x-th, x-tr, x-td. Definitions of these elements can be found in the online reference "HTML & XHTML", Chapter 10. The particular details can be found in section 10.2. Be careful: the examples in the book are in old html, so the elements th, td, and tr are not written as wrappers. In xhtml, these elements must wrap around data with a matching delimiter. So, for example, in xhtml you may not write: Eating Kumquats Poke In The Eye ... but rather, you must write Eating Kumquats Poke In The Eye ... ------------- Suppose we want to make an arrangement that looks like the following, with the stuff in each box indicated by the letters A,B,C,D,E. --------------------------- | | | | | | D | | | A | | | | |-------| | | | | | |---------| E | G | | | | | | | | |-------| | | B | C | | | | | | F | | | | | | | --------------------------- This kind of layout is a real pain in xhtml, because the layout must be globally computed. One way to understand the computation required is: 1. Extend all of the horizontal lines to cover the entire table structure. In the figure shown this produces 4 rows. 2. For each row, make a table entry for each logical box that starts in that row, in left-to-right order. 3. Specify the number of rows and the number of columns that the logical box needs, using rowspan and colspan attributes. For example, the figure above can be constructed with the following xhtml structure:
A D G
E
B C
F
This global computation must be redone if anything is changed, for example, if A is subdivided. What we would really like to write is something like: (x-arrange (t-row (t-column A (t-row B C)) (t-column D E F) G)) where the objects represented by capital letters A--G are any xhtml elements that could appear in a table. Unlike the other procedures we have made, t-row and t-column should not return strings representing xhtml elements, because x-arrange will have to do a global computation to build this into a table. In fact, it is most appropriate for t-row and t-column to return a compound data structure (probably a list structure) and have x-arrange produce the xhtml table structure implied by this arrangement. ------------- Problem 1.5: Design and build an xhtml table compiler, x-arrange, that takes descriptions of the arrangement desired as combinations of t-row and t-column constructions, as indicated above. ------------- A real xhtml document has other required parts. For example, it needs an xml declaration with version and encoding attributes, a doctype declaration, and an html element with an xmlns attribute. Here is an example from the official description of xhtml. You can find it in http://www.w3.org/TR/2002/REC-xhtml1-20020801. Virtual Library

Moved to example.org.

------------- Problem 1.6: Complete the xhtml generator in Scheme by building other elements that are required to make a legal xhtml document. You need not implement all of the elements (whew!), just enough so that you can make real pages and put them up. Use your Scheme program to make a web page for your problem set answers and put it up on some server for us to see! Include the URL of your page in the paper answers that you hand in. ------------- We hope that this was fun. ;;;; This is the file simple-html.scm (define ((wrap-content key) . content) (flatten-append "\n" "<" key ">" content "")) (define (flatten-append . pieces) (apply string-append (map (lambda (piece) (cond ((string? piece) piece) ((number? piece) (number->string piece)) ((list? piece) (apply flatten-append piece)) (else (error "Unknown piece type: flatten-append" piece)))) pieces))) (define x-body (wrap-content "body")) (define x-paragraph (wrap-content "p")) (define ((empty-element key)) (string-append "\n" "<" key " />")) (define x-break (empty-element "br")) (define x-horizontal-rule (empty-element "hr")) #| ;;; For example (display (x-body "Now is the time" (x-paragraph "for all good men") (x-paragraph "to come" (x-break) " to the aid") (x-paragraph "of their country."))) Now is the time

for all good men

to come
to the aid

of their country.

(display (x-body "Factorials" (map (lambda (n) (x-paragraph n "! = " (factorial n))) (iota 10)))) Factorials

0! = 1

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120

6! = 720

7! = 5040

8! = 40320

9! = 362880

|# #| ;;; By the way, iota and factorial are defined as follows in the ;;; scmutils system. (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1))))) (define (iota to #!optional from increment) (define (step where) (if (>= where to) '() (cons where (step (+ where increment))))) (if (default-object? from) (set! from 0)) (if (default-object? increment) (set! increment 1)) (step from)) Also, display is an output procedure that interprets control characters such as line-feed (\n) and tab (\t) as instructions to control the format of the output. |#