• Due: Wednesday, May 4
  • Notes:

    • Although the official deadline is Wed. May 4, I will accept this (and all other remaining CS251 work) until the end of finals period = 5pm Mon. May 16.
    • This problem set is now complete. It has four problems worth 100 points.
    • It has been designed in such a way that you can expect 10 points to require approximately 1 hour. Please let me know if this expectation is wrong on particular problems!
    • Please keep track of the time estimates for each problem/subproblem.
  • Submission:
    • In the yourFullName CS251 Spring 2016 Folder, create a Google Doc named yourFullName CS251 PS8.
    • For each problem and subproblem, please indicate at the beginning of each writeup approximately how long that problem took you to solve and write up.
    • You will need to draw many environment diagrams in this pset. You can use Google Doc’s Insert Drawing feature to create an environment diagram to insert into your doc.
    • You will flesh out the following code file in this pset:
      • Problem 4: Counters.java
    • Include all answers, including copies of relevant code from your .hfl and .java files in your PS8 Google Doc.
    • Drop a copy of your Counters.java file in your ~/cs251/drop/ps08 drop folder on cs.wellesley.edu. (You need not drop a copy of exp3.hfl in your drop folder.

1. Static and Dynamic Scope in Hofl (30 points)

Before starting this problem, study Sections 8 (Static Scoping) and 9 (Dynamic Scoping) in the Hofl notes.

  1. (12 points) Suppose that the following program is run on the input argument list [5].

    (hofl (a)
      (bind linear (fun (a b)
                     (fun (x)
                       (+ (* a x) b)))
        (bind line1 (linear 1 2) 
          (bind line2 (linear 3 4)
            (bind try (fun (b) (list (line1 b) (line2 (+ b 1)) (line2 (+ b 2)))) 
              (try (+ a a)))))))

    Draw an environment diagram that shows all of the environments and closures that are created during the evaluation of this program in statically scoped Hofl. You can use Google Doc’s Insert Drawing feature to create a drawing to insert into your doc.

    In order to simplify this diagram:

    • you should treat bind as if it were a kernel construct and ignore the fact that it desugars into an application of an abs. That is, you should treat the evaluation of (bind I_defn E_defn E_body) in environment F as the result of evaluating Ebody in the environment frame F', where F' binds I_defn to V_defn, V-defn is the result of evaluating E_defn in F, and the parent frame of F' is F.

    • you should treat fun as if it were a kernel construct and ignore the fact that it desugars into nested abstractions. In particular, (1) the evaluation of (fun (I_1 ... I_n) E_body) should be a closure consisting of (a) the fun expression and (b) the environment of its creation and (2) the application of the closure < (fun (I_1 ... I_n ) E_body ), F_creation > to argument values V_1 … V_n should create a new environment frame F whose parent frame is F_creation and which binds the variables I_1I_n to the values V_1V_n.

  2. (2 points) What is the final value of the program from part (a) in statically scoped Hofl? You should figure out the answer on your own, but may wish to check it using the statically scoped Hofl interpreter.

  3. (10 points) Draw an environment diagram that shows all of the environments created in dynamically scoped HOFL when running the above program on the input argument list [5].

  4. (2 points) What is the final value of the program from part (c) in dynamically scoped Hofl?

  5. (4 points) In a programming language with higher-order functions, which supports modularity better: lexical scope or dynamic scope? Explain your answer.

Note: You can use the Hofl interpreters to check your results to parts b and d by following these steps:

  1. Copy the entire contents of the cs251-download directory on cs.wellesleley.edu to your local cs251-download directory using the following command. This may overwrite some of your existing files in this directory, but that’s OK. (If you think it’s not OK, then save versions of files you care about elsewhere first!) Of course, as usual, here and elsewhere you should replace username gdome by your own account name:

    scp -r gdome@cs.wellesley.edu:/home/cs251/download/* /home/wx/cs251-download
  2. If you don’t already have one, create a *sml* SML interpreter buffer within Emacs. All of the subsequent steps involve evaluating SML expressions in this buffer.

  3. Execute the following SML command to change the default directory:

    - Posix.FileSys.chdir "/home/wx/cs251-download/hofl";
  4. Load both the static and dynamic Holf interpreters as follows:

    - use "load-hofl-interps.sml";
  5. You can launch a REPL for the statically scoped Hofl interpreter and evaluate expressions and run programs as shown below:

    - HoflEnvInterp.repl();
    
    hofl> (bind a 5
            (bind add-a (fun (x) (+ x a))
              (bind a 100
                (add-a 12))))
    17
    
    hofl> (#run (hofl (a b c) 
                  (bind add-a (fun (x) (+ x a))
                    (bind a b
                      (add-a c))))
                5 100 12)
    17
    
    hofl> (#quit)
    Moriturus te saluto!
    val it = () : unit
    -

    Note that it is not possible to use Hofl’s load to evaluate an expression or run a program.

  6. Launching and using the dynamically scoped Hofl interpreter is similar:

    - HoflEnvInterpDynamicScope.repl();
    
    hofl-dynamic-scope> (bind a 5
                          (bind add-a (fun (x) (+ x a))
                            (bind a 100
                              (add-a 12))))
    112
    
    hofl-dynamic-scope> (#run (hofl (a b c) 
                                (bind add-a (fun (x) (+ x a))
                                  (bind a b
                                    (add-a c))))
                               5 100 12)
    112
    
    hofl-dynamic-scope> (#quit)
    Moriturus te saluto!
    val it = () : unit
    -

2. Recursive Bindings (20 points)

Before starting this problem, study Sections 8 (Static Scoping), 9 (Dynamic Scoping), and 10 (Recursive Bindings) in the Hofl notes.

Consider the following Hofl expression E:

(bind f (abs x (+ x 1)) 
  (bindrec ((f (abs n 
                 (if (= n 0) 
                     1
                     (* n (f (- n 1)))))))
    (f 3)))
  1. (6 points) Draw an environment diagram showing the environments created when E is evaluated in statically scoped Hofl, and show the final value of evaluating E.

  2. (6 points) Consider the expression E' that is obtained from E by replacing bindrec by bindseq. Draw an environment diagram showing the environments created when E' is evaluated in statically scoped Hofl, and show the final value of evaluating E'.

  3. (6 points) Draw an environment diagram showing the environments created when E' is evaluated in dynamically scoped Hofl, and show the final value of evaluating E'.

  4. (2 points) Does a dynamically scoped language need a recursive binding construct like bindrec in order to support the creation of local recursive procedures? Briefly explain your answer.

Note: You can use the Hofl interpreters to check your results to parts a, b, and c by following the testing steps from Problem 1.

3. Distinguishing Scopes (10 points)

In this problem, you will write a single expression that distinguishes static and dynamic scope in Hofl.

Setup

Begin this problem by performing the following steps:

  1. Copy the entire contents of the cs251-download directory on cs.wellesleley.edu to your local cs251-download directory using the following command. This may overwrite some of your existing files in this directory, but that’s OK. (If you think it’s not OK, then save versions of files you care about elsewhere first!) Of course, as usual, here and elsewhere you should replace username gdome by your own account name:

    scp -r gdome@cs.wellesley.edu:/home/cs251/download/* /home/wx/cs251-download
  2. If you don’t already have one, create a *sml* SML interpreter buffer within Emacs.

  3. In the *sml* buffer, execute the following SML command to change the default directory:

    - Posix.FileSys.chdir "/home/wx/cs251-download/ps8";

Your Task

Create a file /home/wx/cs251-download/ps8/exp3.hfl containing a simple Hofl expression that evaluates to (sym static) in a statically-scoped Hofl interpreter but evaluates to (sym dynamic) in dynamically-scoped interpreter. The only types of values that your expression should should manipulate are symbols and functions; it should not use integers, booleans, characters, strings, or lists. You can test your expression in SML as follows:

- use "Problem3Tester.sml"; (* this only need be executed once *)
... lots of output omitted ...

- testProblem3(); (* you can execute this multiple times *)

This evaluates the expression in the exp3.hfl file in both scoping mechanisms and displays the results. A correct solution should have the following output:

- testProblem3();
/home/wx/cs251-download/ps8/exp3.hfl contains the expression:
... details omitted ...
Value of expression in static scope: (sym static)
Value of expression in static scope: (sym dynamic)
val it = () : unit

To submit the solution to this problem, just copy the expression in exp3.hfl to your PS8 doc. You needn’t submit anything to the drop folder.

4. Counters (40 points)

Recall that in Racket (1) every variable name is bound to an implicit cell; (2) references to a variable implicitly dereference (return the contents of) the cell; and (3) a variable Id can be assigned a new value via the assignment construct (set! Id E), which changes the contents of the implicit cell associated with Id to the value of E.

This problem involves the following Racket functions for implementing and testing various counter objects (which can be found in the file ps8/counters.rkt):

(define make-counter1
  (let ((count 0))
    (λ ()
      (λ ()
        (begin (set! count (+ count 1))
               count)))))

(define make-counter2
  (λ ()
    (let ((count 0))
      (λ ()
        (begin (set! count (+ count 1))
               count)))))

(define make-counter3
  (λ ()
    (λ ()
      (let ((count 0))
        (begin (set! count (+ count 1))
               count)))))

(define test-counter
  (λ (make-counter)
    (let ((a (make-counter))
          (b (make-counter)))
      (begin (println (a))
             (println (b))
             (println (a))))))
  1. (30 points) For each of the following expressions, (1) show the values displayed when the expression is evaluated and (2) draw an environment diagram for the evaluation of the expression. In your diagram, be sure to show empty environment frames from invoking nullary functions.

    • (test-counter make-counter1)
    • (test-counter make-counter2)
    • (test-counter make-counter3)

    For conventions on drawing environment diagrams with implicit cells, including empty environments, study this example of environment diagrams from Racket.

  2. (10 points) Let i range over the numbers {1,2,3}. Then each of the Racket functions make-counteri can be modeled in Java by an instance of class Counteri that implements the Counter interface in the following code:

    interface Counter {
      public int invoke();
    }
    
    class Counter1 implements Counter {
      // Flesh out this skeleton
    }
    
    class Counter2 implements Counter {
      // Flesh out this skeleton
    }
    
    class Counter3 implements Counter {
      // Flesh out this skeleton
    }
    
    public class Counters {
    
      public static void testCounters(Counter a, Counter b) {
        System.out.println(a.invoke());
        System.out.println(b.invoke());
        System.out.println(a.invoke());
      }
    
      public static void main (String [] args) {
        System.out.println("testCounters(new Counter1(), new Counter1()):");
        testCounters(new Counter1(), new Counter1());
        System.out.println("testCounters(new Counter2(), new Counter2()):");
        testCounters(new Counter2(), new Counter2());
        System.out.println("testCounters(new Counter3(), new Counter3()):");
        testCounters(new Counter3(), new Counter3());
      }
    
    }

    In this subproblem your task is to flesh out the definitions of the three Counteri classes in the above code so that they correctly model the behavior of the Racket function make-counteri.

    The above code can be found in the file ps8/CountersSkeleton.java. Begin this problem by making a copy of ps8/CountersSkeleton.java named ps8/Counters.java, and flesh out the missing class definitions in ps8/Counters.java.

    Notes:

    • In addition to its single nullary instance method invoke, each class Counteri should have a single class, instance, or local variable named count.

    • The testCounters method of the Counters class takes two objects from classes satisfying the Counter interface and tests them in a way similar to Racket’s test-counter. The test expression (test-counter make-counteri) in Racket can be modeled by the Java statement testCounters(new Counteri, new Counteri);

    • To compile and run the Counters program in the wx virtual machine, execute the following Linux shell commands:

      cd "~/cs251-download/ps8" 
      javac Counters.java 
      java Counters

      This will display the result of testing the three Counteri classes. These results should be similar to calling Racket’s test-counter function on the three make-counteri functions.