CS 251: PS10: Extra Credit Problems

Due: I will accept all work through the end of finals period = 5pm Thu. Dec. 21. If you need to go beyond that, there is some flexibility; please contact me to discuss options.
Notes:
- This problem set contains some completely optional extra credit problems related to the last week of material in the course. You may do any subset of these problems (including the empty subset!)
- There are 110 total points in the five problems here.
- 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.
Submission:
- In the yourFullName CS251 Fall 2017 Folder, create a Google Doc named yourFullName CS251 PS10.
- 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 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.

Starting this Problem Set

Problems 1 and 2 involve starter files in the ~wx/cs251/sml/ps10 directory in your wx Virtual Machine.

To create this directory, execute the following two commands in a wx VM shell:

cd ~/cs251/sml
git add -A
git commit -m "my local changes"
git pull origin master --rebase

Several students have encountered problems when executing this steps. If you have problems, please contact lyn.

1. Partial Evaluation (20 points)

Avoiding Magic Constants

It is good programming style to avoid “magic constants” in code by explicitly calculating certain constants from others. For instance, consider the following two Bindex programs for converting years to seconds:

; Program 1
(bindex (years)
  (* 31536000 years))

; Program 2
(bindex (years)
  (bind seconds-per-minute 60 
    (bind minutes-per-hour 60
      (bind hours-per-day 24
        (bind days-per-year 365 ; ignore leap years
          (bind seconds-per-year (* seconds-per-minute 
                                    (* minutes-per-hour 
                                       (* hours-per-day days-per-year)))
            (* seconds-per-year years)))))))

The first program uses the magic constant 31536000, which is the number of seconds in a year. (It is worth noting that this number is approximately π × 10⁷. So a century is approximately π × 10⁹ seconds, which means that π seconds is approximately one nano-century!)

The second program shows how this constant is calculated from simpler constants. By showing the process by which seconds-per-year is calculated, the second program is a more robust and well-documented software artifact. Calculated constants also have the advantage that they are easier to modify. Although the numbers in the above program aren’t going to change, there are many so-called “constants” built into a program that change over its lifetime. For instance, the size of word of computer memory, the price of a first-class stamp, and the rate for a certain tax bracket are all numbers that could be hard-wired into programs but which might need to be updated in future version of the software.

However, magic constants can have performance advantages. In the above programs, the program with the magic constant performs one multiplication, while the other program performs four multiplications. If performance is critical, the programmer might avoid the clearer style and instead opt for magic constants.

Partial Evaluation

Is there a way to get the best of both approaches? Yes! We can write our program in the clearer style, and then automatically transform it to the more efficient style via a process known as partial evaluation. Partial evaluation transforms an input program into a residual program that has the same meaning by performing computation steps that would otherwise be performed when running the program. Any computation steps that can be performed during partial evaluation are steps that do not need to be performed when the residual program is run later. In most cases, the residual program has better run-time performance than the original program.

For instance, we can use partial evaluation to systematically derive the first program above from the second. We begin via a step known as constant propagation, in which we substitute the four constants at the top of the second program into their references to yield:

(bindex (years)
  (bind seconds-per-minute 60
    (bind minutes-per-hour 60 
      (bind hours-per-day 24
        (bind days-per-year 365 ; ignore leap years
          (bind seconds-per-year (* 60 (* 60 (* 24 365)))
            (* seconds-per-year years)))))))

Next, we eliminate the now-unnecessary first four bindings via a step known as dead code removal:

(bindex (years)
  (bind seconds-per-year (* 60 (* 60 (* 24 365)))
    (* seconds-per-year years)))

We can now perform the three multiplications involving manifest integers in a step known as constant folding:

(bindex (years)
  (bind seconds-per-year 31536000
    (* seconds-per-year years)))

Finally, another round of constant propagation and dead code removal yields the first program:

(bindex (years)
  (* 31536000 years))

