Com S 342 --- Principles of Programming Languages HOMEWORK 3: SYNTACTIC ABSTRACTION AND DATA ABSTRACTION (File $Date: 1999/03/04 16:17:36 $) Due: problems 1,3-5,8,11-13,16,18-19, at beginning of class, March 4. problem 20 at beginning of class March 9. In this homework, you will learn about syntactic abstraction, data abstraction, and abstract syntax. (Then again, Scheme's syntax *is* a form of abstract syntax, so you already know something about that. :-) All code is to be written in Scheme, using the exact procedure names specified in the problem descriptions. Please use the typed interpreter scm342 on the Com S dept machines, which will make sure that you are treating abstract data abstractly. Unless the problem says otherwise, your code should type check. Also, unless directed in the problems, do not change any of the .def files we provide, and do not write your own .def files; this will ensure that the type checker can do its job. This interpreter also has the define-record syntax abstraction working. (If you don't use the Com S dept machines, you are responsible for getting define-record to work. If you are using SCM at home as directed by us, you should already have it working; if not, see the file $PUB/lib/eopl.scm. Chez Scheme on Project Vincent should already have this working, however.) For code hand in *both* your printout of the code and a transcript of testing. See the directory $PUB/data/hw3/hw3.tst for test data for each coding problem. 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!) ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 3.1-3 1. (5 points) [value of let expressions] Do exercise 3.1.1 in the text. This should be handwritten. (In fact it's best to only use the computer to check your work after you understand it yourself. A computer can't think for you!) 2. (suggested practice) [let->application] Do exercise 3.1.2 in the text. Use the grammar and helping procedures described in the next problem. 3. (20 points) [desugar-let] This problem deals with the lambda-if-let-exp grammar below. (Despite the name, this also includes quote.) ::= | ( quote ) | ( lambda ( {}* ) ) | ( if ) | ( let ( {}+ ) ) | ( {}* ) ::= ( ) ::= ::= There are helping procedures for the grammar in the file $PUB/lib/decl.scm (with its .def file $PUB/lib/decl.def). There are also helping procedures for the grammar in $PUB/lib/lambda-if-let-exp.scm (with its .def file $PUB/lib/lambda-if-let-exp.def). You can use these by simplying putting (load-quietly-from-lib "lambda-if-let-exp.scm") at the top of your file. Write a procedure desugar-let : (-> (lambda-if-let-exp) lambda-if-let-exp) that takes a possibly containing let expressions as subexpressions, and desugars it into a semantically equivalent lambda-if-let-exp that does not use let. For example, (desugar-let (parse-lambda-if-let-exp 'x)) ==> x (desugar-let (parse-lambda-if-let-exp '(quote hamlet))) ==> (quote hamlet) ;; this may print as 'hamlet (desugar-let (parse-lambda-if-let-exp '(let ((x (quote y))) x))) ==> ((lambda (x) x) (quote y)) (desugar-let (parse-lambda-if-let-exp '(let ((x (quote y)) (y (quote x))) (let ((z (cons x y))) (list x y z))))) ==> ((lambda (x y) ((lambda (z) (list x y z)) (cons x y))) (quote y) (quote x)) (desugar-let (parse-lambda-if-let-exp '(f (let ((head (car lst))) (if (eq? head (quote car)) (let ((arg (cadr lst))) (list head arg)) (let ((rubarb (let ((y (quote pie))) (list y y)))) (list rubarb rubarb))))))) ==> (f ((lambda (head) (if (eq? head (quote car)) ((lambda (arg) (list head arg)) (cadr lst)) ((lambda (rubarb) (list rubarb rubarb)) ((lambda (y) (list y y)) (quote pie))))) (car lst))) As usual, hand in your code and a transcript of your testing. You can test the code using (test-hw3 "desugar-let") Be sure your code type checks; we will not give credit for code that does not type check. 4. (5 points) [vector-index] Using tail recursion and a letrec that defines at least one local, recursive procedure, write the procedure vector-index : (-> (symbol (vector symbol)) number) that is described in problem 2.2.7 part 4 of the text. (test-hw3 "vector-index") You can modify your solution to homework 1 problem 21, but note that no points will be given unless you use both tail recursion and a letrec. 5. (20 points) [free-vars, bound-vars] This problem deals with the lambda-if-letrec-exp grammar below. (Despite the name, this also includes quote and let.) ::= | ( quote ) | ( lambda ( {}* ) ) | ( if ) | ( let ( {}+ ) ) | ( letrec ( {}+ ) ) | ( {}* ) ::= ( ) ::= ::= There are helping procedures for the grammar in the file $PUB/lib/decl.scm (with its .def file $PUB/lib/decl.def). There are also helping procedures for the grammar in $PUB/lib/lambda-if-letrec-exp.scm (with its .def file $PUB/lib/lambda-if-letrec-exp.def). You can use both of these by simplying putting (load-quietly-from-lib "lambda-if-letrec-exp.scm") at the top of your file, since this file loads the "decl.scm" file also. Write procedures free-vars : (-> (lambda-if-letrec-exp) (set symbol)) bound-vars : (-> (lambda-if-letrec-exp) (set symbol)) which compute the sets of free and bound variables in a expression. The key to this problem is understanding what the scope of variables declared with let and letrec are. You might want to write out the definitions of a free variable and a bound variable first (in a comment!), and then write the code. Note that, for example, (free-vars (parse-lambda-if-letrec-exp '(let ((v three) (w v)) (plus v w)))) = (set-of 'three 'v 'plus) but (free-vars (parse-lambda-if-letrec-exp '(letrec ((v (lambda (y) (w y))) (w (lambda (z) (v z)))) (plus (v forty) (w two))))) = (set-of 'plus 'forty 'two) You can test these using (test-hw3 "free-vars") (test-hw3 "bound-vars") 6. (50 points extra credit) [lexical-address+let, lexical-address+letrec] Do exercise 3.1.5 in the text. You'll have to make a modified version of $PUB/lib/lexical-addr-exp.scm and its .def file to solve this problem. 7. (25 points extra credit) [and-preds, and or-preds] a. Write two variable argument procedures and-procs : (-> ((-> (T) boolean) ...) (-> (T) boolean)) or-procs : (-> ((-> (T) boolean) ...) (-> (T) boolean)) that take any number of predicate procedures as arguments, and produce a predicate procedure that, when applied to an argument, x, give the 'and' or 'or', respectively of the predicates applied to x. In mathematics, one says that these "lift" the Scheme special-forms 'and' and 'or' to predicates. b. Could Scheme be defined so that 'and' and 'or' automatically do this when given predicates instead of boolean-valued expressions? Why or why not? 8. (50 points) [desugar-cond] This problem deals with the lambda-cond-letrec-exp grammar below. (Despite the name, this also includes quote, if, let, and letrec.) ::= | ( quote ) | ( lambda ( {}* ) ) | ( if ) | ( cond {}+ (else ) ) | ( let ( {}+ ) ) | ( letrec ( {}+ ) ) | ( {}* ) ::= ( ) ::= ( ) ::= ::= There are helping procedures for the grammar in the file $PUB/lib/decl.scm (with its .def file $PUB/lib/decl.def). Helping procedures for the grammar are in the file $PUB/lib/cond-clause.scm (with its .def file $PUB/lib/cond-clause.def). There are also helping procedures for the grammar in $PUB/lib/lambda-cond-letrec-exp.scm (with its .def file $PUB/lib/lambda-cond-letrec-exp.def). You can use these by simplying putting (load-quietly-from-lib "lambda-cond-letrec-exp.scm") at the top of your file. Write a procedure desugar-cond : (-> (lambda-cond-letrec-exp) lambda-cond-letrec-exp) that takes a possibly containing cond expressions as subexpressions, and desugars it into a semantically equivalent that does not use cond. (Your procedure should not do anything with let expressions.) For example, (desugar-cond (parse-lambda-cond-letrec-exp 'x)) ==> x (desugar-cond (parse-lambda-cond-letrec-exp '(quote hamlet))) ==> (quote hamlet) ;; this may print as 'hamlet (desugar-cond (parse-lambda-cond-letrec-exp '(let ((x (quote y))) x))) ==> (let ((x (quote y))) x) (desugar-cond (parse-lambda-cond-letrec-exp '(cond (x y) (else z)))) ==> (if x y z) (desugar-cond (parse-lambda-cond-letrec-exp '(f (cond ((cond (a b) (else c)) (let ((z (quote y))) (cond (b z) (else (quote f))))) ((if d (f g) (h i)) (l (cond (x (quote z)) (else (quote q))) m)) (else (letrec ((f (lambda (ls) (cond ((null? ls) (quote nil)) (else (cons (car ls) (f (cdr ls)))))))) (cond (qq rr) (else (quote ss))))))))) ==> (f (if (if a b c) (let ((z (quote y))) (if b z (quote f))) (if (if d (f g) (h i)) (l (if x (quote z) (quote q)) m) (letrec ((f (lambda (ls) (if (null? ls) (quote nil) (cons (car ls) (f (cdr ls))))))) (if qq rr (quote ss)))))) As usual, hand in your code and a transcript of your testing. You can test the code using (test-hw3 "desugar-cond") Be sure your code type checks; we will not give credit for code that does not type check. 9. (20 points extra credit) [desugar] Write a procedure, desugar, that is does both of the jobs of desugar-let and desugar-cond on the grammar. 10. (25 points extra credit) [lexical-address] Do exercise 3.3.2 in the text for the grammar of . ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 3.4-6 11. (5 points) [leaf-sum] Compare the code for leaf-sum found in $PUB/lib/leaf-sum.scm with the code on p. 80 of the text. (a) What are the differences? (b) Why do those differences make the procedure have the type advertised in the code of $PUB/lib/leaf-sum.scm? Your answer to this can be handwritten. 12. (20 points) [eval-arith-expr] Consider the following arithmetic expression grammar. ::= | ( ) | (- ) ::= + | - | * | ** We will represent this in Scheme using the following abstract syntax. (define-record literal (number)) (define-record op-call (left-arg op right-arg)) (define-record unary-minus (arg)) For example, the (3 + (4 ** 2)) would be represented by the record (make-op-call (make-literal 3) '+ (make-op-call (make-literal 4) '** (make-literal 2))) This is what the parse-arith-expr procedure does. The parse-arith-expr procedure, the above definitions, and other helpers are given in the file $PUB/lib/arith-expr.scm. To use this, put (load-quietly-from-lib "arith-expr.scm") in your solution. Your task is to write a procedure eval-arith-expr: (-> (arith-expr) number) that takes an arith-expr and its value. The operators have their conventional meanings, and ** means exponentiation. (In Scheme, you can use the expt procedure to do exponentiation for you. For example, (eval-arith-expr (make-op-call (make-literal 4) '** (make-literal 2))) ==> 16 (eval-arith-expr (make-op-call (make-literal 4) '** (make-literal 3))) ==> 64 (eval-arith-expr (make-literal 3)) ==> 3 (eval-arith-expr (make-literal 4)) ==> 4 (eval-arith-expr (make-unary-minus (make-literal 3))) ==> -3 (eval-arith-expr (make-op-call (make-literal 3) '+ (make-op-call (make-literal 4) '** (make-literal 2)))) ==> 19 You must use the variant-case sugar to solve this problem; we will not give points for solutions that do not use variant-case. (Hint: use an else clause that invokes Scheme's error procedure in your variant-case to get it to type check.) You can test your solution using (test-hw3 "eval-arith-expr") 13. (20 points) [strength-reduce] Optimizing compilers sometimes use a technique called "strength reduction" that is akin to desugaring. The idea is to replace calls to expensive operations with equivalent calls to less expensive ones. In this problem you will write a simple version of such a procedure: strength-reduce : (-> (arith-expr) arith-expr) that transforms subexpressions of the form (e1 ** 2) into expressions of the form (e1 * e1) and transforms subexpressions of form (e1 * 2) into expressions of the form (e1 + e2). (There are more such strength reductions that one can imagine, but this will give you the idea.) For example, we would have the following equations between Scheme expressions of type arith-expr: (strength-reduce (make-op-call (make-literal 4) '** (make-literal 2))) = (make-op-call (make-literal 4) '* (make-literal 4)) (strength-reduce (parse-arith-expr '(4 ** 2))) = (make-op-call (make-literal 4) '* (make-literal 4)) (strength-reduce (parse-arith-expr '(- (3 * 2)))) = (make-unary-minus (make-op-call (make-literal 3) '+ (make-literal 3))) (strength-reduce (parse-arith-expr 3)) = (make-literal 3) (strength-reduce (parse-arith-expr '(- ((7 ** (1 + 1)) * (5 - 3))))) = (make-unary-minus (make-op-call (make-op-call (make-literal 7) '** (make-op-call (make-literal 1) '+ (make-literal 1))) '* (make-op-call (make-literal 5) '- (make-literal 3)))) (strength-reduce (parse-arith-expr '(2 ** 2))) = (make-op-call (make-literal 2) '* (make-literal 2)) You must use the variant-case sugar to solve this problem. You can test your solution using (test-hw3 "strength-reduce") 14. (40 points, extra credit) Do exercise 3.4.2 in the text [max-interior using variant-case]. The book suggests using a record type: (define-record max-sum (symbol sum)) to solve the problem. The information in this record type, even though it's what suggested by the book, doesn't seem to be enough to solve the problem. Try returning 3 things from a tree: the actual sum of the whole tree, as well as the symbol and sum of the maximal subtree of that tree. You might need to use a record such as: (define-record actual-max (whole-sum max-rec)) where whole-sum is a number (the sum of the whole tree), and max-rec is the max-sum record of the largest subtree in the tree. (or something equivalent). Have your helping procedure return an actual-max record. That is, it would have the type (-> (tree) actual-max). Use the helpers in $PUB/lib/binary-tree-of-num.scm for type checking. 15. (suggested practice) [derivation of parse tree] Do exercise 3.4.3 in the text. 16. (15 points) [record-free?, record-bound-vars] Consider the following grammar for a lambda calculus with numeric literals. ::= | | (lambda () ) | ( ) ::= ::= We will represent this the abstract syntax given in the book on page 83. These records and some helpers are found in the file $PUB/lib/record-lambda-1+number-exp.scm (with its .def file $PUB/lib/record-lambda-1+number-exp.def). You can use these by simplying putting (load-from-lib "record-lambda-1+number-exp.scm") at the top of your file. Do exercise 3.4.5 in the text. That is write procedures record-free? : (-> (symbol lambda-1+number-exp) boolean) record-bound-vars : (-> (lambda-1+number-exp) (set symbol)) Be sure to use the type checker and get your code to type check. Since the point of this problem is to give you practice using records, do *not* use parse or unparse in your solution. Instead, take your code for the lambda-1+quote version of free? and bound-vars, and modify it to work with the grammar and abstract syntax described above. Also, modify it to use the variant-case sugar. You can test these with: (test-hw3 "record-free") (test-hw3 "record-bound-vars") 17. (suggested practice) What are the differences between parse-lambda-1+number-exp given in $PUB/lib/record-lambda-1+number-exp.scm and the code on page 85 for parse? What differences are motivated by getting the code to type check? Think about the same issues for unparse. 18. (10 points) [vector rep of records] Do exercise 3.4.7 in the text. You can test the procedures you write by using the following. (test-hw3 "interior-as-vector") Put this a your file "interior-as-vector.scm" and copy $PUB/lib/interior-as-vector.def to the same directory. This will allow Scheme to type check your code. 19. (10 points) [list rep of records] Define the procedures of the interior record type (of the previous problem) such that records are represented as lists rather than vectors. You can test the procedures you write by using the following, (test-hw3 "interior-as-list") For this problem, we want you to define your own interior-as-list.def file so that your code type checks. (Hint: edit a copy of interior-as-vector.def and change the defrep.) Hand in both your .scm and your .def files for this problem. 20. (20 points) [finite function ADT] Do exercise 3.6.1 in the text. In addition, write a function defined-in-ff? : (-> ((ff T) symbol) boolean) that tests whether a symbol is in a finite function. We will use the type (ff T) for a finite function that maps symbols to values of type T. To get the type checking to work, call your .scm file ff-ADT.scm and copy the file $PUB/lib/ff-ADT.def to the directory where your file ff-ADT.scm lives. The following are examples of what your functions should do in this representation. (create-empty-ff) ==> () (defined-in-ff? (create-empty-ff) 'x) ==> #f (extend-ff* '(e f) '(5 6) (create-empty-ff)) ==> (((e f) . #(5 6))) (defined-in-ff? (extend-ff* '(e f) '(5 6) (create-empty-ff)) 'e) ==> #t (defined-in-ff? (extend-ff* '(e f) '(5 6) (create-empty-ff)) 'f) ==> #t (defined-in-ff? (extend-ff* '(e f) '(5 6) (create-empty-ff)) 'g) ==> #f (extend-ff* '(x y z) '(1 2 3) (extend-ff* '(e f) '(5 6) (create-empty-ff))) ==> (((x y z) . #(1 2 3)) ((e f) . #(5 6))) (apply-ff (extend-ff* '(a w) '(val-a val-w) (create-empty-ff)) 'a) ==> val-a (apply-ff (extend-ff* '(a w) '(val-a val-w) (create-empty-ff)) 'w) ==> val-w Our tests won't show it, but invoking (apply-ff '(((a w) . #(val-a val-w))) 'hmm) should give an error with the message: empty-ff: no association for symbol hmm I could not get my code for apply-ff to type check. It seems unavoidable that you will have a type error in calls to ribassoc in apply-ff, since you will be testing to see if the value of the recursive call is the symbol *fail*, and then trying to use the value in the other cases as if it were of type T. So if you have a type error from a call to ribassoc in apply-ff do not worry about it. Or, if that is a bother, then do not use the type checker (use scm342untyped instead) for this problem. In real life, once I determined that the type checker wasn't up to this, I would put trustme! in the .def file for ff-ADT.def, but that would turn off all type checking on the ff-ADT.scm file. You can use our ribassoc procedure, which will help the type checker a bit, by putting (load-from-lib "ribassoc.scm") at the top of your file. To test this, load your file ff-ADT.scm, and then use (test-hw3 "ff-ADT") 21. (suggested practice) [extend-ff using extend-ff*] Do exercise 3.6.2 in the text. You should *not* modify the .def file to get this to work. extend-ff is a client function. 22. (10 points, extra credit) [ribassoc, apply-ff] Do exercise 3.6.3 in the text. What type checking problems, if any do you encounter? 23. (20 points, extra credit) [leaf-sum using records represented as lists] Do problem 3.5.1 in the text. That is, represent both leaf and interior records as lists (you did this for interior records in problem 19). Make a .def file for this that type checks (see $PUB/lib/binary-tree-of-num.def for a hint). Does your code work with the code in $PUB/lib/leaf-sum.scm?