Com S 342 --- Principles of Programming Languages HOMEWORK 3: SYNTACTIC ABSTRACTION AND DATA ABSTRACTION (File $Date: 1995/10/02 18:32:20 $) Due: problems 1-2,4 at beginning of class, September 20; problems 5,8 at beginning of your discussion section, September 22; problems 11,15,17-18 at your discussion section, September 29; problem 19 at beginning of class, October 4. 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, see appendix A, which will help you get define-record working on Project Vincent under Chez Scheme; the code is in the file $PUB/eopl/appendixa.ss. For PC Scheme, use $PUB/eopl/pcmacros.s, for gambit, use gambitmacros.s; See $PUB/eopl/README for details on these and other Scheme implementations.) 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. (You can use the procedure test-hw3 to run our tests, as described in homework 1. Recall that $PUB means /home/cs342/public.) 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) Do exercise 3.1.1 in the text. (This can be handwritten.) 2. (15 points) Do exercise 3.1.2 in the text [let->application]. 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. (10 points extra credit) 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) Do exercise 3.1.3 in the text [subst using letrec]. 5. (15 points) Do exercise 3.1.4 in the text [free-vars, bound-vars]. Your code should work with the following grammar: ::= | ( if ) | ( lambda ( ) ) | ( ) | ( let ( ) ) | ( letrec ( ) ) ::=

::= | ::= ::= | ::= ( ) ::= | 6. (suggested practice) Do exercise 3.1.5 in the text. Call your procedure lexical-address+let. 7. (10 points extra credit) Do exercise 3.2.1 in the text [and-proc, and or-proc]. 8. (20 points) Do exercise 3.3.1 in the text [if->cond, cond->if]. 9. (10 points extra credit) 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) 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. (10 points) Do exercise 3.4.1 in the text [leaf-sum using records]. 12. (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). 13. (suggested practice) Do exercise 3.4.3 in the text [derivation of parse tree]. (This can be handwritten.) 14. (10 points, extra credit) Do exercise 3.4.4 in the text [parse with error checking]. 15. (15 points) Do exercise 3.4.5 in the text. 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") 16. (20 points, extra credit) Do exercise 3.4.6 in the text [extended lambda calculus parse]. 17. (10 points) Do exercise 3.4.7 in the text [vector rep of records]. 18. (10 points) Do exercise 3.5.1 in the text [list rep of records]. 19. (20 points) Do exercise 3.6.1 in the text [finite function ADT]. To test this, load your code with the functions "create-empty-ff", "extend-ff*" and "apply-ff", and then use (test-hw3 "ff-ADT") 20. (suggested practice) Do exercise 3.6.2 in the text [extend-ff using extend-ff*]. 21. (10 points, extra credit) Do exercise 3.6.3 in the text [ribassoc, apply-ff].