Com S 342 --- Principles of Programming Languages HOMEWORK 4: REDUCTION RULES AND IMPERATIVE PROGRAMMING (File $Date: 96/10/30 3:11:29 $) Due: problems 1-3,8-10,12-13 at beginning of class, March 25. problems 20,21,23,28-32 at beginning of class, April 1. In this homework, you will review some of the ideas studied in the last chapter about syntactic abstraction and data abstraction. You will also study imperative programming features and their semantics, as well as get a glimpse of the semantics of object-oriented languages. (There is also extra credit work related to the semantics of the lambda calculus.) For code hand in *both* your printout of the Scheme code and a transcript of testing. See the directory $PUB/data/hw4/hw4.tst for test data for each coding problem. (You can 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. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 3.1-3 For the problems in this section, please give a brief answer: no more than about three (3) sentences. Use examples to illustrate your ideas, so that you aren't just copying ideas from the book or notes. (These can be handwritten.) 1. (5 points) Give an example of syntactic abstraction in some programming language other than Scheme or LISP (e.g., Pascal, C, C++, Ada, CLU, BASIC, ...). The example should also be different from those given below in C/C++ (there are lots of other syntactic sugars in C/C++). Give an example of the "sugared" form and the equivalent "desugared" form. Some C/C++ examples given in class: i++ ==> i = i + 1 i-- ==> i = i - 1 i+= x ==> i = i + x i-= x ==> i = i - x i*= x ==> i = i * x i%= x ==> i = i % x i/= x ==> i = i / x i->x ==> (*i).x 2. (5 points) What are the advantages of syntactic abstraction as a means of specifying features of a programming language? (As opposed to giving the semantics directly.) Give an example. 3. (10 points) What is the difference between "cond" and "case" in Scheme? What is an example of something similar to each one in some other language? 4. (suggested practice) Could "if" expressions be eliminated from Scheme? 5. (10 points, extra credit) Why is the syntactic sugar for "or" in Scheme more complex than that for "and"? 6. (suggested practice) What is more like "and" in Scheme: C++'s "&&" or "&"? Why does C++ have both "&&" and "&"? Which is like the "and" in Pascal? 7. (15 points, extra credit) Is there any way that a syntactic abstraction is different from a macro? ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 3.4-7 For the problems in this section, please give a brief answer: no more than about three (3) sentences. Use examples to illustrate your ideas, so that you aren't just copying ideas from the book or notes. (These can be handwritten.) 8. (5 points) What are the advantages and disadvantages of transparent representations for ADTs? 9. (10 points) Recall the Scheme record declarations for binary trees used in section 3.4: (define-record interior (symbol left-tree right-tree)) (define-record leaf (number)) Recall also the procedure leaf-sum from EOPL page 81: (define leaf-sum (lambda (bin-tree) (variant-case bin-tree (leaf (number) number) (interior (left-tree right-tree) (+ (leaf-sum left-tree) (leaf-sum right-tree))) (else (error "leaf-sum: Invalid tree" tree))))) In Scheme, this could be tested as follows. (define tree-a (make-interior 'a (make-leaf 2) (make-leaf 3))) (leaf-sum tree-a) In C++, the corresponding declarations would be: enum BinaryTreeTag { interior_tag, leaf_tag }; struct BinaryTree { BinaryTreeTag tag; union { struct { char * symbol; BinaryTree *left_tree; BinaryTree *right_tree; } interior; struct { int number; } leaf; }; }; In C++, the code for leaf-sum would be: #include #include long int LeafSum(BinaryTree *bin_tree) { if (bin_tree == 0) { cerr << "LeafSum: null pointer passed!" << endl; exit(-1); } switch (bin_tree->tag) { case leaf_tag: return bin_tree->leaf.number; break; default: return LeafSum(bin_tree->interior.left_tree) + LeafSum(bin_tree->interior.right_tree); break; } } In C++, this could be tested as follows. #include #include int main() { BinaryTree *tree_a = new BinaryTree; tree_a->tag = interior_tag; tree_a->interior.symbol = new char[2]; strcpy(tree_a->interior.symbol, "a"); BinaryTree *leaf2 = new BinaryTree; leaf2->tag = leaf_tag; leaf2->leaf.number = 2; BinaryTree *leaf3 = new BinaryTree; leaf3->tag = leaf_tag; leaf3->leaf.number = 3; tree_a->interior.left_tree = leaf2; tree_a->interior.right_tree = leaf3; cout << LeafSum(tree_a) << endl; return(0); } Briefly write answers to the following questions. (a) Why are the errors that need to be checked in the C++ version different from the Scheme version? (That is, why is the error check in the Scheme version unnecessary in C++, and why is the error check in the C++ version unnecessary in Scheme?) (b) Between Scheme and 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. Which is more error-prone? Why? 10. (10 points) Give abstract syntax for the following grammar. ::= := | begin {}* end | goto