Com S 342 --- Principles of Programming Languages HOMEWORK 6: ENVIRONMENT PASSING INTERPRETERS I (File $Date: 2001/12/03 16:24:27 $) Due: problems 2-5,7-8,11-12 at beginning of class, December 4, 2001; Note that extra credit problems can't be handed in after Dec. 11, 2001. 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, provided you clearly label (with comments) which part of the code is solving what problems in this homework. For coding problems, aside from your printout of the code, you must also hand in a transcript of testing. See the directory $PUB/homework/hw6 for test scripts for each coding problem. (You can use the procedure test-hw6 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 these. Here are some ideas for increasing your understanding of the ideas in chapter 3, which is the core 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/lib than the code in the book. For more fun (;->), try to convert the code in the book to type check, and compare your solution to ours (in the library). Let us know if you find problems with our code! (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 the Unix command: diff -c 3-1.scm 3-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 "3-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). (load-from-lib "3-1.scm") Once you do that, then you can have a transcript like: typed> (run "+(3,4)") 7 : expressed-value 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 use the procedure "scan&parse" as follows. typed> (scan&parse "add1(2)") (a-program (primapp-exp (incr-prim) ((lit-exp 2)))) : program Finally, you can invoke the read-eval-print loop, to make a transcript like: typed> (read-eval-print) --> +(3,4) 7 Note that typing your shell's interrupt character (Control-c) to the read-eval-print loop's prompt will get you out of it. 1. (suggested practice) Read the code for the interpreter, starting from the file $PUB/lib/3-1.scm and following the loaded 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. 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, 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. 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/lib/3-1.scm and $PUB/lib/3-1-grammar.scm to your directory. It's probably best to rename these files, say to my-3-1.scm and my-3-1-grammar.scm. Put in the usual lines to display your name and section at the top of my-3-1.scm. Then edit the code in these two files to solve the problems. Be sure to change the line in my-3-1.scm that loads 3-1-grammar.scm to load your own grammar file; that is, change it to: (load "my-3-1-grammar.scm") If you get an error from sllgen during parsing when running our tests, then you have forgotten to do this. Hint: in Scheme, (begin (writeln x) 1) writes the value of x and returns 1, and (- 3) returns -3. Test it yourself first, using either the run procedure or the read-eval-print loop as in problem 2. Then use: (test-hw6 "print") (test-hw6 "minus") to do the final testing. Your code should type check. 4. (20 points) [order of evaluation of arguments to primitives] Do exercise 3.2 on page 75 in the text. 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) Helpers for this revised domain are found in the following file. $PUB/lib/ex3-7-expressed-value.scm Your solution for this problem should build on your solution to problem 3. However, instead of loading $PUB/lib/3-1-expressed-value.scm, you must modify your code to load the file $PUB/lib/ex3-7-expressed-value.scm Test it yourself first, using either the run procedure or the read-eval-print loop as in problem 2. Then use: (test-hw6 "lists") to do the final testing. Your code should type check. 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 "3-1.scm", or the interpreter you have built in the previous problems, 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 first, then use: (test-hw6 "comparisons") (test-hw6 "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 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, then use: (test-hw6 "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**8] Write an expression in the defined language to calculate 3**8, that is 3 to the eighth 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. Hand in a transcript showing that your expression works. Use the interpreter "3-4.scm" to do this problem. That is, before you start working, use the following to load the interpreter's code. (load-from-lib "3-4.scm") 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. 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-hw6 "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? This can be handwritten, although we'd prefer to see it typed.