Machine Problem 5: Implementing State, Programming with State

Out: Friday, 15 February 2008

Due: 5 PM Friday, 22 February 2008 10 AM Sunday, 24 February 2008

Submission: Individual

This assignment is to be done individually, not in pairs.

Purpose

One purpose of this assignment is to get further experience extending and modifying interpreters. Another purpose is to explore the issues that arise when programming with state. By the end of this assignment, you should be comfortable making large changes to the LETREC language, and you should understand how state is specified and implemented in the EXPLICIT-REFS language.

Tasks

  1. [7pts] To prepare for extending the LETREC language in the next task, do the following exercise to explore the semantics of let and letrec in the Scheme language.

    Consider the following (very complicated, completely artificial) Scheme expression: 

    (let ((f (lambda (h)                                      ; line 01
           (letrec ((w (lambda (j) "P01"))                ; line 02
                    (g (lambda (k)                        ; line 03
                         (let ((g ((lambda (y) (y g))     ; line 04 
                                   (lambda (y) "P02"))))  ; line 05
                           "P03"))))                      ; line 06
             (letrec ((k (lambda (h) "P04"))              ; line 07
                      (f (lambda (w) "P05")))             ; line 08 
               (let ((k "P06")                            ; line 09
                     (f "P07"))                           ; line 10
                 "P08"))))))                              ; line 11
  (letrec ((k (lambda (s)                                 ; line 12
                (lambda (j)                               ; line 13
                  (letrec ((z (lambda (j) "P09"))         ; line 14
                           (v (lambda (f) "P10"))         ; line 15
                           (f (lambda (y)                 ; line 16
                                (let ((z "P11"))          ; line 17
                                  "P12"))))               ; line 18
                    "P13"))))                             ; line 19
           (g (lambda (y)                                 ; line 20
                (let ((w "P14"))                          ; line 21
                  "P15"))))                               ; line 22
    (let ((j (lambda (f) "P16")))                         ; line 23
      "P17")))                                            ; line 24
    Note that this expression is closed; it has no free variables.

    1. List the variables in scope at the expression "P17", with the line number of each variable's binding.
    2. List the variables in scope at the expression "P04", with the line number of each variable's binding.
    3. List the variables in scope at the expression "P06", with the line number of each variable's binding.
    4. List the variables in scope at the expression "P09", with the line number of each variable's binding.
    As an example, here is how you should answer the first part of this question: 
    The bound variables at the expression labelled "P17" are: 
f (line 01), 
k (line 12),
g (line 20), and 
j (line 23).
    Hint: if you are not sure about your answers at any point during this exercise, we strongly encourage you to construct experimental expressions in Scheme to test your answer. For example, to test the answer about "P17" above, one might replace the string "P17" with various other expressions to try to learn which variables are in scope and which bindings they refer to. One might also construct smaller expressions using let and letrec, binding simpler expressions to the variables, and see how they behave.
  2. [7pts] Extend the provided interpreter for the LETREC language by making all changes necessary to implement and to test the extension described by EoPL 3.32. Don't forget to change the comments that will need changing, and don't forget to add tests for the new feature of the language.

    Hint: The expression in task 1 illustrates the complexities of variable scoping. A good way to start this task would be to write programs in the proposed extension of the LETREC language that test whether you get the scoping rules right. Remember that the goal of testing is to find errors, and there are ample opportunities for error here.

  3. [3pts] While experimenting at the REPL with the provided interpreter for the EXPLICIT-REFS language, you encounter the following behavior: 
    > (equal? (run "newref(3)") 
          (run "newref(4)"))
#t
    1. Does the behavior above imply that EXPLICIT-REFS expression newref(3) is equivalent to the EXPLICIT-REFS expression newref(4)? If not, explain how the two expressions are different, and explain, in terms of the implementation of the interpreter, why the Scheme equal? expression above is returning #t.
    2. Is this behavior guaranteed according to the specification of the EXPLICIT-REFS language? Explain your answer.
  4. [3pts] Change the provided interpreter for the EXPLICIT-REFS language so that it now implements the language REFS-EXPLETIVE, which is the same language as EXPLICIT-REFS except that the evaluation rule for -(exp1, exp2) is changed in the following manner:
    (value-of exp2 ρ σ) = (val2, σ1)
    (expval->num val2) = n2
    (value-of exp1 ρ σ1) = (val1, σ2)
    (expval->num val1) = n1
    n1 - n2 = n
    ----------------------------------------------------
    (value-of (diff-exp exp1 exp2) ρ σ) = ((num-val n), σ2)

    Every EXPLICIT-REFS program is also a program in the REFS-EXPLETIVE (and vice versa), but the languages are not the same.

    Demonstrate this by making a program that produces a number m in EXPLICIT-REFS and a number n in REFS-EXPLETIVE, where m does not equal n.

Infrastructure

You are given the following interpreters:

The easiest way to copy these interpreters into one of your own directories is to use the cp command on a CCIS Solaris machine: 

        cp -r /course/csg111/.www/interps/letrec-lang .
        cp -r /course/csg111/.www/interps/explicit-refs .

Deliverables

  1. A complete interpreter for the LETREC language with all of the extensions you implement for task 2. You should submit all of the files needed to run your extended interpreter, even if some of those files are exactly the same as the files provided by the instructors.
  2. A text file mp5.txt that contains your answers for tasks 1 and 3, as well as the demonstration program for task 4.
  3. A complete interpreter for the REFS-EXPLETIVE language you implement for task 4. You should submit all of the files needed to run your modified interpreter, even if some of those files are exactly the same as the files provided by the instructors.
  4. A Development Diary

Back to Machine Problems

Felix S Klock II

Last modified: 16 February 2008

Valid XHTML 1.0!