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 and 6 at beginning of class, October 3, 2006; problems 8-10 at beginning of class, October 10, 2006. 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. ::= "var-exp (id)" | (quote ) "quote-exp (symbol)" | ( lambda ( ) ) "lambda-exp (id body)" | ( ) "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 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 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". ::= "var-exp (id)" | (quote ) "quote-exp (symbol)" | ( lambda ( {}* ) ) "lambda-exp (ids body)" | ( if "if-exp (test-exp true-exp ) false-exp)" | ( {}* ) "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 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: ::= "la:var-exp (lexical-addr)" | (quote ) "la:quote-exp (symbol)" | ( lambda ( {}* ) "la:lambda-exp (ids ) body)" | ( if "la:if-exp (test-exp true-exp ) false-exp)" | ( "la:app-exp (rator {}* ) rands)" ::= ( : ) Helpers for this grammar are found in the file $PUB/lib342/lexical-addr-exp-mod.scm which uses and exports the helpers for the 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...)