Com S 342 --- Principles of Programming Languages HOMEWORK 7: ENVIRONMENT PASSING INTERPRETERS I (File $Date: 2006/11/13 22:08:55 $) Due: problems 2-5,7-8,11-12 at beginning of class, October 24, 2006. In this homework, you will learn the basics of interpreters, including primitives, conditional evaluation, and local binding. As you go along in this homework, you will accumulate the code for a useful interpreter. In general, each problem's code should add to the code for the problem before it, so that your interpreter becomes more and more useful. For this reason, you can hand in one printout of your code, however, be sure to: Clearly label (with comments) which part of the code is solving what problems in this homework. As a debugging aid, we have made the starting files for the problems in which you change or modify the interpreters be regular Scheme files, not modules. That is, from the library interpreters, we removed the lines starting "(module", the matching close parenthesis, and the (provide ...) form. Thus you can use the DrScheme Run button (or the Scheme load primitive) instead of "require". For coding problems 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 problems, 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/hw7 for test scripts for each coding problem. Use the procedure test-hw7 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 these. Here are some ideas for increasing your understanding of the ideas in chapter 3, which is the second major part of the course. These ideas are all centered around making your reading of the interpreters more active. If you just read the code quickly, you'll have trouble understanding what's going on. Instead, try whatever of the following seems appropriate, and keep doing what works for you. (a) For each procedure in the interpreters, ask yourself: what is the job (specification) of this procedure? Write this down, and revise it as necessary when you discover otherwise. This should be abstract. Don't write: "it takes the car of rands, ...", instead write something more like "it evaluates all the expressions in rands". Describe what it does, not how. (b) When you read the code for one procedure and see a call to another, don't immediately look at the code for the called procedure, instead think about what it's job is, and imagine it does that correctly. This is important, because the code is so recursive. (c) Explain what is happening in the interpreter to someone else; this is a good way to do part (b) if you have a willing friend. (d) When you read the code of a procedure, think about whether it's correct and why it's correct, with respect to its job. This often involves several passes though the code and textual commentary surrounding it. Don't rush through it. This is the main thing I think about when I read code, so I highly recommend it. (e) Ask yourself: what happens if I change this part of the code? Try to think if you could do the same thing better, or more elegantly. (f) Imagine you want to do a similar thing to what you've seen in the code you just read. How would you do it? (g) Think about the types of the code, and why the code is type correct. This is easier to do with the code in $PUB/lib342 than the code in the book. (h) Draw diagrams of the execution data structures for some examples. Try to be careful and consistent about it. Put in "displayln" statements in the interpreter to print out the data structures, and use that to check your work. (i) Trace through some examples by hand. Use the "trace" procedure that is built in to the Scheme interpreter to trace the execution on-line after doing this, to verify what you've done and get feedback on whether you were understanding it correctly. (j) Use (Unix) commands like: diff -c ch3-1.scm ch3-4.scm to see what changes between these interpreters. Try this with different pairs of interpreters. Run the Unix command man diff to see how to read the output if it's not clear. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 3.1-3.2 In this section, use the interpreter "ch3-1.scm" as a basis for your work. Thus, to use this interpreter, first use the following to load the code from Section 3.1 of the chapter (on the department machines). (require (lib "ch3-1.scm" "lib342")) Once you do that, then you can have a transcript like: > (run "+(3,4)") 7 You can also run just the scanner and parser and see the abstract syntax tree that results. This may be helpful in learning about the parser. To do this in DrScheme, select the Language menu, and then "Choose Language", then (at the bottom left) click on the button that says "Show Details", then from the right side, under "output syntax" choose "constructor", and click on the "OK" button. Then you can use the procedure "scan&parse" to show the output as follows. > (scan&parse "add1(2)") (a-program (primapp-exp (incr-prim) (list (lit-exp 2)))) This gives you an idea of what is going on in the parser. Finally, you can invoke the read-eval-print loop, to make a transcript like: > (read-eval-print) --> +(3,4) 7 Note that interrupting the read-eval-print loop or sending it an EOF will get you out of the loop 1. (suggested practice) Read the code for the interpreter, starting from the file $PUB/lib342/ch3-1.scm and following the loaded and required files. Do this in conjunction with reading sections 3.1-3.2, to be sure you understand how things work. Note that there are some differences due to type checking and modules. 2. (10 points) [transcripts for run and read-eval-print with 4 commas] Do exercise 3.4 on page 79 in the text; that is get the interpreter running and play with it some. (See the end of this problem for what to hand in.) Hand in a transcript that shows: (a) how you used the run procedure, (b) how you use the scan&parse procedure to print the abstract syntax trees (see above for how to make this useful in DrScheme), and (c) how you used the read-eval-print procedure to evaluate expressions. For both (a) and (c) you should evaluate at least 4 different expressions. To show you can work with the defined language's grammar, at least one input for parts (a) and (b) should have 4 commas (`,' characters) in it. Please circle these inputs on your transcript. The purpose of this is to have you explore the grammar a bit. 3. (20 points) [add print and minus to the interpreter] Do exercises 3.5 and 3.6 on page 79 in the text. Start by copying the code in $PUB/homework/hw7/my-3-1.scm to your directory. (This is a slightly altered version of $PUB/lib342/ch3-1.scm, which has lists as expressed values for problem 5 below, and is not in a module.) Add your name as a comment at the top of the file where indicated. Then edit the code in this file to solve the problem. Hint: in Scheme, (begin (writeln x) 1) writes the value of x and returns 1, and (- 3) returns -3. Test it yourself first, by pressing the run button (or use load) and then using either the run procedure or the read-eval-print loop as in problem 2. Then use: (test-hw7 "print") (test-hw7 "minus") to do the final testing. Hint: you can also look at the test cases for examples when solving such problems. See $PUB/homework/hw7/print.tst and $PUB/homework/hw7/minus.tst for the test scripts. 4. (10 points) [order of evaluation of arguments to primitives] Do exercise 3.2 on page 75 in the text. (If you are not using DrScheme, then be sure to state what Scheme interpreter you used in your testing.) 5. (20 points) [add cons, car, cdr, list, and emptylist to interpreter] Do exercises 3.7 on page 79 in the text. This problem adds lists to the interpreter, revising the domain of expressed values to be: Expressed-Value = Number + List(Expressed-Value) The section that implements Expressed-Values for the interpreter in my-3-1.scm already has definitions to work with lists as expressed values. These include the procedures list->expressed and expressed->list. Your solution for this problem should build on your solution to problem 3. Test it yourself first, by using either the run procedure or the read-eval-print loop as in problem 2. Then use: (test-hw7 "lists") to do the final testing. 6. (20 points; extra credit) [check number of arguments to primitives] Do exercise 3.9 on page 79 of the text. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 3.3 Note: In this section, use the interpreter you have built in the previous problems (my-3-1.scm), as a basis for your work. 7. (24 points) [add if, equal?, zero?, greater?, less?, and null?] a. Do exercise 3.10 on page 81 in the text. Test your solution after adding the predicates for part (b) below. b. Do exercises 3.11 and 3.12 on page 81 in the text. Extend your solution to Problem 5 by adding the primitive procedures equal?, zero?, greater?, less? and null? to the interpreter. Test it yourself, and then use: (test-hw7 "comparisons") (test-hw7 "null") Testing for this will test part (a) as well. 8. (30 points) [add cond to interpreter] Do exercise 3.13 on page 81 in the text. Note that if you use the SLLGEN grammar specification: (expression ("cond" (arbno expression "==>" expression) "end") cond-exp) Then SLLGEN input will construct syntax trees that contain two fields for cond-exps: the first will contain a list of the test expressions (the ones before the ==>) and the second will contain a list of the consequence expressions (the ones following the ==>). Try using scan&parse to see what happens. Test it yourself first, and then use: (test-hw7 "cond") 9. (20 points; extra credit) [add boolean values] Do exercise 3.14 on page 81 in the text. 10. (30 points; extra credit) [add boolean expressions as syntax] Do exercise 3.15 on page 81 in the text. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 3.4 11. (10 points) [calculate 3**64] Write an expression in the defined language to calculate 3**64, that is 3 to the sixty fourth power, using only let, (and the rest of let's syntax: = and in), *, variable names, and the number 3. See above for how to run the interpreter. Using let, you should make your code efficient (i.e., don't write out 64 multiplications). Hand in a transcript showing that your expression works. Use the interpreter "ch3-4.scm" to do this problem. That is, before you start working, use the following to load the interpreter's code. (require (lib "ch3-4.scm" "lib342")) 12. (30 points) [add unpack to defined language] Do exercise 3.18 on page 84 in the text. Note that your code should work with any number of identifiers, not just with three as in the example on page 84. Use error or eopl:error to report when the list of identifiers is not equal to the length of the list. The meaning of unpack is to bind all the names to elements in parallel (at the same time), not sequentially. Note that you will need the list primitives from problem 5 to do this work. You won't need the let primitive however, so you can build on your code from problem 5 above. (On the other hand, you may want to add let to your solution to problem 5 first, to familiarize yourself with the relevant ideas.) Test it yourself first, then use: (test-hw7 "unpack") 13. (suggested practice) [add eq?] Do exercise 3.17 on page 84 in the text. That is, extend the interpreter by adding the primitive eq?, which should correspond to the Scheme procedure eq? The number returned by this primitive should be 1 or 0 representing true or false. Your solution should extend your solution to problem 5 above, that is, your interpreter should have cons, car, cdr, list, and emptylist, etc. so it can be adequately tested. 14. (5 points, extra credit) [why is let needed to test eq?] Why is let needed in the interpreter to adequately test the eq primitive?