Com S 342 --- Principles of Programming Languages HOMEWORK 5: INTERPRETERS (File $Date: 96/11/01 19:46:04 $) Due: problems 1,4-6 at beginning of class, November 11; problems 8,12,13,14,16 at beginning of class, November 15; problems 18-20,21,31 at beginning of class, November 22. problems 35,36,40-42,44-45 at beginning of class, December 6. (Note: On Dec. 6, you will also have problems from Homework 6 due...) 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. Recall that $PUB means /home/cs342/public.) The section headings below give the readings related to the problems. ESSENTIALS OF PROGRAMING LANGUAGES: Sections 4.5-6 The problems in this section can be handwritten. 1. (5 points) In what way is an object in C++ like a closure in Scheme? 2. (suggested practice) Are variables in Scheme first-class objects? Are variables in C++ (or C, or Pascal) first-class objects? Explain. 3. (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 IMPORTANT: In this section, use the interpreter "ch5-1.scm" as a basis for your work. 4. (10 points) [transcripts for run and read-eval-print with 5 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.) 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, 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. Hand in a transcript that shows (a) how you used the run procedure and (b) how you used the read-eval-print procedure. To show you can work with the defined language's grammar, at least one input to each interpreter should have 5 commas (`,' characters) in it. Circle this input 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. Test it yourself first, using either the run procedure or the read-eval-print loop as in problem 4. Then use: (test-hw5 "minus") and (test-hw5 "lists") to do the final testing. Copy the file `$PUB/homework/hw5.tst/primitives.scm' and add your code to this file. (Hint: in Scheme, (- 3) returns -3.) ESSENTIALS OF PROGRAMING LANGUAGES: Sections 5.2 IMPORTANT: 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 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") ESSENTIALS OF PROGRAMING LANGUAGES: Section 5.3 IMPORTANT: In this section, use the interpreter "ch5-3.scm" as a basis for your work. 7. (suggested practice) [add let] Do exercise 5.3.1 in the text. (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. 8. (10 points) [calculate 2^16] Write an expression in the defined language to calculate 2^16, that is 2 to the 16th power, using only let, *, variable names, and the number 2. For Secton 5.3, use the following to load the interpreter code from Section 5.3 of the text (on the department machines). (load-from-lib "ch5-3.scm") 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 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. Because of the implementation, you cannot use both run and read-eval-print at the same time. Hand in a transcript showing that your program works. 9. (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 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 5 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 5, send email to cs342s@cs.iastate.edu for a solution.) 10. (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. ESSENTIALS OF PROGRAMING LANGUAGES: Section 5.4 IMPORTANT: In this section, use the interpreter "ch5-4.scm" as a basis for your work. 11. (suggested practice) [add user-defined procedures] Do exercise 5.4.1 in the text. (Use the character string syntax.) 12. (10 points) [thirdPower written in defined language] Write the procedure thirdPower, which raises an integer to the power 3, 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 thirdPower. The idea is to have you write a program in the defined language as a user. (run "let thirdPower = ... in cons(thirdPower(3), cons(thirdPower(5), cons(thirdPower(10), emptylist)))") ==> (27 125 1000) 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") 13. (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 You'll have to test this on your own. 14. (25 points) [user-defined procedures with apply] Do exercise 5.4.2 in the text. Use the following outline for your code: (load-from-lib "ch5-4.scm") (define apply-proc ; TYPE: (-> (proc (list Expressed-Value)) Expressed-Value) (lambda (proc args) (apply proc args))) (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 a procedure. Hint: Haven't we seen this type of program transformation before? Test it yourself first, then use: (test-hw5 "make-closure-with-apply") 15. (15 points, extra credit) [apply-proc variation] Do exercise 5.4.3 in the text. 16. (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. Also, for your own sanity, 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 IMPORTANT: In this and the next section, use the interpreter "ch5-5-let.scm" as a basis for your work. 17. (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. 18. (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. Test it yourself first, then use: (test-hw5 "begin") 19. (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 18 as the interpreter. 20. (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 18 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") 21. (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. Copy the file $PUB/homework/hw5.tst/define.scm. IMPORTANT: Load your solution to Problem 18 [begin] at the top of your new file since the "begin" construct is required by the test cases. To test this, use (test-hw5 "define") 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. 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; however, if you wish to do that, you might want to use the environment ADT in the file $PUB/lib/updateable-environments.scm, which you will have to load yourself. We will give you 20 points extra credit, if you do mutually recursive procedures; you will have to show that by additional testing.) 22. (15 points, extra credit) [use ribcage to avoid cells] Do exercise 5.5.2 in the text. 23. (20 points, extra credit) [unspecified values printing] Do exercise 5.5.6 in the text. 24. (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? 25. (25 points, extra credit) [optimized mutable variables] Do exercise 5.5.8 in the text. 26. (65 points, extra credit) [denotational-style stores] Do exercise 5.5.9 in the text. ESSENTIALS OF PROGRAMING LANGUAGES: Section 5.6 27. (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. 28. (25 points, extra credit) [add letrec] Do exercise 5.6.2 in the text. 29. (20 points, extra credit) [wrapping cells around closures] Do exercise 5.6.3 in the text. 30. (25 points, extra credit) [efficiency issues] Do exercise 5.6.4 in the text. 31. (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 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 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.) Test it yourself first, 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.) 32. (suggested practice) Write a version of list-index in the defined language, using letrecproc to define the helping procedure. 33. (15 points, extra credit) Implement the semantics shown on page 163. ESSENTIALS OF PROGRAMING LANGUAGES: Section 5.7 34. (suggested practice) [add dynamic scoping] Do exercise 5.7.1 in the text. 35. (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 19 (syntax-expand) after you load the interpreter, or expand each let by hand.) 36. (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 19 (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 19, then you can just run the test using a let.) 37. (suggested practice) [add environment stack] Do exercise 5.7.3 in the text. 38. (25 points, extra credit) [procedures done with Scheme and dynamic] Do exercise 5.7.4 in the text. 39. (50 points, extra credit) [shallow binding] Do exercise 5.7.5 in the text. 40. (10 points) [understanding dynamic scoping] Do exercise 5.7.6 in the text. Explain how the answer came to be. (This can be handwritten.) 41. (10 points) [understanding dynamic assignment] Do exercise 5.7.7 in the text. Briefly justify your answer. (This can be handwritten.) 42. (30 points) [add letdynamic] Do exercise 5.7.8 in the text. IMPORTANT: Copy your solution for Problem 18 [begin] and then add the semantics of the letdynamic abstract syntax as specified in the exercise. Test it yourself first, then use: (test-hw5 "letdynamic") 43. (40 points, extra credit) [dynassign via syntax-expand] Do exercise 5.7.9 in the text. 44. (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. 45. (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.