Com S 342 --- Principles of Programming Languages HOMEWORK 6: DATA ABSTRACTION AND REPRESENTATION STRATEGIES FOR DATA TYPES (File $Date: 2006/03/05 22:50:11 $) Due: problems 2-3,7, 11-14 at beginning of class, Tuesday, March 7, 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 (require (lib "bintree-mod.scm" "lib342")) 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 is not a solution! 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 (require (lib "arith-expr-mod.scm" "lib342")) 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. However, during your testing you may find these useful. Don't use Scheme's eval procedure in your code. Don't write the same code multiple times in your solution; we will take off points for duplicated 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 we will 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 (the = below thus means the expressions compare true when used as arguments to equal?): (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. Use (require (lib "arith-expr-mod.scm" "lib342")) in your code. Don't use parse-arith-expr, parse-infix-op, unparse-arith-expr, or eval in your code. Also, it's bad form to compare arith-exprs using equal?, instead use cases to take apart the parts of an arith-expr and compare numbers using Scheme's = procedure. However, during your testing you may find that parse-arith-expr, unparse-arith-expr, and equal? are quite useful, and it's fine to use them in doing testing. In particular unparse-arith-expr will show you the output in parsed form. Alternatively, use DrScheme's printing to see the results of tests. To do this in DrScheme, select the Language menu, and then "Choose Language", then (at the bottom left) click on the button that says "Show Details", then from the right side, under "output syntax" choose "constructor", and click on the "OK" button. Don't write the same code multiple times in your solution; we will take off points for duplicated 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. Note: don't write the same code multiple times in your solution, we will take off points for duplicated code. 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-mod.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 our dialect of Scheme (Typedscm) 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 discuss the advantages of both languages in handling variant record types. Briefly explain why an objective person should agree with your statements about this. Don't just state what you prefer, instead give a brief argument that uses some facts about the code, what it would be like to maintain the code, and about what a program can do with the code in each language. (b) Which is more error-prone? Briefly explain why, again using some facts about the code, what it would be like to maintain the code, and about what a program can do with the code in each language. 12. (10 points) [abstract syntax for a grammar] Give abstract syntax (i.e., a define-datatype) for the following grammar, where and