Com S 342 --- Principles of Programming Languages HOMEWORK 8: ENVIRONMENT PASSING INTERPRETERS III (File $Date: 2004/04/21 22:16:05 $) Due: problems 3-5,8 at beginning of class, Thursday, April 22, 2004; problem 9 at beginning of class, Tuesday, April 27, 2004. In this homework, you will learn more about interpreters, including variable assignment and call by reference. 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/hw8 for test scripts for each coding problem. (You can use the procedure test-hw8 to run our tests, as described in homework 1.) You should have a transcript that clearly shows testing for each problem. Unless noted otherwise, your code should type check without error (without using has-type-trusted or trustme!). 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 language 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 them. Refer to homework 6 for some ideas to help aid your understanding when reading chapter 3 of the text. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 3.7 1. (suggested practice) Think about how you would do exercise 3.39 on page 104 of the text. This is already implemented in our interpreters, but using the funky named lambda feature of Scheme, so you might want to implement it yourself using the parts of Scheme you understand. 2. (suggested practice) Do exercise 3.40 on page 104 of the text. Note that this is different than the implementation of define in homework 7, although it can use the same or a similar grammar. The difference is that there is an assignment that can take place for redefinitions. named lambda feature of Scheme, so you might want to implement it yourself using the parts of Scheme you understand. 3. (40 points) [arrays] As in exercise 3.42 on page 105 of the text, we will add arrays to the defined language of section 3.7. This is done using 4 new primitives in the defined language: array, arrayref, arraylen, and arrayset. To do this, first change to a directory of your own where you want to keep files for these problems, and then do the following to copy files to this directory: cp $PUB/lib/3-7.scm my-3-7.scm cp $PUB/homework/hw8/my-3-7-grammar.scm my-3-7-grammar.scm cp $PUB/homework/hw8/my-3-7-expressed-value.scm my-3-7-expressed-value.scm cp $PUB/homework/hw8/indirect-arrays.scm indirect-arrays.scm Now change my-3-7.scm so that it loads your files, i.e., change the line (load-quietly-from-lib "3-7-grammar.scm") to (load "my-3-7-grammar.scm") and change the line (load-quietly-from-lib "3-7-expressed-value.scm") to (load "my-3-7-expressed-value.scm") and in the line just before that add the line (load "indirect-arrays.scm") so that the interpreter will use your files instead of the ones from the library and so it will use the abstract array values. Now edit the code in my-3-7.scm file to add the primitives array, arrayref, arraylen, and arrayset to the defined language. These are specified as follows. For all numbers n, for all arrays a, for all expressed values v, array(n) is an array of n elements, where each element in the result is the expressed value 0 arrayref(a, n) is the nth, zero-indexed element of a arrayset(a, n, v) changes the value of the nth, zero-indexed element of a to be v, and returns 0 arraylen(a) is the length of a Thus we have the following equations between terms in the defined language for all numbers n, for all arrays a, for all expressed values v, for all i such that 0 <= i and i < n, and for all j such that 0 <= j and j < n: arraylen(array(n)) == n, arrayref(array(n), i) == 0 arrayset(a, i, v) == 0 begin arrayset(a, i, v); arraylen(a) end == arraylen(a) begin arrayset(a, i, v); arrayref(array(a, j)) end == if -(i,j) % i.e., if i is not equal to j then arrayref(a, j) else v You will have to change the define-datatype for primitive and the apply-primitive procedure. Use the ADT for arrays given in the indirect-arrays.scm file to make your code type check. You can test your solution using: (test-hw8 "arrays") 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. You don't need to answer the question at the end of this exercise (which has a syntax error: p(a) should be (p a) in the body of the begin). 4. [ref] (a) (30 points) Do exercise 3.43 on page 105. The changes to the grammar are provided in my-3-7-grammar.scm (see problem 3 above). The changes to the domain of expressed-values are also included in my-3-7-expressed.scm (see problem 3 also). So you just have to add a treatment of the ref expression, and the deref and setref primitives to the interpreter in my-3-7.scm. To explain the semantics of these primitives a bit more, note that the ref expression is supposed to return a reference (pointer essentially) to a variable. It's like the C language's & operator. The deref expression obtains the value from a reference, like the C language's * operator (not multiplication, but dereference as in *p). Thus deref(ref x) has the same value as the variable x. The setref primitive sets the value pointed to by a reference, which is like a combination of * and = in C. We define the value returned by calling the setref primitive to be 0. For example, let x = 3 in let rx = ref x in let srv = setref(rx, 5) in list(srv, deref(rx), x) would return the list (0 5 5), if you had the list primitive available, which you don't for this problem. You can test your code with (test-hw8 "ref") As always hand in a printout of a transcript of your testing and your code. This is the time to print your code for this section. Please clearly mark with comments the part of the code used to solve this problem (and the previous one). (b) (10 points) Write answers to the two (English) questions at the end of exercise 3.43 on page 105. (Hint for the first question: look at the test output). 5. (10 points) [recursion using two passes and assignment] Do exercise 3.44 on page 106 of the text. Just describe how this translation works to produce the right answer. In particular, describe how the closure formed for times4 in the translation gets the right environment. You don't have to write any code for this. 6. (suggested practice) [setdynamic] Do exercise 3.47 on page 107 of the text. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 3.8 7. (suggested practice) Read and play with the code for the call by reference interpreter in $PUB/lib/3-8ref.scm. 8. [drawing pictures for call by reference] (a) (20 points) Draw 2 pictures, corresponding to the state of the expression when execution reaches the places indicated by the comments in the code. Your pictures should be like those shown in class. In this problem use call by reference. let a0 = 342 a1 = 541 in let i = 100 in let f = proc(x,b0,b1) begin %% Draw the first picture for this point set x = +(9,i); set a0 = i; set b1 = b0 end in begin (f i a0 a1); %% Draw the second picture for this point +(*(100000,i),+(*(1000,a0),a1)) end (b) (10 points) Give the output of the above expression, using call by reference. (You should do this by hand, and only use the computer to check the answer.) 9. (30 points) [drawing pictures for call by value result] Repeat the previous problem using call by value result. Call by value result is described in exercise 3.55 on page 114. 10. (suggested practice) [call by value-result] Do exercise 3.55 on page 114 of the text. To start, change to a directory of your own, and then make your own copy of the section 3.6 interpreter basis as follows: cp $PUB/lib/3-8ref.scm my-3-8value-result.scm There are no grammar changes for this problem. Hand in a printout of your changes to the interpreter and a transcript of your testing. 11. (suggested practice) [call by reference with arrays] Do exercise 3.54 in the text. Note that the example in the exercise at the end, (swap (arrayref a i) (arrayref a j)) has the wrong syntax, as arrayref is not a user-defined procedure. If arrayref is a primitive, then the syntax of the example should instead be: (swap arrayref(a,i) arrayref(a,j)). However, can arrayref really be a primitive for this problem? The alternative is to make it an expression, and then the syntax would look, perhaps, like: (swap access(a,i) access(a,j)) where you add access expressions to the language. Hand in a printout of your changes to the interpreter and a transcript of your testing.