CS 251: PS11: A Hofl Lot

Notes:
- This problem set contains only completely optional problems related to the last week of material in the course. Problem 1 is a Solo problem; all the other problems are Regular problems. These problems count as extra credit problems in their respective categories (solo/regular). 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 regular extra credit points that can be earned. That limit does not apply to the solo problem on this pset.
- Any of these problems (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 21). If you need to go beyond this date, please consult with Lyn.
Submission:
- In the yourFullName CS251 Spring 2019 Folder, create a Google Doc named yourFullName CS251 PS11.
- 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.
- Include all answers, including copies of relevant code from your .sml, .hfl and .java files in your PS11 Google Doc.
- 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.
- Seen individual problems for what you need to submit for that problem.

Starting this Problem Set

All problems on this pset involve starter files in the ~/cs251/sml/ps11 directory in your csenv/wx Virtual Machine.

To create this directory, follow the git instructions in this doc If you encounter any problems with this step, please contact Lyn.

REMINDER: ALWAYS MAKE A BACKUP OF YOUR .sml FILES AT THE END OF EACH DAY TO AVOID POTENTIAL LOSS OF WORK.

1. Solo Problem: Compex (35 points)

This is the final version of this problem. Some details of the comp construct, as well as the example programs and testing details, have changed.

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 Id_num E_num E_pos E_zero E_neg)

Note: The comp construct is now a binding construct that include the identifier Id_num, which is a local name for the value of E_num. See the details in the updated description below. The changes are not highlighted in magenta.

This comp expression evaluates E_num to the integer value V_num and locally gives the name Id_num to this value. It then compares V_num with zero:

if V_num is greater than zero, the value of the expression E_pos is returned.
if V_num is equal to zero, the value of the expression E_zero is returned.
if V_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.

The name Id_num is a local name for the value V_num whose scope is the three expressions E_pos, E_zero, and E_neg.

Here are some examples of programs using the comp construct. These are all in your ps11 folder in separately named files, like pgm1.cpx:

; ps11/pgm1.cpx
;
; Return the absolute value of a*b
(compex (a b) (comp prod (* a b) prod 0 (- 0 prod)))

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

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

; ps11/pgm4.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 diffxy (- x y)
  (comp diffyz (- y z) (+ y (+ (* 2 z) (+ diffxy diffyz))) (/ y 0) (/ z 0))
  (comp diffyz2 (- y z) (/ y 0) (+ z (+ diffxy diffyz2)) (/ z 0))
  (comp diffyz3 (- y z) (/ y 0) (/ z 0) (* (+ diffxy y) (* (+ diffyz3 z) z)))))

; ps11/pgm5.cpx
;
; Test the interaction of comp with bind and itself
(compex (p q r)
  (+ (bind p (- p q)
       (comp q (- p q)
             (+ p q)
             (- q p)
             (bind p (- p q) (* p q))))
     (comp r (- r q)
       (bind r (- p r) (comp p (- p r) (* p r) (+ p r) (- p r)))
       (bind r (- q r) (comp q (- r q) (* q r) (+ q r) (- q r)))
       (bind r (- r p) (comp p (- r p) (* r p) (+ r p ) (- r p))))))

; ps11/pgm6.cpx
;
; A complex program that tests comp in many expression positions.
(compex (a b c d e f g h)
  (+ (comp sumab (+ a b)
       (comp sumcd (+ c d) (+ sumab sumcd) (+ 17 (+ sumab sumcd)) (* sumab sumcd))
       (comp sumef (+ e f) (- sumab sumef) (+ 19 (+ sumab sumef)) (+ sumab sumef))
       (comp sumgh (+ g h) (* sumab sumgh) (+ 23 (+ sumab sumgh)) (- sumab sumgh))
       )
     (comp compres (comp sumcd (+ c d)
                     (comp sumef (+ e f) (+ sumcd sumef) (+ 42 (+ sumcd sumef)) (* sumcd sumef))
                     (comp sumgh (+ g h) (- sumcd sumgh) (* sumcd sumgh) (+ sumcd sumgh))
                     (comp sumab (+ a b) (* sumcd sumab) (+ 57 (+ sumcd sumab)) (- sumcd sumab))
                     )
       (comp sumef (+ e f) (+ compres sumef) (- compres sumef) (* compres sumef))
       (comp sumgh (+ g h) (- compres sumgh) (+ 87 (+ compres sumgh)) (+ compres sumgh))
       (comp sumab (+ a b) (* compres sumab) (- sumab compres) (+ compres sumab))
       )
     )
  )

