Com S 342 --- Principles of Programming Languages HOMEWORK 3: STATIC PROPERTIES OF VARIABLES (File $Date: 2001/10/25 16:36:41 $) Due: problems 1-2,4-9 at beginning of class, October 23, 2001; problems 10-11,14 at beginning of class, October 25, 2001; problems 17-19 at beginning of class, October 30, 2001. In this homework, you will review a bit about type checking and currying, learn more about recursion over grammars, and learn important programming language concepts relating to 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, and you should be sure to use the type checker. Also, don't use the parse-... procedures in your own code, but use the other helpers. 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 because they mixed recursion over a grammar with recursion over a list, 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 we apply to the test cases to do the relevant error checking. Hence, you don't have to worry about the error checking. As we discussed in class, think about the following questions/tips for full recursion (which should be your default in this homework): (1) Are there examples needed? Write out related simpler examples. (2) What is the type? (3) What is the input grammar? Use an outline that matches it. (4) Use only one kind of recursion per procedure. (5) Recurse for each helping procedure. Don't hesitate to use helping procedures, especially for lists. For coding problems, code is to be written in Scheme, using the exact procedure names specified in the problem descriptions. For coding problems starting with problem 2, we suggest that, for practice for tests, that you first write out by hand a solution to the problem, and only then type in your solution to the computer. However, you should hand in just a printout of the code, and an unedited transcript of testing. See the directory $PUB/homework/hw3 for test data for each coding problem. (You can use the procedure test-hw3 to run our tests, as described in homework 1.) The section headings below give the readings related to the problems. (Please read them!) CLASSROOM DISCUSSIONS ESSENTIALS OF PROGRAMMING LANGUAGES, Section 2.1 STRUCTURE AND INTERPRETATION OF PROGRAMMING LANGUAGES, Section 2.1 1. (5 points) [static vs. dynamic type checking] In the previous homework, many students had the experience that they could get programs involving the types sym-exp and s-lists to work but had some difficulty with the type checker. What does this tell you about the relative advantages and disadvantages of static vs. dynamic type checking? Briefly explain. 2. (10 points) [type checking and abstraction] Consider the difference between the program code in $PUB/lib/subst.scm and the textbook's code on pages 19-20, which is found in $PUB/lib/1.scm. (a) Briefly summarize the difference between the outputs from the following, which executes the book's subst procedure on some tests using sym-exp-cooked.scm in the untyped interpreter for Scheme, scheme342 (or scm342) ... > (load-from-lib "1.scm") ; the book's code > (load-from-lib "sym-exp-cooked.scm") > (subst 'a 'b (parse-s-list '((b c) (b () d)))) > (subst 'hmm 'symbol (parse-s-list '((symbol c) (symbol () d)))) > (s-list? (subst 'hmm 'symbol (parse-s-list '((symbol c) (symbol () d))))) ... and the following which executes the same tests but using the code in $PUB/lib/subst.scm and sym-exp-cooked.scm. > (load-from-lib "subst.scm") > (load-from-lib "sym-exp-cooked.scm") > (subst 'a 'b (parse-s-list '((b c) (b () d)))) > (subst 'hmm 'symbol (parse-s-list '((symbol c) (symbol () d)))) > (s-list? (subst 'hmm 'symbol (parse-s-list '((symbol c) (symbol () d))))) Be sure to summarize the differences, not just to describe both outputs. Hint: you may want to look at the code of the two procedures subst-in-symbol-expression and subst-sym-exp in these two files. (b) What does the experiment above tell you about the utility and the need to treat data abstractly through interfaces? A TYPE NOTATION FOR SCHEME (http://www.cs.iastate.edu/~cs342/docs/typedscm_toc.html) 3. (5 points; extra credit) The current version of the type checker (which you can run by using scheme342typed), gives the following error for file 1.scm (among others): 1.scm: lines 45 to 49: Expected type of variable and definition differ Variable: subst-in-symbol-expression Type from deftype or uses : (forall (t) (-> ((list-of t) (list-of t) t) t)) Type of defining expression: (forall (t) (-> ((list-of t) (list-of t) (list-of t)) (list-of t))) This type error report is a confusion on the part of the type checker, since the code actually doesn't encounter an error at run-time. It is caused by the outermost if-expression in subst-in-symbol-expression in $PUB/lib/1.scm. Can you explain why the type checker gives this type error but isn't confused by the code in $PUB/lib/subst.scm? STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS, SECTION 1.3 (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3) 4. (5 points) [average3-c] Define a curried version of the following procedure, call it average3-c, and write the deftype for it as well. (deftype average3 (-> (number number number) number)) (define average3 (lambda (a b c) (/ (+ a b c) 3))) Use the type checked interpreter, in scheme342typed, to do your testing for this problem. After loading (and thus type checking your code), test your code by executing the following. (test-hw3 "average3-c") Remember, for this and all of the following coding problems, you must hand in both a printout of your code file and a transcript showing testing using our test data. Be sure to include statements at the top of your code file identifying yourself, as described in previous homeworks. 5. (5 points) [average-9-42] Using your solution from problem 4, define a procedure, (deftype average-9-42 (-> (number) number)) that takes a number, c, and returns the average of 9, 42, and c. For example, (average-9-42 0) ==> 17 (average-9-42 3) ==> 18 Use the type checked interpreter, in scheme342typed, to do your testing for this problem. After loading (and thus type checking your code), test your code by executing the following. Test your code by executing the following. (test-hw3 "average-9-42") Important: your solution must use average3-c from the previous problem. You will get zero points if your solution's code does not depend on average3-c. STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS, SECTIONS 1.1.6 (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html#%_sec_1.1.6) REVISED^5 REPORT ON THE ALGORITHMIC LANGUAGE SCHEME CODE EXAMPLES PAGE (http://www.cs.iastate.edu/~cs342/docs/code-examples.html#SyntacticAbstraction) 6. (10 points) [occurs-twice using "and" and "or"] Write the procedure occurs-twice? from homework 1, problem 5 without using #t and #f, but using "and" and "or". Hand in a printout of your code and a transcript of testing that includes our test cases, which you can execute using: (test-hw3 "occurs-twice") Use of the type checker is optional for this problem, although it should work fine and may be helpful to you. 7. (10 points) [vector-index with letrec] Write the procedure, vector-index, from homework 2 problem 17 using "letrec" and tail recursion. Do not use Scheme's procedures vector->list or list->vector. You can run our the tests using (test-hw2 "vector-index") Use of the type checker is optional for this problem, although it should work fine and may be helpful to you. 8. (5 points) [example of syntactic sugar] Give an example of a statement or expression in C++ that is a syntactic sugar. Explain by a simple example how to desugar this statement or expression. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 1.3.1 In addition to the section of the book named above, please also read the file $PUB/lib/lambda-1+quote-exp-examples.scm closely, which illustrates by example the grammar and helping procedures for this set of problems. See also $PUB/lib/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.) 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". 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/lib/lambda-1+quote-exp.scm These are designed to work with our type checker, so you should use the type-checked interpreter for these problems. 9. (10 points total) [lambda-helpers] Load the file lambda-1+quote-exp.scm from the library by typing: (load-from-lib "lambda-1+quote-exp.scm") a. (5 points) Without using parse-lambda-1+quote-exp, 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.) x (x (quote y)) (f x) (lambda (x) (f x)) ((lambda (x) (f x)) (quote x)) All of these should have the type lambda-1+quote-exp. 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 x from each of the 5 expressions in part a. 10. For this problem, a ``lambda calculus expression'', means an in the language lambda-1+quote-exp. a. (15 points) [free-vars] Write a procedure, free-vars, with type given by (deftype 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 use your set-ops.scm file from homework 2. (If you didn't get problem 7 of homework 2 working, email us for a working solution.) Your code should satisfy the following equations between sets, (where set is as in homework 2, that is, (set 'x 'y) means the set containing the symbols x and y). (free-vars (parse-lambda-1+quote-exp 'x)) = (set 'x) (free-vars (parse-lambda-1+quote-exp 'z)) = (set 'z) (free-vars (parse-lambda-1+quote-exp '(quote z))) = the-empty-set (free-vars (parse-lambda-1+quote-exp '(x (x y)))) = (set 'x 'y) (free-vars (parse-lambda-1+quote-exp '(x (f (quote y))))) = (set 'x 'f) (free-vars (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = (set 'y) (free-vars (parse-lambda-1+quote-exp '(x (lambda (x) (x (x y)))))) = (set 'x 'y) (free-vars (parse-lambda-1+quote-exp '((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 type check. In particular it should only be called recursively with arguments that are in the above grammar (n.b., 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-exp.scm to make sure the type checker can do its job. To do this, put (load-quietly-from-lib "lambda-1+quote-exp.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.) 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-hw3 "free-vars") Remember, for this and all of the following coding problems, you must hand in: a printout of your code and 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?, with type, (deftype 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-lambda-1+quote-exp 'y)) = #f (free? 'x (parse-lambda-1+quote-exp '(x (x y)))) = #t (free? 'y (parse-lambda-1+quote-exp '(x (x y)))) = #t (free? 'y (parse-lambda-1+quote-exp '(x (x (quote y))))) = #f (free? 'a (parse-lambda-1+quote-exp '(x (x y)))) = #f (free? 'x (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = #f (free? 'y (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = #t (free? 'x (parse-lambda-1+quote-exp '(x (lambda (x) (x (x y)))))) = #t After doing your own testing, you can use our tests by typing: (test-hw3 "free") 11. For this problem, a lambda calculus expression means an in the language lambda-1+quote-exp. a. (15 points) [bound-vars] Write a procedure, bound-vars, with type (deftype 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/lib/lambda-1+quote-exp.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-exp 'x)) = the-empty-set (bound-vars (parse-lambda-1+quote-exp '(quote z))) = the-empty-set (bound-vars (parse-lambda-1+quote-exp '(x (x y)))) = the-empty-set (bound-vars (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = (set 'x) (bound-vars (parse-lambda-1+quote-exp '(lambda (y) x))) = the-empty-set (bound-vars (parse-lambda-1+quote-exp '(lambda (y) (quote y)))) = the-empty-set (bound-vars (parse-lambda-1+quote-exp '(x (lambda (x) (x (x y)))))) = (set 'x) To receive full credit your procedure must follow the grammar for lambda-1+quote-exp 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-hw3 "bound-vars") b. (5 points) [bound?] Write a procedure, bound?, with type (deftype 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-exp 'x)) = #f (bound? 'z (parse-lambda-1+quote-exp 'y)) = #f (bound? 'x (parse-lambda-1+quote-exp '(x (x y)))) = #f (bound? 'y (parse-lambda-1+quote-exp '(x (x y)))) = #f (bound? 'a (parse-lambda-1+quote-exp '(x (x y)))) = #f (bound? 'x (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = #t (bound? 'y (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = #f (bound? 'x (parse-lambda-1+quote-exp '(x (lambda (x) (x (x y)))))) = #t For testing this problem, you can use (test-hw3 "bound") 12. (10 points, extra credit) Do exercise 1.20 on p. 31 in the text. 13. (suggested practice) Do exercise 1.21 on p. 31 in the text. 14. (40 points) [free-vars and bound-vars for lambda+if-exp] The language lambda+if-exp, used in this problem, 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 (-> (lambda+if-exp) (set-of symbol))) b. (deftype bound-vars (-> (lambda+if-exp) (set-of symbol))) Use the file $PUB/lib/lambda+if-exp.scm for helping procedures for this grammar that work with the type checker. See the file $PUB/lib/lambda+if-exp-examples.scm for examples using these, and $PUB/lib/lambda+if-exp-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 and bound-vars 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-hw3 "free-vars-lambda+if-exp") (test-hw3 "bound-vars-lambda+if-exp") 15. (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...) ESSENTIALS OF PROGRAMMING LANGUAGES: Section 1.3.2 16. (suggested practice) [scoping] Do exercises 1.27 and 1.28 on pp. 34-35 in the text. 17. (5 points) [lexical address idea] Do exercise 1.29 on p. 36 in the text. (This can be handwritten.) 18. (5 points) [lexical address idea] Do exercise 1.30 on p. 36 in the text. (This can be handwritten.) 19. (45 points) [lexical-address] (This is similar to, but different than, exercise 1.31 on p. 37 in the text. We treat free variables differentyl and in addition treat quoted data.) Write the procedure, lexical-address, whose type is given by (deftype lexical-address (-> (lambda+if-exp) lexical-addr-exp)) where lambda+if-exp is the type of s specified by the grammar in $PUB/lib/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/lib/lexical-addr-exp.scm which loads helpers for the grammar in $PUB/lib/lexical-addr.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 (parse-lambda+if-exp 'car)) ==> (car : 0 0) (lexical-address (parse-lambda+if-exp 't)) ==> (t : 0 0) (lexical-address (parse-lambda+if-exp '(car ls))) ==> ((car : 0 0) (ls : 0 1)) ;; see note (*) below (lexical-address (parse-lambda+if-exp '(if t (car ls) ls))) ==> (if (t : 0 0) ((car : 0 1) (ls : 0 2)) (ls : 0 2)) (lexical-address (parse-lambda+if-exp '(lambda (car ls) (car ls)))) ==> (lambda (car ls) ((car : 0 0) (ls : 0 1))) (lexical-address (parse-lambda+if-exp '(lambda (ls car) (car ls)))) ==> (lambda (ls car) ((car : 0 1) (ls : 0 0))) (lexical-address (parse-lambda+if-exp '(lambda (ls car) (ls)))) ==> (lambda (ls car) ((ls : 0 0))) (lexical-address (parse-lambda+if-exp '(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-lambda+if-exp '(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-lambda+if-exp '(car ls)) ==> ((car : 0 0) (ls : 0 1)) (lexical-address (parse-lambda+if-exp '(car ls)) ==> ((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/hw3/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 type check and follow the grammar. For testing this problem, you can use (test-hw3 "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. 20. (60 points, extra credit) [un-lexical-address] Do exercise 1.32 on p. 37 in the text.