Com S 342 --- Principles of Programming Languages HOMEWORK 5: REPRESENTATION STRATEGIES FOR DATA TYPES (File $Date: 2004/04/01 22:02:58 $) Due: problems 1-4 at beginning of class, March 30, 2004. In this homework, you will learn about different representation strategies for abstract data types. For code hand in *both* your printout of the Scheme code and a transcript of testing. (You can use the procedure test-hw5 to run our tests, as described in homework 1.) For this homework, you only need to use the typed interpreter for those problems that we specifically require it. Some problems you should not use the type checker for. The section headings below give the readings related to the problems. 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.) 1. (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/lib/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/hw5/BinaryTree.java, and a C++ version is found in the files $PUB/homework/hw5/BinaryTree.h, and $PUB/homework/hw5/BinaryTree.h): 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. 2. (10 points) [abstract syntax for a grammar] Give abstract syntax (i.e., a define-datatype) for the following grammar. ::= := | begin {}* end | goto