Com S 342 --- Principles of Programming Languages HOMEWORK 2: STATIC PROPERTIES OF VARIABLES (File $Date: 1998/10/01 19:29:12 $) Due: problems 1,2,3,6,9,10 at beginning of class, October 2; problem 11 at beginning of class, October 5; In this homework, you will learn more about recursion over grammars, and the important concepts of static properties of variables. In terms of learning about recursion, we aim to ensure that you don't think that all recursions are recursions over flat lists. To that end you will work with variants of the lambda calculus, which are abstractions of functions, naming, and application in programming languages. Please remember the tips given in class for working these kinds of problems. In the past, students have made life harder for themselves by making the problems harder than they are. The way they made things harder was by not following the relevant grammar for the problem, which led to confusion and several extra cases that didn't need to be handled. Please don't make that mistake. That is, don't code for examples which are not in the relevant language's grammar. We provide a parser for the relevant grammar, which will do error checking. As we discussed in class, think about the following questions/tips for full recursion (which should be your default in this homework): (a) Are there examples needed? Write out related simpler examples. (b) What is the type? (c) What is the input grammar? This gives you the outline for the procedure(s) (as in class). (d) Use only one kind of recursion per procedure. (e) Do the same thing for each helping procedure. For coding problems, code is to be written in Scheme, using the exact procedure names specified in the problem descriptions. For code, hand in *both* your printout of the code and an unedited transcript of testing. See the directory $PUB/data/hw2/hw2.tst for test data for each coding problem. (You can use the procedure test-hw2 to run our tests, as described in homework 1. Recall that $PUB means /home/course/cs342/public.) The section headings below give the readings related to the problems. (Please read them!) ESSENTIALS OF PROGRAMMING LANGUAGES: Section 2.3.1 In addition to the section of the book named above, please also read the file $PUB/lib/lambda-1+quote-examples.scm closely, which illustrates by example the grammar and helping procedures for this set of problems. See also $PUB/lib/lambda-1+quote-examples.tst for test cases for those examples. Pay particular attention to the subst-varrefs example, as that illustrates the most general case. The language lambda-1+quote, used in the first three problems below, is defined by the following grammar. (In this langauge, quotation for symbols means the same thing as in Scheme.) ::= | ( quote ) | ( lambda ( ) ) | ( ) ::= ::= We have provided you with helping procedures in the following file. $PUB/lib/lambda-1+quote.scm These are designed to work with our type checker, so you should use the type-checked interpreter for these problems. (If you are using your home computer, when you download that file, be sure to also download the file $PUB/lib/lambda-1+quote.def.) 1. (10 points total) [lambda-helpers] Load the file lambda-1+quote.scm from the library by typing: (load-from-lib "lambda-1+quote.scm") a. (5 points) Without using parse-lambda-1+quote, make a trasnscript that shows how you use the other helping procedures defined in lambda-1+quote.scm, to build the following expressions: x (x (quote y)) (f x) (lambda (x) (f x)) ((lambda (x) (f x)) (quote x)) Hint: use Scheme's define special form, to help in the next part. All of these should have the type lambda-1+quote-exp. b. (5 points) Using the helping procedures in lambda-1+quote.scm, make a transcript that shows how to extract the x from each of the 5 expressions in part a. 2. For this problem, a lambda calculus expression, means a in the language lambda-1+quote. a. (15 points) [free-vars] Write a procedure, free-vars : (-> (lambda-1+quote-exp) (set 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 use your set-ops.scm file from homework 1. To make the type checker work with sets abstractly, you'll need to copy the file $PUB/lib/set-ops.def to the same directory where you keep your set-ops.scm file. You should also add the code in $PUB/lib/set-ops-missing.scm to your set-ops.scm file; this file contains two operations we did not provide or ask you to write in homework 1. (If you didn't get problem 7 of homework 1 working, email us for a working solution.) Your code should satisfy the equations between sets, (where set-of is as in homework 1, that is, (set-of 'x 'y) means the set containing the symbols x and y). (free-vars (parse-lambda-1+quote 'x)) = (set-of 'x) (free-vars (parse-lambda-1+quote 'z)) = (set-of 'z) (free-vars (parse-lambda-1+quote '(quote z))) = the-empty-set (free-vars (parse-lambda-1+quote '(x (x y)))) = (set-of 'x 'y) (free-vars (parse-lambda-1+quote '(x (f (quote y))))) = (set-of 'x 'f) (free-vars (parse-lambda-1+quote '(lambda (x) (x (x y))))) = (set-of 'y) (free-vars (parse-lambda-1+quote '(x (lambda (x) (x (x y)))))) = (set-of 'x 'y) (free-vars (parse-lambda-1+quote '((lambda (y) y) (lambda (x) (y x))))) = (set-of 'y) To receive full credit your procedure must follow the lambda-1+quote grammar and it must type check. In particular it should only be called recursively with arguments that are in the above grammar (e.g., empty lists are not in the grammar). If your code passes the type checker, this will be assured. You should use the helping procedures in the file $PUB/lib/lambda-1+quote.scm to make sure the type checker can do its job. To do this, put (load-from-lib "lambda-1+quote.scm") 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.) 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-hw2 "free-vars") Remember, for all coding problems, you must hand in 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. b. (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 (make-varref 'x)) = #t (free? 'x (make-quote 'x)) = #f (free? 'z (parse-lambda-1+quote 'y)) = #f (free? 'x (parse-lambda-1+quote '(x (x y)))) = #t (free? 'y (parse-lambda-1+quote '(x (x y)))) = #t (free? 'y (parse-lambda-1+quote '(x (x (quote y))))) = #f (free? 'a (parse-lambda-1+quote '(x (x y)))) = #f (free? 'x (parse-lambda-1+quote '(lambda (x) (x (x y))))) = #f (free? 'y (parse-lambda-1+quote '(lambda (x) (x (x y))))) = #t (free? 'x (parse-lambda-1+quote '(x (lambda (x) (x (x y)))))) = #t After doing your own testing, you can use our tests by typing: (test-hw2 "free?") 3. For this problem, a lambda calculus expression means an in the language lambda-1+quote. a. (15 points) [bound-vars] Write a procedure, bound-vars : (-> (lambda-1+quote-exp) (set 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/lib/lambda-1+quote.scm for helping functions that work with the type checker. (Hint: use free-vars too!) See problem 1 for more information. (bound-vars (parse-lambda-1+quote 'x)) = the-empty-set (bound-vars (parse-lambda-1+quote '(quote z))) = the-empty-set (bound-vars (parse-lambda-1+quote '(x (x y)))) = the-empty-set (bound-vars (parse-lambda-1+quote '(lambda (x) (x (x y))))) = (set-of 'x) (bound-vars (parse-lambda-1+quote '(lambda (y) x))) = the-empty-set (bound-vars (parse-lambda-1+quote '(lambda (y) (quote y)))) = the-empty-set (bound-vars (parse-lambda-1+quote '(x (lambda (x) (x (x y)))))) = (set-of 'x) To receive full credit your procedure must follow the grammar for lambda-1+quote and it must type check. 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-hw2 "bound-vars") b. (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-lambda-1+quote 'x)) = #f (bound? 'z (parse-lambda-1+quote 'y)) = #f (bound? 'x (parse-lambda-1+quote '(x (x y)))) = #f (bound? 'y (parse-lambda-1+quote '(x (x y)))) = #f (bound? 'a (parse-lambda-1+quote '(x (x y)))) = #f (bound? 'x (parse-lambda-1+quote '(lambda (x) (x (x y))))) = #t (bound? 'y (parse-lambda-1+quote '(lambda (x) (x (x y))))) = #f (bound? 'x (parse-lambda-1+quote '(x (lambda (x) (x (x y)))))) = #t For testing this problem, you can use (test-hw2 "bound?") 4. (suggested practice) Do exercise 2.3.3 in the text. 5. (10 points, extra credit) Do exercise 2.3.4 in the text. 6. (40 points) [free-vars-lcm+if, bound-vars-lcm+if] The language lcm+if-exp, used in this problem, is defined by the following grammar. ::= | ( quote ) | ( lambda ( {}* ) ) | ( if ) | ( {}* ) ::= ::= For this problem, you should write two procedures that compute the sets of free and bound variables for the above grammar: a. free-vars-lcm+if : (-> (lcm+if-exp) (set symbol)) b. bound-vars-lcm+if : (-> (lcm+if-exp) (set symbol)) Use the file $PUB/lib/lambda-multiple+if.scm for helping procedures for this grammar that work with the type checker. See the file $PUB/lib/lambda-multiple+if-examples.scm for examples using these, and $PUB/lib/lambda-multiple+if-examples.tst for test cases for the examples. Again, use your set-ops.scm file, to work with sets. To receive full credit, your code for free-vars+lcm+if bound-vars-lcm+if must type check 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-hw2 "free-vars-lcm+if") (test-hw2 "bound-vars-lcm+if") 7. (100 points, extra credit) [inheritance] Isn't it a pain to have to duplicate code when changing your free-vars to free-vars+multiple and free-vars+if? 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. Well, you might try, for example, having free-vars+multiple call free-vars to do part of its work; but you'll find that the recursions in free-vars point to free-vars instead of free-vars+multiple. Renaming doesn't help, since you need the two pieces of code. But 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. (define free-vars ; TYPE: (-> ((-> (lambda-1+quote-exp) (set varref))) ; (-> (lambda-1+quote-exp) (set varref))) (lambda (recur) (lambda (exp) ... code for free-vars, except that recur replaces free-vars ...))) Use this idea to write free-vars and free-vars-lcm+if 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!) ESSENTIALS OF PROGRAMMING LANGUAGES: Section 2.3.2 8. (suggested practice) [scoping] Do exercises 2.3.8 and 2.3.9 in the text. 9. (5 points) [lexical address idea] Do exercise 2.3.11 in the text. (This can be handwritten.) 10. (5 points) [lexical address idea] Do exercise 2.3.12 in the text. (This can be handwritten.) 11. (45 points) [lexical-address] Do exercise 2.3.10 in the text. The type of lexical-address is (-> (lcm+if-exp) lexical-addr-exp) where lcm+if-exp is the type of data specified by the grammar for problem 6 above, and lexical-addr-exp is the type of data defined by the following grammar: ::= | (quote ) | (if ) | (lambda ({}*) ) | ( {}*) ::= ( : ) ::= Helpers for this grammar are found in the file $PUB/lib/lexical-addr-exp.scm and for the grammar in $PUB/lib/lexical-addr.scm. (If you are working from home, also take the .def files.) For example: (lexical-address (parse-lcm+if 'car)) ==> (car : 0 0) (lexical-address (parse-lcm+if 't)) ==> (t : 0 0) (lexical-address (parse-lcm+if '(car ls))) ==> ((car : 0 0) (ls : 0 1)) ;; see note (*) below (lexical-address (parse-lcm+if '(if t (car ls) ls))) ==> (if (t : 0 0) ((car : 0 1) (ls : 0 2)) (ls : 0 2)) (lexical-address (parse-lcm+if '(lambda (car ls) (car ls)))) ==> (lambda (car ls) ((car : 0 0) (ls : 0 1))) (lexical-address (parse-lcm+if '(lambda (ls car) (car ls)))) ==> (lambda (ls car) ((car : 0 1) (ls : 0 0))) (lexical-address (parse-lcm+if '(lambda (ls car) (ls)))) ==> (lambda (ls car) ((ls : 0 0))) (lexical-address (parse-lcm+if '(lambda (x) (if p (f x g) (f y h))))) ==> (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-lcm+if '(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))))))) ==> ((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-lcm+if '(car ls)) ==> ((car : 0 0) (ls : 0 1)) (lexical-address (parse-lcm+if '(car ls)) ==> ((car : 0 1) (ls : 0 0)) We will discuss this problem in discussion sections. It is important to plan your solution carefully, and/or to attend the discussion section, as this problem always gives students a lot of trouble. Think about the tips for writing recursions over grammars carefully. Full credit will only be given for solutions that type check and follow the grammar. For testing this problem, you can use (test-hw2 "lexical-address") 12. (60 points, extra credit) [un-lexical-address] Do exercise 2.3.13 in the text. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 2.3.3 13. (20 points, extra credit) [rename] Do exercise 2.3.14 in the text. 14. (20 points, extra credit) [alpha-convert] Do exercise 2.3.15 in the text. ADDITIONAL EXTRA CREDIT PROBLEMS (See chapter 7 of Springer and Friedman's book, Scheme and the Art of Programming, which is on reserve at the library.) 15. (50 points, extra credit) Write a procedural abstraction of recursion over the grammar (see problem 6), called lcm+if-recur. By a procedural abstraction we mean a procedure that can be passed arguments to make tools such as free-vars-lcm+if, and bound-vars-lcm+if and count-varrefs (adapting the example in class to this grammar). Test your procedure by creating these procedures. 16. (150 points, extra credit) Write a procedural abstraction of procedures such as the one called for in problem 15. You might want to first write a few more examples like problem 15 for other grammars (e.g., the slist grammar, the types grammar, and so on.) Then write a procedure that can be used to create such procedural abstractions. (This is one level of tool making more abstract than problem 15.) You'll probably have to pass to your procedure some representation of the grammar it is supposed to make a tool-maker for. Test your procedure by creating these tool-makers, and them using them to make procedures such as free-vars, and bound-vars, and count-varrefs for various grammars.