Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Com S 342 --- Principles of Programming Languages HOMEWORK 6: DATA ABSTRACTION AND REPRESENTATION STRATEGIES FOR DATA TYPES (File $Date: 2006/11/13 22:08:55 $) Due: problems 2-3,7, 11-14 at beginning of class, Tuesday, March 25th, 2008. 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 coding problems hand in: - a printout of the code with your name in a comment, and - if our tests reveals any errors with your code for that problem, then include a transcript showing a run of our tests. That is, you only have to hand in output of your testing if it reveals problems in your code (that you have not fixed). We expect you to run our tests for each problem, but since the output in the case where the tests all pass is not very interesting, we will trust you to have done this. However, you must hand in a transcript of your testing if your code does *not* pass our tests perfectly, as this will alert us to the problem and will help us assign partial credit. If we find that your code is not correct and the problem would have been revealed by our testing, but you did not hand in test results showing these problems, then you will receive 0 points for that problem. You may also hand in a transcript that includes our tests if you wish. 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 abstract int 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; } public int leafSum() { return num; } } 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; } public int leafSum() { return left_tree().leafSum() + right_tree().leafSum(); } //@ 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 are intended to be synonyms for Scheme s. ::= := | begin {}* end | goto | : ::= | ( - ) That is, write an appropriate set of define-datatype definitions. Note: The `:=' operator means assignment (like Pascal), so the production ::= := gives the syntax for the assignment command. An example is x := 10 - 5 You are allowed to decide other details of the grammar as you see fit. We don't give examples so you can make such decisions on your own. Hand in a transcript which loads your abstract syntax into Scheme. (You can use the "Run" button in DrScheme to load what is in its definition window.) Your transcript should create some objects using the constructors given by your define-datatype expression. If you wish, you can use the "cases" expression to examine the parts of objects you construct. Alternatively, use DrScheme's constructor printing. 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. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 2.3.1-2.3.2 13. (15 points) [inf-set-as-proc] Using a *procedural* representation for data, one can encode infinite data structures, as we did in class for mathematical sequences. (See $PUB/lib342/seq-as-proc.scm.) In this problem you will do the same for sets. In set theory, a "set comprehension expression" is something like { x | x is an integer and x > 5 }. That is, it has a bound variable (like x) that represents a typical element, and a predicate (like "x is an integer and x > 5") that tells when something is in the set. Note that the set described by the above set comprehension expression is infinite, yet we can describe it compactly (with a few characters). We can think of this as a way to turn a predicate (the description) into a potentially infinite set. A predicate can be represented as a procedure (i.e., a closure) in Scheme. As usual, a predicate has type (-> (datum) boolean) meaning a one-argument function that takes an argument of any type and returns a boolean. Your problem then, is to implement the operations of the type inf-set of potentially infinite sets. The operations you are to implement have the types below. You are to implement them using a procedural representation. Note that all but set-member? are constructors. (deftype inf-set-comprehend (-> ((-> (datum) boolean)) inf-set)) (deftype inf-set-union (-> (inf-set inf-set) inf-set)) (deftype inf-set-intersection (-> (inf-set inf-set) inf-set)) (deftype inf-set-complement (-> (inf-set) inf-set)) (deftype inf-set-member? (-> (datum inf-set) boolean)) For examples, consider the following. (deftype the-empty-inf-set inf-set) (define the-empty-inf-set (inf-set-comprehend (lambda (x) #f))) (deftype universal-inf-set inf-set) (define universal-inf-set (inf-set-comprehend (lambda (x) #t))) (deftype greater-than-maker (-> (number) inf-set)) (define greater-than-maker (lambda (n) (inf-set-comprehend (lambda (x) (and (number? x) (> (has-type-trusted number x) n)))))) (deftype greater-than-5 number) (define greater-than-5 (greater-than-maker 5)) (inf-set-member? 342 the-empty-inf-set) ==> #f (inf-set-member? 'x universal-inf-set) ==> #t (inf-set-member? 3 (inf-set-comprehend number?)) ==> #t (inf-set-member? 'b (inf-set-comprehend number?)) ==> #f (inf-set-member? 3 greater-than-5) ==> #f (inf-set-member? 7 greater-than-5) ==> #t (inf-set-member? 'b greater-than-5) ==> #f (inf-set-member? '7 (inf-set-union (greater-than-maker 5) (inf-set-complement (greater-than-maker 342)))) ==> #t (inf-set-member? '7 (inf-set-intersection (greater-than-maker 5) (inf-set-complement (greater-than-maker 342)))) ==> #t Hint: inf-set-comprehend and inf-set-member? should be *really* simple, since you are using a procedural representation. For the others, think of how the set theoretic concepts relate to logic; this is helpful because the predicates are essentially boolean-valued. For example, recall that the union { x | x > 5 } union { x | x < 0 } is the set { x | x > 5 or x < 0 }. Think about how the two predicates that describe the two sets being unioned relate to the predicate that describes the set in the result. Start by copying the file $PUB/homework/hw6/inf-set-as-proc.scm to your directory. Remember, for all coding problems, you must hand in a printout of your code. If some tests do not pass you must also hand in a transcript showing testing using our test data. For this problem, you can use the following to test your code. (require "inf-set-as-proc.scm") (test-hw6 "inf-set") 14. (20 points) [inf-set-as-ast] Transform your procedural representation of sets into an abstract syntax tree representation. Start by copying the file $PUB/homework/hw6/inf-set-as-ast.scm to your directory. Then fill in code where the comments indicate for the define-datatype, and implement the procedures from the previous problem. Test using the new code, but with the same test set as in the previous problem. (require "inf-set-as-ast.scm") (test-hw6 "inf-set"). To receive credit, your code for this problem must use the abstract syntax tree representation.