It is not possible to eliminate bindings whose definition ultimately depends on the program parameters. Nevertheless, it is often possible to partially simplify such definitions. For example, consider:

(bindex (a)
  (bind b (* 3 4)
    (bind c (+ a (- 15 b)) 
      (bind d (/ c b)
        (* d c)))))

The transformation techniques described above can simplify this program to:

(bindex (a)
  (bind c (+ a 3)
    (bind d (/ c 12) (* d c))))

In this example, (+ a (- 15 b)) cannot be replaced by a number (because the value of a is unknown), but it can be simplified to the residual expression (+ a 3). Similarly, (/ c b) is transformed to the residual expression (/ c 12) and (bind b ...) is transformed to the residual expression (bind c (+ a 3) (bind d (/ c 12) (* d c))).

Setup

Begin this problem by making a copy of the file ps10/BindexPartialEvalSkeleton.sml named ps10/BindexPartialEval.sml, and use this latter file for all of your work in this problem.

[wx@wx ~]$ cd /home/wx/cs251/sml/ps10
[wx@wx ps10]$ cp BindexPartialEvalSkeleton.sml BindexPartialEval.sml

Your Task

In this problem, your task is to flesh out the definition of a function partialEval that performs partial evaluation on a Bindex program. Given a Bindex program, partialEval should return another Bindex program that has the same meaning as the original program, but which also satisfies the following properties:

The program should not contain any bind expressions in which a variable is bound to an integer literal.
The program should not contain any binary applications in which an arithmetic operator is applied to two integer literals. There are two exceptions to this property: the program may contain binary applications of the form (/ n 0) or (% n 0), since performing these applications would cause an error in the partial evaluation process.

It is possible to write separate functions that perform the constant propagation, constant folding, and dead-code elimination steps, but it is tricky to get them to work together to perform all simplifications. It turns out that it is much more straightforward to perform all three kinds of simplification at the same time in a single walk over the expression tree.

By analogy with BindexEnvInterp.eval, partial evaluation of an expression can be performed by the peval function:

val peval: Bindex.exp -> int Env.env -> Bindex.exp:

Given a Bindex expression exp and a partial evaluation environment env, returns the partially evaluated version of exp. The partial evaluation environment contains name/value bindings for names whose integer values are known.

The function that corresponds with BindexEnvInterp.run is partialEval:

(* val partialEval: Bindex.pgm -> Bindex.pgm *)
(* Returns a partially evaluated version of the given Bindex program. *)
fun partialEval (Bindex(fmls,body)) = Bindex(fmls, peval body Env.empty)

Your goal is to implement simplification by fleshing out the peval function definition in BindexPartialEval.sml.

Note that there is a correspondence between run/eval in BindexEnvInterp and partialEval/peval. peval is effectively a version of eval that evaluates as much of an expression as it can based on the “partial” environment information it is given. Because bindings for some names may be missing in the environment, peval cannot always evaluate every expression to the integer it denotes and in some cases must instead return a residual expression that will determine the value when the program is executed. Because of this, peval must always return an expression rather than an integer; even in the case where it can determine the value of an expression, that value must be expressed as an integer literal node (tagged with the Int constructor), not an integer.

Notes:

