Com S 342 --- Principles of Programming Languages HOMEWORK 6: PARAMETER PASSING (File $Date: 1998/12/03 21:02:18 $) Due: problems 2-5,8-10 at beginning of class, December 2; problems 13-16 at beginning of class, December 4; problems 17,18,20-21 at beginning of class, December 7. In this homework, you will learn about various array (and object) models and parameter passing mechanisms. These are basic dimensions along which languages may vary, and will help you use the languges you know better, and to learn new languages faster. For code hand in *both* your printout of the Scheme code and a transcript of testing. See the directory $PUB/data/hw6/hw6.tst for test data for each coding problem. (You can use the procedure test-hw6 to run our tests, as described in homework 1.) Unless noted otherwise, your code should type check without error, and without changing any .def files we give you or writing your own .def files. The section headings below give the readings related to the problems. Please read them in the revised chapter 6, found in very recent printings of the text (such as the 6th or later printing). If in doubt, check the file $PUB/eopl/ch6.ps (or from the course web page) against your book's chapter 6 to be sure they match. You can view it without printing it by using the Unix command ghostview, or from a web browser. If you don't have this version in your text, you should read it from this file. Note that it is a postscript file, and so if you want to print it, you must do so on a postscript printer (or use a program like Adobe Acrobat). Note for emacs users: it seems that comments in the defined langauge 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. Note that no late homework will be accepted after December 4. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 6.1 1. (suggested practice) [play with the indirect array interpreter] Do exercise 6.1.1. You can get this interpreter by executing: (load-from-lib "ch6-1-3.scm") 2. (30 points) [drawing pictures for call by value with indirect array model] In this exercise, use the indirect array model. (a) Draw 2 pictures, corresponding to the state of the expression below at the places indicated by the comments in the code. Your pictures should be like those shown in class (or the revised chapter 6). (b) Give the output of the expression. (You should do this by hand, and only use the computer to check the answer.) let skip = % TYPE: (-> (T) void) proc(x) % EFFECT: do nothing x := x in letrec init3 = % TYPE: (-> ((array integer) integer integer) void) proc (a, e, i) % EFFECT: make a[i] be e, a[i+1] be e+1, and a[i+2] be e+2 if equal(i, 3) then skip(i) else begin a[i] := e; init3(a, +(1,e), +(1,i)) end; write3 = % TYPE: (-> ((array T) integer) void) proc(a, i) % EFFECT: print a[i], a[i+1], ... if equal(i, 3) then newline() else begin write(a[i]); space(); write3(a, +(i,1)) end in letarray a[3]; b[3]; c[3] in begin a[0] := 0; a[1] := 0; a[2] := 0; b[0] := 0; b[1] := 0; b[2] := 0; c[0] := 0; c[1] := 0; c[2] := 0; init3(a, 0, 0); init3(b, 342, 0); init3(c, 541, 0); %%% picture (i): show what the arrays a, b, and c look like here let p = proc(x, y, z) begin x := y; y := z; z := x; x[0] := y[0]; y[0] := x[1]; z[0] := x[1]; x[0] end in begin p(a, b, c); %%% picture (ii): show what arrays a, b, and c look like here write3(a, 0); write3(b, 0); write3(c, 0) end end 3. (20 points) [drawing pictures for call by value with indirect array model] In this exercise, use the indirect array model. (a) Draw a picture, corresponding to the state of the expression below at the place indicated by the comment in the code. (b) Give the output of the expression. (You should do this by hand; only use the computer to check the answer.) letarray a[2]; b[2] in begin a[0] := 10; a[1] := 11; b[0] := 20; b[1] := 21; let x = 3 in let p = proc(c,e,v,w) begin b[0] := v; a := c; v := e; w := x; %%% draw a picture for this point c[0] end in let r = p(b,a[1],x,b[0]) in list(r, a[0], a[1], b[0], b[1], x) end 4. (10 points) [arraymapin in defined language] In the defined language, using the "ch6-1-3.scm" interpreter, define a procedure arraymapin : (-> ((-> (S) T) (array S)) void) that takes a procedure, p, and an array a, and modifies the array so that a[i] holds the value of the former p(a[i]). (You are prohibited from adding a new primitive to the interpreter to solve this problem.) The following defines two helping procedures, and then gives two examples. define writearray = % TYPE: (-> ((array T) integer) void) proc(a, i) % REQUIRES: 0 <= i <= arraylength(a) % EFFECT: print a[i], a[i+1], ... a[len-1] if equal(i, arraylength(a)) then newline() else begin write(a[i]); space(); writearray(a, +(i,1)) end; define arraygenerator = % TYPE: (-> ((-> (integer) T)) % (-> (integer) (array T))) proc(f) proc(len) % EFFECT: return an array of size len, where the ith % element is f(i) letarray res[len] in letrec loop = % TYPE: (-> (integer) (array T)) proc(i) if equal(i, len) then res else begin res[i] := f(i); loop(add1(i)) end in loop(0); begin let v = (arraygenerator(proc(i) i))(7) in begin writearray(v, 0); % prints: 0 1 2 3 4 5 6 arraymapin(proc(e) *(e,e), v); writearray(v, 0) % prints: 0 1 4 9 16 25 36 end; let u = (arraygenerator(proc(i) 0))(5); timescalled = let count = 0 in proc(e) begin count := add1(count); count end in begin writearray(u, 0); % prints: 0 0 0 0 0 arraymapin(timescalled, u); writearray(u, 0) % prints: 1 2 3 4 5 end end Note that you need to give your definition of arraymapin to the interpreter before you use the examples above. Hint: study the definition of writearray carefully. Test your solution using either run or the read-eval-print loop. If you use the read-eval-print loop, cut out the above text, and paste it as the input to the interpreter. If you use run, you will have to pass each of the top-level defines separately to the interpreter, taking out the semicolons at the end of each top-level define. Then you can pass the whole begin as one big string to run. In either case hand in a printout of your procedure and testing. 5. (10 points) [arraymult in the defined language] In the defined language, using the "ch6-1-3.scm" interpreter, define a procedure arraymult : (-> ((array integer) (array integer) integer) (array integer)) that takes two arrays of the same length, and returns an array which is their componentwise product. For example, arraymult(a, b, 7) returns a new array, call it c, of length 7, such that, for 0 <= i < 7, c[i] = a[i] * b[i] The original arrays a and b should not be modified. (You are prohibited from adding a new primitive to the interpreter to solve this problem.) Test your solution using either run or the read-eval-print loop. In either case hand in a printout of your procedure and testing. 6. (suggested practice) [makearray] Replace the letarray construct by a new primitive procedure, makearray, that takes one argument, the size of the array, and returns an array of the specified size. Work from the interpreter in ch6-1-3.scm. 7. (suggested practice) [play with the direct model interpreter] Play with the direct array interpreter for this section. You can load the interpreter by executing: (load-from-lib "ch6-1-4.scm") 8. (10 points) [does it work with direct arrays?] Your answers to this problem can be handwritten (pictures would be helpful in your explanations). But you are urged to try the "ch6-1-4.scm" interpreter to see how things work. (a) Do the procedures writearray and arraygenerator defined in problem 4 above work for call by value with the direct array model? Explain why it does not work, if it does not. (b) Does your code for arraymapin (problem 4) work on the test cases for call by value with the direct array model? Explain why it does not work, if it does not. 9. (50 points) [pictures for call by value with direct array model] Do problems 2 and 3 (above) again, but this time use the direct array model. Use "?" or "#" to represent the value in an array element that is uninitialized in your drawings. Note that the diagrams in the old version of chapter 6 are wrong for the direct model, use the kind of pictures shown in class or in the revised chapter 6. 10. (10 points) [side-effects and aliasing in the direct model] Is it true that, using the direct array model and call-by-value parameter passing: a. prevents side-effects from being visible to the caller of a procedure? Briefly explain your answer. b. prevents arrays from being aliased? Briefly explain your answer. (This can be handwritten.) 11. (50 points, extra credit) [subarrays in the direct model] Modify the direct array interpreter, ch6-1-4.scm, to allow array elements inside arrays. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 6.2 12. (suggested practice) [swap in the defined language] Test the call-by-reference interpreter with indirect arrays on procedures swap and swap2. The interpreter can be had by executing: (load-from-lib "ch6-2.scm") Also, you can get the text of these examples in $PUB/eopl/examples. 13. (15 points) [Draw pictures to explain fig. 6.2.3] Using diagrams, as in Figure 6.2.2 of the revised chapter 6 (i.e., as shown in class, but not like the old version of chapter 6), trace the program in Figure 6.2.3 (which is the same in the revised version of chapter in the original) and show the value printed using call-by-reference with: (i) indirect arrays, and (ii) direct arrays. (This can be handwritten.) 14. (20 points) [does it work with call-by-reference?] Your answers to this problem can be handwritten (pictures would be helpful in your explanations). But you are urged to try the "ch6-2.scm" and do problem 14 to see how things work. a. Do the procedures writearray and arraygenerator defined in problem 4 above work with: (i) the indirect model and (ii) the direct array model when using call by reference? Explain why it does not work, if it does not. b. Does your code for arraymapin (problem 4) work on the test cases with (i) the indirect model and (ii) the direct array model when using call by reference? Explain why it does not work, if it does not. 15. (80 points) [pictures with call by reference in both array models] Do problems 2 and 3 (above) again, but this time use call by reference and both (i) the indirect array model and (ii) the direct array models. Use "?" or "#" to represent the value in an array element that is uninitialized in your drawings. Note that the diagrams in the old version of chapter 6 are wrong for the direct model, use the kind of pictures shown in class or in the revised chapter 6. 16. (70 points) [reference-direct] Implement call-by-reference with the direct model of arrays. Do this by copying the code from $PUB/homework/hw6.tst/reference-direct.scm and filling in the code needed. To do this, you should make a suitable blend of $PUB/lib/ch6-2.scm (call by reference with the indirect model) and $PUB/lib/ch6-1-4.scm (call by value with the direct model). You can test your code by executing: (test-hw6 "reference-direct") I wasn't able to get the types of my procedures denoted->expressed, expressed->denoted, denoted-value-assign!, and array-element-assign! to be right; they all have datum as the type of various arguments instead of the correct type. So don't worry when this happens to you. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 6.3 17. (50 points) [implement call by value-result with indirect arrays] Implement an interpreter with call by value-result, using the indirect array model. Copy the file $PUB/homework/hw6.tst/value-result-indirect.scm to your directory and use it as a basis for your implementation. Implement the algorithm as given in class with left to right copy back. You can test your code by executing: (test-hw6 "value-result-indirect") Hint: Remember to save the return value from the call of the procedure. Recall that we also had to save the return value in the semantics of dynamic assignment. In the call-by reference interpreter that your solution builds on, ch6-2.scm, the type of the procedures denoted->expressed, expressed->denoted, denoted-value-assign!, and array-element-assign! are not right; they all have datum as the type of various arguments instead of the correct type. So don't worry about this. 18. (10 points) What would have to be changed in your solution to problem 17 above to implement call by value-result for the direct model of arrays? 19. (suggested practice) [New example illustrating differences] Do exercise 6.3.2 in the text twice: (i) for the indirect model of arrays, and (ii) for the direct model of arrays. Give the values returned for each parameter mechanism. Make diagrams showing the state of the variables at important points of your program to show why the particular result is returned. 20. (20 points) [does it work with call-by-value-result?] Your answers to this problem can be handwritten (pictures would be helpful in your explanations). You may assume that results are restored in left-to-right order. a. Do the procedures writearray and arraygenerator defined in problem 4 above work with (i) the indirect model and (ii) the direct array model when using call by value-result? Explain why it does not work, if it does not. b. Does your code for arraymapin (problem 4) work on the test cases with (i) the indirect model and (ii) the direct array model when using call by value-result? Explain why it does not work, if it does not. 21. (80 points) [pictures with call by value-result in both array models] Do problems 2 and 3 (above) again, but this time use call by value-result and both (i) the indirect array model and (ii) the direct array models. You may assume that results are restored in left-to-right order. Use "?" or "#" to represent the value in an array element that is uninitialized in your drawings. Note that the diagrams in the old version of chapter 6 are wrong for the direct model, use the kind of pictures shown in class or in the revised chapter 6. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 6.5 We are skipping the rest of chapter 6, but if you want to read more, section 6.5 is the most interesting. The interpreter for call by name is in $PUB/lib/ch6-5-2.scm, and the interpreter for call by need is in $PUB/lib/ch6-5-3.scm. If you have time (maybe after the semester ;-) you might want to read about and play with these. UNRELATED PROBLEM 22. (100 points extra credit) Speed up the type checker. See the code in $PUB/lib/type-check* and try using (verbose 3) in the interpreter to get some idea of what's taking the time. It may be that name lookup is a problem. Partial credit will be given for ideas, give your code or suggestions to Gary directly.