Com S 342 --- Principles of Programming Languages HOMEWORK 3: SYNTACTIC ABSTRACTION AND DATA ABSTRACTION (File $Date: 96/10/10 15:59:18 $) Due: problems 1,2,4,5,8 at beginning of class, October 18; problems 12,17,19-21 at beginning of class, October 25. In this homework, you will learn about syntactic abstraction, data abstraction, and abstract syntax. All code is to be written in Scheme, using the exact procedure names specified in the problem descriptions. If you use the interpreter scm342 on the Com S dept machines, the define-record syntax, and our testing machinery, will work. (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 gambitmacros.s. For SCM, be sure to get our corrected version of SLIB's struct.scm file, which you can find in /usr/unsup/scheme/scm/slib/struct.scm on the Com S machines. 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. (10 points) [let->application] Do exercise 3.1.2 in the text. Note that this is not recursive. (Hint: you might want to use map.) 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-hw3 "let->application") on the Com S department machines when running scm342 to test these. 3. (15 points extra credit) [desugar-let] Write a procedure, desugar-let, that is like let->application of the previous problem, but which recursively eliminates all uses of let in an expression. 4. (5 points) [subst using letrec]. Do exercise 3.1.3 in the text. You can test it using (test-hw3 "subst") The idea is to define at least one local, recursive procedure inside your definition of "subst", using a letrec. 5. (20 points) [free-vars, bound-vars] Extend the code for free-vars and bound-vars to work with the following grammar: ::= | ( if ) | ( lambda ( {}* ) ) | ( {}+ ) | ( let ( {}+ ) ) | ( letrec ( {}+ ) ) ::= ::= ( ) 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 (free-vars '(let ((v three) (w v))) (plus v w)) = (set-of 'three 'v 'plus) but (free-vars '(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. (suggested practice) [lexical-address+let, lexical-address+letrec] Do exercise 3.1.5 in the text. 7. (10 points extra credit) [and-proc, and or-proc] Do exercise 3.2.1 in the text Be sure to test your procedures, and also to answer the text's question. 8. (20 points) [if->cond, cond->if] Do exercise 3.3.1 in the text. You can test these using (test-hw3 "if->cond") (test-hw3 "cond->if") 9. (10 points extra credit) [desugar-cond] Write a procedure, desugar-cond, that is like cond->if of the previous problem, but which recursively eliminates all uses of cond in an expression. 10. (15 points extra credit) [lexical-address+let+cond] Do exercise 3.3.2 in the text. Call your procedure lexical-address+let+cond. It should handle let, letrec, if, and cond. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 3.4-6 11. (suggested practice) [leaf-sum using records] Do exercise 3.4.1 in the text. 12. (20 points) [eval-expression] 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)) 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-expression: (-> (expression) number) that takes an expression and its value. For example (eval-expression (make-literal 3)) ==> 3 (eval-expression (make-literal 4)) ==> 4 (eval-expression (make-unary-minus (make-literal 3))) ==> -3 (eval-expression (make-op-call (make-literal 3) '+ (make-op-call (make-literal 4) '* (make-literal 2))) ==> 11 You can test your solution using (test-hw3 "eval-expression") 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 (-> (interior) actual-max). 15. (suggested practice) [derivation of parse tree] Do exercise 3.4.3 in the text. 16. (10 points, extra credit) [parse with error checking] Do exercise 3.4.4 in the text. 17. (15 points) [record-free?, record-bound-vars] Do exercise 3.4.5 in the text. 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 version of free? and bound-vars, and modify it to work with the grammar and abstract syntax given in EOPL on page 83. Note that this grammar has a production for numbers that is not in lambda-1. Call your procedures for this problem record-free? and record-bound-vars. Thus when you do testing you will load your code and then type the following to produce the transcript for us. (test-hw3 "record-free?") (test-hw3 "record-bound-vars") 18. (20 points, extra credit) [extended lambda calculus parse] Do exercise 3.4.6 in the text. 19. (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 "vector-rep") 20. (10 points) [list rep of records] Do exercise 3.5.1 in the text. You can test the procedures you write by using the following, which has in it a solution to the leaf-sum problem. (test-hw3 "list-rep") 21. (20 points) [finite function ADT] Do exercise 3.6.1 in the text. 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 To test this, load your code with the functions "create-empty-ff", "extend-ff*" and "apply-ff", and then use (test-hw3 "ff-ADT") 22. (suggested practice) [extend-ff using extend-ff*] Do exercise 3.6.2 in the text. 23. (10 points, extra credit) [ribassoc, apply-ff] Do exercise 3.6.3 in the text.