Com S 342 --- Principles of Programming Languages HOMEWORK 4: DATA ABSTRACTION (File $Date: 2004/03/11 18:00:52 $) Due: problems 1-3,7 at beginning of class, March 30, 2004. In this homework, you will learn about 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. Unless the problem states otherwise, please use the typed interpreter scheme342typed which will make sure that you are treating abstract data abstractly, and get your code to type check. Also, unless directed in the problems, do not change the given types (and do not use the special forms "has-type-trusted" or "trustme!"); this will ensure that the type checker can do its job in making sure your code respects data abstraction. This interpreter also has the define-datatype syntax working. Note that, while we do not require you to write out your code by hand before attempting programming problems, you are encouraged to write out initial versions of your code on paper, especially if that helps you plan your code or to practice for tests. For code hand in *both* your printout of the code and a transcript of testing. See the directory $PUB/homework/hw4 for test data for each coding problem. Use the procedure test-hw4 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-2 1. (10 points) [bintree-to-list] Do exercise 2.4 on page 47 in the text. You can get the define-datatype for bintree using (load-quietly-from-lib "bintree.scm") Be sure to use "cases". The code (define bintree-to-list (lambda (bt) bt)) will pass all the tests (because of the representation of bintree), but will get you zero points! For this problem, don't use the type checker (which doesn't work well with non-homogeneous lists). Instead use scheme342untyped. Test your solution using (test-hw4 "bintree-to-list") 2. (20 points) [eval-arith-expr] Consider the following arithmetic expression grammar. ::= "lit-exp (datum)" | ( "binary-op-exp (left-arg op ) right-arg)" | (- ) "unary-minus-exp (arg)" ::= + "plus-op" | - "minus-op" | * "times-op" | ** "exponent-op" We will represent this in Scheme using the following abstract syntax. (define-datatype arith-expr arith-expr? (lit-exp (datum number?)) (binary-op-exp (left-arg arith-expr?) (op infix-op?) (right-arg arith-expr?)) (unary-minus-exp (arg arith-expr?))) (define-datatype infix-op infix-op? (plus-op) (minus-op) (times-op) (exponent-op)) For example, the (3 + (4 ** 2)) would be represented by the record (binary-op-exp (lit-exp 3) (plus-op) (binary-op-exp (lit-exp 4) (exponent-op) (lit-exp 2))) Putting together these calls 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 (deftype eval-arith-expr (-> (arith-expr) number)) that takes an arith-expr and returns its value. The operators have their conventional meanings; e.g., ** means exponentiation. (In Scheme, you can use the expt procedure to do exponentiation for you.) For example, (eval-arith-expr (binary-op-exp (lit-exp 4) (exponent-op) (lit-exp 2))) ==> 16 (eval-arith-expr (binary-op-exp (lit-exp 4) (exponent-op) (lit-exp 3))) ==> 64 (eval-arith-expr (lit-exp 3)) ==> 3 (eval-arith-expr (lit-exp 4)) ==> 4 (eval-arith-expr (unary-minus-exp (lit-exp 3))) ==> -3 (eval-arith-expr (binary-op-exp (lit-exp 3) (plus-op) (binary-op-exp (lit-exp 4) (exponent-op) (lit-exp 2)))) ==> 19 You must use "cases" sugar to solve this problem; we will not give points for solutions that do not use "cases". Use the type checker, but as always, not has-type-trusted or trustme!. Don't use parse-arith-expr or unparse-arith-expr in your code. Don't use Scheme's eval procedure in your code. You can test your solution using (test-hw4 "eval-arith-expr") 3. (30 points) [strength-reduce] Optimizing compilers sometimes use a technique called "strength reduction". 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: (deftype 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). Note that (2 ** 2) strength-reduces to (2 * 2) and that this itself strength reduces to (2 + 2). Also, note that you are only to perform these reductions when the argument is literally 2. (Another optimization, evaluation of constant expressions also applies here, since there are no variables, but let's not use that so that we can get the idea without the complications of dealing with variables. Also there are more strength reductions you could perform, but just doing these two simple ones will give you the idea.) For example, we would have the following equations between Scheme expressions of type arith-expr: (strength-reduce (binary-op-exp (lit-exp 4) (exponent-op) (lit-exp 2))) = (binary-op-exp (lit-exp 4) (times-op) (lit-exp 4)) (strength-reduce (parse-arith-expr '(4 ** 2))) = (binary-op-exp (lit-exp 4) (times-op) (lit-exp 4)) (strength-reduce (parse-arith-expr '(- (3 * 2)))) = (unary-minus-exp (binary-op-exp (lit-exp 3) (plus-op) (lit-exp 3))) (strength-reduce (parse-arith-expr 3)) = (lit-exp 3) (strength-reduce (parse-arith-expr '(- ((7 ** (1 + 1)) * (5 - 3))))) = (unary-minus-exp (binary-op-exp (binary-op-exp (lit-exp 7) (exponent-op) (binary-op-exp (lit-exp 1) (plus-op) (lit-exp 1))) (times-op) (binary-op-exp (lit-exp 5) (minus-op) (lit-exp 3)))) (strength-reduce (parse-arith-expr '(2 ** 2))) = (binary-op-exp (lit-exp 2) (plus-op) (lit-exp 2)) You must use "cases" to solve this problem. Don't use parse-arith-expr, parse-infix-op, or unparse-arith-expr in your code. You can test your solution using (test-hw4 "strength-reduce") 4. (40 points, extra credit) [max-interior]. Do exercise 2.5 on page 47 in the text. Your code should type check for full credit. Hint: you may need an auxiliary data structure. 5. (suggested practice) Do exercise 2.6 on page 50 of the text. 6. (suggested practice) What are the differences between the parse-expression procedure on page 51 of the text and the parse-expression procedure in the file $PUB/lib/lambda-1+quote-exp-as-ast.scm? 7. (15 points) [bound-vars] This problem uses a define-datatype version of the lambda-1+quote-exp grammar and helpers. These can be found in the file $PUB/lib/lambda-1+quote-exp-as-ast.scm. You can use the define-datatype in that file by putting (load-from-lib "lambda-1+quote-exp-as-ast.scm") at the top of your code. Using this file and "cases", write the procedure bound-vars from homework 3, problem 11(a). That is write procedure (deftype bound-vars (-> (expression) (set-of 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 "cases", do *not* use parse-expression or unparse-expression in your solution. Instead, take your code for the lambda-1+quote version of bound-vars (and whatever helpers you need :-), and modify it to work with the grammar and abstract syntax described above, using "cases". You should find that most of the interesting parts can be left unchanged, although be warned that the interface of the ADT in lambda-1+quote-exp-as-ast.scm is slightly different from that in lambda-1+quote-exp.scm, since there are no "case discriminator" procedures (like app-exp?), and no observer procedures (like app-exp->rator). Also, the type is now called expression instead of lambda-1+quote-exp, so be sure to change your deftypes! You can test these with: (test-hw4 "bound-vars") 8. (40 points, extra credit) [lexical address using cases] Do exercise 2.7 on page 52 of the text. 9. (30 points, extra credit) [fresh-ids, all-ids] Do exercise 2.10 on page 53 of the text. (See the errata if you have an older copy of EOPL 2e.) 10. (40 points, extra credit) [lambda-calculus-subst] Do exercise 2.11 on pages 53-54 of the text.