Com S 342 --- Principles of Programming Languages HOMEWORK 6: DATA ABSTRACTION AND REPRESENTATION STRATEGIES FOR DATA TYPES (File $Date: 2005/03/07 20:00:02 $) Due: problems 2-3 and 7 at beginning of class, Thursday, March 3, 2005. problems 11-14 at beginning of class, Tuesday, March 8, 2005. 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. :-) In the second part you will also learn about different representation strategies for abstract data types. All code is to be written in Scheme, using the exact procedure names specified in the problem descriptions. For code hand in *both* your printout of the code and a transcript of testing. See the directory $PUB/homework/hw6 for test data for each coding problem. Use the procedure test-hw6 to run our tests. If you want to see more output, execute (show-test-output!); to see less output, execute (hide-test-output!). The section headings below give the readings related to the problems. (Please read them!) ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 2.1-2 1. (suggested practice) [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! Test your solution using (test-hw6 "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/lib342/arith-expr.scm. To use this, put (load-quietly-from-lib "arith-expr.scm") in your solution. Your task is to write a procedure with type defined by (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". 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-hw6 "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 + e1). 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 right argument to ** or * is literally 2. (To simplify the coding, we ignore the left argument of *.) (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 (unary-minus-exp (binary-op-exp (lit-exp 3) (times-op) (lit-exp 2)))) = (unary-minus-exp (binary-op-exp (lit-exp 3) (plus-op) (lit-exp 3))) (strength-reduce (unary-minus-exp (binary-op-exp (lit-exp 2) (times-op) (lit-exp 3)))) = (unary-minus-exp (binary-op-exp (lit-exp 2) (times-op) (lit-exp 3))) (strength-reduce (lit-exp 3)) = (lit-exp 3) (strength-reduce (binary-op-exp (lit-exp 2) (exponent-op) (lit-exp 2)) = (binary-op-exp (lit-exp 2) (plus-op) (lit-exp 2)) (strength-reduce (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) (binary-op-exp (lit-exp 2) (exponent-op) (lit-exp 2)))))) = (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) (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-hw6 "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/lib342/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/lib342/lambda-1-quote-exp-as-ast.scm. You can use the define-datatype in that file by putting (require (lib "lambda-1-quote-exp-as-ast.scm" "lib342")) at the top of your code. Using this file and "cases", write the procedure bound-vars from homework 5, problem 3(b). That is write procedure (deftype bound-vars (-> (expression) (set-of symbol))) where "expression" is the type of a lambda-1-quote-exp defined in the library file "lambda-1-quote-exp-as-ast.scm". 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-exp 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. In particular, there are no "case discriminator" procedures (like app-exp?), and no observer procedures (like app-exp->rator). You should not write such procedures, and instead use cases directly. That will save you time in the long run. (Also, the type is now called expression instead of lambda-1-quote-exp, so be sure to change your deftypes.) You can test this procedure with: (test-hw6 "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. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 2.2 For the problems in this section, please give a brief answer: no more than about five (5) sentences. Use examples to illustrate your ideas, so that you aren't just copying ideas from the book or notes. (These can be handwritten, although we'd prefer to see them typed.) 11. (15 points) [define-datatype and cases as syntactic abstractions] Recall the Scheme define-datatype declaration for binary trees used in section 2.1, p. 46 (and found in $PUB/lib342/bintree.scm): (define-datatype bintree bintree? (leaf-node (datum number?)) (interior-node (key symbol?) (left bintree?) (right bintree?))) Recall also the procedure leaf-sum from EOPL page 81: (deftype leaf-sum (-> (bintree) number)) (define leaf-sum (lambda (tree) (cases bintree tree (leaf-node (datum) datum) (interior-node (key left right) (+ (leaf-sum left) (leaf-sum right))) ))) In Scheme, this could be tested as follows. (define tree-a (interior-node 'a (leaf-node 2) (leaf-node 3))) (leaf-sum tree-a) In Java, the corresponding code would declare an abstract class BinaryTree, with two subclasses: Leaf and Interior. The procedure leaf-sum becomes a method, leafSum, of the abstract class BinaryTree, and the code to do the testing is put in the method "main" of BinaryTree (the following is also in $PUB/homework/hw6/BinaryTree.java, and a C++ version is found in the files $PUB/homework/hw6/BinaryTree.h, and $PUB/homework/hw6/BinaryTree.cpp): public abstract class BinaryTree { public /*@ pure @*/ abstract boolean isLeaf(); //@ public invariant !isLeaf() ==> this instanceof Interior; public int leafSum() { if (this.isLeaf()) { return ((Leaf)this).number(); } else { Interior meAsInterior = (Interior)this; return meAsInterior.left_tree().leafSum() + meAsInterior.right_tree().leafSum(); } } public static void main(String [] argv) { BinaryTree tree_a = new Interior(new Leaf(2), "a", new Leaf(3)); System.out.println(tree_a.leafSum()); } } class Leaf extends BinaryTree { private int num; public /*@ pure @*/ boolean isLeaf() { return true; } public int number() { return num; } public Leaf(int n) { num = n; } } class Interior extends BinaryTree { private String sym; private BinaryTree left, right; //@ private invariant sym != null && left != null && right != null; public /*@ pure @*/ boolean isLeaf() { return false; } public BinaryTree left_tree() { return left; } public BinaryTree right_tree() { return right; } public String symbol() { return sym; } //@ requires l != null && s != null && r != null; public Interior(BinaryTree l, String s, BinaryTree r) { left = l; sym = s; right = r; } } Write brief answers to the following questions. (a) Between Scheme and Java (or C++), which language has the advantage for declaring such variant record types, writing code to process them, and building variant records? Briefly explain why. Include the advantages and disadvantages of both languages in handling variant record types. (b) Which is more error-prone? Briefly explain why. 12. (10 points) [abstract syntax for a grammar] Give abstract syntax (i.e., a define-datatype) for the following grammar, where and