<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: STATIC PROPERTIES OF VARIABLES
                 (File $Date: 2006/11/13 22:08:55 $)

Due: problems 1-3, 6, 8-10 at beginning of class, Thursday March 13, 2008;

In this homework, you will review a bit about recursion over grammars
while you learn important programming language concepts relating to
static properties of variables.

Please remember to work systematically, using the "Following the
Grammar" tips given in class for working these kinds of problems.
In the past, students have made life harder for themselves
by not doing this, which makes the problems harder than they are.
Also, don't make the problems harder by coding for
examples which are not in the relevant language's grammar.
We provide a parser for the relevant grammar, which we apply to the test
cases to do the relevant error checking.  Hence, you don't have to
worry about the error checking.  However, you cannot use the parse-X
procedures in your solution code.

For coding problems, code is to be written in Scheme, using the exact
procedure names specified in the problem descriptions.

To better practice for tests, we suggest that you first write out by
hand a solution to each problem on paper, as if taking a test, and 
only then type in your solution to the computer.  However, you should
hand in just a printout of the code.  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.

See the directory $PUB/homework/hw5 for test data for each coding
problem.  (You can use the procedure test-hw5 to run our tests, as
described in homework 1.)  

The section headings below give the readings related to the problems.
(Please read them!)


ESSENTIALS OF PROGRAMMING LANGUAGES: Start of 1.3 to the end of 1.3.1

In addition to the sections of the book described in the heading above,
please also read the file $PUB/lib342/lambda-1-quote-exp-examples.scm
closely, which illustrates by example the grammar and helping procedures
for this set of problems.  See also $PUB/lib342/lambda-1-quote-exp-examples.tst
for test cases for those examples.  Pay particular attention to the
subst-var-exps example, as that illustrates the most general case.

The language lambda-1-quote-exp, used in the first three problems
below, is defined by the following grammar.  In this language,
quotation for symbols means the same thing as in Scheme.  In
particular, note that quoting a name produces a symbol, and is not a
var-exp.  Hence (quote x) does not constitute use a variable x.

The grammar comments enclosed in quotes to the right of the grammar below
tell you information about the name of the production and the names of
its "fields".  For example, the first production is named "var-exp"
and has one field named "id".  These names determine the names of the
helping procedures.  For example, as indicated next to the first
production, there is a predicate named var-exp?, a constructor
var-exp, and an observer var-exp->id.

     <expression> ::=
          <identifier>                               "var-exp (id)"
        | (quote <identifier>)                       "quote-exp (symbol)"
        | ( lambda ( <identifier> ) <expression> )   "lambda-exp (id body)"
        | ( <expression> <expression> )              "app-exp (rator rand)"

We have provided you with helping procedures in the following file.
   $PUB/lib342/lambda-1-quote-exp.scm

1. (10 points total) [lambda-helpers]
   Use the file lambda-1-quote-exp.scm from the library by typing:

        (require (lib "lambda-1-quote-exp.scm" "lib342"))

a. (5 points) Without using parse-expression, make a transcript that
   shows how you use the (other) helping procedures defined in
   lambda-1-quote-exp.scm, to build the following expressions:
   (If you use "define" to bind them to names, that will help in part b.)

        y

        (y (quote z))

        (g y)

        (lambda (y) (g y))

        ((lambda (y) (g y)) (quote y))

   All of these should have the type lambda-1-quote-exp.

   Note: when Scheme prints (quote x), it prints it as 'x; you can also type
   (quote y) in as 'y in test cases if you wish.  But watch out:
   as ''y ==> (quote y) prints as 'y, but 'y ==> y.

b. (5 points) Using the helping procedures in lambda-1-quote-exp.scm, and
   names you defined in part (a), make a transcript that shows an
   expression that returns the var-exp y from each of the 5
   expressions in part a.

2. For this problem, a ``lambda calculus expression'',
   means an <expression> in the language lambda-1-quote-exp.

a. (5 points)
   Consider again each of the expressions in problem 1, part (a)
   above.  As a warmup for the free-vars problem in part b below, give
   the complete set of free variables for each of these expressions. 
   (See section 1.3.1 of the textbook.)

