Com S 342 --- Principles of Programming Languages HOMEWORK 2: STATIC PROPERTIES OF VARIABLES (File $Date: 1997/09/18 20:11:24 $) Due: problems 0,1,2,5,6 at beginning of class, September 22; problems 10-12 at beginning of class, September 29; In this homework, you will learn more about recursion over grammars, and the important concepts of static properties of variables. 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. 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 The language lambda-1, used in the first three problems below, is defined by the following grammar. ::= | (lambda () ) | ( ) ::= ::= 0. (5 points) [lambda-helpers] Write the lambda helping procedures varref?, lambda?, lambda->body, lambda->formal, app->rator, and app->rand. Here are some examples: (varref? 'z) ==> #t (varref? '(lambda (x) z)) ==> #f (varref? '(f z)) ==> #f (lambda? '(lambda (x) (f x))) ==> #t (lambda? '(lambda x)) ==> #f ; Note that the list doesn't have 3 elements ; so lambda would have to be a varref here, ; so it does satisfy the grammar if lambda ; isn't a reserved word (conclusion: make ; sure the list has a length of 3). (lambda? 'x) ==> #f (lambda->body '(lambda (x) z)) ==> z (lambda->body '(lambda (x) (f x))) ==> (f x) (lambda->body '(lambda (x) (lambda (f) (f x)))) ==> (lambda (f) (f x)) (lambda->formal '(lambda (x) (f z))) ==> x (app->rator '(f x)) ==> f (app->rand '(f x)) ==> x (app->rator '(g (f x))) ==> g (app->rand '(g (f x))) ==> (f x) (app->rator '((lambda (z) (g z)) (f x))) ==> (lambda (z) (g z)) Remember, for all coding problems, you must hand in a transcript showing testing using our test data. For testing this problem, use (test-hw2 "lambda-helpers") 1. For this problem, a lambda calculus expression, means a in the language lambda-1. a. (10 points) [free-vars] Write a procedure, free-vars : (-> (lambda-exp) (set varref)) that takes a lambda calculus expression, expr, and returns the set of the variables that occur free in expr. (See the book for the definition of ``occurs free.'') Set of variables are to be represented by lists of symbols with *no* duplicates. (Hint, use the helping functions from homework 1 that deal with sets for maximum credit.) Your code should satisfy the following equations (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 'x) = (set-of 'x) (free-vars 'z) = (set-of 'z) (free-vars '(x (x y))) = (set-of 'x 'y) (free-vars '(lambda (x) (x (x y)))) = (set-of 'y) (free-vars '(x (lambda (x) (x (x y))))) = (set-of 'x 'y) (free-vars '((lambda (y) y) (lambda (x) (y x)))) = (set-of 'y) To receive full credit your procedure must follow the grammar. So it should only be called recursively with arguments that are in the above grammar (e.g., empty lists are not in the grammar). Hints: Use the lambda helpers from problem 0 above. Do not flatten the lambda calculus into a list, as your solution will be wrong. Remember, for all coding problems, you must hand in a transcript showing testing using our test data (see above). For this problem, you can use (test-hw2 "free-vars") on the Com S department machines when running scm342 to test these. b. (5 points) [free?] Write a procedure, free? : (-> (symbol lambda-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 'x) = #t (free? 'z 'y) = #f (free? 'x '(x (x y))) = #t (free? 'y '(x (x y))) = #t (free? 'a '(x (x y))) = #f (free? 'x '(lambda (x) (x (x y)))) = #f (free? 'y '(lambda (x) (x (x y)))) = #t (free? 'x '(x (lambda (x) (x (x y))))) = #t For testing this problem, you can use (test-hw2 "free?") 2. For this problem, a lambda calculus expression means an in the language lambda-1. a. (10 points) [bound-vars] Write a procedure, bound-vars : (-> (lambda-exp) (set varref)) that takes a lambda calculus expression, expr, and returns the set of the variables that occur bound in expr. (See the book for the definition of ``occurs bound.'') Set of variables are to be represented by lists of symbols with *no* duplicates. (Hint, use the helping functions from homework 1 that deal with sets for maximum credit.) Your code should satisfy the following equations (where set-of is as in homework 1). (bound-vars 'x) = (set-of) (bound-vars 'z) = (set-of) (bound-vars '(x (x y))) = (set-of) (bound-vars '(lambda (x) (x (x y)))) = (set-of 'x) (bound-vars '(x (lambda (x) (x (x y))))) = (set-of 'x) To receive full credit your procedure must follow the grammar. So when calling itself recursively it should only be passed arguments that are in the above grammar (e.g., empty lists are not in the grammar). Hint: Use the lambda helpers from problem 0 above and do not flatten the list. For testing this problem, you can use (test-hw2 "bound-vars") b. (5 points) [bound?] Write a procedure, bound? : (-> (symbol lambda-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 'x) = #f (bound? 'z 'y) = #f (bound? 'x '(x (x y))) = #f (bound? 'y '(x (x y))) = #f (bound? 'a '(x (x y))) = #f (bound? 'x '(lambda (x) (x (x y)))) = #t (bound? 'y '(lambda (x) (x (x y)))) = #f (bound? 'x '(x (lambda (x) (x (x y))))) = #t For testing this problem, you can use (test-hw2 "bound?") 3. (suggested practice) Do exercise 2.3.3 in the text. 4. (10 points, extra credit) Do exercise 2.3.4 in the text. 5. (15 points) [free-vars+multiple, bound-vars+multiple] The language lambda*, used in this problem, is defined by the following grammar. ::= | (lambda ({}*) ) | ( {}*) ::= ::= Do exercise 2.3.5 in the text. For this problem, you should write two procedures: free-vars+multiple and bound-vars+multiple. Don't forget to include the appropriate type comments in your code! To receive full credit, your code for free-vars+multiple and bound-vars+multiple follow the grammar. Make sure that recursive calls only pass arguments in the above grammar. Hint: Add to the helpers lambda->formals and app->rands. The result of app->rands should be processed by a helper that understands lists and/or use map. For testing this problem, you can use (test-hw2 "free-vars+multiple") (test-hw2 "bound-vars+multiple") 6. (10 points) [free-vars+if, bound-vars+if] Do exercise 2.3.6 in the text. For this problem, you should write two procedures: free-vars+if and bound-vars+if. We leave writing out the appropriate grammar to you, but it should be able to handle expressions such as (f x y). See our test cases for more examples. (You should include the grammar as a comment in your code. And don't forget those type comments either!) To receive full credit your procedure should follow your grammar. Don't pass empty lists, for example, on recursive calls. Hint: Write and use the helpers if?, if->test, if->then, and if->else. For testing this problem, you can use (test-hw2 "free-vars+if") (test-hw2 "bound-vars+if") 7. (suggested practice) [quote changes?] Do exercise 2.3.7 in the text. The question can be rephrased: if you add the syntax (quote e) to the lambda-calculus, how would your definition of free-vars and bound-vars have to change? 8. (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-exp) (set varref))) ; (-> (lambda-exp) (set varref))) (lambda (recur) (lambda (exp) ... code for free-vars, except that recur replaces free-vars ...))) Use this idea to write free-vars+multiple and free-vars+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 9. (suggested practice) [scoping] Do exercises 2.3.8 and 2.3.9 in the text. 10. (5 points) [lexical address idea] Do exercise 2.3.11 in the text. (This can be handwritten.) 11. (5 points) [lexical address idea] Do exercise 2.3.12 in the text. (This can be handwritten.) 12. (45 points) [lexical-address] Do exercise 2.3.10 in the text. The type of lexical-address is (-> (lambda-exp) lexical-addr-exp) where lambda-exp is the type of data specified by the grammar in exercise 2.3.10, and lexical-addr-exp is the type of data defined by the following grammar: ::= | (if ) | (lambda ({}*) ) | ({}+) ::= ( : ) ::= For example: (lexical-address 'car) ==> (car : 0 0) (lexical-address 't) ==> (t : 0 0) (lexical-address '(car ls)) ==> ((car : 0 0) (ls : 0 1)) ;; see note (*) below (lexical-address '(if t (car ls) ls)) ==> (if (t : 0 0) ((car : 0 1) (ls : 0 2)) (ls : 0 2)) (lexical-address '(lambda (car ls) (car ls))) ==> (lambda (car ls) ((car : 0 0) (ls : 0 1))) (lexical-address '(lambda (ls car) (car ls))) ==> (lambda (ls car) ((car : 0 1) (ls : 0 0))) (lexical-address '(lambda (ls car) (ls))) ==> (lambda (ls car) ((ls : 0 0))) (lexical-address '(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 '(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 '(car ls)) ==> ((car : 0 0) (ls : 0 1)) (lexical-address '(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. For testing this problem, you can use (test-hw2 "lexical-address") 13. (60 points, extra credit) [un-lexical-address] Do exercise 2.3.13 in the text. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 2.3.3 14. (20 points, extra credit) [rename] Do exercise 2.3.14 in the text. 15. (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.) 16. (50 points, extra credit) Write a procedural abstraction of recursion over the grammar lambda* (see problem 5), called lambda*-recur. By a procedural abstraction we mean a procedure that can be passed arguments to make tools such as free-vars+multiple, and bound-vars+multiple, and count-varrefs (adapting the example in class to this grammar). Test your procedure by creating these procedures. 17. (150 points, extra credit) Write a procedural abstraction of procedures such as the one called for in problem 16. You might want to first write a few more examples like problem 16 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 16.) 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+multiple, and bound-vars+multiple, and count-varrefs for various grammars.