• Dueish: The required solo problem is dueish Fri. May 11. All the regular problems are completely option extra credit problems.

  • Notes:

    • This problem set contains one required solo problem. It also has some completely optional regular problems related to the last week of material in the course. These regular problems count as extra credit problems. You may do any subset of these problems (including the empty subset!)
    • In addition to doing any of these problems, you can also submit extra credit problems from previous assignments.
    • Any points from extra credit problems will simply be added to the point total of your regular problem component of your course grade. So you could use some of these problems to replace other regular problems during the semester.
    • Of course, partial credit will be awarded where appropriate for incomplete problems.
    • Recall that there is a limit of 100 extra credit points that can be earned.
    • Although formally “due” on Fri., May. 11, this (and all your other as-yet-incomplete CS251 work) can be submitted through the end of finals period (i.e., the end of Tue. May 22). However, there is very little flexibility to submit anything after Tue. May 22. In particular, senior grades must be submitted by noon on Fri. May 25.

1. Compex (30 points)

Background

This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.

In this problem, you will flesh out details of a new language Compex that extends Bindex with a comp construct:

(comp E_num E_pos E_zero E_neg)

This comp expression evaluates E_num to the integer value n_num and then compares this with zero:

  • if n_num is greater than zero, the value of the expression E_pos is returned.
  • if n_num is equal to zero, the value of the expression E_zero is returned.
  • if n_num is less than zero, the value of the expression E_neg is returned.

At most one of E_pos, E_zero, or E_neg will be evaluated.

Here are some examples of programs using the comp construct:

; ps11/pgm1.cpx
;
; An absolute value program 
(compex (n) (comp n n 0 (- 0 n)))

; ps11/pgm2.cpx
;
; Given program arguments a and b:
; * return the square of their difference if a > b
; * return twice a if a = b
; * return the product of a and the difference if a < b
(compex (a b) 
  (bind diff (- a b) 
    (comp diff (* diff diff) (* 2 a) (* a diff))))

; ps11/pgm3.cpx
;
; Return the max of a, b, and c
(compex (a b c)
  (comp (- a b)
        (comp (- a c) a a c)
        (comp (- a c) a a c)
        (comp (- b c) b b c)))

; ps11/pgm4.cpx
;
; Test the interaction of comp with bind and itself
(compex (p q r)
  (+ (bind s (- p q)
       (bind t (- q r)
         (* (comp s (+ p q) (+ p r) (+ q r))
            (comp t (- p q) (- p r) (- q r)))))
     (comp (- r q)
       (bind u (+ p q) (comp u u (* 2 u) (* 3 u)))
       (bind v (+ p r) (comp v (* 4 v) (* 5 v) (* 6 v)))
       (bind w (+ q r) (comp w (* 7 w) (* 8 w) (* 9 w))))))

; ps11/pgm5.cpx
;
; If x > y > z, returns the sum of x, y, and z. 
; If x = y = z, returns x
; If x < y < z, returns the product of x, y, and z.
; Otherwise gives a divide-by-zero error. 
; (tests that only one branch is evaluated)
(compex (x y z)
  (comp (- x y)
        (comp (- y z) (+ x (+ y z)) (/ y 0) (/ z 0))
        (comp (- y z) (/ y 0) x (/ z 0)
        (comp (- y z) (/ y 0) (/ z 0) (* x (* y z))))))

Setup

Begin this problem by making copies of files in the ps11 directory:

[wx@wx ~]$ cd /home/wx/cs251/sml/ps11
[wx@wx ps11]$ cp CompexSkeleton.sml yourAccountName-Compex.sml
[wx@wx ps11]$ cp CompexEnvInterpSkeleton.sml yourAccountName-CompexEnvInterp.sml 
[wx@wx ps11]$ cp CompexToPostFixSkeleton.sml yourAccountName-CompexToPostFix.sml

Note that CompexSkeleton.sml, CompexEnvInterpSkeleton.sml, and CompexToPostFixSkeleton are just copies of Bindex.sml, BindexEnvInterp.sml, and BindedToPostFix.sml from the Bindex language. You will need to modify them as described below to extend Bindex to Compex.

Additionally:

  • In the file yourAccountName-CompexEnvInterp.sml, change the first line of the file from

    use "CompexSkeleton.sml";

    to

    use "yourAccountName-Compex.sml"

  • In the file yourAccountName-CompexToPostFix.sml, change the first two lines of the file from:

    use "CompexSkeleton.sml"; (* semi-colon required! *)
use "CompexEnvInterpSkeleton.sml"; (* semi-colon required! *)

    to

    use "yourAccountName-Compex.sml"; (* semi-colon required! *)
use "yourAccountName-CompexEnvInterp.sml"; (* semi-colon required! *)

Your Tasks

  1. (2 points) Change yourAccountName-Compex.sml and yourAccountName-CompexEnvInterp.sml so that all occurrences of Bindex and bindex are changed, respectively, to Compex and compex in in structure definitions, datatype declarations, patterns, strings, etc. (Hint: use M-x replace-string in Emacs.)

  2. (2 points) In yourAccountName-Compex.sml extend the exp datatype to have a Comp constructor for comp expressions.

  3. (2 points) Extend the definition of sexpToExp in yourAccountName-Compex.sml to correctly parse comp expressions.

  4. (2 points) Extend the definition of expToSexp in yourAccountName-Compex.sml to correctly unparse comp expressions.

    You can test that the above parts work by loading yourAccountName-Compex.sml into an *sml* buffer and trying the following tests in this buffer:

    - Control.Print.printDepth := 100;
(* ... lots of output omitted ... *)
val it = () : unit

