Com S 342 --- Principles of Programming Languages HOMEWORK 8: ENVIRONMENT PASSING INTERPRETERS II (File $Date: 2005/03/29 19:16:27 $) Due: problems 2-3,5 at beginning of class, Thursday, March 24, 2005; problem 6,8,9 at beginning of class, Tuesday, Tuesday, March 29, 2005. In this homework, you will learn more about interpreters, including procedures, scoping and recursion. These issues are a few of the basic ones along which languages vary, and learning them will help you use the languages you know better, and will help you learn new languages faster. 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. Use the procedure test-hw8 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 6 for some ideas to help aid your understanding when reading chapter 3 of the text. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 3.5 1. (suggested practice) Do exercise 3.19 on page 89 of the text. That is, use the file $PUB/lib342/3-5.scm to play with the language of this section. 2. (20 points) [factorial using higher-order procedures] Do exercise 3.21 on page 89. Make a transcript of your session where you define the factorial procedure. Hint: you should look at the code in $PUB/lib342/3-5.scm to see what primitives are available for writing this code. It will be helpful to write this out in a Scheme file using the "run" interface to the defined language, so that you can edit more easily. That is make a Scheme file containing something like: (displayln "Name: ") (displayln "Section: ") ;; problem 2, exercise 3.21 (load-from-lib "3-5.scm") (displayln (run "let ... in (fact 6)")) If you do that, hand in both a printout of both your Scheme file and your transcript. 3. (20 points) [checked apply-procval] Do exercise 3.20 on page 89 of the text. 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 the file $PUB/lib342/3-5.scm to this directory: cp $PUB/lib342/3-5.scm my-3-5.scm Now edit the code in my-3-5.scm file to solve the problem. You'll have to test this problem yourself, as our test procedures are not capable of checking for correct issuance of errors. A sample of testing and output appears in the file $PUB/homework/hw8/checked-apply-procval-sample-output.txt. Note that I used eopl:error to issue error messages. 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. 4. (25 points; extra credit) [apply primitive] Modify the grammar in my-3-5.scm to add an "apply" primitive to the defined language. Then add the "apply" primitive to the interpreter. The "apply" primitive should work like the "apply" procedure in Scheme. That is, it should take two arguments: a procedure and a list of expressed values, and should call the procedure on the list of expressed values. We already have added lists to the domain of expressed values in $PUB/lib342/3-5.scm, so they should be in your copy, but you will need to add the list primitives from homework 7 so that the program will be useful. Besides your own tests, you can also test with the following. (test-hw8 "apply") 5. (30 points) [traceproc syntax and semantics] Do exercise 3.29 on page 91. To do this, you will need to (a) modify the syntax for the language in my-3-5.scm; the concrete syntax should be just like the concrete syntax for "proc", except that it uses "traceproc" instead of "proc". You'll also need to (b) add a variant in the define-datatype for expressions, in my-3-5.scm, for traceproc (call it traceproc-exp). Finally, (c) change the code in my-3-5.scm to do the actual work. To test your solution, use the following. (test-hw8 "traceproc") Note that our test harness can't capture output from Scheme, so this is only testing that the value returned by a traceproc is correct. You'll have to look at the output yourself. A sample is provided in the file $PUB/homework/hw8/traceproc-sample-output.txt. Note that in my solution, I made some effort to print out closures in a more succinct format, which makes them easier to read. I also wrote a procedure to print comma-separated lists like "maker, x", which is nice, but not really necessary. Hand in a printout of a transcript of your testing. Also this is the time to print your code for this problem and the section 3.5 interpreter problems above. Be sure that your solution for each problem is marked in the printout you hand in. 6. (10 points) [Understanding dynamic binding/scoping] See problems 3.30-3.33 in the text for background on this problem. Consider the following expression in the defined langauge let x = 3; y = 5 in let p = proc(i, k) %% draw the picture when execution is here list(x, y, i, k) x = 7 in let x = 9 in let ls = (p let y = 11 in y x) in cons(x, cons(y, ls)) Using dynamic scoping, (a) draw a picture of the run-time stack when execution reaches the point indicated (with the stack growing down the page), and (b) give the result (if any) of the above expression. If the expression has no result, or encounters an error, write that and briefly explain what the problem is. 7. (suggested practice) [More on dynamic binding/scoping] Draw the same kind of stack diagram as in the previous problem for the code in problem 3.30, and check that you get the answer of 35. 8. (40 points) [Implementing dynamic binding/scoping] Do exercise 3.30 on page 91 in the text. To start, change to your own directory and do cp $PUB/homework/hw8/my-3-5-dynamic.scm . Then edit your copy of the file my-3-5-dynamic.scm and fill in the indicated parts to solve the problem. Now you have two tasks. The first is to implement the ADT of "procedure texts". This is the ADT representing the defined language procedures, as described at the bottom of exercise 3.30 on page 91 in the text. We call them procedure texts (instead of procedure values), as discussed in class. Hint: look at the types in this file. The second task is to implement the parts of eval-expression that are left out so that the interpreter implements dynamic scoping. In particular, you'll have to change the way the interpreter works in the proc-exp and app-exp cases. You can test your code with: (test-hw8 "dynamic-scoping") ESSENTIALS OF PROGRAMMING LANGUAGES: Section 3.6 9. (30 points) [define at the top level] In this problem, you will implement top-level, recursive definitions in defined language programs. 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/homework/hw8/my-3-6-basis.scm . The grammar in this file changes the concrete syntax for programs (note: not expressions!) to be the following: ::= { define ( {}*(,) ) = }* For example, define fact1(x) = if zero?(x) then 1 else *(x, (fact2 sub1(x))) define fact2(x) = if zero?(x) then 1 else *(x, (fact1 sub1(x))) (fact1 6) is a program that returns 720 when evaluated. This grammar changes the interpreter to allow zero or more top-level, mutually recursive procedure definitions before the main expression. The SLLGEN input for this thus changes the input for program to: (program ((arbno "define" identifier "(" (separated-list identifier ",") ")" "=" expression) expression) a-program) Note that this completely replaces the syntax used in the textbook for the nonterminal program, and is not an addition to it. The procedure definitions that precede the main expression recursively extend the initial environment, and their names can be used in their bodies and in the program's main expression. Now you should change the define-datatype definition in my-3-6-basis.scm to have an appropriate abstract syntax for programs (i.e., revise the a-program variant of the program AST). (Hint: compare to the abstract syntax for letrec). Finally, the main problem is to change the code for eval-program (not eval-expression) in my-3-6-basis.scm to deal correctly with programs that have mutually recursive definitions. You can test your code using (test-hw8 "define") Hand in a printout of my-3-6-basis.scm, and a transcript of your testing.