Setup

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

[~]$ cd ~/cs251/sml/ps11
[ps11]$ cp CompexSkeleton.sml yourAccountName-Compex.sml
[ps11]$ cp CompexEnvInterpSkeleton.sml yourAccountName-CompexEnvInterp.sml 
[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! *)

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

In the file yourAccountName-CompexToPostFix.sml, make sure that the declaration val tests ... at the end is commented out. In an earlier version of the ps11 code, this declaration was not commented out, but it should be (because there is now a different way to do testing in this problem).

In the file CompexFreeVarsExpTest.sml, change the first line of the file from:

use "Compex.sml"; (* rename this to be your version! *)

use "yourAccountName-Compex.sml"; (* rename this to be your version! *)

In the file CompexEnvInterpTest.sml, change the first line of the file from:

use "CompexEnvInterp.sml"; (* rename this to be your version! *)

use "yourAccountName-CompexEnvInterp.sml"; (* rename this to be your version! *)

In the file CompexToPostFixTest.sml, change the first line of the file from:

use "CompexToPostFix.sml"; (* rename this to be your version! *)

use "yourAccountName-CompexToPostFix.sml"; (* rename this to be your version! *)

Your Tasks

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

(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 diff (- a b) (+ a diff) (/ b diff) (% diff c))";
val exp1 =
  Comp
    ("diff",BinApp (Sub,Var "a",Var "b"),BinApp (Add,Var "a",Var "diff"),
     BinApp (Div,Var "b",Var "diff"),BinApp (Rem,Var "diff",Var "c"))
  : Compex.exp

- Compex.expToString(exp1);
val it = "(comp diff (- a b) (+ a diff) (/ b diff) (% diff c))" : string
                        
- val pgm4 = Compex.fileToPgm("pgm4.cpx");
val pgm4 =
  Compex
    (["x","y","z"],
     Comp
       ("diffxy",BinApp (Sub,Var "x",Var "y"),
        Comp
          ("diffyz",BinApp (Sub,Var "y",Var "z"),
           BinApp
             (Add,Var "y",
              BinApp
                (Add,BinApp (Mul,Int 2,Var "z"),
                 BinApp (Add,Var "diffxy",Var "diffyz"))),
           BinApp (Div,Var "y",Int 0),BinApp (Div,Var "z",Int 0)),
        Comp
          ("diffyz2",BinApp (Sub,Var "y",Var "z"),BinApp (Div,Var "y",Int 0),
           BinApp (Add,Var "z",BinApp (Add,Var "diffxy",Var "diffyz2")),
           BinApp (Div,Var "z",Int 0)),
        Comp
          ("diffyz3",BinApp (Sub,Var "y",Var "z"),BinApp (Div,Var "y",Int 0),
           BinApp (Div,Var "z",Int 0),
           BinApp
             (Mul,BinApp (Add,Var "diffxy",Var "y"),
              BinApp (Mul,BinApp (Add,Var "diffyz3",Var "z"),Var "z")))))
  : Compex.pgm

- print(Compex.pgmToString(pgm4));
(compex (x y z)
        (comp diffxy
              (- x y)
              (comp diffyz
                    (- y z)
                    (+ y (+ (* 2 z) (+ diffxy diffyz)))
                    (/ y 0)
                    (/ z 0)
                    )
              (comp diffyz2 (- y z) (/ y 0) (+ z (+ diffxy diffyz2)) (/ z 0))
              (comp diffyz3
                    (- y z)
                    (/ y 0)
                    (/ z 0)
                    (* (+ diffxy y) (* (+ diffyz3 z) z))
                    )
              )
        )val it = () : unit

(4 Points) Extend the definition of freeVarsExp in Compex.sml to correctly determine the free variables of a comp expression.

You can automatically test freeVarsExp on various comp test cases by loading CompexFreeVarsExpTest.sml into an *sml* buffer. If everything succeeds, you will see a sequence of test case results that end with the following:
```
Passed all 8 test cases
signature COMPEX_FREE_VARS_EXP_TEST = sig end
structure CompexFreeVarsExpTest : COMPEX_FREE_VARS_EXP_TEST
val it = () : unit
```
Otherwise, you will see an indication of test cases on which there was a mismatch between expected and actual results.

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