- val exp1 = Compex.stringToExp("(comp (- a b) (+ a c) (/ b d) (% d e))");
val exp1 =
  Comp
    (BinApp (Sub,Var "a",Var "b"),BinApp (Add,Var "a",Var "c"),
     BinApp (Div,Var "b",Var "d"),BinApp (Rem,Var "d",Var "e")) : Compex.exp

- Compex.expToString(exp1);
val it = "(comp (- a b) (+ a c) (/ b d) (% d e))" : string

- val pgm5 = Compex.fileToPgm("pgm5.cpx");
val pgm5 =
  Compex
    (["x","y","z"],
     Comp
       (BinApp (Sub,Var "x",Var "y"),
        Comp
          (BinApp (Sub,Var "y",Var "z"),
           BinApp (Add,Var "x",BinApp (Add,Var "y",Var "z")),
           BinApp (Div,Var "y",Int 0),BinApp (Div,Var "z",Int 0)),
        Comp
          (BinApp (Sub,Var "y",Var "z"),BinApp (Div,Var "y",Int 0),Var "x",
           BinApp (Div,Var "z",Int 0)),
        Comp
          (BinApp (Sub,Var "y",Var "z"),BinApp (Div,Var "y",Int 0),
           BinApp (Div,Var "z",Int 0),
           BinApp (Mul,Var "x",BinApp (Mul,Var "y",Var "z"))))) : Compex.pgm


- print(Compex.pgmToString(pgm5));
(compex (x y z)
        (comp (- x y)
              (comp (- y z) (+ x (+ y z)) (/ y 0) (/ z 0))
              (comp (- y z) (/ y 0) x (/ z 0))
              (comp (- y z) (/ y 0) (/ z 0) (* x (* y z)))
              )
        )val it = () : unit

  5. (2 points) Extend the definition of freeVarsExp in Compex.sml to correctly determine the free variables of a comp expression.

    You can test that freeVarsExp works by loading yourAccountName-Compex.sml into an *sml* buffer and trying the following tests in this buffer:

    - StringSetList.toList(Compex.freeVarsExp(Compex.stringToExp("(comp (- a b) (+ a c) (/ b d) (% d e))")));
val it = ["a","b","c","d","e"] : string list

- Compex.varCheck(Compex.fileToPgm("pgm5.cpx"));
val it = true : bool

  6. (5 points) Extend the definition of eval in yourAccountName-CompexEnvInterp.sml to correctly evaluate comp expressions using the environment model. You should evaluate E_num exactly once.

    Use the #run functionality of the Compex REPL to test that your eval function works as expected. For example:

    - CompexEnvInterp.repl()

compex> (#run pgm1.cpx -42)
42

compex> (#run pgm1.cpx 17)
17

compex> (#run pgm1.cpx 0)
0

compex> (#run pgm2.cpx 6 2)
16

compex> (#run pgm2.cpx 3 3)
6

compex> (#run pgm2.cpx 2 6)
~8

compex> (#run pgm3.cpx 1 2 3)
3

compex> (#run pgm3.cpx 1 3 2)
3

compex> (#run pgm3.cpx 3 1 2)
3

compex> (#run pgm4.cpx 7 3 1)
68

compex> (#run pgm4.cpx 7 1 3)
~8

compex> (#run pgm4.cpx 3 7 1)
24

compex> (#run pgm4.cpx 3 1 7)
~20

compex> (#run pgm4.cpx 1 3 7)
~36

compex> (#run pgm4.cpx 1 7 3)
10

compex> (#run pgm5.cpx 4 3 2)
9

compex> (#run pgm5.cpx 3 3 3)
3

compex> (#run pgm5.cpx 2 3 4)
24

compex> (#run pgm5.cpx 4 2 3)
Error: Division by 0: 3

compex> (#quit)
Moriturus te saluto!
val it = () : unit

  7. (15 points) In this part, you will extend the Compex to PostFix translator in yourAccountName-CompexToPostFix.sml to correctly handle the translation of the comp construct from Compex to PostFix. Do this by adding a clause to the expToCmds function that correctly translates the comp construct.

    Notes:

    • Think carefully about this translation in the context of some concrete examples.

    • The PostFix sel, exec, and executable sequence commands are all helpful in this translation.
    • Loading yourAccountName-CompexToPostFix.sml will not only load this file, but will test it on the Compex programs pgm1.cpx through pgm5.cpx.

2. 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. Alternatively, you can draw diagrams on paper and scan the paper or take photos of them.

    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_1 … I_n to the values V_1 … V_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. If you don’t already have one, create a *sml* SML interpreter buffer within Emacs.

  2. In a *sml* buffer, load both the static and dynamic Holf interpreters as follows:

    Posix.FileSys.chdir("/home/wx/cs251/sml/hofl");
use "load-hofl-interps.sml";

  3. 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.

  4. 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
-

3. 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 2.

4. 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. If you don’t already have one, create a *sml* SML interpreter buffer within Emacs.

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

    - Posix.FileSys.chdir "/home/wx/cs251/sml/ps11";

Your Task

Create a file /home/wx/cs251/ps11/exp4.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 "Problem4Tester.sml"; (* this only need be executed once *)
... lots of output omitted ...

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

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

- testProblem4();
/home/wx/cs251/ps11/exp4.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 exp4.hfl to your PS11 doc. You needn’t submit anything to the drop folder.

5. 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 ps11/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 ps11/CountersSkeleton.java. Begin this problem by making a copy of ps11/CountersSkeleton.java named ps11/yourAccountName-Counters.java, and flesh out the missing class definitions in ps11/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/ps11" 
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