<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
          Com S 342 --- Principles of Programming Languages

            HOMEWORK 7: ENVIRONMENT PASSING INTERPRETERS I
                  (File $Date: 2006/10/23 20:09:36 $)

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 probems, 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?