Com S 342 --- Principles of Programming Languages HOMEWORK 3: SYNTACTIC ABSTRACTION AND DATA ABSTRACTION (File $Date: 1998/10/15 16:14:14 $) Due: problems 1,3,4,5 at beginning of class, October 9; problems 8,11 at beginning of class, October 12; problems 12,16,18-19,20 at beginning of class, October 16; problem 20 at beginning of class, October 19. 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 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. For PC Scheme, use $PUB/eopl/pcmacros.s, for gambit, use $PUB/eopl/gambitmacros.s. For SCM, do what we're doing with scm342; see the file $PUB/lib/eopl.scm. See $PUB/eopl/README for more details. 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-from-lib "lambda-if-let-exp.scm") at the top of your file. You can change this to (load-quietly-from-lib "lambda-if-let-exp.scm") if you don't want to see the types of these helpers. 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 11, but note that no points will be given unless you use 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 these by simplying putting (load-from-lib "lambda-if-letrec-exp.scm") at the top of your file. 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. (40 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. (15 points extra credit) [and-preds, and or-preds] 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. 8. (50 points) [desugar-cond] This problem deals with the lambda-cond-letrec-exp grammar below. (Despite the name, this also includes quote, if, and let.) ::= | ( 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-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 are those differences needed to make the procedure type check? 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 (num)) (define-record op-call (left-arg op right-arg)) (define-record unary-minus (arg)) These and a few helpers are defined in the file $PUB/lib/arith-expr.scm. 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))) Your task is to write a procedure eval-arith-expr: (-> (arith-expr) number) that takes an arith-expr and its value. For example (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))) ==> 11 (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. (suggested practice) If you didn't use variant-case to solve problem 12, go back and make your solution use variant case. 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 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. 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 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") 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) ==> () (extend-ff* '(e f) '(5 6) (create-empty-ff)) ==> (((e f) . #(5 6))) (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 '(((a w) . #(val-a val-w))) 'a) ==> val-a (apply-ff '(((a w) . #(val-a val-w))) '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. So if you have a type error from a call to ribassoc in apply-ff do not worry about it. (It makes the type of the symbol into a datum, because of your call to error.) 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 $PUB/lib/leaf-sum.scm?