Com S 342 --- Principles of Programming Languages HOMEWORK 5: INTERPRETERS (File $Date: 1999/04/15 16:51:36 $) Due: problems 4-6, at beginning of class, April 1; problems 7,11-13,15,17-18,20,21 at beginning of class, April 8; problems 22-23,34,38,39,43-45,47,48 at beginning of class, April 15. In this homework, you will learn the basics of interpreters, You will also investigate the topics of syntax abstraction, 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.) Unless noted otherwise, your code should type check without error, and without changing any .def files we give you or writing your own .def files. If you have trouble with getting characters to erase when interacting with the interpreters, see the file $PUB/docs/erase-message.txt. Note for emacs users: it seems that comments in the defined langauge cause problems if you use the emacs interface to Scheme to run the interpreters. The solution is to run the interpreters without emacs in the middle. The section headings below give the readings related to the problems. Please read these. Here are some ideas for increasing your understanding of the ideas in chapter 5, which is the core of the course. These ideas are all centered around making your reading of the interpreters more active. If you just read the code quickly, you'll have trouble understanding what's going on. Instead, try whatever of the following seems appropriate, and keep doing what works for you. (a) For each procedure in the interpreters, ask yourself: what is the job (specification) of this procedure? Write this down, and revise it as necessary when you discover otherwise. This should be abstract. Don't write: "it takes the car of rands, ...", instead write something more like "it evaluates all the expressions in rands". Describe what it does, not how. (b) When you read the code for one procedure and see a call to another, don't immediately look at the code for the called procedure, instead think about what it's job is, and imagine it does that correctly. This is important, because the code is so recursive. (c) Explain what is happening in the interpreter to someone else; this is a good way to do part (b) if you have a willing friend. (d) When you read the code of a procedure, think about whether it's correct and why it's correct, with respect to its job. This often involves several passes though the code and textual commentary surrounding it. Don't rush through it. This is the main thing I think about when I read code, so I highly recommend it. (e) Ask yourself: what happens if I change this part of the code? Try to think if you could do the same thing better, or more elegantly. (f) Imagine you want to do a similar thing to what you've seen in the code you just read. How would you do it? (g) Think about the types of the code, and why the code is type correct. This is easier to do with the code in $PUB/lib than the code in the book. For more fun (;->), try to convert the code in the book to type check, and compare your solution to ours (in the library). Let us know if you find problems with our code! (h) Draw diagrams of the execution data structures for some examples. Try to be careful and consistent about it. Put in "displayln" statements in the iterpreter to print out the data structures, and use that to check your work. (i) Trace through some examples by hand. Use the "trace" procedure that is built in to the Scheme interpreter to trace the execution on-line after doing this, to verify what you've done and get feedback on whether you were understanding it correctly. (j) Use the Unix command: diff -c ch5-1.scm ch5-3.scm to see what changes between these interpreters. Try this with different pairs of interpreters. Run the Unix command man diff to see how to read the output if it's not clear. ESSENTIALS OF PROGRAMING LANGUAGES: Sections 4.5-6 The problems in this section can be handwritten, although we would prefer to see them typed. 1. (suggested practice) a. In what way is an object in C++ like a closure in Scheme? b. Are variables in Scheme first-class objects? Are variables in C++ (or C, or Pascal) first-class objects? Explain (and be sure to say what language you are talking about). 2. (10 points extra credit) Why doesn't Scheme or Java have pointer types and pointer arithmetic? Do you think Scheme or Java would be more efficient at run-time if it did? Why? ESSENTIALS OF PROGRAMING LANGUAGES: Sections 5.1 In this section, use the interpreter "ch5-1.scm" as a basis for your work. Thus, to use this interpreter, first use the following to load the code from Section 5.1 of the chapter (on the department machines). (load-from-lib "ch5-1.scm") To use the "run" procedure (for part a below), 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 : expressed-value To use the "read-eval-print" procedure (for part b below) instead of run, 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. (Another way to get the read-eval-print loop is to just load the file "read-eval-print-5-1.scm".) Because of the implementation, you cannot use both run and read-eval-print at the same time. You can also change the read-eval-print loop to not do evaluation, but rather to print the abstract syntax trees. This may be helpful in learning about the parser. To do this (for part c below), first load "rep5-1.scm" and then load "parser-debugger.scm", as follows. (load-from-lib "ch5-1.scm") (load-from-lib "rep5-1.scm") (load-from-lib "parser-debugger.scm") If you do that, then you will have a transcript like the following. > (read-parse-print) --> +(3,4); #(app #(varref +) (#(lit 3) #(lit 4))) --> end (Another way to get the read-parse-print loop is to just load the file "read-parse-print-5-1.scm".) 3. (suggested practice) Read the code for the interpreter, starting from the file $PUB/lib/ch5-1.scm and following the loaded files. Do this in conjunction with reading the chapter, to be sure you understand how things work. Note that there are some differences due to type checking. 4. (10 points) [transcripts for run and read-eval-print with 4 commas] Do exercise 5.1.2 in the text; that is get the interpreter running and play with it some. (See the end of this problem for what to hand in.) Hand in a transcript that shows: (a) how you used the run procedure, (b) how you used the read-eval-print procedure to evaluate expressions, and (c) how you use the parser-debugger to print the abstract syntax trees. For both (a) and (b) you should evaluate at least 4 different expressions. To show you can work with the defined language's grammar, at least one input for parts (a) and (b) should have 4 commas (`,' characters) in it. Circle these inputs on your transcript. 5. (20 points) [add minus, cons, car, cdr, list, and emptylist] Do exercises 5.1.3 and 5.1.4 in the text. Exercse 5.1.4 adds lists to the interpreter, revising the domains to be: Denoted-Value = Number + Procedure + List(Expressed-Value) Expressed-Value = Number + Procedure + List(Expressed-Value) Helpers for the revised domains are found in the following files. $PUB/lib/ch5-1-4-expressed-value.scm $PUB/lib/ch5-1-4-denoted-value.scm We've provided a start or outline for your solution in the following file $PUB/homework/hw5.tst/primitives.scm Copy this to your directory, and then add your code to this file. (Hint: in Scheme, (- 3) returns -3.) Test it yourself first, using either the run procedure or the read-eval-print loop as in problem 4. Then use: (test-hw5 "minus") (test-hw5 "lists") to do the final testing. Your code should type check. ESSENTIALS OF PROGRAMING LANGUAGES: Sections 5.2 Note: In this section, use the interpreter "ch5-1.scm" as a basis for your work. 6. (20 points) [add if, equal, zero, greater, less, null] a. Do exercise 5.2.1 in the text. (Use the character string syntax for if. The define-record for the `if' variant-record type as given in the text is automatically provided by the parser, so you don't need to define it.) Copy the following file $PUB/homework/hw5.tst/if.scm and add your code to this file. Test your solution after adding the predicates for part (b) below. Make sure your solution loads the primitives added in part (b) (see the comments in the file you copied above). b. Do exercises 5.2.2 and 5.2.3 in the text. Extend your solution to Problem 5 by adding the primitive procedures equal, zero, greater, less and null. Test it yourself first, then use: (test-hw5 "comparisons") (test-hw5 "null") Testing for this will test part (a) as well. ESSENTIALS OF PROGRAMING LANGUAGES: Section 5.3 In this section, use the interpreter "ch5-3.scm" as a basis for your work. Thus, for this section, use the following to load the interpreter code. (load-from-lib "ch5-3.scm") You might want to also play with the file "ch5-3-traced.scm", which is a version of the interpreter with tracing output. From now on, in order to use the "run" procedure, you must also load "run.scm", by typing: (load-from-lib "run.scm") If you do that, then you can make a transcript like: > (run "+(3,4)") 7 : expressed-value Also from now on, in order to use the "read-eval-print" procedure, you must load "rep.scm", by typing: (load-from-lib "rep.scm") If you do that, then you can make a transcript like: > (read-eval-print) --> +(3,4); 7 --> end As before, 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. (You can also load and start the read-eval-print loop by loading the file "read-eval-print.scm". Furthermore, you can load the "parser-debugger.scm" file after loading "rep.scm" if you want to see the abstract syntax trees.) Again, because of the implementation, you cannot use both run and read-eval-print at the same time. 7. (10 points) [calculate 3**8] Write an expression in the defined language to calculate 3**8, that is 3 to the eighth power, using only let, *, variable names, and the number 3. See above for how to run the interpreter. Hand in a transcript showing that your expression works. 8. (suggested practice) [add eq] Extend the interpreter by adding the primitive procedure eq, which should correspond to the Scheme procedure eq? The type of the eq procedure you will add should be: (-> (Expressed-Value Expressed-Value) number) with the number returned representing true or false. Your solution should extend your solution to problem 5 above, that is, your interpreter should have cons, car, cdr, list, and emptylist, etc. so it can be adequately tested. 9. (5 points, extra credit) [why is let needed to test eq] Why is let needed in the interpreter to adequately test the eq primitive? (Hint: think about object identity and cons, and compare with problem 6 above, which has equal for testing numbers.) This can be handwritten, although we'd prefer to see it typed. ESSENTIALS OF PROGRAMING LANGUAGES: Section 5.4 In this section, use the interpreter "ch5-4.scm" as a basis for your work. You interact with it as described in the previous section. This interaction will be the same for all the other sections of this chapter. 10. (suggested practice) [add user-defined procedures] Do exercise 5.4.1 in the text. (Use the character string syntax.) 11. (10 points) [square written in defined language] Write the procedure square, which raises an integer to the power 2, in the defined language. The following is an example that should work when your code is substituted in the ... part below. You are *not* allowed to extend the defined language with a primitive to compute square. The idea is to have you write a program in the defined language as a user. (run "let square = ... in cons(square(2), cons(square(3), cons(square(5), cons(square(10), emptylist))))") ==> (4 9 25 100) You'll have to test this on your own. (Hand in a transcript of the testing.) To load the interpreter code from Section 5.4 of the text (on the department machines). (load-from-lib "ch5-4.scm") 12. (10 points) [max written in defined language] Write the procedure max, which computes the maximum of 3 numeric arguments, in the defined language. Like the previous problem, do not add a primitive to the defined langauge, but write the code as a user. The following is an example that should work when your code is substituted in the ... part below. (run "let max = ... in max(1, 72, 5)") ==> 72 Again, you'll have to test this on your own. (Hand in a transcript of the testing.) We expect to see more than just this one test case, which is not itself adequate for testing. 13. (30 points) [make-closure-with-apply] Do exercise 5.4.2 in the text. To do this copy the following files to your directory: $PUB/lib/procedure-as-closure.scm $PUB/lib/procedure-as-closure.def Then, in another file, such as make-closure-with-apply.scm use the following to start your coding. (load-from-lib "ch5-4.scm") (load "procedure-as-closure.scm") ; copy from $PUB/lib and edit this (load-quietly-from-lib "ch5-4-2-denoted-value.scm") (load-quietly-from-lib "ch5-4-2-expressed-value.scm") ;; You need to redefine init-env so that it contains Scheme closures. ;; Put your redefinition of init-env after this line. Write the needed code in procedure-as-closure.scm and redefine init-env so that the interpreter type checks and works. Note that make-closure created a record previously, but now it will be creating a Scheme procedure. Hint: Haven't we seen (the reverse of) this type of program transformation before? Test it yourself first, then use: (test-hw5 "make-closure-with-apply") 14. (20 points, extra credit) [apply-proc variation] Do exercise 5.4.3 in the text. You may need to create your own versions of some of the helpers used in the previous problem. 15. (40 points) [syntax-expand] Do exercises 5.4.4 in the text. Note that the procedure syntax-expand has the type: (-> (parsed-exp) parsed-exp) To test this, you have to be sure that your syntax-expand is loaded after the chapter file (a variation of ch5-4.scm) is loaded; this is because ch5-4.scm loads a version of syntax-expand itself. That is, your code, or testing, should start with the following line. (load-from-lib "ch5-4.scm") Your procedure should handle the the following syntax rules: ::= | | if then else | proc ( ) | ( ) | let in ::= ::= | | , ::= ::= | ( ) ::= | | , ::= = ::= | ; Hints: 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. You'll need a helping procedure. Also, for your own sanity and for the type checking, 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: Section 5.5 Note: In this and the next section, use the interpreter "ch5-5-let.scm" as a basis for your work. 16. (suggested practice) [add cells to the let-interpreter] Do exercise 5.5.1 in the text. Alternatively, put let in the interpreter of Figure 5.5.1. 17. (20 points) [begin] Do exercise 5.5.4 in the text. Note that the parser produces the kind of abstract syntax trees described by the problem already. (So you don't have to change it.) To do this problem, first copy the file $PUB/homework/hw5.tst/begin.scm (which uses ch5-5-let.scm) and then add the semantics of the begin abstract syntax for sequencing expressions. Hint: when I first did this, I got a type error saying that "Expression in begin with ignored result has non-void type" To get around this, use the procedure ignore found in $PUB/lib/ignore.scm. Test it yourself first, then use: (test-hw5 "begin") 18. (10 points) [swapxy in defined language] In the defined language, write a procedure swapxy, that swaps the values in variables x and y, which are global to swapxy. The following is an example that should work when your code is substituted in the ... part below. (run "let x = 3; y = 4 in let swapxy = ... in begin swapxy(); cons(x, cons(y, emptylist)) end") ==> (4 3) You'll have to test this on your own. Hand in a transcript of your testing. Use your solution to Problem 17 as the interpreter. 19. (5 points extra credit) Why doesn't the swapxy procedure in the previous problem take x and y as arguments? 20. (30 points) [multiassign] In this exercise, we'll add the following multiple assignment expression to the defined language. ::= multiassign := | ... The abstract syntax used for a multiple assignment expression is as follows. (define-record multiassign (vars exps)) This abstract syntax is already included in the parser used in $PUB/lib/ch5-5-let.scm. The meaning of a multiple assignment expression is to first evaluate all the operands (in an arbitrary order), and then to assign them to the corresonding varaiables. No value is specified as the value of the multiple assignment expression as a whole. For example, multiassign (x,y) := (3,4) assigns 3 to x and 4 to y. Similarly, multiassign (x,y) := (y,x) swaps the values of the variables x and y. If the number of variables differs from the number of expressions, then the interpreter should give an appropriate error message. Change your solution to problem 17 to handle these multiple assignment expressions. IMPORTANT: Modify your solution to Problem 17 [begin], since the "begin" construct is required by the test cases. Hint: I had to use void->expressed from $PUB/lib/ch5-5-expressed-value.scm to get this to type check. Compare this with the code for varassign. To test this, use (test-hw5 "multiassign"). 21. (30 points) [while] In this exercise, we'll add the following while loop expression to the defined language. ::= while do | ... ::= ::= The abstract syntax used for a while loop expression is as follows. (define-record while (test-exp body)) This abstract syntax is already included in the parser used in $PUB/lib/ch5-5-let.scm. The meaning of a while loop expression is to first evaluate the expression; if that is true, then the expression is evaluated (for its side effects), and then the loop is repeated; if the expression evaluates to false then the loop ends. No value is specified as the value of the while loop expression as a whole. For example, while less(0, x) do x := sub1(x) makes x be 0 (slowly) if x is initially non-negative, and if x is initially negative, it loops forever. Change your solution to problem 17 (or 20) to handle while loop expressions. IMPORTANT: The "begin" construct is required by the test cases. To test this, use (test-hw5 "while") 22. (15 points) [redefine eval-rands for new apply-proc] Do exercise 5.5.3 in the text. Copy the file $PUB/homework/hw5.tst/apply-proc-with-denoted.scm and modify eval-rands to work with the new version of apply-proc. IMPORTANT: Load your solution to Problem 17 [begin] at the top of your new file, since the "begin" construct is required by the test cases. Test it yourself first, then use: (test-hw5 "apply-proc-with-denoted") 23. (25 points) [define] Do exercise 5.5.5 in the text. 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 (and run), all you need to change is the function eval-form; you can modify this from its current definition in the following file. $PUB/homework/hw5.tst/define.scm. You should copy this file to your own directory and edit it to solve the problem. IMPORTANT: Load your solution to Problem 17 [begin] at the top of your file, since the "begin" construct is required by the test cases. To test this, use (test-hw5 "define") Hint: Use the function defined-in-env? found in $PUB/lib/environments.scm to test whether what is being defined is already in the init-env. You may use this procedure without copying the file, since it is already loaded by the file "ch5-5-let.scm" in your solution to [begin]. You are not required to get mutually recursive procedures to work. (See the next problem if you want to do that.) 24. (20 points, extra credit) [define with mutual recursion] In the previous problem, you added define but were not required to get mutually recursive procedures to work. In this problem, adapt your solution to make mutually recursive procedures work. To do this, you may want to use the environment ADT in the file $PUB/lib/updateable-environments.scm, which you will have to load yourself. 25. (15 points, extra credit) [use ribcage to avoid cells] Do exercise 5.5.2 in the text. 26. (20 points, extra credit) [unspecified values printing] Do exercise 5.5.6 in the text. 27. (40 points, extra credit) [mutable and immutable variables] Do exercise 5.5.7 in the text. Also answer the following: what is this like in C++ or Pascal? 28. (25 points, extra credit) [optimized mutable variables] Do exercise 5.5.8 in the text. 29. (65 points, extra credit) [denotational-style stores] Do exercise 5.5.9 in the text. ESSENTIALS OF PROGRAMING LANGUAGES: Section 5.6 30. (20 points, extra credit) [add letrecproc] Do exercise 5.6.1 in the text. You can get the environment ADT from $PUB/eopl/sources.ss. 31. (25 points, extra credit) [add letrec] Do exercise 5.6.2 in the text. 32. (20 points, extra credit) [wrapping cells around closures] Do exercise 5.6.3 in the text. 33. (25 points, extra credit) [efficiency issues] Do exercise 5.6.4 in the text. 34. (40 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 do the expansion of letrecproc. 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 expand "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. (IMPORTANT: be sure to have an "else" clause in your variant-case like the ones from the interpreters in the book, as this is needed for type checking and debugging.) Test it yourself first, by loading ch5-5-let.scm and then your code; then use: (test-hw5 "letrecproc-expand") Hint: (parse "begin e1; e2; e3; e4 end") = (make-begin (parse "e1") (make-begin (parse "e2") (make-begin (parse "e3") (parse "e4")))) For example, (parse "begin x; 1; 2; z; y end") = #(begin #(varref x) #(begin #(lit 1) #(begin #(lit 2) #(begin #(varref z) #(varref y))))) b. What is the difference between the semantics of letrec shown on page 163 and the semantics given above? (This part can be handwritten, although we'd prefer to see it typed.) 35. (suggested practice) Write a version of list-index in the defined language, using letrecproc to define the helping procedure. 36. (15 points, extra credit) Implement the semantics shown on page 163. ESSENTIALS OF PROGRAMING LANGUAGES: Section 5.7 37. (suggested practice) [add dynamic scoping] Do exercise 5.7.1 in the text. 38. (10 points) [examples of dynamic scoping] 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, and should not just differ in the names of variables or numbers. b. Use the interpreter with dynamic scoping, by running (load-from-lib "ch5-7-1.scm") to show what your example does with dynamic scoping. (If you are working on this problem before we have released our solution to syntax-expand-let, then this interpreter won't be expanding let properly. To use let with the interpreter, load your solution to problem 15 (syntax-expand) after you load the interpreter, or expand each let by hand.) 39. (20 points) [fact with dynamic scoping] Do exercise 5.7.2 in the text. Turn in your defined language code, and a transcript of testing it with the interpreter that you get by running (load-from-lib "ch5-7-1.scm") (Note that the problem is asking you to write out the desugared version of a let, which you will need to do before we release our solution to problem 15 (syntax-expand). Note that let x = 3 in +(x,x) desugars to (proc(x) +(x,x))(3) in the defined language. If you are working on this after we release our solution to problem 15, then you can just run the test using a let.) 40. (suggested practice) [add environment stack] Do exercise 5.7.3 in the text. 41. (25 points, extra credit) [procedures done with Scheme and dynamic] Do exercise 5.7.4 in the text. 42. (50 points, extra credit) [shallow binding] Do exercise 5.7.5 in the text. 43. (10 points) [understanding dynamic scoping] Do exercise 5.7.6 in the text. Explain how the answer came to be. (This can be handwritten, although we'd prefer to see it typed.) 44. (10 points) [understanding dynamic assignment] Do exercise 5.7.7 in the text. Briefly justify your answer. (This can be handwritten, although we'd prefer to see it typed.) 45. (30 points) [letdynamic] a. (25 points) Do exercise 5.7.8 in the text. IMPORTANT: Copy your solution for Problem 17 [begin] to a new file, and then add the semantics of the letdynamic abstract syntax as specified in the exercise. Test it yourself first, then use: (test-hw5 "letdynamic") b. (5 points) Why start with the solution for Problem 17? Why not start with the ch5-7-1.scm interpreter? 46. (40 points, extra credit) [dynassign via syntax-expand] Do exercise 5.7.9 in the text. 47. (10 points) What are the advantages of a language with dynamic assignment versus one with dynamic scoping? Explain. This can be handwritten. 48. (10 points) a. Does C++, Java, (or Ada, Pascal, BASIC, ...) have any feature like dynamic scoping? Briefly explain, using an example if possible. State what language you are using!