Com S 342 --- Principles of Programming Languages HOMEWORK 7: ENVIRONMENT PASSING INTERPRETERS II (File $Date: 2004/04/10 21:45:23 $) Due: problems 2-3,5-6,8 at beginning of class, Tuesday, April 13, 2004; problem 9 at beginning of class, Tuesday, April 20, 2004. 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/hw7 for test scripts for each coding problem. (You can use the procedure test-hw7 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.5 1. (suggested practice) Do exercise 3.19 on page 89 of the text. That is, use the file $PUB/lib/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/lib/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 "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 files to this directory: cp $PUB/lib/3-5.scm my-3-5.scm cp $PUB/lib/3-5-grammar.scm my-3-5-grammar.scm cp $PUB/lib/procval-as-ast.scm my-procval-as-ast.scm Now change my-3-5.scm so that it loads your files, i.e., change the line (load-quietly-from-lib "3-5-grammar.scm") to (load "my-3-5-grammar.scm") and change the line (load-quietly-from-lib "procval-as-ast.scm") to (load "my-procval-as-ast.scm") so that the interpreter will use your files instead of the ones from the library. Now edit the code in my-procval-as-ast.scm file to solve the problem. (Note that in this problem, there are no changes to be made to the my-3-5-grammar.scm or to the my-3-5.scm files, but they will be changed for other problems in this homework.) You'll have to test this problem yourself, as our test procedures are not capable of checking for correct issuance of errors. To make the testing easier, use the untyped interpreter, which doesn't stop Scheme when it encounters an error, by using scheme342untyped. A sample of testing and output appears in the file $PUB/homework/hw7/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-grammar.scm to add an apply primitive to the defined language. (See the file $PUB/homework/hw7/my-3-6-grammar.scm if you wish to know how this is done.) Then add the apply primitive to the interpreter. The apply primitive should work like "apply" 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. Of course, you'll have to add lists to the domain of expressed values to do this problem. To add lists, change your interpreter to load from the library 3-5-expressed-value-with-lists.scm (instead of the usual expressed values). You'll also need to add the list primitives from homework 6 so that the program will be useful. Besides your own tests, you can also test with (test-hw7 "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-grammar.scm; the concrete syntax should be just like the concrete syntax for "proc", except that it uses "traceproc" instead of "proc". (Double check that your my-3-5.scm loads my-3-5-grammar.scm!) 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-procval-as-ast.scm and my-3-5.scm to do the actual work. To test your solution, use (test-hw7 "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/hw7/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. Your code for this problem should type check. Be sure to change the public declaration in your file my-procval-as-ast.scm if you add new procedures or variants. 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] Do problem 3.33 on page 92 of the text. This problem asks you to give the output of the following code in a version of the defined language that uses dynamic binding (i.e., dynamic scoping). let a = 3 p = proc () a % ** in let f = proc (a) (p) a = 5 in (f 2) You can write out the answer to this on paper. Include a picture of the run-time stack (growing down the page) at the point where execution reaches the body of p, i.e., the line marked with the ** comment. 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/lib/3-5.scm my-3-5-dynamic.scm cp $PUB/homework/hw7/proctext-as-proc.scm . Then edit your file my-3-5-dynamic.scm and change the line: (load-quietly-from-lib "procval-as-ast.scm") to (load "proctext-as-proc.scm") and also change the following line from (load-quietly-from-lib "3-5-expressed-value.scm") to (load-quietly-from-lib "ex3-30-expressed-value.scm") Now you have two tasks. The first is to edit the file proctext-as-proc.scm 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 edit the file my-3-5-dynamic.scm to work with the operations on procedure texts to implement dynamic scoping. In particular, you'll have to change the way the interpreter works in the proc-exp and app-exp cases. Your code should type check. You can test your code with: (test-hw7 "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/lib/3-6-basis.scm my-3-6-basis.scm Also copy our grammar for section 3.6 with the grammar for this problem added to your directory: cp $PUB/homework/hw7/my-3-6-grammar.scm my-3-6-grammar.scm Then edit the main file, my-3-6-basis.scm, to change the line (load-quietly-from-lib "3-6-grammar.scm") to (load "my-3-6-grammar.scm") The grammar we have given you 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, in my-3-6-grammar.scm is 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. Your code should type check. You can test your code using (test-hw7 "define"). Hand in a printout of my-3-6-basis.scm, and a transcript of your testing.