Com S 342 --- Principles of Programming Languages HOMEWORK 10: ENVIRONMENT PASSING INTERPRETERS IV (File $Date: 2005/04/12 22:43:39 $) Due: problems 1-3 at beginning of class, Thursday, April 14, 2005; problems 4,6-9 at beginning of class, Tuesday, April 19, 2005. In this homework, you will learn more about interpreters, including call by name, call by need, and statement-oriented languages. For this homework, be sure to clearly mark what parts of the code you changed (e.g., with a comment in the Scheme code) to solve what problems. For coding problems, aside from your printout of the code, you must also hand in a transcript of testing. See the directory $PUB/homework/hw10 for test scripts for each coding problem. Use the procedure test-hw10 to run our tests. If you want to see more output, execute (show-test-output!); to see less output, execute (hide-test-output!). The section headings below give the readings related to the problems. Please read them. Refer to homework 7 for some ideas to help aid your understanding when reading chapter 3 of the text. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 3.8, pages 115-119 1. [let-semantics] Consider the call by need interpreter in $PUB/lib342/3-8need.scm. You can load this by using (load-from-lib "3-8need.scm") a. (5 points) Does this interpreter evaluate the right hand sides of let expressions in a lazy or eager fashion? How can you tell? b. (5 points) Using this interpreter, write a test program in the defined language that demonstrates your answer to part (a). You may wish to use the "run" procedure provided by the interpreter for writing your code. For example, (run "") This has the advantage that you can more easily edit mistakes in your defined language program. Hand in a printout of your defined language program and its output, if any. 2. (10 points) [unless] Using the defined language of the 3-8need.scm interpreter, write a procedure, "unless", that takes two arguments, test and body, and is such that it evaluates the body if and only if the test has the value 0 (i.e., the value representing false in the defined language). (If the body is not evaluated, the result of the call to unless itself should be 0.) The following are examples in the defined language: --> let unless = proc ... in let x = 3 in begin (unless 0 set x = 1); x end 1 --> let unless = proc ... in let x = 3 in begin (unless +(x,1) set x = 1); x end 3 --> let unless = proc ... in letrec ohno() = (ohno) in begin (unless 1 (ohno)); 5 end 5 Run the tests above and any other tests you think appropriate, where the "..." in each case is your procedure for "unless". Note that you are not supposed to change the interpreter for this problem. Hand in a printout of your defined language program and its testing. 3. (5 points) [are macros needed?] Does a language with lazy evaluation need to have macros (as in the C or C++ #define facility) to allow users to write their own definitions of control structures ? Briefly explain. 4. (50 points) [conz, caz, cdz, random] Do exercise 3.61 on page 119 of the text. To start, copy $PUB/lib342/3-8need.scm to your directory, as in cp $PUB/lib342/3-8need.scm my-3-8need.scm The problem is to implement the 4 primitives in your copy of the call-by-need interpreter: conz, caz, and cdz are lazy versions of cons, car, and cdr. The primitive "random" can be implemented using Scheme's built-in procedure "random", which has type: (-> (number) number) You will need to add to the concrete syntax for these 4 primitives and to the abstract syntax, and then add code to apply-primitive for these 4 primitives. You will also need to change the way that the interpreter handles primitives so that the arguments are not evaluated too early. You don't have to make changes to the expressed value domain and helping procedures for this problem, although you may if you wish. Although the file $PUB/lib342/3-8-expressed-value.scm already supports lists as expressed values, if you follow the suggested strategy for representing lazy lists as procedures (see Figure 3.22), you won't be using the list domain, but rather procvals to represent the result of applying conz. Some hints: Think about what the code in figure 3.22 does. Note that the code for conz in figure 3.22 has no free variables. Note also that it is not necessary for the result of conz to print as a normal list; it does not in our implementation. Hand in a printout of your changes to the interpreter and a transcript of your testing. You can test this problem using (test-hw10 "conz-caz-cdz") 5. (20 points; extra credit) [strict or lazy let] What you are to do in this problem depends on your answer to problem 1. If you believe that the "let" expressions in the 3-8need.scm interpreter are lazy, then add new syntax for "strictlet" to the interpreter and implement it so that strictlet is strict (eagerly evaluated). The new syntax should be exactly like the syntax for "let", except that it should use the keyword "strictlet" instead of "let". If, instead, you believe that the "let" expressions in the 3-8need.scm interpreter are strict (eagerly evaluated), then add new syntax for "lazylet" to the interpreter and implement it so that it is lazyily evaluated. The new syntax should be exactly like the syntax for "let", except that it should use the keyword "lazylet" instead of "let". As always hand in a printout of a transcript of your testing and your code. However, you can wait to print out your code, until you are done with the problems in this section. If you do that, clearly mark with comments the part of the code used to solve this problem. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 3.9 6. (15 points) [do-while] Do exercise 3.63 on page 121 of the text. To start, copy $PUB/lib342/3-9.scm to your directory, as in cp $PUB/lib342/3-9.scm my-3-9.scm Then add the following syntax for the do-while statement to the interpreter. (statement ("do" statement "while" expression) do-while-statement) You will then need to add appropriate abstract syntax, and finally implement this in execute-statement. You can test your solution using: (test-hw10 "do-while") As always hand in a printout of a transcript of your testing and your code. However, you can wait to print out your code, until you are done with the problems in this section. If you do that, clearly mark with comments the part of the code used to solve this problem. 7. (15 points) [assert statement] To your copy of the 3.9 interpreter, add an assert statement, with the following syntax: (statement ("assert" expression) assert-statement) You will then need to add appropriate abstract syntax, and finally implement this in execute-statement. An assert statement first evaluates the expression. If the expression evaluates to 0, then a message is printed, and the interpreter stops executing the program (you should call either error or eopl:error to achieve this effect). Otherwise, execution continues following the assert statement with no other effects. Since our test harness is not capable of testing errors, you will have to test this yourself. As always hand in a printout of a transcript of your testing and your code. However, you can wait to print out your code, until you are done with the problems in this section. If you do that, clearly mark with comments the part of the code used to solve this problem. 8. (15 points) [side-effect free expressions] Make changes to the grammar in your copy of the 3-9.scm interpreter so that expressions cannot have side effects; that is, after your grammar change, each expression, E, should not be able to change the values of any variable locations that exist before the execution of E. (Thus, calling a procedure does not necessarily have side effects.) Describe these changes in a prominent comment or in a separate write-up so that we can see what they are easily. 9. (40 points) [for loops] Design and implement a for-loop statement and implement it in your copy of the section 3.9 interpreter. You are responsible for its syntax and semantics. Briefly describe any decisions you made in a separate write-up or in a prominent comment. You will have to test this yourself.