Com S 342 --- Principles of Programming Languages HOMEWORK 6: PARAMETER PASSING (File $Date: 1995/12/06 21:26:28 $) Due: problems 1,5,7-8 at your discussion section, December 1; problems 11-12 at the beginning of class, December 4, problems 13-14 at your discussion section, December 8. In this homework, you will learn about various parameter passing mechanisms in programming languages. 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. Recall that $PUB means /home/cs342/public.) The section headings below give the readings related to the problems. Note that no late homework will be accepted after December 1. ESSENTIALS OF PROGRAMMING LANGUAGES: Chapter 5 1. (50 points) In this problem you will assemble and test a composite interpreter from the material in chapter 5. (a) Considering the features of the interpreters in chapter 5, write down two (2) lists: (i) of features you think are helpful and would be used by most programmers, and (ii) features you think might be problematic, or not used very often. "Features" studied include: let, proc, the scope rules (static and dynamic), and so on. You don't have to list all the primitives, just list groups of them (e.g., numerical procedures, list-processing procedures, etc.). Be sure that whatever features you list in part (i) are found in the interpreter you assemble for part (b) below, and that none of the features you list in part (ii) are found in that interpreter. (b) Collect the code for your interpreter into one file. You can load files in $PUB/lib if you wish, and please do that for the parser at least. Don't put in duplicate versions of the code for any procedure. Be sure that the documentation in your interpreter (the comments) corresponds to what is in your interpreter. Your interpreter should include a version of syntax-expand (if you want features like let and letrec), and a version of eval-print (if you want define). (c) Using your interpreter, write and test procedures in the defined language to do the following: (i) compute x to the power y, for integer x and positive integer y. (ii) compute the average of a list of numbers. You are prohibited from doing these by calling a single primitive; that is, the following is illegal as a solution to (i): define exponent = proc(x, y) expt(x,y) % expt is a primitive Instead use recursion and helping procedures in the defined language. (Hint: but you may need to add primitive procedures to do lists and division. Also, you can't use "/" as the name of the division operation, use something like "div" instead. And apparently you can't use "sum" either, it seems to be a reserved word; use something else.) You should hand in your answers to (a), your code for (b), and a transcript showing both your code for (c) and testing of it. We will not be providing test data for part (c). If you use the read-eval-print loop, you will probably find it useful to put your test cases in variables. (See the file $PUB/homework/hw5.tst/letrecproc-expand.tst for examples of this.) 2. (50 points, extra credit) Write an interpreter for the lambda calculus in the defined language. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 6.1 3. (suggested practice) Do exercise 6.1.1. [play with the indirect array interpreter] You can get this interpreter by executing: (load-from-lib "ch6-1-3.scm") 4. (suggested practice) Do exercise 6.1.2. [makearray] 5. (20 points) 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. (b) Give the output of the expression. (You should do this by hand, and only use the computer to check the answer.) let skip = proc(x) % EFFECT: do nothing x := x in letrec init3 = proc (a, e, i) % EFFECT: make a[i] be e, a[i+1] be e+1, ... if equal(i, 3) then skip(i) else begin a[i] := e; init3(a, +(1,e), +(1,i)) end; write3 = 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 init3(a, 0, 0); init3(b, 20, 0); init3(c, 40, 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 the arrays a, b, and c look like here write3(a, 0); write3(b, 0); write3(c, 0) end end 6. (suggested practice) Play with the direct array interpreter for this section. You can load the interpreter by executing: (load-from-lib "ch6-1-4.scm") 7. (20 points) Do problem 5 (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. 8. (5 points) Write out an answer to exercise 6.1.3. [side-effects with call-by-value] (This can be hand-written.) 9. (10 points, extra credit) Do exercise 6.1.4. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 6.2 10. (suggested practice) 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. 11. (5 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), trace the program in Figure 6.2.3 (which is the same in the revised version of chapter in the original) using call-by-reference with: (i) indirect arrays and (ii) direct arrays. (iii) What value is printed in each case? 12. (25 points) Implement call-by-reference with the direct model of arrays. Do this by copying the code from $PUB/lib/ch6-2.scm and changing what procedures need to be changed to make the interpreter use the direct model of arrays. You can test your code by executing: (test-hw6 "reference-direct") ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 6.3 13. (20 points) Do exercise 6.3.1 in the text. [Call by value-result with indirect arrays]. Do this by editing your code into the following template: (load-from-lib "ch6-2.scm") (define apply-proc ; TYPE: (-> (Procedure (list Denoted-Value)) Expressed-Value) ; ... put your code here ... ) You can test your code by executing: (test-hw6 "value-result-indirect") 14. (10 points) Do exercise 6.3.2 in the text. [New example illustrating differences.] You should state whether your program assumes either the direct or indirect model of arrays. (This can be handwritten.)