<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 5: RECURSION OVER DATA DESCRIBED BY GRAMMARS AND TAIL RECURSION

Due: by 2:00pm Thursday, Mar 5, 2009 in Computer Science Front Office;

In this homework, you will learn more about recursion over data
described by more complex grammars and about tail recursion.

PRELIMINARIES

1. Download, unzip and install the typedscm library from: 
http://www.cs.iastate.edu/~cs342/homework/typedscm.zip
in the collects directory of your PLT scheme installation.
As a result of this step you should have a directory 
collects/typedscm. To test if this has worked correctly 
type the following in your interpreter.
(require (lib "typedscm.ss" "typedscm"))

TypedSCM is a typed dialect for Scheme made available by 
Professor Gary T. Leavens from University of Central 
Florida and his students. More information about this 
dialect is available from the following web-page. 
http://www.eecs.ucf.edu/~leavens/typedscm/

2. Download and add the following modules to your lib342 
directory as instructed in HW1, question 4.
http://www.cs.iastate.edu/~cs342/homework/all-mod.scm
http://www.cs.iastate.edu/~cs342/homework/window-layout-mod.scm
http://www.cs.iastate.edu/~cs342/homework/bexp-mod.scm

INSTRUCTIONS

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 the examples that we provide as test cases.  For coding
problems hand in:

  - a printout of the code, and
  - if our examples 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 examples 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
examples, 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 examples if you wish.

The section headings below give the readings related to the problems.
(Please read them!)

ESSENTIALS OF PROGRAMMING LANGUAGES: SECTION 1.2
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.

------------------------------------------------------------------------
WINDOW LAYOUT 
------------------------------------------------------------------------
Suppose we want to descibe how windows are layed out in a window manager.
For the purposes of problems 1 and 2, we will use the following grammar
to describe these layouts.  Informally, a window-lay out is a window
or a horizontal layout of 0 or more window layouts or a verticle 
layout of of 0 or more window layouts. Window layouts follow the grammar
below:

<window-layout> ::=
		(window <symbol> <number> <number>)
	|	(horizontal {<window-layout>}*
	|	(verticle	{<window-layout>}*
	
Notice that this is a recursively defined grammar. We have provided a
representation of this data type in the file "window-layout-mod.scm"
which contains many helper procedures for processing layouts.

Useful helpers:
;; type predicate
( window-layout? (type-predicate-for window-layout))

;; case testers (discriminators)
( window? (-> (window-layout) boolean))
( horizontal? (-> (window-layout) boolean))
( vertical? (-> (window-layout) boolean))

;; constructors
( window (-> (symbol number number) window-layout))
( horizontal (-> ((list-of window-layout)) window-layout))
( vertical (-> ((list-of window-layout)) window-layout))

;; observers 
( window->name (-> (window-layout) symbol))
( window->width (-> (window-layout) number))
( window->height (-> (window-layout) number))
( horizontal->subwindows (-> (window-layout) (list-of window-layout)))
( vertical->subwindows (-> (window-layout) (list-of window-layout)))

1. (30 points) [smallest-width]

     smallest-width : (-> (window-layout) number)

   such that (smallest-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.

   (smallest-width (parse-window-layout '(horizontal )))
     ==> 0
   (smallest-width (parse-window-layout '(vertical )))
     ==> 0
   (smallest-width (parse-window-layout '(window simpsons 30 40)))
     ==> 30
   (smallest-width (parse-window-layout '(window family-guy 70 11)))
     ==> 70
   (smallest-width
      (parse-window-layout '(horizontal (window family-guy 30 15)
                                        (window futurama 89 55))))
     ==> 30
   (smallest-width
      (parse-window-layout
           '(vertical
              (vertical (window simpsons 200 150))
              (horizontal (horizontal (window news 50 5)))
              (horizontal (window family-guy 30 15)
                          (window futurama 89 55)))))
     ==> 30

   You must use the helping procedures in 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"))


2. (20 points) [grow-by]
   This is a problem about the window layouts discussed above.
   Write a procedure

     grow-by : (-> (number number window-layout) window-layout)

   such that (grow-bywidth 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.

   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
   window-layout-mod.scm work, in the examples below, we often
   use the helping procedures directly to construct window layouts.

   (grow-by 10 39 (parse-window-layout '(vertical )))
     ==> (vertical)
   (grow-by 10 39 (parse-window-layout '(horizontal )))
     ==> (horizontal)
   (grow-by 10 39 (parse-window-layout '(window simpsons 30 40)))
     ==> (window simpsons 40 79)
   (grow-by 80 5 (window 'family-guy 30 11))
     ==> (window family-guy 110 16)
   (grow-by 20 30 (horizontal
                       (list (window 'family-guy 30 15)
                             (window 'futurama 89 55))))
     ==> (horizontal (window family-guy 50 45) 
					 (window futurama 109 85))
   (grow-by 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 220 180))
				(horizontal (horizontal (window news 25 35)))
				(horizontal (window family-guy 50 45) (window futurama 109 85)))

   You must use the helping procedures in window-layout-mod.scm
   in your solution.  You can load these into your solution using:

         (require (lib "window-layout-mod.scm" "lib342"))

------------------------------------------------------------------------
BOOLEAN EXPRESSIONS
------------------------------------------------------------------------
Let the following be the grammar that describes boolean expressions and 
operators for those expressions. 

<bexp> ::=	<varref>
		|	(and <bexp> <bexp>)
		|	(or <bexp> <bexp>)
		|	(not <bexp>)
<varref> ::=	  P 
                | Q

Note: the varref used (P or Q) will affect how the boolean expression is 
evaluated. We have provided a representation of this data type in the 
file "bexp-mod.scm" which contains many helper procedures for processing 
boolean expressions and operators.
		
Useful Helpers:

;; type predicate
( bexp? (type-predicate-for bexp))
( varref? (type-predicate-for varref))

;; case testers (discriminators)
( var-exp? (-> (bexp) boolean))
( and-exp? (-> (bexp) boolean))
( or-exp? (-> (bexp) boolean))
( not-exp? (-> (bexp) boolean))
( P? (-> (varref) boolean))
( Q? (-> (varref) boolean))

;; constructors
( var-exp (-> (varref) bexp))
( and-exp (-> (bexp bexp) bexp))
( or-exp (-> (bexp bexp) bexp))
( not-exp (-> (bexp) bexp))
( P (-> () varref))
( Q (-> () varref))

;; observers 
( var-exp->varref (-> (bexp) varref))
( and-exp->left (-> (bexp) bexp))
( and-exp->right (-> (bexp) bexp))
( or-exp->left (-> (bexp) bexp))
( or-exp->right (-> (bexp) bexp))
( not-exp->arg (-> (bexp) bexp))
		
3. (20 points) [beval]
   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 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.