Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Com S 342 --- Principles of Programming Languages HOMEWORK 9: ENVIRONMENT PASSING INTERPRETERS III (File $Date: 2006/10/23 20:35:35 $) Due: problems 3-5,8-10 at beginning of class, Tuesday, November 14, 2006. In this homework, you will learn more about interpreters, including recursion, 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 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 probems, 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!). 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.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 better. 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. 3. Roughly following exercise 3.42 on page 105 of the text, your task in this problem is to 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. a. (40 points) [arrays] 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/homework/hw9/my-3-7.scm my-3-7.scm This file has been adapted from ch3-7.scm in the library by adding arrays to the domain of expressed values. These changes have made the domain equations contain: Expressed-Value = Number + ProcVal + List(Expressed-Value) + Arr Arr = (Ref(Expressed-Value))* We have also made my-3-7.scm require the file "indirect-arrays.scm" from the course library. This library file defines a datatype for array values. You should read the code there, and consult the section on vectors in the Revised^5 Report on Scheme, if need be, to see what this code does. Your task is to edit the code in my-3-7.scm file to add the primitives "array", "arrayref", "arraylen", and "arrayset" to the defined language. First, add the grammar and the abstract syntax these four primitives. Then add their semantics, by modifying apply-primitive. The four primitives are specified as follows. For all numbers n, for all arrays a, for all expressed values v, array(n) is a fresh 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 non-negative integers n, for all arrays a of length n, 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 arraylen(a) == begin arrayset(a, i, v); arraylen(a) end 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 After changing the apply-primitive procedure, you can test your solution using: (test-hw9 "arrays") 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. b. (5 points) [arrays question] Answer the question at the end of exercise 3.42 in the text. (Note that that question has a syntax error: the expression p(a) should be (p a) in the body of the begin.) Check your answer by running your code for part a. 4. [ref] (a) (30 points) Do exercise 3.43 on page 105. For this problem, work in the file my-3-7.scm that you worked on for the previous problem. To solve the problem, you'll have to change the interpreter's grammar to add the "ref" expression and to add the "deref" and "setref" primitives. You also must make similar changes to the abstract syntax. The change to the domain of Expressed-Values is as follows: Expressed-Value = Number + ProcVal + List(Expressed-Value) + Arr + Ref(Expressed-Value) After changing the concrete and abstract syntax, in this problem 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 two 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 +(+(*(x,100), *(rx,10)), srv) would return 550. You can test your code with (test-hw9 "ref") 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, using (show-test-output!) before running the tests). 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/lib342/ch3-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. (50 points) [call by value-result] Do exercise 3.55 on page 114 of the text. However, as with call by reference, we won't consider it an error to pass an expression as an argument; instead we will assume that a new location (i.e., a direct target) is created to hold such arguments, and thus a call such as (f add1(c)) will copy the value of add1(c) into the formal, but the actual will be copied back to this new location instead of into any previously existing variable's location (i.e., the variable c won't be affected). To start, change to a directory of your own, and then copy a non-module version of the section 3.8 call-by-reference interpreter, as follows: cp $PUB/homework/value-result.scm value-result.scm There are no grammar changes for this problem. The domains are also unchanged. You just have to change the interpreter to use call by value-result as described in the problem. It may help to look at the test cases in $PUB/homework/hw9/value-result.tst to understand this better. For the implementation, it's very helpful to think about the types and the way that refrences and targets are used in the implementation of call by reference. Then think about what you want to do, in apply-procval, to copy the arguments' values to new targets, execute the procedure body, and then copy the values back to the original argument targets at the end. (Hint: I found it helpful to reuse some of the code of deref, by making a helping procedure from part of it, and having deref call that.) You can test this problem using (test-hw9 "value-result") Hand in a printout of your changes to the interpreter 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. Since arrayref is a primitive, 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 have added a new access expression to the language.