Com S 342 --- Principles of Programming Languages HOMEWORK 5: INTERPRETERS (File $Date: 1995/11/16 22:14:24 $) Due: problems 1-2,4-5,9-10 at beginning of your discussion section, October 27; problems 0,13 at the beginning of class, October 30; problems 15,17,19 at your discussion section, November 3; problems 22-23 at the beginning of class, November 6; problems 24,32,34,39 at your discussion section, November 10; problems 35,37, at the beginning of class, November 13; problems 40-41,43-44 at the beginning of class, November 27. In this homework, you will review some of the concepts about reduction rules and imperative programming, and learn the basics of interpreters. You will also investigate the topics of recursion and dynamic scoping in some detail. As you go along in this homework, you will accumulate the code for a useful interpreter. In general, each problem's code should add to the code for the problem before it, so that your interpreter becomes more and more useful. For code hand in *both* your printout of the Scheme code and a transcript of testing. See the directory $PUB/data/hw5/hw5.tst for test data for each coding problem. (You can use the procedure test-hw5 to run our tests, as described in homework 1. Recall that $PUB means /home/cs342/public.) The section headings below give the readings related to the problems. ESSENTIALS OF PROGRAMING LANGUAGES: Sections 3.4-5 0. (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 different in the C++ version and the Scheme version? (That is, why is each kind of error check needed in each language and not in the other?) (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? Which is more error-prone? Briefly explain why. (These can be handwritten.) 0.5 (10 points extra credit) Show how to write the above program in Pascal, and post your solution to the newsgroup. (Only the first person to post a correct answer to the newsgroup gets these points.) ESSENTIALS OF PROGRAMING LANGUAGES: Sections 4.3, 4.5-6 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. 1. (5 points) What is the difference between applicative order reduction and normal order (what the book calls "leftmost") reduction? Give an example to illustrate the difference. 2. (5 points) What evaluation order is used by C++ (or Pascal). 3. (suggested practice) What does the comma syntax ( , ) do in C++ (or C)? What feature of Scheme is like that? 4. (5 points) Why do you think that C++ (or Pascal) doesn't have a read-eval-print loop? 5. (5 points) In what way is an object in C++ like a closure in Scheme? 6. (suggested practice) Are variables in Scheme first-class objects? Are variables in C (or C++, or Pascal) first-class objects? Explain. 7. (10 points extra credit) Why doesn't Scheme have reference or pointer types? Do you think Scheme would be more efficient at run-time if it did? Why? ESSENTIALS OF PROGRAMING LANGUAGES: Sections 5.1-2 You are *strongly* urged to do exercise 8, even though it's no credit, as it will familiarize you with the interpreter on the system. 8. (suggested practice) Do exercise 5.1.2 in the text; that is get the interpreter running and play with it some. Use the following to load the code from the chapter (on the department machines). (load-from-lib "ch5-1.scm") To use the "run" procedure, you must also load "run5-1.scm", by typing: (load-from-lib "run5-1.scm") If you do that, then you can have a transcript like: > (run "+(3,4)") 7 To use the "read-eval-print" procedure, you must load "rep5-1.scm", by typing: (load-from-lib "rep5-1.scm") If you do that, then you can have a transcript like: > (read-eval-print) --> +(3,4); 7 --> end You must follow each expression with a semicolon in the read-eval-print loop to get an output. Note that typing end to the read-eval-print loop's prompt will get you out of it. Because of the implementation, you cannot use both run and read-eval-print at the same time. 9. (20 points) Do exercise 5.1.3 in the text. [add minus to the interpreter] Test it yourself first, using either the run procedure or the read-eval-print loop as in problem 8. Then use: (test-hw5 "minus") to do the final testing. 10. (30 points) Do exercise 5.1.4 in the text. [add cons, car, cdr, list, emptylist] Test it yourself first (as in problem 8), then use: (test-hw5 "lists") 11. (suggested practice) Do exercise 5.2.2 in the text. [add if] (Use the character string syntax.) 12. (suggested practice) Do exercise 5.2.3 in the text. [add equal, zero, greater, less] 13. (15 points) Do exercise 5.2.3 in the text. [add null] Test it yourself first, then use: (test-hw5 "null") ESSENTIALS OF PROGRAMING LANGUAGES: Sections 5.3-4 14. (suggested practice) Do exercise 5.3.1 in the text. [add let] (Use the character string syntax.) You might want to also play with the file "ch5-3-traced.scm", which is a version of the interpreter with tracing output. 15. (10 points) Extend the interpreter by adding the primitive procedure eq, which should correspond to the Scheme procedure eq? The type of the eq you add should be: (-> (Expressed-Value Expressed-Value) number) with the number returned representing true or false. Your solution should also contain a solution to problem 10 above, that is, an interpreter with cons, car, cdr, list, and emptylist, so it can be adequately tested. (If you don't have a solution to problem 10, send email to cs342s@cs.iastate.edu for a solution.) Test it yourself first, then use: (test-hw5 "eq") 15.5 (5 points, extra credit) Why is let needed in the interpreter to adequately test the eq primitive? (Hint: think about object identity and cons, and compare with problem 12 above, which has equal for testing numbers.) This can be handwritten. 16. (suggested practice) Do exercise 5.4.1 in the text. [add user-defined procedures] (Use the character string syntax.) 17. (20 points) Do exercise 5.4.2 in the text. [user-defined procedures with apply] Use the following outline for your code: (load-from-lib "ch5-4.scm") (define apply-proc apply) (define make-closure (lambda (formals body env) (lambda args ;; put the body of your procedure here ))) ;; You need to redefine init-env so that it contains Scheme closures. ;; Put your redefinition of init-env after this line. Write make-closure and redefine init-env so that the interpreter works. Note that make-closure created a record previously, but now it will be creating procedures. Hint: Haven't we seen this type of program transformation before? Test it yourself first, then use: (test-hw5 "make-closure-with-apply") 18. (10 points, extra credit) Do exercise 5.4.3 in the text. [apply-proc variation] 19. (25 points) Do exercises 5.4.4 in the text. [syntax-expand] Note that the procedure syntax-expand has the type: (-> (parsed-exp) parsed-exp) To test this, you can use the files run-expanding.scm and rep-expanding.scm in $PUB/lib. (The usual versions of run and read-eval-print won't work.) Your procedure should handle the the following syntax rules: ::= | | if then else | proc ( ) | ( ) | let in ::= ::= | , ::= ::= | ( ) ::= | , ::= = ::= | ; VERY IMPORTANT: Be sure to put the following line in your file! (load-from-lib "ch5-4.scm") Hint: use make-proc rather than make-closure. Make-proc produces a parsed-exp (an abstract syntax tree), which is what is needed. (The result of make-closure is a semantic object, not a parsed-exp. Another hint: be sure to have an "else" clause in your variant-case like the ones from the interpreters in the book. Test it yourself first, then use: (test-hw5 "syntax-expand") ESSENTIALS OF PROGRAMING LANGUAGES: Sections 5.5 In this and the next section, use the interpreter "ch5-5-let.scm" as a basis for your work. 20. (suggested practice) Do exercise 5.5.1 in the text. [add cells to the let-interpreter] Alternatively, put let in the interpreter of Figure 5.5.1. 21. (15 points, extra credit) Do exercise 5.5.2 in the text. [use ribcage to avoid cells] 22. (15 points) Do exercise 5.5.3 in the text. [redefine eval-rands for new apply-proc] You can get the code quoted in the exercise from $PUB/eopl/sources.ss. Use the interpreter "ch5-5-let.scm" for this exercise. (The interpreter in "ch5-5.scm" doesn't have let or all the primitives we wanted for testing.) VERY IMPORTANT: Be sure to put the following line in your file! (load-from-lib "ch5-5-let.scm") Test it yourself first, then use: (test-hw5 "apply-proc-with-denoted") 23. (20 points) Do exercise 5.5.4 in the text. [begin] Note that the parser produces the kind of abstract syntax trees described by the problem already. Test it yourself first, then use: (test-hw5 "begin") 24. (25 points) Do exercise 5.5.5 in the text. [define] Note that the parser already has the capability to read this syntax, so you don't have to modify the parser, despite what the problem says. To modify the read-eval-print loop of appendix F, all you should change is the function eval-print (see it's definition in $PUB/lib/appendix-f.scm). Since this involves the read-eval-print loop, you'll have to test it yourself. Use as part of your testing, the inputs in the following file. $PUB/homework/hw5.tst/define.inputs Hint: use the function defined-env? found in $PUB/lib/environments.scm to test whether what is being defined is already in the init-env. 25. (20 points, extra credit) Do exercise 5.5.6 in the text. [unspecified values printing] 26. (40 points, extra credit) Do exercise 5.5.7 in the text. [mutable and immutable variables] Also answer the following: what is this like in C++ or Pascal? 27. (25 points, extra credit) Do exercise 5.5.8 in the text. [optimized mutable variables] 27.5 (65 points, extra credit) Do exercise 5.5.9 in the text. [denotational-style stores] ESSENTIALS OF PROGRAMING LANGUAGES: Section 5.6 28. (20 points, extra credit) Do exercise 5.6.1 in the text. [add letrecproc] You can get the environment ADT from $PUB/eopl/sources.ss. 29. (25 points, extra credit) Do exercise 5.6.2 in the text. [add letrec] 30. (20 points, extra credit) Do exercise 5.6.3 in the text. [wrapping cells around closures] 31. (25 points, extra credit) Do exercise 5.6.4 in the text. [efficiency issues] 32. (25 points) (a) Do exercise 5.6.5 in the text. [syntax expansion of letrecproc into let] The syntax for letrecproc, and the abstract syntax record declarations are already understood by the parser. What you have to do is to make syntax-expand work with this. The translation you are to use is the following: letrecproc var-1 (formals-1) = exp-1; . . . var-n (formals-n) = exp-n in body ==> let var-1 = 0; . . . var-n = 0 in begin var-1 := proc (formals-1) exp-1; . . . var-n := proc (formals-n) exp-n; body end Note that your syntax-expand still has to work with "let". You will also have to add cases for the syntax that is new versus the older version of syntax-expand you may have; this includes begin and varassign. (Hint: be sure to have an "else" clause in your variant-case like the ones from the interpreters in the book.) IMPORTANT: Because this syntactic sugar uses "begin", for our testing you will need to use your solution to problem 23 for this problem. (If you don't have a version of syntax-expand that works with let, or a solution to problem 23, you can get one by sending email to cs342s@cs.iastate.edu.) Test it yourself first, then use: (test-hw5 "letrecproc-expand") (b) What is the difference between the semantics of letrec shown on page 163 and the semantics given above? (This part can be handwritten.) 32.5 (15 points, extra credit) Implement the semantics shown on page 163. ESSENTIALS OF PROGRAMING LANGUAGES: Section 5.7 33. (suggested practice) Do exercise 5.7.1 in the text. [add dynamic scoping] 34. (5 points) (a) Give an example of one expression in the defined language that has a different value with static and dynamic scoping. Your example must be *different* than those found in class or the book. (b) Use the interpreter with dynamic scoping, by running (load-from-lib "$PUB/lib/ch5-7-1.scm") to show what your example does with dynamic scoping. Note that this interpreter doesn't have let defined for it. You can either use your solution to problem 19 (syntax-expand) along with the expanding versions of the read-eval-print loop or the run procedure (in $PUB/lib/rep-expanding.scm and $PUB/lib/run-expanding.scm), or expand them by hand. 35. (15 points) Do exercise 5.7.2 in the text. [fact with dynamic scoping] Turn in your defined language code, and a transcript of testing it with the interpreter that you get by running (load-from-lib "$PUB/lib/ch5-7-1.scm") (Note that the problem is asking you to write out the desugared version of a let, which is a good thing, because this intrepreter doesn't support let anyway. Note that let x = 3 in +(x,x) desugars to (proc(x) +(x,x))(3).) 36. (suggested practice) Do exercise 5.7.3 in the text. [add environment stack] 37. (25 points) Do exercise 5.7.4 in the text. [procedures done with Scheme and dynamic] Copy the file $PUB/homework/hw5.tst/apply-dynamic.scm and make the modifications indicated in that file. It is similar to what you did for exercise 5.5.2 (Problem 17) but the interpreter should implement dynamic scope. Test it yourself first, then use: (test-hw5 "apply-dynamic") 38. (50 points, extra credit) Do exercise 5.7.5 in the text. [shallow binding] 39. (5 points) Do exercise 5.7.6 in the text. [understanding dynamic scoping] Explain how the answer came to be. (This can be handwritten.) 40. (5 points) Do exercise 5.7.7 in the text. [understanding dynamic assignment] Briefly justify your answer. (This can be handwritten.) 41. (30 points) Do exercise 5.7.8 in the text. [add letdynamic] Copy the file $PUB/homework/hw5.tst/apply-letdynamic.scm and add the semantics of the letdynamic abstract syntax as specified in exercise 5.7.8. Test it yourself first, then use: (test-hw5 "apply-letdynamic") 42. (40 points, extra credit) Do exercise 5.7.9 in the text. [dynassign via syntax-expand] 43. (10 points) Which do you think is best: (a) a language with no dynamic assignment or dynamic scoping, (b) a language with only dynamic scoping, or (c) a language with static scoping and dynamic assignment? Pick *one* of these, and briefly defend why it is the best. 44. (10 points) Does C or C++ (or Pascal, BASIC, ...) have any feature like dynamic scoping or dynamic assignment? Briefly explain, using an example if possible.