In order to load the partial evaluator, evaluate the following two expressions in a *sml* interpreter buffer:
```
Posix.FileSys.chdir("/home/wx/cs251/sml/ps10");

use "load-peval.sml";
```
Use BindexEnvInterp.binopToFun as part of applying an operator to two integers.
Divisions and remainders whose second operands are zero must be left in the program. Such programs will encounter divide-by-zero errors when they are later executed. For example,
```
(bindex (a)
  (bind b (* 3 4)
    (bind c (/ b (- 12 b)) (* c b))))
```
should be transformed to:
```
(bindex (a)
  (bind c (/ 12 0)
    (* c 12)))
```
In some cases it would be possible to perform more aggressive simplification if you took advantage of algebraic properties like the associativity and commutativity of addition and multiplication. To simplify this problem, you should not use any algebraic properties of the arithmetic operators. For example, you should not transform (+ 1 (+ a 2)) into (+ 3 a), but should leave it as is. You should not even perform “obvious” simplifications like (+ 0 a) ⇒ a, (* 1 a) ⇒ a, and (* 0 a) ⇒ 0. Although the first two of these simplification are valid, the last is unsafe in the sense that it can change the meaning of a program. For instance, (* 0 (/ a b)) cannot be simplified to 0, because it does not preserve the meaning of the program in the case where b is 0 (in which case evaluating the expression should give an error).
You can also test your partial evaluator by evaluating testAll(). This applies your partial evaluator to all the test entries in the list testEntries in the file BindexPartialEvalTest.sml. The entries in this list are by no means exhaustive. You are strongly encouraged to add more entries to this list. If all tests succeed, you will see this:
```
- testAll();
Add-2-3 -- OK!
Simple1 -- OK!
Years -- OK!
Residuals1 -- OK!
Residuals2 -- OK!
Residuals3 -- OK!
```
If any tests fail, testAll() will show the actual output vs expected output.

To test your partial evaluator on individual programs, you can use the testPartialEval function, which takes a string representation of a Bindex program. For example:

- testPartialEval "(bindex () (+ 1 2))";
(bindex () 3)
val it = () : unit

- testPartialEval "(bindex (a)\
=                 \  (bind b (* 3 4)\
=                 \    (bind c (/ b (- 12 b)) (* c b))))";
(bindex (a) (bind c (/ 12 0) (* c 12)))
val it = () : unit

- testPartialEval "(bindex (a)\
=                 \  (+ (* (+ 1 2) a)\
=                 \     (+ (* 3 4)\
=                 \        (+ (* 0 a)\
=                 \           (+ (* 1 a)\
=                 \              (+ 0 a))))))";
(bindex (a) (+ (* 3 a) (+ 12 (+ (* 0 a) (+ (* 1 a) (+ 0 a))))))
val it = () : unit

The last two examples show the SML conventions for entering multiline strings. Each nonterminal line must end with a backslash character, and the next line must begin with a backslash character.

2. Compex (30 points)

Background

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:

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

; ps10/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))))

; ps10/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)))

; ps10/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))))))

; ps10/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 ps10 directory:

[wx@wx ~]$ cd /home/wx/cs251/sml/ps10
[wx@wx ps10]$ cp CompexSkeleton.sml Compex.sml
[wx@wx ps10]$ cp CompexEnvInterp.sml CompexEnvInterp.sml 
[wx@wx ps10]$ cp CompexToPostFixSkeleton.sml CompexToPostFix.sml

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

Your Tasks

(2 points) Change Compex.sml and 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 points) In Compex.sml extend the exp datatype to have a Comp constructor for comp expressions.
(2 points) Extend the definition of sexpToExp in Compex.sml to correctly parse comp expressions.

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

You can test that the above parts work by loading 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

(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 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

(5 points) Extend the definition of eval in 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

(15 points) In this part, you will extend the Compex to PostFix translator in 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 "CompexToPostFix.sml" will not only load this file, but will test it on the Compex programs pgm1.cpx through pgm5.cpx.

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

(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 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.
(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].
(2 points) What is the final value of the program from part (c) in dynamically scoped Hofl?
(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:

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

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.

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
-

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

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

5. 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:

If you don’t already have one, create a *sml* SML interpreter buffer within Emacs.
In the *sml* buffer, execute the following SML command to change the default directory:
```
- Posix.FileSys.chdir "/home/wx/cs251/sml/ps10";
```

Your Task

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

- testProblem5(); (* 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:

- testProblem5();
/home/wx/cs251/ps10/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 exp5.hfl to your PS10 doc. You needn’t submit anything to the drop folder.