b. (15 points) [free-vars]
   Write a procedure,

        free-vars : (-> (lambda-1-quote-exp) (set-of symbol))

   that takes a lambda calculus expression, expr, and returns the set of the
   symbols that occur free in expr.  (See the book for the definition of
   ``occurs free.'')

   To work with sets, you should put (require "set-ops.scm") in your
   solution, assuming that "set-ops.scm" is a path to your solution to
   the set-ops problem from homework 3.  If you didn't get a working
   solution from homework 3, use "set-ops-as-vector.scm" from
   the course library, by writing:

      (require (lib "set-ops-as-vector.scm" "lib342"))

   in your code instead of a require of of your own "set-ops.scm" file.

   Your code should satisfy the following equations between sets,
   (where set is as in homework 3, that is, (set 'x 'y) means
   the set containing the symbols x and y).

   (free-vars (parse-expression 'x)) = (set 'x)
   (free-vars (parse-expression 'z)) = (set 'z)
   (free-vars (parse-expression '(quote z))) = the-empty-set
   (free-vars (parse-expression '(x (x y)))) = (set 'x 'y)
   (free-vars (parse-expression '(x (f (quote y))))) = (set 'x 'f)
   (free-vars (parse-expression '(lambda (x) (x (x y))))) = (set 'y)
   (free-vars (parse-expression '(x (lambda (x) (x (x y))))))
      = (set 'x 'y)
   (free-vars (parse-expression '((lambda (y) y) (lambda (x) (y x)))))
      = (set 'y)

   To receive full credit your procedure must follow the
   lambda-1-quote-exp grammar and it must use the helping procedures
   for the grammar In particular it should only be called recursively
   with arguments that are in the above grammar (note that empty lists
   are not in the grammar).  You should use the helping procedures in
   the file $PUB/lib342/lambda-1-quote-exp.scm.  To do this, put

        (require (lib "lambda-1-quote-exp.scm" "lib342"))

   at the top of your file.

   Warning: do not try to flatten the lambda calculus expressions into a list,
   since that will make your solution wrong!  (See the last example above.)

   For this and all succeeding problems, we suggest that you write out
   a solution by hand first, and then type in your code to the
   computer.  Please try testing your code by hand first, so you are
   in control of the testing process.  After you debug this way, then
   try using our test cases by typing.

        (test-hw5 "free-vars")

   Remember, for this and all of the following coding problems, you
   must hand in: a printout of your code and, if your some tests do
   not pass, a transcript showing testing using our test data.

   Note: when Scheme prints (quote x), it prints it as 'x; you can also type
   (quote y) in as 'y in test cases if you wish.  But watch out:
   as ''y ==> (quote y) which prints as 'y, but 'y ==> y.

c. (5 points) [free?]
   Write a procedure,

        free? : (-> (symbol lambda-1-quote-exp) boolean)

   that takes a symbol, s, and a lambda calculus expression, expr,
   and returns #t just when s occurs free in expr.

   Your code should satisfy the following equations.

   (free? 'x (var-exp 'x)) = #t
   (free? 'x (quote-exp 'x)) = #f
   (free? 'z (parse-expression 'y)) = #f
   (free? 'x (parse-expression '(x (x y)))) = #t
   (free? 'y (parse-expression '(x (x y)))) = #t
   (free? 'y (parse-expression '(x (x (quote y))))) = #f
   (free? 'a (parse-expression '(x (x y)))) = #f
   (free? 'x (parse-expression '(lambda (x) (x (x y))))) = #f
   (free? 'y (parse-expression '(lambda (x) (x (x y))))) = #t
   (free? 'x (parse-expression '(x (lambda (x) (x (x y)))))) = #t

   After doing your own testing, you can use our tests by typing:

        (test-hw5 "free")

3. For this problem, a lambda calculus expression
   means an <expression> in the language lambda-1-quote-exp.

a. (5 points)
   Consider again each of the expressions in problem 1, part (a)
   above.  As a warmup for the bound-vars problem in part b below, give
   the complete set of bound variables for each of these expressions. 
   (See section 1.3.1 of the textbook.)

b. (15 points) [bound-vars]
   Write a procedure,

        bound-vars : (-> (lambda-1-quote-exp) (set-of symbol))

   that takes a lambda calculus expression, expr, and returns the set of the
   symbols that occur bound in expr.  (See the book for the definition of
   ``occurs bound.'')

   Again, use your set-ops.scm file, as in the previous problem to work
   with sets.  And use the file $PUB/lib342/lambda-1-quote-exp.scm for helping
   functions.  (Hint: use free-vars too!)

   (bound-vars (parse-expression 'x)) = the-empty-set
   (bound-vars (parse-expression '(quote z))) = the-empty-set
   (bound-vars (parse-expression '(x (x y)))) = the-empty-set
   (bound-vars (parse-expression '(lambda (x) (x (x y)))))
     = (set 'x)
   (bound-vars (parse-expression '(lambda (y) x)))
     = the-empty-set
   (bound-vars (parse-expression '(lambda (y) (quote y))))
     = the-empty-set
   (bound-vars (parse-expression '(x (lambda (x) (x (x y))))))
     = (set 'x)

   To receive full credit your procedure must follow the grammar
   for lambda-1-quote-exp.   It will have little chance of being
   correct if you don't! 

   After doing your own testing, you can use our tests by typing:

        (test-hw5 "bound-vars")

c. (5 points) [bound?]
   Write a procedure,

        bound? : (-> (symbol lambda-1-quote-exp) boolean)

   that takes a symbol, s, and a lambda calculus expression, expr,
   and returns #t just when s occurs bound in expr.

   Your code should satisfy the following equations.

   (bound? 'x (parse-expression 'x)) = #f
   (bound? 'z (parse-expression 'y)) = #f
   (bound? 'z (parse-expression '(quote z))) = #f
   (bound? 'x (parse-expression '(x (x y)))) = #f
   (bound? 'y (parse-expression '(x (x y)))) = #f
   (bound? 'a (parse-expression '(x (x y)))) = #f
   (bound? 'x (parse-expression '(lambda (x) (x (x y))))) = #t
   (bound? 'x (parse-expression '(lambda (x) (quote x)))) = #f
   (bound? 'y (parse-expression '(lambda (x) (x (x y))))) = #f
   (bound? 'x (parse-expression '(x (lambda (x) (x (x y)))))) = #t

   For testing this problem, you can use

        (test-hw5 "bound")

4. (10 points, extra credit)
   Do exercise 1.20 on p. 31 in the text.

5. (suggested practice)
   Do exercise 1.21 on p. 31 in the text.

6. (40 points)  [free-vars and bound-vars for lambda-if-exp]
   The language lambda-if-exp, used in this problem, adds
   if-expressions, which have the same meaning as in Scheme.  It is
   defined by the following grammar.  The grammar comments enclosed in
   quotes to the right of the grammar tell you information about the
   name of the production and the names of its "fields".

      <expression> ::=
           <identifier>                                "var-exp (id)"
         | (quote <identifier>)                        "quote-exp (symbol)"
         | ( lambda ( {<identifier>}* ) <expression> ) "lambda-exp (ids body)"
         | ( if <expression>                           "if-exp (test-exp
                <expression>                                    true-exp
                <expression> )                                  false-exp)"
         | ( <expression> {<expression>}* )            "app-exp (rator rands)"

   For this problem, you should write two procedures that compute the sets
   of free and bound variables for the above grammar:

a.      (deftype free-vars (-> (expression) (set-of symbol)))
b.      (deftype bound-vars (-> (expression) (set-of symbol)))

   Use the file $PUB/lib342/lambda-if-exp.scm for helping procedures
   for this grammar.    See the file $PUB/lib342/lambda-if-exp-examples.scm
   for examples using these, and $PUB/lib342/lambda-if-exp-examples.tst
   for test cases for the examples.

   Again, require your set-ops.scm file, to work with sets, or use our
   $PUB/lib342/set-ops-as-vector.scm file

   To receive full credit, your code for free-vars and bound-vars must
   use the helping procedures and follow the grammar.  Beware that our
   test cases may not ensure that your code is perfect: you must be
   sure to recurse in every place the grammar recurses yourself.

   For testing this problem, you can use

        (test-hw5 "free-vars-lambda-if-exp")
        (test-hw5 "bound-vars-lambda-if-exp")


ESSENTIALS OF PROGRAMMING LANGUAGES: Section 1.3.2

7. (suggested practice)  [scoping]
   Do exercises 1.27 and 1.28 on pp. 34-35 in the text.

8. (5 points) [lexical address idea]
   Do exercise 1.29 on p. 36 in the text.

9. (5 points) [lexical address idea]
   Do exercise 1.30 on p. 36 in the text.

10. (50 points)  [lexical-address]
   (This is similar to, but different than, exercise 1.31 on p. 37 in
   the text. We treat free variables differently and in addition treat quoted
   data.) Write the procedure, lexical-address, whose type is given by

        (deftype lexical-address (-> (expression) lexical-addr-exp))

   where lambda-if-exp is the type of <expression>s specified by the grammar
   in $PUB/lib342/lambda-if-exp.scm, and lexical-addr-exp is the type of data
   defined by the following grammar:

      <lexical-addr-exp> ::=
           <lexical-addr>                           "la:var-exp (lexical-addr)"
         | (quote <identifier>)                     "la:quote-exp (symbol)"
         | ( lambda ( {<identifier>}* )             "la:lambda-exp (ids
               <lexical-addr-exp> )                                 body)"
         | ( if <lexical-addr-exp>                  "la:if-exp (test-exp
                <lexical-addr-exp>                              true-exp
                <lexical-addr-exp> )                            false-exp)"
         | ( <lexical-addr-exp>                     "la:app-exp (rator
             {<lexical-addr-exp>}* )                             rands)"

      <lexical-addr> ::= ( <symbol> : <number> <number> )

   Helpers for this grammar are found in the file
   $PUB/lib342/lexical-addr-exp-mod.scm which uses and exports the
   helpers for the <lexical-addr> grammar in
   $PUB/lib342/lexical-addr-mod.scm.  Note that the helpers for
   lexical-addr-exp all have "la:" prefixed to their names, so that
   you can distinguish them from the helpers for lambda-if-exp.

   For example:

      (lexical-address (var-exp 'car))
        = (la:var-exp (lexical-addr 'car 0 0)) 

      (lexical-address (quote-exp 'car))
        = (la:quote-exp 'car) 

      (lexical-address
         (lambda-exp '(f) (app-exp (var-exp 'f)
                                   (list (quote-exp 'car)))))
        = (la:lambda-exp '(f) (la:app-exp (la:var-exp (lexical-addr 'f 0 0))
                                          (list (la:quote-exp 'car)))) 

      (lexical-address (var-exp 't))
        = (la:var-exp (lexical-addr 't 0 0)) 

      (lexical-address
         (lambda-exp
          '(car ls)
          (app-exp (var-exp 'car)
                   (list (var-exp 'ls)))))
        = (la:lambda-exp
           '(car ls)
           (la:app-exp (la:var-exp (lexical-addr 'car 0 0))
                       (list (la:var-exp (lexical-addr 'ls 0 1))))) 

      (lexical-address
         (lambda-exp
          '(ls car)
          (app-exp (var-exp 'car)
                   (list (var-exp 'ls)))))
        = (la:lambda-exp
           '(ls car)
           (la:app-exp (la:var-exp (lexical-addr 'car 0 1))
                       (list (la:var-exp (lexical-addr 'ls 0 0))))) 

      (lexical-address
         (lambda-exp
          '(ls car)
          (app-exp (var-exp 'ls) (list))))
        = (la:lambda-exp
           '(ls car)
           (la:app-exp (la:var-exp (lexical-addr 'ls 0 0)) (list)))

      (lexical-address
         (parse-expression
                         '(lambda (x) (if p (f x g) (f y h)))))
        = (parse-lexical-addr-exp
                         '(lambda (x) (if (p : 1 0)      ;; see note (*) below
                                          ((f : 1 2) (x : 0 0) (g : 1 1))
                                          ((f : 1 2) (y : 1 3) (h : 1 4))))

      (lexical-address
          (parse-expression
               '(x
                 (lambda (z f)
                   (x z f
                      (lambda (q r)
                        (x z f q r))))
                 (lambda (f z)
                   (x z f
                      (lambda (r q)
                        (x z f q r)))))))
        = (parse-lexical-addr-exp
            '((x : 0 0)
              (lambda (z f)
                ((x: 1 0) (z : 0 0) (f : 0 1)
                 (lambda (q r)
                   ((x : 2 0) (z : 1 0) (f : 1 1)
                    (q : 0 0) (r : 0 1)))))
              (lambda (f z)
                ((x: 1 0) (z : 0 1) (f : 0 0)
                 (lambda (r q)
                   ((x : 2 0) (z : 1 1) (f : 1 0)
                    (q : 0 1) (r : 0 0))))))

   (*) Note that, for an expression with free variables, the position number
   of the lexical address of free variables is left up to your implementation.
   That is any assignment of position numbers to free variables is okay,
   as long as they are all different.  For example,
   both of the following are correct:

        (lexical-address (parse-expression '(car ls))
           = (parse-lexical-addr-exp '((car : 0 0) (ls : 0 1)))
        (lexical-address (parse-expression '(car ls))
           = (parse-lexical-addr-exp '((car : 0 1) (ls : 0 0)))

   It is important to plan your solution carefully, as this problem
   always gives some students trouble.  Think about the tips for
   writing recursions over grammars carefully.  Which one is the input
   grammar?  As an additional aid, start by copying the file
   $PUB/homework/hw5/lexical-address.scm to your directory, which
   is a file of hints, and contains an basic outline of the code you
   can use.

   Full credit will only be given for solutions that properly use the
   helping procedures and follow the grammar.  Don't directly treat
   sets or expressions according to their representations, as we will
   deduct points for that.  To help ensure you conform to proper use
   of the helping procedures, we strongly recommend using the type
   checker.

   For testing this problem, you can use
   
        (test-hw5 "lexical-address")
   
   When you print your code, you can remove all (or most) of the hints
   in the comments we gave you in lexical-address.scm.  This will help
   save some paper.  Be sure to put your name in the file.

11. (60 points, extra credit)   [un-lexical-address]
   Do exercise 1.32 on p. 37 in the text.

12. (100 points, extra credit) [inheritance]
   Isn't it a pain to have to duplicate code when changing your free-vars
   to work on a different grammar?  As an object-oriented programmer
   this will look to you like a job for inheritance, especially if you
   remember that a procedure in Scheme is like an object in an OO
   language.  To make things clearer, rename the procedures in the
   above problem to be free-vars-lambda-if-exp and bound-vars-lambda-if-exp.
   Now, you might try, for example, having free-vars-lambda-if-exp call
   free-vars on the lambda-1-quote grammar to do part of its work; but
   you'll find that the recursions in free-vars point to free-vars
   instead of free-vars-lambda-if-exp. 
   However, the problem with the recursion can be solved by thinking of it
   as a changing part.  If you do that, then the next step is obvious:
   abstract it!  So you'd write free-vars as follows.

   (deftype free-vars-gen
      (forall (T)
        (-> ((-> (T) (set-of symbol))) (-> (T) (set-of symbol)))))
   (define free-vars-gen
     (lambda (recur)
       (lambda (exp)
         ... code for free-vars, except that recur replaces free-vars ...)))

   Use this idea to write free-vars and free-vars-lambda-if-exp so that
   you can reuse the code you've written (in this new style)
   without editing it to make extended versions.  

   (Note: this is essentially the semantics of inheritance in OO programs!
    It looks harder than it is.  Just try it...)