You can automatically test eval on various comp test cases involving the programs pgm1.cpx through pgm6.cpx by loading CompexEnvInterpTest.sml into an *sml* buffer. If everything succeeds, you will see a sequence of test case results that end with the following:

Passed all 120 test cases
signature COMPEX_ENV_INTERP_TEST = sig end
structure CompexEnvInterpTest : COMPEX_ENV_INTERP_TEST
val it = () : unit

Otherwise, you will see an indication of test cases on which there was a mismatch between expected and actual results.

You can also interactively test that your eval function works as expected. To do this, load ``yourAccountName-CompexEnvInterp.sml into ansml buffer, and evaluateCompexEnvInterp.repl();. You can then use the#run` functionality of the Compex REPL to run program files on arguments. For example:

- CompexEnvInterp.repl();

compex> (#run pgm1.cpx 2 3)
6

compex> (#run pgm1.cpx 3 ~4)
12

compex> (#run pgm1.cpx ~4 ~5)
20

compex> (#run pgm1.cpx ~5 0)
0

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

compex> (#run pgm2.cpx 5 5)
10

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 4 3 2)
9

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

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

compex> (#run pgm4.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 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 to PostFix.

Notes:
- Review the compilation of the bind construct from PS10 Problem 2 before starting this problem. The comp construct binds a name to a value, so is similar to the bind construct in this respect.
- Think carefully about this translation in the context of some concrete examples. Unlike bind, the comp construct also involves conditional execution: only one of the expressions E_pos, E_zero and E_neg should be evaluated. For this aspect of the translation, the PostFix sel, exec, and executable sequence commands are all helpful.
- In the file yourAccountName-CompexToPostFix.sml, make sure that the declaration val tests ... at the end is commented out. In an earlier version of the ps11 code, this declaration was not commented out, but it should be (because there is now a different way to do testing in this problem; see the next bullet).
- You can automatically test the Compex to PostFix compiler on the programs pgm1.cpx through pgm6.cpx by loading CompexToPostFixTest.sml into an *sml* buffer.
  
  This will begin by first displaying the PostFix code that results from compiling the six sample programs. This is a good way to see the PostFix code that your compiler is generating for these examples.
  
  It will then test the generated PostFix code on numerous examples. If everything succeeds, you will see a sequence of test case results that end with the following:
```
Passed all 120 test cases
signature COMPEX_TO_POSTFIX_TEST = sig end
structure CompexToPostFixTest : COMPEX_TO_POSTFIX_TEST
val it = () : unit
```
  Otherwise, you will see an indication of test cases on which there was a mismatch between expected and actual results.

2. Desugaring `classify` (30 points)

The `classify` construct

You are a summer programming intern at Sweetshop Coding, Inc. Your supervisor, Dexter Rose, has been studying the syntactic sugar for Valex and is very impressed by the cond construct. He decides that it would be neat to extend Valex with a related classify construct that classifies an integer relative to a collection of ranges. For instance, using his construct, Dexter can write the following grade classification program:

; Classify Program 1
(valex (grade) 
  (classify grade
    ((90 100) 'A') 
    ((80 89) 'B')
    ((70 79) 'C')
    ((60 69) 'D') 
    (otherwise 'F')))

This program takes an integer grade value and returns a character indicating which range the grade falls in.

In general, the classify construct has the following form:

(classify E_disc
   ((Elo_1 Ehi_1) Ebody_1)
   ...
   ((Elo_n Ehi_n) Ebody_n)
   (otherwise E_default))

The evaluation of classify should proceed as follows.

First the discriminant expression E_disc should be evaluated to the value V_disc, which is expected to be an integer. Then V_disc should be matched against each of the clauses ((Elo_i Ehi_i) Ebody_i) from top to bottom until one matches. The value matches a clause if it lies in the range between Vlo_i and Vhi_i, inclusive, where Vlo_i is the integer value of Elo_i, and Vhi_i is the integer value of Ehi_i. When the first matching clause is found, the value of the associated expression Ebody_i is returned. If none of the clauses matches V_disc , the value of the default expression E_default is returned.

Here are a few more examples of the classify construct:

; Classify program 2 
(valex (a b c d)
  (classify (* c d)
    ((a (- (/ (+ a b) 2) 1)) (* a c)) 
    (((+ (/ (+ a b) 2) 1) b) (* b d)) 
    (otherwise (- d c))))

Program 2 emphasizes that any of the subexpressions of classify may be arbitrary expressions that require evaluation. In particular, the upper and lower bound expressions need not be integer literals. For instance, here are some examples of the resulting value returned by Program 2 for some sample inputs:

a	b	c	d	result
10	20	3	4	30
10	20	3	6	120
10	20	3	5	2

; Classify program 3
(valex (a)
  (classify a
    ((0 9) a)
    (((/ 20 a) 20) (+ a 1)) 
    (otherwise (/ 100 (- a 5)))))

Program 3 emphasizes that (1) ranges may overlap (in which case the first matching range is chosen) and (2) expressions in clauses after the matching one are not evaluated. For instance, here are here are some examples of the resulting value returned by Program 3 for some sample inputs:

a	result
0	0
5	5
10	11
20	21
25	5
30	4

Your Tasks

Dexter has asked you to implement the classify construct in Valex as syntactic sugar. You will do this in three phases.

(9 points) In your PS11 Google Doc, write down how you would like each of the three example programs above to be desugared into equivalent Valex programs that do not have classify. Your programs may include other sugar constructs, such as &&.
(9 points) In your PS11 Google Doc, write down incremental desugaring rules that desugar classify into other Valex constructs. These rules should be expressed as rewrite rules on s-expressions. For example, here are the desugaring rules for Valex’s sugared constructs except quote:
```
(&& E_rand1 E_rand2) ↝ (if E_rand1 E_rand2 #f) 
(|| E_rand1 E_rand2) ↝ (if E_rand1 #t E_rand2) 

(cond (else E_default)) ↝ E_default
(cond (E_test E_then) ...) ↝ (if E_test E_then (cond ...))

(list) ↝ #e 
(list E_head ...) ↝ (prep E_head (list ...))

(bindseq () E_body) ↝ E_body
(bindseq ((Id E_defn) ...) E_body) ↝ (bind Id E_defn (bindseq (...) E_body))

(bindpar ((Id_1 E_defn_1) ... (Id_n E_defn_n)) E_body)
  ↝ (bind Id_list (* fresh variable name *)
          (list E_defn_1 ... E_defn_n) (* eval defns in parallel *)
          (bindseq ((Id_1 (nth 1 Id_list))
                    ...
                    (Id_n (nth n Id_list)))
             E_body))
```
Note that ... means zero or more occurrences of the preceding kind of syntactic entity.

NOTES:
- Your desugaring rules may rewrite an s-expression into an s-expression that includes other sugar constructs, such as &&.
- Your desugaring rules should be written in such a way that E_disc is evaulated only once. To guarantee this, you will need to name the value of E_disc with a “fresh” variable (one that does not appear elsewhere in the program).
- Your desugaring rules should be written in such a way that the Elo and Ehi expressions in each clause are evaluated at most once.
- You should treat differently the cases where E_disc is an identifier and when it is not an identifier.
- Your rules should be designed to give the same output for the three sample programs as in part a.
(12 points) In this part, you will implement and test your desugaring rules from the previous part.

Begin this part by (1) renaming the files ValexPS11.sml and ValexEnvInterpPS11.sml to be yourAccountName-ValexPS11.sml and yourAccountName-ValexEnvInterpPS11.sml and (2) in yourAccountName-ValexEnvInterpPS11.sml, changing use "ValexPS11.sml"; to use "yourAccountName-ValexPS11.sml";.

NOTES:

Be careful to change to yourAccountName-ValexPS11.sml, not any files in the valex directory.
Use Utils.fresh to create a fresh variable.

To test your implementation after editing yourAccountName-ValexPS11.sml, first load yourAccountName-ValexEnvInterpPS11.sml into a *sml* buffer, and then pay attention to the following:

In the ps11 directory, the files classify1.vlx, classify2.vlx, and classify3.vlx contain the three example classify programs from above. The file sort3.vlx contains a test file that not using classify that returns a sorted list of its 3 arguments.

Your implementation should give the same output for the three sample programs as in part a. For seeing the output of the desugaring of your classify construct for examples, use one of the following approaches:

To desugar a file, use Valex.desugarFile to print the result of desugaring the program in the file. For example, supposed sort3.vlx contains this program:

(valex (a b c)
  (cond ((&& (<= a b) (<= b c)) (list a b c))
        ((&& (<= a c) (<= c b)) (list a c b))
        ((&& (<= b a) (<= a c)) (list b a c))
        ((&& (<= b c) (<= c a)) (list c b a))
        ((&& (<= c a) (<= a b)) (list c a b))
        (else (list c b a))))

Then here is the result of using Valex.desugarFile on this program:

- Valex.desugarFile "sort3.vlx";
(valex (a b c)
       (if (if (<= a b) (<= b c) #f)
           (prep a (prep b (prep c #e)))
           (if (if (<= a c) (<= c b) #f)
               (prep a (prep c (prep b #e)))
               (if (if (<= b a) (<= a c) #f)
                   (prep b (prep a (prep c #e)))
                   (if (if (<= b c) (<= c a) #f)
                       (prep c (prep b (prep a #e)))
                       (if (if (<= c a) (<= a b) #f)
                           (prep c (prep a (prep b #e)))
                           (prep c (prep b (prep a #e)))
                           )
                       )
                   )
               )
           )
       )
val it = () : unit

To desugar an expression, one approach is to invoke the Valex.desugarString function on a string representing the expression you want to desugar. For example:

- Valex.desugarString "(&& (|| a b) (|| c d))" 
(if (if a #t b) (if c #t d) #f)
- : unit = ()

- Valex.desugarString "(list 1 2 3)"
(prep 1 (prep 2 (prep 3 #e)))
- : unit = ()

To desugar an expression, another approach is to use ValexEnvInterp.repl() to launch a read-eval-print loop and use the #desugar directive to desugar an expression. For example:

- ValexEnvInterp.repl();

valex> (#desugar (&& (|| a b) (|| c d))) 
(if (if a #t b) (if c #t d) #f)

valex> (#desugar (list 1 2 3)) 
(prep 1 (prep 2 (prep 3 #e)))

There are several ways to test the evaluation of your desugared classify construct:
1. To run a program, one approach is to invoke ValexEnvInterp.runFile on the filename and a list of integer arguments. For example:
```
- ValexEnvInterp.runFile "sort3.vlx" [23, 42, 17];
val it = List [Int 17,Int 23,Int 42] : Valex.value
```
2. To run a program, another approach is to use ValexEnvInterp.repl() to launch a read-eval-print loop and use the #run directive to run a fileon arguments. For example:
```
- ValexEnvInterp.repl();

valex> (#run sort3.vlx 23 42 17)
(list 17 23 42)
```
3. To evaluate an expression, use ValexEnvInterp.repl() to launch a read-eval-print loop and enter the expression. To evaluate an expression with free variables, use the #args directive to bind the variables. For example:
```
- ValexEnvInterp.repl();

valex> (#args (a 2) (b 3))

valex> (bindpar ((a (+ a b)) (b (* a b))) (list a b))
(list 5 6)

valex> (bindseq ((a (+ a b)) (b (* a b))) (list a b))
(list 5 15)
```

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("~/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 2.

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 "~/cs251/sml/ps11";
```

Your Task

Create a file ~/cs251/ps11/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 exp5.hfl file in both scoping mechanisms and displays the results. A correct solution should have the following output:

- testProblem5();
~/cs251/ps11/exp5.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 PS11 doc. You needn’t submit anything to the drop folder.

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

(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.
(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/csenv 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

7. A Hofl Interpreter in Hofl (35 points)

The Hofl Handout describes a Hofl program named bindex-interp.hfl that is a
Bindex interpreter written in Hofl. (This program can also be found in the
~/cs251/sml/hofl directory.)

Create a Hofl program named hofl-interp.hfl that is an interpreter for Hofl.
You can start by making hofl-interp.hfl be a copy of bindex-interp.hfl
and extend it to be a complete HOFL interpreter. Your program should have
a run function that can run a Hofl program on a list of integer arguments.

For this problem you do not need to implement a Read/Eval/Print Loop (REPL),
or handle loading of Hofl programs from a file.

Starting this Problem Set

1. Solo Problem: Compex (35 points)

Background

Setup

Your Tasks

2. Desugaring classify (30 points)

The classify construct

Your Tasks

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

4. Recursive Bindings (20 points)

5. Distinguishing Scopes (10 points)

Setup

Your Task

6. Counters (40 points)

7. A Hofl Interpreter in Hofl (35 points)

2. Desugaring `classify` (30 points)

The `classify` construct