Com S 342 --- Principles of Programming Languages HOMEWORK 2: STATIC PROPERTIES OF VARIABLES (File $Date: 96/02/27 12:11:19 $) Due: problems 1,2,5-6,9-10 at beginning of your discussion section, Feb. 20; problem 11 at beginning of your discussion section, Feb. 27. (Note: on Feb. 27, you will also have problems from homework 3 due...) 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 an abstraction of most programming langauges. Please remember the tips given in class for working these kinds of problems. Last semester, students 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 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: (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 a 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.2 $PUB/docs/type-notation.txt 0. (50 points (25 each), extra credit) Extend your code for the procedures polymorphic? and instantiate, from homework 1 problem 17, to deal with the entire grammar for our type notation, as given below. ::= | | | | ::= number | boolean | string | character | symbol | void | datum | poof | ::= any symbol except one of the s ::= S | T | U | V | W | X | Y | Z ::= (-> ({}*) ) ::= (list ) | (pair ) | (vector ) ::= (and {}+) ESSENTIALS OF PROGRAMMING LANGUAGES: Section 2.3.1 The language lambda-1, used in the first two problems below, is defined by the following grammar. ::= | (lambda () ) | ( ) ::= ::= 1. For this problem, a lambda calculus expression means an 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). (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) 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. (6 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) For testing this problem, you can use (test-hw2 "bound-vars") b. (6 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. (16 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! 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 up 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!) 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? 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 (-> (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 gave students last semester 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") 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 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. 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+multiple, and bound-vars+multiple, and count-varrefs for various grammars.