Com S 342 --- Principles of Programming Languages HOMEWORK 10: ENVIRONMENT PASSING INTERPRETERS IV (File $Date: 2006/11/13 22:17:24 $) Due: problems 1-3 at beginning of class, Tuesday, November 28, 2006; problems 4,6-9 at beginning of class, Tuesday, December 5, 2006. In this homework, you will learn more about interpreters, including call by name, call by need, and statement-oriented languages. For coding problems for which we provide test cases, hand in: - a printout of the code with your name in a comment, and - if our tests reveals any errors with your code for that problem, then include a transcript showing a run of our tests. That is, you only have to hand in output of your testing if it reveals problems in your code (that you have not fixed). We expect you to run our tests for each problem, but since the output in the case where the tests all pass is not very interesting, we will trust you to have done this. However, you must hand in a transcript of your testing if your code does *not* pass our tests perfectly, as this will alert us to the problem and will help us assign partial credit. If we find that your code is not correct and the problem would have been revealed by our testing, but you did not hand in test results showing these problems, then you will receive 0 points for that problem. You may also hand in a transcript that includes our tests if you wish. See the directory $PUB/homework/hw9 for test scripts for each coding problem. Use the procedure test-hw9 to run our tests. If you want to see more output, execute (show-test-output!); to see less output, execute (hide-test-output!). 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. 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/ch3-8need.scm. You can load these interpreters by using (require (lib "ch3-8need.scm" "lib342")) a. (5 points) Does this interpreter evaluate the right hand sides of let expressions in a lazy or eager fashion? (Hint: look at the code for the interpreter!) b. (5 points) Using this interpreter, write a test program in the defined language that clearly demonstrates your answer to part (a) in the sense that would have different behavior if it were not evaluated as your answer to part (a) claims. 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. c. (5 points) Do one of the following, depending on your answer to part (a). - (eager) If your answer for part (a) is that the right-hand sides of let-expressions are evaluated eagerly, then demonstrate that your code for part (b) has different behavior if you desugar the let expression(s) in your code to be applications of procedures. Do this by desugaring your code for part (b) and run the desugared version using the ch3-8need.scm interpreter to prove that it has different behavior. In this case, hand in a printout of your two defined language programs and their output (if any). - (lazy) If your answer for part (a) is that the right-hand sides of let-expressions are evaluated lazily, then your code for part (b) should have different behavior when run under the ch3-8ref.scm interpreter (which uses eager evaluation). So run your code for part (b), unchanged, using the ch3-8ref.scm interpreter to prove that it has different behavior. In this case, hand in a printout of your defined language program and its output (if any) under both interpreters. 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 (since you are doing the testing yourself) 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, such as "ifThen" or "unless"? That is, can users write a procedure that affects the flow of control, deciding when to evaluate arguments or not evaluate them, or do then need macros to do that? Briefly explain. 4. (40 points) [conz, caz, cdz, random] Do exercise 3.61 on page 119 of the text. To start, copy $PUB/homework/hw10/my-3-8need.scm to your directory, as in cp $PUB/homework/hw10/my-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. Test this problem's solution using (test-hw10 "conz-caz-cdz") Hand in a printout of your changes to the interpreter. 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 ch3-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 ch3-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". Hand in a printout of your code and a transcript of your testing that demonstrates the proper eager or lazy behavior. 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/homework/hw10/my-3-9.scm to your directory, as in cp $PUB/homework/hw10/my-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") However, you can wait to print out your code, until you are done with the problems in this section. Remember to 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. Hand in printout of your testing for this problem, along with a printout of your code. However, you can wait to print out your code, until you are done with the problems in this section. Remember to 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 ch3-9.scm interpreter so that expressions cannot have side effects; that is, after your grammar change, each expression, E, cannot change the values of any variable locations that exist before the execution of E. Note that, since procedures have an expression in their body, procedures will also be unable to have side effects when called. (Hint: This problem is easy and mainly conceptual. Think about what ultimately causes side effects in expressions? Is there any redundancy between statements and expressions in the grammar of the defined language?) Describe your changes and why they work 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. Your for-loop statement must include setting a variable that can be accessed in the body of the loop; for example, this should let you print the numbers from 1 to 20 easily. You are responsible for the details of your for-loop's syntax and semantics. Briefly describe any decisions you made in a separate write-up or in a prominent comment. Note: you will lose points if your for loop is just a while loop with different syntax; it should automate as much as possible for its users. That is, the for-loop should (as noted above) initialize a variable that is accessible in the loop body by just using its name, and it should take care of incrementing and testing that variable for users. Something like the Java/C++/C for-loop is fine. If you have trouble with the syntax in SLLGEN, email the staff and include an example of what the loops should look like. In general, adding more keywords (at appropriate places) will help SLLGEN be able to do the parsing. Since the syntax and semantics are your own, you will have to test this yourself. Hand a printout of your code and your testing.