<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
          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, 7-8 at the beginning of class Tuesday, February 26, 2008;
     problems 10, 14 at the beginning of class Thursday, February 28, 2008.

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: 

    <document> ::=
       (*TOP* {<PI>}* {<comment>}* <element>) "document (PIs comments element)"
    <element> ::=
       ( <symbol> {<child-of-element>}* )  "named (name children)"
     | ( <symbol> ( @ {<attribute>}* )     "attributed (name attributes 
                  {<child-of-element>}* )               children)"
    <attribute> ::=
       ( <symbol> <string> )               "name-value (name value)"
     | ( <symbol> )                        "name-only (name)"
    <child-of-element> ::=
       <element>                           "child (element)"
     | <string>                            "text (string)"
     | <PI>                                "child-pi (PI)"
     | <comment>                           "child-comment (comment)"
     | ( *ENTITY* <string> <string> )      "entity (public-id system-id)"
    <PI> ::=
      ( *PI* <symbol> <string> )           "PI (target content)"
    <comment> ::=
      ( *COMMENT* <string> )               "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 <element> and <attribute> 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> ::=
       ( <symbol> ( @ {<attribute>}* )      "element (name attributes
                   {<child-of-element>}* )            children)"
     <attribute> ::=
       ( <symbol> <string> )                "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 <element> and <attribute>
   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 <element>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