Com S 342 --- Principles of Programming Languages HOMEWORK 4: RECURSION OVER DATA DESCRIBED BY GRAMMARS AND TAIL RECURSION (File $Date: 2006/11/13 22:08:55 $) Due: problems 2-4 at the beginning of class Tues., Sept. 26, 2006; problems 7-8, 10, 14 at the beginning of class Thurs., Sept. 28, 2006. In this homework, you will learn more about recursion over data described by more complex grammars and about tail recursion. All code is to be written in Scheme, using the exact procedure names specified in the problem descriptions. Test using your own tests and also use our tests, as described in homework 1. For coding problems hand in: - a printout of the code with your name in a comment, and - if our tests reveals any errors with your code for that problem, then include a transcript showing a run of our tests. That is, you only have to hand in output of your testing if it reveals problems in your code (that you have not fixed). We expect you to run our tests for each problem, but since the output in the case where the tests all pass is not very interesting, we will trust you to have done this. However, you must hand in a transcript of your testing if your code does *not* pass our tests perfectly, as this will alert us to the problem and will help us assign partial credit. If we find that your code is not correct and the problem would have been revealed by our testing, but you did not hand in test results showing these problems, then you will receive 0 points for that problem. You may also hand in a transcript that includes our tests if you wish. Tests are in the directory $PUB/homework/hw4 for test data for each coding problem. (Recall that $PUB means /home/course/cs342/public/.) This applies even if you aren't using the Com S machines. (If you're not, see the course web page for how to test at home.) The section headings below give the readings related to the problems. (Please read them!) FOLLOWING THE GRAMMAR HANDOUT http://www.cs.iastate.edu/~cs342/docs/follow-grammar.pdf ESSENTIALS OF PROGRAMMING LANGUAGES: SECTION 1.2 CODE EXAMPLES WEB PAGE, http://www.cs.iastate.edu/~cs342/lib342/code-examples.html#DerivingPrograms THE LITTLE SCHEMER, CHAPTER 5 In these problems, you are not to use the parse-... procedures in your own code, but you should use the other helpers given in the files described. The reason for this is that parsing is considered an expensive operation, and once done once, shouldn't be done internally in your code. Instead of using the parsing procedures in your code, use the constructor procedures. We have tried to illustrate how to use the constructor procedures in many of the examples. Don't hesitate to write additional helping procedures, especially for recursion over the lists that are implicit in the use of Kleene star (*) in various grammars. 1. (suggested practice) [largest-width] This is a problem about the window layouts discussed in section 5.2 of the "Following the Grammar" handout. Write a procedure largest-width : (-> (window-layout) number) such that (largest-width layout) returns the largest width of any window found in layout. If the layout has no windows, the result should be zero. You can assume that the input window layout has been constructed according to the grammar. That is, you don't have to check for errors in the input, and can assume that the input has been parsed. (largest-width (parse-window-layout '(horizontal ))) ==> 0 (largest-width (parse-window-layout '(vertical ))) ==> 0 (largest-width (parse-window-layout '(window simpsons 30 40))) ==> 30 (largest-width (parse-window-layout '(window family-guy 70 11))) ==> 70 (largest-width (parse-window-layout '(horizontal (window family-guy 30 15) (window futurama 89 55)))) ==> 89 (largest-width (parse-window-layout '(vertical (vertical (window simpsons 200 150)) (horizontal (horizontal (window news 5 5))) (horizontal (window family-guy 30 15) (window futurama 89 55))))) ==> 200 You must use the helping procedures in $PUB/lib/window-layout-mod.scm in your solution. You can load these into your solution using the following in your file: (require (lib "window-layout-mod.scm" "lib342")) After doing your own testing you must test your code using: (test-hw4 "largest-width") 2. (20 points) [shrink-to] This is a problem about the window layouts discussed in section 5.2 of the "Following the Grammar" handout. Write a procedure shrink-to : (-> (number number window-layout) window-layout) such that (shrink-to width height wl) returns a window layout that is just like wl, except that each window in wl is made to have width w-new and height h-new, where w-new is the minimum of the window's current width and the width parameter, and h-new is the minimum of the window's current height and the height parameter. You can assume that the input window layout has been constructed according to the grammar. That is, you don't have to check for errors in the input, and can assume that the input has been parsed. However, to better show how the helping procedures in $PUB/lib/window-layout-mod.scm work, in the examples below, we often use the helping procedures directly to construct window layouts. (shrink-to 10 39 (parse-window-layout '(vertical ))) ==> (vertical) (shrink-to 10 39 (parse-window-layout '(horizontal ))) ==> (horizontal) (shrink-to 10 39 (parse-window-layout '(window simpsons 30 40))) ==> (window simpsons 10 39) (shrink-to 10 39 (window 'simpsons 30 11)) ==> (window simpsons 10 11) (shrink-to 80 39 (window 'family-guy 30 11)) ==> (window family-guy 30 11) (shrink-to 80 5 (window 'family-guy 30 11)) ==> (window family-guy 30 5) (shrink-to 20 30 (horizontal (list (window 'family-guy 30 15) (window 'futurama 89 55)))) ==> (horizontal (window family-guy 20 15) (window futurama 20 30)) (shrink-to 20 30 (vertical (list (vertical (list (window 'simpsons 200 150))) (horizontal (list (horizontal (list (window 'news 5 5))))) (horizontal (list (window 'family-guy 30 15) (window 'futurama 89 55)))))) ==> (vertical (vertical (window simpsons 20 30)) (horizontal (horizontal (window news 5 5))) (horizontal (window family-guy 20 15) (window futurama 20 30))) You must use the helping procedures in $PUB/lib/window-layout-mod.scm in your solution. You can load these into your solution using: (require (lib "window-layout-mod.scm" "lib342")) After doing your own testing you must test your code using: (test-hw4 "shrink-to") 3. (20 points) [beval] This is a problem about the boolean expressions discussed in section 5.3 of the "Following the Grammar" handout. Write a procedure beval : (-> (bexp boolean boolean) boolean) such that (beval bexp p-val q-val) returns the value for bexp when P has the value p-val and Q has the value q-val. You are to write this without using Scheme's eval function. You can assume that the input bexp has been constructed according to the grammar. That is, you don't have to check for errors in the input, and can assume that the input has been parsed. The following are examples. (beval (parse-bexp 'P) #t #f) ==> #t (beval (parse-bexp 'Q) #t #f) ==> #f (beval (parse-bexp '(not P)) #t #f) ==> #f (beval (parse-bexp '(or (not P) Q)) #t #f) ==> #f (beval (parse-bexp '(and P (or Q (not Q)))) #t #f) ==> #t (beval (parse-bexp '(and (or P P) (or (or P P) (or Q Q)))) #f #t) ==> #f (beval (parse-bexp '(and (or P P) (or (or P P) (or Q Q)))) #t #f) ==> #t (beval (parse-bexp '(or (not (and P P)) (and (not (not (and P P))) (not (and P Q))))) #t #f) ==> #t You must use the helping procedures in $PUB/lib/bexp-mod.scm in your solution. You can load these into your solution using: (require (lib "bexp-mod.scm" "lib342")) Note that in DrScheme, procedure names in modules seem to be case sensitive. So be sure to use the names P?, Q?, P, and Q in your code in upper case. After doing your own testing you must test your code using: (test-hw4 "beval") 4. (25 points) [bswap] This is a problem about the boolean expressions discussed in section 5.3 of the "Following the Grammar" handout. Write a procedure bswap : (-> (bexp) bexp) such that (bswap be) returns a bexp that is the same as be except that every P in be is changed to Q and every Q in be changed to P. For example, the following equations hold (note these are not evaluations, but are equations between Scheme terms): (bswap (var-exp (P))) = (var-exp (Q)) (bswap (var-exp (Q))) = (var-exp (P)) (bswap (not-exp (var-exp (P)))) = (not-exp (var-exp (Q))) (bswap (or-exp (not-exp (var-exp (P))) (var-exp (Q)))) = (or-exp (not-exp (var-exp (Q))) (var-exp (P))) (bswap (and-exp (var-exp (P)) (or-exp (var-exp (Q)) (not-exp (var-exp (Q)))))) = (and-exp (var-exp (Q)) (or-exp (var-exp (P)) (not-exp (var-exp (P))))) You must use the helping procedures in $PUB/lib/bexp-mod.scm in your solution. You can load these into your solution using: (require (lib "bexp-mod.scm" "lib342")) Note that in DrScheme, procedure names in modules seem to be case sensitive. So be sure to use the names P?, Q?, P, and Q in your code in upper case. Be sure to use a helping procedure, such as bswap-varref, in your solution so that your code follows the grammar. After doing your own testing you must test your code using: (test-hw4 "bswap") 5. (suggested practice) [size of a bexp] Suppose we say that the size of a boolean formula is its maximum depth of nesting. Hence P has size 0, (not P) size 1, (and (not P) Q) size 2 and so on. Write and test the procedure size. 6. (45 points; extra credit) [tautologies] A tautology is a boolean expression that is true for all values of its variables. (For example, (or P (not P)) is a tautology. Write a procedure tautologies such that (tautologies n) returns a list of all boolean expressions of size less than or equal to n that are tautologies. Hint: don't test with very large sizes. 7. (40 points) [all-ids] This is a problem about the statement and expression grammar discussed in section 5.4 of the "Following the Grammar" handout. Write a procedure all-ids : (-> (statement) (set-of symbol)) such that (all-ids stmt) returns a set of all symbols used in the statement as identifiers. These may occur in a number of places in the grammar, but the base cases are as var-exps and in the set-stmts. The following are examples. (set-equal? (all-ids (exp-stmt (var-exp 'x))) (set 'x)) ==> #t (set-equal? (all-ids (exp-stmt (var-exp 'y))) (set 'y)) ==> #t (set-equal? (all-ids (exp-stmt (num-exp 42))) (set )) ==> #t (set-equal? (all-ids (set-stmt 'y (var-exp 'x))) (set 'y 'x)) ==> #t (set-equal? (all-ids (set-stmt 'x (var-exp 'x))) (set 'x)) ==> #t (set-equal? (all-ids (set-stmt 'myvar (num-exp 3))) (set 'myvar)) ==> #t (set-equal? (all-ids (set-stmt 'myvar (num-exp 3))) (set 'myvar)) ==> #t (set-equal? (all-ids (exp-stmt (begin-exp '() (var-exp 'zz-top)))) (set 'zz-top)) ==> #t (set-equal? (all-ids (parse-statement '(begin zz-top))) (set 'zz-top)) ==> #t (set-equal? (all-ids (parse-statement '(begin bart (set! marge 1) (set! homer zz-top) zz-top))) (set 'bart 'marge 'homer 'zz-top)) ==> #t You must use the helping procedures in $PUB/lib/statement-expression.scm in your solution. You can load these into your solution using: (require (lib "statement-expression.scm" "lib342")) These are needed to be sure your code is independent of the representation details of the statement-expression grammar, whose helpers are designed to make problems if you don't use all the helpers! Also be sure to use a helping procedure, such as all-ids-exp, in your solution so that your code follows the grammar. You need to use your solution to the set-ops problem on homework 3, or if you don't have one, you can use a library file with a different representation that will work fine as well; to get that use (require (lib "set-ops-as-vector.scm" "lib342")). After doing your own testing you must test your code using: (test-hw4 "all-ids") 8. (40 points) [subst-identifier] This is a problem about the statement and expression grammar discussed in section 5.4 of the "Following the Grammar" handout. Write a procedure subst-identifier : (-> (symbol symbol statement) statement) such that (subst-identifier new old stmt) takes two symbols, new and old, and a statement stmt, and returns a statement that is just like stmt, except that all occurrences of old as an identifier in stmt are replaced by new. The following are examples. (subst-identifier 'new 'old (exp-stmt (var-exp 'old))) = (exp-stmt (var-exp 'new)) (subst-identifier 'new 'old (exp-stmt (var-exp 'x))) = (exp-stmt (var-exp 'x)) (subst-identifier 'x 'a (exp-stmt (var-exp 'a))) = (exp-stmt (var-exp 'x)) (subst-identifier 'x 'a (set-stmt 'a (num-exp 3))) = (set-stmt 'x (num-exp 3)) (subst-identifier 'x 'a (set-stmt 'a (begin-exp (list (set-stmt 'a (num-exp 3))) (var-exp 'b)))) = (set-stmt 'x (begin-exp (list (set-stmt 'x (num-exp 3))) (var-exp 'b))) (subst-identifier 'x 'a (parse-statement '(set! a (begin (set! a 3) (set! b a) b)))) = (parse-statement '(set! x (begin (set! x 3) (set! b x) b))) (subst-identifier 'x 'a (parse-statement '(begin a))) = (parse-statement '(begin x)) (subst-identifier 'x 'a (parse-statement '(set! a (begin (begin a))))) = (parse-statement '(set! x (begin (begin x)))) (subst-identifier 'x 'a (parse-statement '(begin (set! a (begin 3)) (set! a (begin (set! a (begin 4)) a)) 5 6 a (begin a) 5 (begin (begin (begin b) a)) (begin (set! b (begin a)) b)))) = (parse-statement '(begin (set! x (begin 3)) (set! x (begin (set! x (begin 4)) x)) 5 6 x (begin x) 5 (begin (begin (begin b) x)) (begin (set! b (begin x)) b))) You must use the helping procedures in $PUB/lib/statement-expression.scm in your solution. You can load these into your solution using: (require (lib "statement-expression.scm" "lib342")) These are needed to be sure your code is independent of the representation details of the statement-expression grammar. The representation used is not what you might think, so beware! Also be sure to use a helping procedure, such as subst-id-exp, in your solution so that your code follows the grammar. After doing your own testing you must test your code using: (test-hw4 "subst-identifier") 9. (50 points; extra credit) [def-before-use] This is a problem about the statement and expression grammar discussed in section 5.4 of the "Following the Grammar" handout. Write a procedure, def-before-use : (-> (statement) boolean) that checks whether each identifier in the argument is the target of a set-stmt before its value is ever used. For example, (def-before-use (parse-statement 'x)) ==> #f (def-before-use (parse-statement (begin (set! x 3) 'x))) ==> #t You have to figure out what the general form of this is for the statement grammar, and you'll have to make up your own tests. 10. (50 points) [mark-selected] This is a problem 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", and reproduced below: ::= (*TOP* {}* {}* ) "document (PIs comments element)" ::= ( {}* ) "named (name children)" | ( ( @ {}* ) "attributed (name attributes {}* ) children)" ::= ( ) "name-value (name value)" | ( ) "name-only (name)" ::= "child (element)" | "text (string)" | "child-pi (PI)" | "child-comment (comment)" | ( *ENTITY* ) "entity (public-id system-id)" ::= ( *PI* ) "PI (target content)" ::= ( *COMMENT* ) "comment (string)" This grammar handles all of XML, except for annotations (and hence namespace annotations). The comments at the right are an aid to remembering the names of the helping procedures. Note that and nonterminals have an extra set of convenience helpers that allow processing their alternatives in a uniform way. That is, these make it seem as if the grammar were: ::= ( ( @ {}* ) "element (name attributes {}* ) children)" ::= ( ) "attribute (name value)" The idea behind these extra helpers is given by the following equations (element sym attrs kids) = (if (null? attrs) (named sym kids) (attributed sym attrs kids)) (element->attributes (named sym kids)) = '() (attribute nm val) = (if (equal? val "") (name-only nm) (name-value nm val)) (attribute->value (name-only nm)) = "" The type predicates element? and attribute? should not be used in most programs, as they are slow. But they wouldn't be needed if you are imagining you are using grammar for and without alternatives. Look in the file $PUB/lib/sxml-helpers.scm for the types of the helpers. See $PUB/lib/sxml-helpers.tst for some examples. Normally XML is manipulated using a specialized query langauge, such as XPath, and there are implementations of this available with the SXML system. However, your task is to write, using the helpers in sxml-helpers.scm, a procedure: mark-selected : (-> (symbol document) document) such that (mark-selected nm doc) returns a document that is like doc, except that each element with name nm anywhere in doc is transformed by adding an additional attribute of the form (selected "true") to that element. You may assume that the attribute name "selected" does not occur anywhere in the document. 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 (mark-selected 'html (document '() '() (named 'html (list )))) ==> (*TOP* (html (@ (selected "true")))) (mark-selected 'body simpledoc) ==> (*TOP* (*PI* x86 "run; die") (*COMMENT* "those x86s...") (html (head (@ (title "Simple doc"))) (body (@ (selected "true")) (p "First paragraph.") (p "Second paragraph.")))) (mark-selected 'p simpledoc) ==> (*TOP* (*PI* x86 "run; die") (*COMMENT* "those x86s...") (html (head (@ (title "Simple doc"))) (body (p (@ (selected "true")) "First paragraph.") (p (@ (selected "true")) "Second paragraph.")))) (mark-selected 'head simpledoc) ==> (*TOP* (*PI* x86 "run; die") (*COMMENT* "those x86s...") (html (head (@ (selected "true") (title "Simple doc"))) (body (p "First paragraph.") (p "Second paragraph.")))) Note that Scheme systems often change all symbols to lower case, which affects the output. DrScheme has an option to preserve case. Although DrScheme does not do this, some Scheme systems also print the symbol @ as |@|. You must use the helping procedures in $PUB/lib/sxml-helpers.scm in your solution. You can load these into your solution using: (require (lib "sxml-helpers.scm" "lib342")) These are needed to be sure your code is independent of the representation details of SXML. They should also be something of a convenience. Be sure to use a helping procedures as necessary so that your code follows the grammar! After doing your own testing you must test your code using: (test-hw4 "mark-selected") 11. (40 points; extra credit) [XML I/O] DrScheme has the SSAX XML parser in PLT/collects/ssax/, where PLT is the directory into which DrScheme is installed. It is documented in the file doc.txt in that directory. Adapt your solution to the mark-selected problem above so that it reads a file from disk in XML's concrete syntax, uses SSAX to parse it into the internal data representation, calls mark-selected, and then outputs the data back into XML's concrete syntax into another file on disk. You'll have to read a lot of the documentation to figure out how all this works. 12. (70 points; extra credit) [only-selected] This is another problem XML data, using the grammar in the library file sxml-helpers.scm. Write, using the helpers in sxml-helpers.scm, a procedure: only-selected : (-> (document) document) such that (only-selected doc) returns a document that is like doc, except that the only s that are present in the result are those that were originally in doc and such that either: 1. The element has an attribute named "selected" with value "true", 2. The element has a descendant child element that meets condition 1, or 3. The element has a parent that meets condition 1. Furthermore, all attributes named "selected" with value "true" are deleted from the elements in the output, so that no such attributes appear in the output. You may assume that at least one element in doc has an attributes named "selected" with value "true", this avoids having to deal with empty documents as a result. Hint: you may need to code condition 2 as a separate helping procedure. It may also be helpful to perform the deletion of attributes named "selected" with value "true" in a second pass over the entire document. The following are examples. These use the definition of simpledoc given above in the mark-selected problem, and mark-selected, to cut down on the space needed to present the examples. (only-selected (document '() '() (attributed 'html (list (name-value 'selected "true")) (list )))) ==> (*TOP* (html)) (only-selected (document '() '() (named 'operas (list (child (attributed 'miestersinger (list (name-only 'funny) (name-value 'selected "true")) (list (text "Fanget an! ...")))) (entity "decca-52" "342d-dfaa:302") (child-pi (PI 'your-code "deletes the following")) (child (attributed 'boheme (list (name-only 'sad) (name-value 'setting "paris")) (list (text "Mimi coughed...")))) (child-comment (comment "That's an oversimplification")) (child (attributed 'lohengrin (list (name-only 'shining-armor) (name-value 'selected "true")) (list (text "When is the next swan? ...")))))))) ==> (*TOP* (operas (miestersinger (@ (funny)) "Fanget an! ...") (*ENTITY* "decca-52" "342d-dfaa:302") (*PI* your-code "deletes the following") (*COMMENT* "That's an oversimplification") (lohengrin (@ (shining-armor)) "When is the next swan? ..."))) (only-selected (mark-selected 'head simpledoc)) ==> (*TOP* (*PI* x86 "run; die") (*COMMENT* "those x86s...") (html (head (title "Simple doc")))) (only-selected (mark-selected 'body simpledoc)) ==> (*TOP* (*PI* x86 "run; die") (*COMMENT* "those x86s...") (html (body (p "First paragraph.") (p "Second paragraph.")))) (only-selected (mark-selected 'p simpledoc)) ==> (*TOP* (*PI* x86 "run; die") (*COMMENT* "those x86s...") (html (body (p "First paragraph.") (p "Second paragraph.")))) You must use the helping procedures in $PUB/lib/sxml-helpers.scm in your solution. You can load these into your solution using: (require (lib "sxml-helpers.scm" "lib342")) Be sure to use a helping procedures as necessary so that your code follows the grammar! After doing your own testing you must test your code using: (test-hw4 "only-selected") You don't need to have mark-selected working to do this problem; the tests don't rely on it. ESSENTIALS OF PROGRAMMING LANGUAGES, Section 1.2.3 STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS, Section 1.2.1 13. (15 points; extra credit) [prove partial-vector-sum correct] Do exercise 1.14 on p. 24 in the text. 14. (10 points) [vector-index] Write a procedure, vector-index, that takes a predicate, pred, and a vector, v, and returns the zero-based index of the first element of v that satisfies pred, or -1 if no element of v satisfies pred. The type of vector-index is thus as follows: (deftype vector-index (forall (T) (-> ((-> (T) boolean) (vector-of T)) number))) For example, (vector-index zero? '#(9 8 0 1 0 3 0)) ==> 2 (vector-index zero? '#(9 8 7 1 3)) ==> -1 (vector-index odd? '#()) ==> -1 (vector-index odd? '#(2 2 2 2 2 2 2 2 2 2 2 2 3 4 2)) ==> 12 You must use tail recursion, and without using Scheme's procedures vector->list or list->vector. After doing your own testing you must test your code as for problem 7 above. You can run our tests by typing to Scheme: (test-hw4 "vector-index") Be sure your name appears in a comment in your code (as in homework 0). 15. (15 points; extra credit) [vector-append-list] Do exercise 1.15 part 10 on p. 25 in the text, except that your code only has to work for vectors and lists of numbers. That is, the type of vector-append-list will be given by: (deftype vector-append-list (-> ((vector-of number) (list-of number)) (vector-of number))) You must use tail recursion on this problem. Hint: use make-vector with two arguments to make a vector whose length is the first argument, for example: (make-vector 7 0) ==> #(0 0 0 0 0 0 0). You will also need to use vector-set! 16. (suggested practice) Do exercise 1.17 on p. 27 in the text [path, sort]. 17. (15 points; extra credit) [car&cdr2] Do exercise 1.18 on p. 27 in the text, part 3