CS 251: PS10: Open to Interpretation

Dueish: Fri. May 10
Notes:
- This is the last pset on which all problems are required. It covers material through the Valex lecture on Wed. May 08. It will be followed by a PS11 on which all problems (including the solo problem) are completely optional extra credit problems. (Earlier plans to require the PS11 solo problem have been canceled.).
- Although formally “due” on Fri. May 10, 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 21). If you need to go beyond this date, please consult with Lyn. Note that senior grades are due at noon on Fri. May 24, so there is very little flexibility for seniors after the Tue. May 21 date.
- This pset has 110 points total: 33 and 77 for three regular problems.
- The problems needn’t be done in order. Feel free to jump around.

Times from Spring ‘18 (in hours, n=22)

Times	Problem 1	Problem 2	Problem 3	Problem 4
average time (hours)	4.25	2.1	3.2	1.8
median time (hours)	4.0	2.0	3.0	1.5
25% took more than	5.1	3.0	4	2.4
10% took more than	7.9	3.9	4	3.0

Submission:
- In your yourFullName CS251 Spring 2019 Folder, create a Google Doc named yourFullName CS251 PS10.
- At the top of your yourFullName CS251 PS10 doc, include your name, problem set number, date of submission, and an approximation of how long each problem part took.
- For all parts of all problems, include all answers (including SML code) in your PS10 google doc. Format code using a fixed-width font, like Consolas or Courier New. You can use a small font size if that helps.
- In Problems 1–5, you will create the following code files from starter files populating your ~/cs251/sml/ps10 directory on your csenv/wx Virtual Machine:
  - Problem 1: yourAccountName-MiniFP.sml, yourAccountName-MiniFPInterp.sml, yourAccountName-MiniFPTest.sml
  - Problem 2: yourAccountName-BindexToPostFix.sml
  - Problem 3: yourAccountName-Simprex.sml and yourAccountName-SimprexEnvInterp.sml
  - Problem 4: yourAccountName-ValexPS10.sml and yourAccountName-ValexEnvInterpPS10.sml
  For these problems:
  - Include all new/modified functions from the files named yourAccountName... in your Google Doc (so that I can comment on them). In the Google Doc, you need only include the functions you modified, not all of the code of all the files you edited!
  - Don’t forget to include the following written (noncode) answers in your solutions:
    - The definitions of F and F_sx from Problem 1a.
    - The result of hand translating the Bindex program in Problem 2a into PostFix (use s-expression syntax).
    - The results of evaluating the sample Simprex programs in Problem 3a.
  - Drop a copy of your entire ps10 directory into your ~/cs251/drop/ps10 drop folder on cs.wellesley.edu by executing the following (replacing both occurrences of gdome by your cs server username):
```
scp -r ~/cs251/sml/ps10 gdome@cs.wellesley.edu:/students/gdome/cs251/drop/ps10
```

Starting this Problem Set

All problems involve starter files in the ~/cs251/sml/ps10 directory in your csenv/wx Virtual Machine. To create this directory, follow the git instructions in this doc. If you enounter 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: MiniFP Interpreter (33 points)

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.

Background

In Section 11 of his Turing Award lecture paper, John Backus describes an applicative language named FP, which you studied in PS7 Problem 2. (Make sure you complete that problem before you start this one.)

In this problem, you will flesh out the skeleton of an interpreter for MiniFP, a subset of FP that implements many of FP’s features. The fact that functional forms in FP (and MiniFP) have implicit parameters (rather than parameters with explicit names) significantly simplifies the structure of this interpreter. In particular, the environment structures used to handle naming in Bindex are not necessary in MiniFP.

Objects

The objects manipulated by MiniFP programs are specified by the obj data type in the file MiniFP.sml:

datatype obj = 
    Int of int (* integer objects *)
  | Seq of obj list (* sequence of objects *)

MiniFP objects are either:

integers (introduced by the Int constructor); or
sequences of objects (introduced by the Seq constructor).

(Note: Although the Int and Seq constructors have the same names as constructors in the Sexp, PostFix, Intex, and Bindex modules, the MiniFP constructors are different. They are defined in the MiniFP module in the file MiniFP.sml in the ps10 directory. Explicit qualification can be used to disambiguate the constructors from these modules — e.g., Sexp.Int vs. MiniFP.Int.)

The following table shows how some objects in FP notation can be expressed as instances of the obj data type, and also in an s-expression notation. In the table, $i$ denotes an integer and $x$ denotes an object.

FP Notation	SML obj Notation	S-expression Notation
$i$	`Int` $i$	$i$
$\langle x_1, \dots, x_n\rangle$	`Seq[`$x_1$`,`$\ldots$`,`$x_n$`]`	`(`$x_1 \ldots\ x_n$`)`
$17$	`Int 17`	`17`
$\langle 8, -3, 6 \rangle$	`Seq[Int 8, Int ~3, Int 6]`	`(8 -3 6)`
$\langle 17, \langle 8, -3, 6\rangle \rangle$	`Seq[Int 17, Seq[Int 8, Int ~3, Int 6]]`	`(17 (8 -3 6))`
$\langle \langle 8, -3, 6\rangle, \langle 5, 1, 7\rangle\rangle$	`Seq[Seq[Int 8, Int ~3, Int 6], Seq[Int 5, Int 1, Int 7]]`	`((8 -3 6) (5 1 7))`

Here are some definitions of MiniFP objects in the file MiniFP.sml that we will use in later examples. Each of these has type MiniFP.obj.

val vector1 = Seq[Int 2,  Int 3,  Int 5]

val vector2 = Seq[Int 10,  Int 20,  Int 30]

val vectors = Seq[vector1,  vector2] (* A pair of vectors or a 2x3 matrix *)

val matrix = Seq[Seq[Int 1,  Int 4],  Seq[Int 8,  Int 6],  Seq[Int 7,  Int 9]] (* A 3x2 matrix *)

val matrices1 = Seq[vectors,  matrix] (* A pair of a 2x3 matrix and a 3x2 matrix *)

val matrices2 = Seq[matrix,  vectors] (* A pair of a 3x2 matrix and a 2x3 matrix *)

For comparison, here are the s-expression forms of the these objects, also defined in MiniFP.sml. Each of these has type Sexp.sexp.

val vector1_sx = Sexp.stringToSexp("(2 3 5)")

val vector2_sx = Sexp.stringToSexp("(10 20 30)")

val vectors_sx = Sexp.Seq([vector1_sx, vector2_sx])

val matrix_sx =  Sexp.stringToSexp("((1 4) (8 6) (7 9))")

val matrices1_sx = Sexp.Seq([vectors_sx, matrix_sx])

val matrices2_sx = Sexp.Seq([matrix_sx, vectors_sx])

Because both MiniFP and Sexp have datatype constructors named Int and Seq, the corresponding versions of this seem similar in printed representation. For example:

- MiniFP.matrix;
val it = Seq [Seq [Int 1,Int 4],Seq [Int 8,Int 6],Seq [Int 7,Int 9]]
  : MiniFP.obj

- MiniFP.matrix_sx;
val it = Seq [Seq [Int 1,Int 4],Seq [Int 8,Int 6],Seq [Int 7,Int 9]]
  : Sexp.sexp

However, notice that matrix has type MiniFP.obj and matrix_sx has type Sexp.sexp. In fully qualified form, matrix would be written:

MiniFP.Seq [MiniFP.Seq [MiniFP.Int 1, MiniFP.Int 4],
            MiniFP.Seq [MiniFP.Int 8, MiniFP.Int 6],
            MiniFP.Seq [MiniFP.Int 7, MiniFP.Int 9]]

while matrix_sx would be written

Sexp.Seq [Sexp.Seq [Sexp.Int 1, Sexp.Int 4],
          Sexp.Seq [Sexp.Int 8, Sexp.Int 6],
          Sexp.Seq [Sexp.Int 7, Sexp.Int 9]]

MiniFP.sml includes the following functions for converting between strings, s-expressions, and MiniFP objects:

- sexpToObj;
val it = fn : Sexp.sexp -> obj

- stringToObj;
val it = fn : string -> obj

- objToSexp;
val it = fn : obj -> Sexp.sexp

- objToString;
val it = fn : obj -> string

For example:

- matrix = sexpToObj matrix_sx;
val it = true : bool

- matrix = stringToObj "((1 4) (8 6) (7 9))";
val it = true : bool

- Sexp.isEqual(objToSexp matrix, matrix_sx);
val it = true : bool
(* Recall that Sexp.sexp is *not* an equality type, so can't compare 
   two sexps with =. Need to use Sexp.isEqual instead. *)

- objToString matrix;
val it = "((1 4) (8 6) (7 9))" : string

Functional Forms

MiniFP programs are functional forms which include primitive functions like $\mathrm{id}$, $\mathrm{+}$, and $\mathrm{distr}$, as well as combining forms like composition ($\circ$), mapping ($\alpha$), and reduction (/).

Here is the data type funForm for representing functional forms in SML:

  and funForm = 
      Id    (* identity *)
    | Add   (* addition *)
    | Sub   (* subtraction *)
    | Mul   (* multiplication *) 
    | Div   (* division *)
    | Distl (* distribute from left *)
    | Distr (* distribute from right *)
    | Trans (* transpose *)
    | Const of obj  (* constant function *)
    | Sel of int    (* selection *)
    | Map of funForm  (* alpha = map *)
    | Reduce of funForm (* / = reduce *)
    | BinaryToUnary of funForm * obj (* bu *)
    | Compose of funForm * funForm  (* o = composition *)
    | FunSeq of funForm list (* [...] = function sequence *)

The following table shows the correspondence between FP notation for functional forms, the SML data type notation, and an s-expression notation. In the table, $i$ denotes an integer, $x$ denotes an object, and $f$ denotes a functional form.

FP Notation	SML funForm Notation	S-expression notation
$\mathrm{id}$	`Id`	`id`
$+$	`Add`	`+`
$-$	`Sub`	`-`
$\times$	`Mul`	`x`
$\div$	`Div`	`-:`
$\mathrm{distl}$	`Distl`	`distl`
$\mathrm{distr}$	`Distr`	`distr`
$\mathrm{trans}$	`Trans`	`trans`
$\overline{x}$	`Const` $x$	`($`$\ x$`)`
$i$	`Sel` $i$	$i$
$\alpha\,f$	`Map` $f$	`(a`$\ f$`)`
$/\,f$	`Reduce` $f$	`(/` $\,f$`)`
$\mathrm{bu}\ \,f\ x$	`BinaryToUnary(`$f$`,`$x$`)`	`(bu`$\ f$$x$`)`
$f_1 \circ\ f_2$	`Compose(`$f_1$`,`$f_2$`)`	`(o`$\ f_1$$f_2$`)`
$[f_1 \dots\ f_n]$	`FunSeq[`$f_1$`,`$\dots$`,`$f_n$`]`	`(`$f_1\ \dots\ f_n$`)`

For example, consider the inner product and matrix multiplication examples from Sections 11.3.2 and 11.3.3 (p. 622) of Backus’s paper:

\[
\begin{array}{rcl}
IP & \equiv{} & (/+)\circ(\alpha{}\times)\circ\mathrm{trans} \\
MM & \equiv{} & (\alpha\alpha\mathrm{IP})\circ(\alpha\mathrm{distl})\circ\mathrm{distr}\circ[1,\mathrm{trans}\circ2]
\end{array}
\]

These can be expressed as SML MiniFP.funForm instances via the following definitions (included in MiniFP.sml):

val IP = Compose(Reduce Add, Compose(Map Mul, Trans))

val MM = Compose(Map(Map IP),
                 Compose(Map Distl,
                         Compose(Distr,
                                 FunSeq[Sel 1, Compose(Trans, Sel 2)])))

These can also be expressed as SML Sexp.sexp instances via the following definitions (also included in MiniFP.sml):

val IP_sx = Sexp.stringToSexp "(o (/ +) (o (a x) trans))"

val MM_sx = Sexp.stringToSexp "(o (a (a (o (/ +) (o (a x) trans))))\
                               \  (o (a distl)                     \
                               \     (o distr                      \
                               \        (1 (o trans 2)))))"

(The MM_sx definition illustrates the SML convention for entering multiline strings. Each nonterminal line must end with a backslash character, and the next line must begin with a backslash character.)

MiniFP.sml includes the following functions for converting between strings, s-expressions, and MiniFP functional forms:

- sexpToFunForm;
val it = fn : Sexp.sexp -> funForm

- stringToFunForm;
val it = fn : string -> funForm

- funFormToSexp;
val it = fn : funForm -> Sexp.sexp

- funFormToString;
val it = fn : funForm -> string

For example:

- IP = sexpToFunForm IP_sx;
val it = true : bool

- IP = stringToFunForm "(o (/ +) (o (a x) trans))";
val it = true : bool

- Sexp.isEqual(funFormToSexp IP, IP_sx);
val it = true : bool

- funFormToString IP;
val it = "(o (/ +) (o (a x) trans))" : string

1a. A MiniFP Program (5 points)

Begin this part by renaming the file MiniFP.sml to be yourAccountName-MiniFP.sml.

In PS7 Problem 2g, you studied this functional form:

\[
F \equiv{} (\alpha{}/+) \circ (\alpha\alpha{}\times) \circ\
(\alpha\mathrm{distl}) \circ \mathrm{distr} \circ [\mathrm{id},\mathrm{id}]
\]

In the file yourAccountName-MiniFP.sml, express this functional form in SML via two definitions that flesh out the skeleton:

val F = ... 

val F_sx = ...

The value of F should have type funForm and the value of F_sx should have type Sexp.sexp.

Notes:

You can safely ignore this warning when when send your yourAccountName-MiniFP.sml buffer into the *sml* interpreter buffer:
```
../utils/Utils.sml:35.48 Warning: calling polyEqual
```

After you send your yourAccountName-MiniFP.sml buffer into the *sml* interpreter buffer, the following equalities should hold with your definitions:

- open MiniFP;
... many lines of printout omitted ...

- F = sexpToFunForm F_sx;
val it = true : bool

- Sexp.isEqual(funFormToSexp F, F_sx);
val it = true : bool

1b. A MiniFP Interpreter (28 points)

Begin this part by renaming the files MiniFPInterp.sml and MiniFPTest.sml to be yourAccountName-MiniFPInterp.sml and yourAccountName-MiniFPTest.sml. Additionally:

In the file yourAccountName-MiniFPInterp.sml, change the first line of the file from
```
use "../ps10/MiniFP.sml";
```
to
```
use "../ps10/yourAccountName-MiniFP.sml";
```
In the file yourAccountName-MiniFPTest.sml, change the first line of the file from
```
use "../ps10/MiniFPInterp.sml";
```
to
```
use "../ps10/yourAccountName-MiniFPInterp.sml";
```

A MiniFP interpreter specifies the object that results from applying a program (i.e., functional form) to an object. So a MiniFP interpreter is simply an apply function with the following type:

val apply: MiniFP.funForm -> MiniFP.obj -> MiniFP.obj

The semantics (meaning) of all MiniFP functional forms is given in Sections 11.2.3 and 11.2.4 of Backus’s paper. The only difference between MiniFP and FP semantics is that in MiniFP, the Reduce functional form is defined only on nonempty sequences. So applying Reduce Add to Seq[] is an error in MiniFP, but not in FP (where it denotes 0).

In this task, your goal is to implement a complete MiniFP interpreter by fleshing out the skeleton of the apply function in the file yourAccountName-MiniFPInterp.sml. In this sekelton, the clauses for Id, Add, and Trans have been written for you, and all other clauses are stubs that act like Id. Your task is to flesh out the clauses for all the other MiniFP functional forms so that they work as expected. x

Notes:

Each functional form takes a MiniFP.obj as an input and returns a MiniFP.obj as an output. The expected type, size (for sequences), etc. of the object depends on the details of the functional form. E.g., distl expects the object to be a sequence of exactly two elements, where the first element can be any object but the second element must be a sequence (with any number of elements). These constraints can be concisely specified via pattern matching in an apply clause; for example:
```
apply Distl (Seq[y,Seq zs]) = ...
```
When implementing a clause, think carefully about the constraints and be sure not to overconstrain the object. E.g., in the Distl clause, the first sequence value can be any object y; you should not force it to be a sequence value Seq ys, which would preclude it from being an integer.
You can test your interpreter by sending your yourAccountName-MiniFPInterp.sml to the *sml* buffer. After you open MiniFPInterp;, you can interactively test your apply function on the kinds of examples shown below. See further down for how to run a suite of test cases on your interpreter.
You can safely ignore this warning when when send your yourAccountName-MiniFPInterp.sml buffer into the *sml* interpreter buffer:
```
../utils/Utils.sml:35.48 Warning: calling polyEqual
```
It is strongly recommended that you flesh out apply incrementally. That is, flesh out one clause and a time and test that before going to the next clause.
Feel free to define and use helper functions.
You should raise an EvalError with an (using raise EvalError error-message-string-goes-here) when an error situation is encountered. The skeleton intepreter already raises two such errors: (1) Error: Ill-formed application for an ill-formed application and Error: transpose -- sequences not all of same length for transpose. Your intepreter clauses should raise an EvalError in the following three cases:
- division by zero
- index out of bounds for Sel
- reduction on an empty list
Here are some sample error messages show using the testApply function described later:
```
- testApply Div (Seq[Int 5, Int 0]);
val it = "EvalError: Division by zero" : string

- testApply (Sel 4) vector1;
val it = "EvalError: Selection index 4 out of bounds [1..3]" : string

- testApply (Reduce Add) (Seq[]);
val it = "EvalError: Reduction of empty sequence" : string
```

Below are numerous examples of the correct behavior of MiniFP’s apply function. Your apply function should behave the same way. (See further down for how to run a suite of automated test cases.)

- open MiniFPInterp; 
... many lines of printout omitted ...

- apply;
val it = fn : funForm -> obj -> obj

- apply Id (Int 17);
val it = Int 17 : obj

- apply Add (Seq[Int 17, Int 3]);
val it = Int 20 : obj

- apply Mul (Seq[Int 17, Int 3]);
val it = Int 51 : obj

- apply Sub (Seq[Int 17, Int 3]);
val it = Int 14 : obj

- apply Div (Seq[Int 17, Int 3]);
val it = Int 5 : obj

- vector1;
val it = Seq [Int 2,Int 3,Int 5] : obj

- apply Id vector1;
val it = Seq [Int 2,Int 3,Int 5] : obj

- apply (Const (Int 17)) vector1;
val it = Int 17 : obj

- apply (Sel 1) vector1;
val it = Int 2 : obj

- apply (Sel 2) vector1;
val it = Int 3 : obj

- apply (Sel 3) vector1;
val it = Int 5 : obj

- apply Distl (Seq[Int 7, vector1]);
val it = Seq [Seq [Int #,Int #],Seq [Int #,Int #],Seq [Int #,Int #]] : obj

- Control.Print.printDepth := 1000;
... many lines of printout omitted ...
val it = () : unit

- apply Distl (Seq[Int 7, vector1]);
val it = Seq [Seq [Int 7,Int 2],Seq [Int 7,Int 3],Seq [Int 7,Int 5]] : obj

- apply Distr (Seq[vector1, Int 7]);
val it = Seq [Seq [Int 2,Int 7],Seq [Int 3,Int 7],Seq [Int 5,Int 7]] : obj

- apply (BinaryToUnary (Add, Int 1)) (Int 17);
val it = Int 18 : obj

- apply (Map (Const (Int 17))) vector1;
val it = Seq [Int 17,Int 17,Int 17] : obj

- apply (Map (BinaryToUnary (Mul, Int 2))) vector1;
val it = Seq [Int 4,Int 6,Int 10] : obj

- apply (Reduce Add) vector1;
val it = Int 10 : obj (* 2 + (3 + 5) *)

- apply (Reduce Mul) vector1;
val it = Int 30 : obj (* 2 * (3 * 5) *)

- apply (Reduce Sub) vector1;
val it = Int 4 : obj (* 2 - (3 - 5) *)

- apply (Compose(Map (BinaryToUnary (Add, Int 1)), Map (BinaryToUnary (Mul, Int 2)))) vector1;
val it = Seq [Int 5,Int 7,Int 11] : obj

(* You can use stringToFunForm and stringToObj to simplify testing *)
- apply (stringToFunForm "(o (a (bu + 1)) (a (bu x 2)))") (stringToObj "(2 3 5)");
val it = Seq [Int 5,Int 7,Int 11] : obj

- apply (FunSeq[Const (Int 17), Id, Map (BinaryToUnary (Add, Int 1))]) vector1;
val it = Seq [Int 17,Seq [Int 2,Int 3,Int 5],Seq [Int 3,Int 4,Int 6]] : obj

- matrix;
val it = Seq [Seq [Int 1,Int 4],Seq [Int 8,Int 6],Seq [Int 7,Int 9]] : obj

- apply Trans matrix;
val it = Seq [Seq [Int 1,Int 8,Int 7],Seq [Int 4,Int 6,Int 9]] : obj

- apply (Compose(Trans,Trans)) matrix;
val it = Seq [Seq [Int 1,Int 4],Seq [Int 8,Int 6],Seq [Int 7,Int 9]] : obj

- vectors;
val it = Seq [Seq [Int 2,Int 3,Int 5],Seq [Int 10,Int 20,Int 30]] : obj

- apply IP vectors;
val it = Int 230 : obj

- matrices1;
val it =
  Seq
    [Seq [Seq [Int 2,Int 3,Int 5],Seq [Int 10,Int 20,Int 30]],
     Seq [Seq [Int 1,Int 4],Seq [Int 8,Int 6],Seq [Int 7,Int 9]]] : obj

- apply MM matrices1;
val it = Seq [Seq [Int 61,Int 71],Seq [Int 380,Int 430]] : obj

- matrices2;
val it =
  Seq
    [Seq [Seq [Int 1,Int 4],Seq [Int 8,Int 6],Seq [Int 7,Int 9]],
     Seq [Seq [Int 2,Int 3,Int 5],Seq [Int 10,Int 20,Int 30]]] : obj

- apply MM matrices2;
val it =
  Seq
    [Seq [Int 42,Int 83,Int 125],
     Seq [Int 76,Int 144,Int 220], (* manually reformated to look better *)
     Seq [Int 104,Int 201,Int 305]] : obj

By default, SML does not display the message of an exception, which makes examples like the following harder to understand. For example:

- apply (Sel 4) vector1;

uncaught exception EvalError
  raised at: /tmp/emacs-region1678BTc:17.10-21.15

The issue here is an index-out-of-bounds exception, but because SML does not display the exception message, this may not be obvious.

For better testing of cases involving exceptions, MiniFPInterp.sml includes the following helper function:

(* testApply: funForm -> obj -> string *)
and testApply funForm obj =
    objToString (apply funForm obj)
    handle (EvalError msg) => "EvalError: " ^ msg
         | (SyntaxError msg) => "SyntaxError: " ^ msg
         | other => "Exception: " ^ (exnMessage other)

Here are some examples of using testApply to show error messages:

- testApply (Sel 4) vector1;
val it = "EvalError: Selection index 4 out of bounds [1..3]" : string

- testApply (Reduce Add) (Seq[]);
val it = "EvalError: Reduction of empty sequence" : string

- testApply Div (Seq[Int 5, Int 0]);
val it = "EvalError: Division by zero" : string

You can test your interpreter on a suite of test cases by sending your yourAccountName-MiniFPTest.sml buffer to your *sml* interpreter buffer. This will load the MiniFPTest structure defined in this file and invoke MiniFPTest.test(), which will test your interpreter on over 100 test cases.

The test cases are defined in a variable testSuite, each of whose entries has the form:

((function-form-string, object-string), result-string)

The tester first parses function-form-string and object-string into a function form f and object x, respectively. It then applies f to x, and converts the resulting object into a string. If this string matches result-string, the test passes by displaying OK!. Otherwise, the test fails by displaying ***TESTING MISMATCH*** and showing the difference between the expected result and the actual result.

If the application of f to x raises an exception, the tester converts the exception message to an error string; this makes it possible for the tester to verify that the interpreter handles error situations correctly.

Your implementation should be able to pass all the test cases in yourAccountName-MiniFPTest.sml. In order to do this, you will have to make the error messages in any EvalError exceptions you raise match the ones in the testing suite.

You are encouraged to add additional test cases to yourAccountName-miniFPTest.sml

2. Bindex To PostFix (22 points)

Background

In lecture, and in PS9 Problem 5, we studied the following intexToPostFix function that automatically translates Intex programs to equivalent PostFix programs:

fun intexToPostFix (Intex.Intex(numargs, exp)) =
  PostFix.PostFix(numargs, expToCmds exp 0)
    (* 0 is a depth argument that statically tracks 
       how many values are on stack above the arguments *)

and expToCmds (Intex.Int i) depth = [PostFix.Int i]
  | expToCmds (Intex.Arg index) depth = [PostFix.Int (index + depth), PostFix.Nget]
   (* specified argument is on stack at index + depth *)
  | expToCmds (Intex.BinApp(binop,exp1,exp2)) depth =
    (expToCmds exp1 depth) (* 1st operand is at same depth as whole binapp *)
    @ (expToCmds exp2 (depth + 1)) (* for 2nd operand, add 1 to depth 
                                      to account for 1st operand *)
    @ [PostFix.Arithop (binopToArithop binop)]

and binopToArithop Intex.Add = PostFix.Add
  | binopToArithop Intex.Sub = PostFix.Sub
  | binopToArithop Intex.Mul = PostFix.Mul
  | binopToArithop Intex.Div = PostFix.Div
  | binopToArithop Intex.Rem = PostFix.Rem

For example, given the Intex program intexP2 expressed as an Intex.pgm datatype instance

val intexP2 = Intex(4, BinApp(Mul,
                              BinApp(Sub, Arg 1, Arg 2),
                              BinApp(Div, Arg 3, Arg 4)))

the intexToPostFix translation is as follows:

- intexToPostFix(intexP2);
val it =
  PostFix
    (4,
     [Int 1,Nget,Int 3,Nget,Arithop Sub,Int 4,Nget,Int 6,Nget,Arithop Div,
      Arithop Mul]) : PostFix.pgm

With the helper function translateString shown below, the input and output of translation can be expressed as strings in s-expression format:

fun translateString intexPgmString =
  PostFix.pgmToString (intexToPostFix (Intex.stringToPgm intexPgmString))

- IntexToPostFix.translateString("(intex 4 (* (- ($ 1) ($ 2)) (/ ($ 3) ($ 4))))");
val it = "(postfix 4 1 nget 3 nget sub 4 nget 6 nget div mul)" : string

There are two key aspects to the translation from Intex to PostFix:

The expToCmds function translates every Intex expression to a sequence of PostFix commands that, when executed, will push the integer value of that expression onto the stack. In the case of translating a binary application expression, this sequence is composed by appending the sequences for the two operands followed by the appropriate arithmetic operator command.
The trickiest part of expToCommands is knowing how many integers are on the stack above the program arguments, so that references to Intex arguments by index can be appropriately translated. This is handled by a depth argument to expToCommands that keeps track of this number. Note that the first operand of a binary application has the same depth as the whole binary application expression, but the second operand has a depth one greater than the first to account for the integer value of the first operand pushed onto the stack.

Your Task

In this problem, you will think about and implement a similar translator from Bindex programs to PostFix programs.

Hand translating a sample Bindex expression (8 points) To get a better sense for the issues involved, give the PostFix program (in s-expression notation) that results from translating by hand the following Bindex program:
```
(bindex (a b)
  (- (bind c (+ a b)
       (+ (bind d (/ c a)
            (* (+ d b)
               (- a d)))
          (* b c)))
     (* b a)))
```
In an earlier version of this assignment, the above program was missing two close parens in the next-to-last line. This has now been fixed.

As in the the Intex-to-PostFix translator studied in class, your translation should have the following properties:
- The operands of an operator should be translated from left to right.
- When the commands translated from an expression are executed on a stack of values, they should have the effect of pushing onto the stack a single value that is the value of that expression. No other changes should be made to the original stack other than pushing this single value.
- The original program arguments should never be removed from the stack; they should always be the bottommost values on the stack.
- The value introduce by a bind should be pushed onto the stack before the body is evaluated and not popped until after the value of the body has been determined.
- You should not perform any clever optimizations in your translation. The purpose of this problem is to give you insight into how the translation can be performed automatically without any cleverness.
Your are required to comment the PostFix code that results from your translation to explain how it corresponds to parts of the original Bindex program.

Run your resulting program in PostFix to verify that it works as expected. In particular, running the PostFix program that results from hand translating the above Bindex program on the arguments 2 6 should return 16. If it doesn’t, there’s a bug in your translation strategy.

Fleshing out the translator (14 points): The file ps10/BindexToPostFix.sml contains a skeleton of the Bindex to PostFix translator in which all Bindex expressions translate to a command sequence consisting of the single integer command 42:

fun makeArgEnv args = Env.make args (Utils.range 1 ((length args) + 1))
(* returned env associates each arg name with its 1-based index *)

fun envPushAll env = Env.map (fn index => index + 1) env
(* add one to the index for each name in env *)

fun envPush name env = Env.bind name 1 (envPushAll env)

fun bindexToPostFix (Bindex.Bindex(args, body)) =
  PostFix.PostFix(length args, expToCmds body (makeArgEnv args))

(* In expToCmds, env statically tracks the depth of each named variable
   value on the stack *)
and expToCmds (Bindex.Int i) env = [PostFix.Int 42] (* replace this stub *)
  | expToCmds (Bindex.Var name) env = [PostFix.Int 42] (* replace this stub *)
  | expToCmds (Bindex.BinApp(binop, rand1, rand2)) env = [PostFix.Int 42] (* replace this stub *)
  | expToCmds (Bindex.Bind(name, defn, body)) env = [PostFix.Int 42] (* replace this stub *)

and binopToArithop Bindex.Add = PostFix.Add
  | binopToArithop Bindex.Sub = PostFix.Sub
  | binopToArithop Bindex.Mul = PostFix.Mul
  | binopToArithop Bindex.Div = PostFix.Div
  | binopToArithop Bindex.Rem = PostFix.Rem

Begin this part by renaming the file BindexToPostFix.sml to be yourAccountName-BindexToPostFix.sml.

When this file is loaded, evaluating the expression BindexToPostFix.testAll() will run the translator on a collection of test cases. Initially, all of these test cases will fail. Your task is to redefine the clauses of expToCmds so that all the test cases succeed.

Notes:

The expToCmds function in the Bindex to PostFix translator uses an environment to track the depth of each variable name in the program. Recall that an environment (defined by the Env structure in utils/Env.sml) maps names to values. In this case, it maps names in a Bindex program to the current stack depth of the value associated with that name. Carefully study the helper functions makeArgEnv, envPushAll, and envPush to understand what they do; all are helpful in the contex of this problem.
As in the Intex to PostFix translator, in the Bindex to PostFix translator, each Bindex expression should translate to a sequence of PostFix commands that, when executed, pushes exactly one value — the integer value of that expression — onto the stack. More formally, translating a Bindex expression to PostFix should obey the following invariant:

A Bindex expression E should translate to a sequence of commands, that, when executed on a stack S, should result in a stack v :: S, where v is the result of evaluating E relative to an environment represented by S.
For simplicity, you may assume there are no unbound variables in the Bindex program you are translating. With this assumption, you may use the Option.valOf function to extract the value v from a SOME(v) value.

The BindexToPostFix structure contains a testTranslator function that takes the name of a file containing a Bindex program and a list of argument lists and (1) displays the Bindex program as an s-expression string, (2) displays the PostFix program resulting from the translation as an s-expression string and (3) tests the behavior of both programs on each of the argument lists in the list of argument lists. If the behaviors match, it prints an approprate message; if they don’t match, it reports an an error with the two different result values. For instance, in the initial skelton, the behavioral tests fail on the program in ../bindex/avg.bdx:

Testing Bindex program file ../bindex/avg.bdx

Bindex program input to translation:
(bindex (a b) (/ (+ a b) 2))

PostFix program output of translation:
(postfix 2 42)
https://www.theguardian.com/society/2019/may/10/blow-up-how-half-a-tonne-of-cocaine-transformed-the-life-of-an-island?utm_source=pocket-newtab
Testing args [3,7]: *** ERROR IN TRANSLATION ***
  Bindex result: 5
  PostFix result: 42

Testing args [15,5]: *** ERROR IN TRANSLATION ***
  Bindex result: 10
  PostFix result: 42

However, when the translator is working, the following will be displayed:

Testing Bindex program file ../bindex/avg.bdx

Bindex program input to translation:
(bindex (a b) (/ (+ a b) 2))

PostFix program output of translation:
(postfix 2 1 nget 3 nget add 2 div)

Testing args [3,7]: both programs return 5

Testing args [15,5]: both programs return 10

The function BindexToPostFix.testAll() runs a suite of test cases. You have succeeded when all of the test cases succeed when you evaluate this expression.
If some test cases succeed but others fail, it is likely that you are not obeying the invariant mentioned above. Think about this invariant carefully!

3. Simprex (37 points)

Background

Rae Q. Cerf of Toy-Languages-я-Us likes the sigma construct from the Bindex lecture, but she wants something more general. In addition to expressing sums, she would also like to express numeric functions like factorial and exponentiation that are easily definable via simple recursion. The functions that Rae wants to define all have the following form:

f(n) = z, if n ≤ 0
f(n) = c(n, f(n-1)), if n > 0

Here, z is an integer that defines the value of f for any non-positive integer value and and c is a binary combining function that combines n and the value of f(n−1) for any positive n. Expanding the definition yields:

f(n) = c(n, c(n-1, c(n−2, ... c(2, c(1, z)))))

For example, to define the factorial function, Rae uses:

z_fact = 1
c_fact(i, a) = i*a

To define the exponentation function bⁿ, Rae uses:

z_expt = 1
c_expt(i, a) = b*a

In this case, c_expt ignores its first argument, but the fact that c_expt is called n times is important.

As another example, Rae defines the sum of the squares of the integers between 1 and n using

z_sos = 0
c_sos(i, a) = (i*i) + a

The examples considered so far don’t distinguish right-to-left vs. left-to-right evaluation, A simple example of that is

z_sub = 0
c_sub(i, a) = i-a

For example, when n is 4, the result is the value of 4 - (3 - (2 - (1 - 0))), which is 2, and not the value of 1 - (2 - (3 - (4 - 0))), which is -2.

Another example that distinguishes right-to-left vs. left-to-right evaluation is using Horner’s method to calculate the value of the polynomial x^(n-1) + 2*(x^(n-2)) + 3*(x^(n-3)) + ... + (n-1)*x + n:

z_horner = 0
c_horner(i, a) = i + x*a

For example, when n is 4 and x is 5, the result is (4 + 5*(3 + 5*(2 + 5*(1 + 5*0)))) = 194, which is the value of 5^3 + 2*5^2 + 3*5^1 + 4 = (125 + 50 + 15 + 4) = 194.

Rae designs an extension to Bindex named Simprex that adds a new simprec construct for expressing her simple recursions:

(simprec E_zero (Id_num Id_ans E_combine) E_arg)

This simprec expression evaluates E_arg to the integer value n_arg and E_zero to the integer value n_zero. If n_arg ≤ 0, it returns n_zero. Otherwise, it returns the value

c(n_arg, c(n_arg−1, c(n_arg−2, ... c(2, c(1, nzero)))))

where c is the binary combining function specified by (Id_num Id_ans E_combine). This denotes a two-argument function whose two formal parameters are named Id_num and Id_ans and whose body is E_combine. The Id_num parameter ranges over the numbers from n_arg down to 1, while the Id_ans parameter ranges over the answers built up by c starting at n_zero. The scope of Id_num and Id_ans includes only E_combine; it does not include E_zero or E_arg.

Here is a diagram illustrating the semantics of (simprec E_zero (Id_num Id_ans E_combine) E_arg), in which V_zero is the value of E_zero and V_arg is the value of E_arg:

simprec semantics diagram

Note that simprec is effectively performing a foldl on the list [1, 2, 3, ..., V_arg] starting with initial value V_zero using a combiner that would be expressed in Racket as (lambda (Id_num Id_ans) E_combine). Since Bindex does not have any functions (inluduing anonymous higher-order functions introduced by lambda), it is necessary to introduce a new simprec construct in which (Id_num Id_ans E_combine) effectively acts like Racket’s (lambda (Id_num Id_ans) E_combine).

Rae’s simprec expression is closely related to the notion of primitive recursive functions defined in the theory of computation.

Here are some sample Simprex programs along with associated diagrams:

;; Program that calculuates the factorial of n
(simprex (n) (simprec 1 (i a (* i a)) n))

simprec semantics diagram

;; Exponentiation program raising base b to power p 
(simprex (b p) (simprec 1 (i ans (* b ans)) p))

simprec semantics diagram

;; Program summing the squares of the numbers from 1 to hi
(simprex (hi) (simprec 0 (i sumSoFar (+ (* i i) sumSoFar)) hi))

simprec semantics diagram

;; Program distingishing right-to-left and left-to-right evaluation via subtraction
(simprex (n) (simprec 0 (i ans (- i ans)) n))

simprec semantics diagram

;; Calculating x^(n-1) + 2*(x^(n-2)) + 3*(x^(n-3)) + ... + (n-1)*x + n via Horner's method
(simprex (n x) (simprec 0 (i a (+ i (* x a)) n)))

simprec semantics diagram

Your Tasks

After completing her design, Rae is called away to work on another language design problem. Toy-Languages-я-Us is impressed with your CS251 background, and has hired you to implement the Simprex language, starting with a version of the Sigmex implementation. (Sigmex is the name of the language that results from extending Bindex with the sigma construct from lecture.) Your first week on the job, you are asked to complete the following tasks that Rae has specified in a memo she has written about finishing her project.

(18 points) Rae’s memo contains the following Simprex test programs. Give the results of running each of the programs on the argument 3. Show your work so that you may get partial credit if your answer is incorrect.

;; program 1 (2 points)
(simprex (a) (simprec 0 (b c (+ 2 c)) a))

;; program 2 (3 points)
(simprex (x) (simprec 0 (n sum (+ n (* x sum))) 4))

;; program 3 (4 points)
(simprex (y) (simprec 0 (a b (+ b (sigma c 1 a (* a c)))) y))

;; program 4 (9 points)
(simprex (n) 
  (simprec (simprec (* n (- n 3)) (q r r) (* n n))
           (c d (+ d (simprec 0 (x sum (+ sum (- (* 2 x) 1))) c))) 
           (simprec -5 (a b (+ 1 b)) (* n n))))

(19 points)

Rae has created a skeleton implementation of Simprex by modifying the files for the Sigmex (= Bindex + sigma) implementation to contain stubs for the simprec construct. Her modified files, which are named Simprex.sml and SimprexEnvInterp.sml, can be found in the ps10 folder.

Finish Rae’s implementation of the Simprex language by completing the following four tasks, which Rae has listed in her memo:
1. (2 points) Extend the definition of sexpToExp in Simprex.sml to correctly parse simprec expressions.
2. (2 points) Extend the definition of expToSexp in Simprex.sml to correctly unparse simprec expressions.
3. (3 points) Extend the definition of freeVarsExp in Simprex.sml to correctly determine the free variables of a simprec expression.
4. (12 points) Extend the definition of eval in SimprexEnvInterp.sml to correctly evaluate simprec expressions using the environment model.
Notes:

Begin this part by renaming the files Simprex.sml and SimprexEnvInterp.sml to be yourAccountName-Simprex.sml and yourAccountName-SimprexEnvInterp.sml. In the file yourAccountName-SimprexEnvInterp.sml, you also need to change the first line of the file from
```
use "../ps10-solns/Simprex.sml";
```
to
```
use "../ps10-solns/yourAccountName-Simprex.sml";
```
- This problem is similar the the Sigmex (= Bindex + sigma) language extension we implemented in lecture. You may wish to study the solution files bindex/Sigmex.sml and bindex/SigmexEnvInterp.sml as part of doing this problem.
- In Simprex.sml, the exp type is defined to be:
```
and exp = Int of int (* integer literal with value *)
        | Var of var (* variable reference *)
        | BinApp of binop * exp * exp (* binary operator application with rator, rands *)
        | Bind of var * exp * exp (* bind name to value of defn in body *)
        | Sigma of var * exp * exp * exp (* E_lo, E_hi, E_body *)
        | Simprec of exp * var * var * exp * exp 
                     (* zeroExp * numVar * ansVar * combExp * argExp *)
```
  The s-expression notation (simprec E_zero (I_num I_ans E_combine) E_arg) is represented in SML as
```
Simprec (<exp for E-zero>, <string for I_num>, <string for I_ans>, 
         <exp for E_combine>, <exp for E_arg>)
```
  For example, the expression (simprec 1 (x a (* x a)) n) is represented in SML as Simprec(Int 1, "x", "a", BinApp(Mul, Var "x", Var "a"), Var "n")
- You can test your modifications of sexpToExp, expToSexp, and freeVarsExp by loading yourAccountName-Simprex.sml into the *sml* buffer, and evaluating the expression Simprex.testSyntax();. This will display the results of various test cases for freeVarsExp, and indirectly will also test sexpToExp and expToSexp. Until sexpToExp is correctly defined, evaluating Simprex.testSyntax(); will raise uncaught exception SyntaxError.
- A common error in this problem is to neglect the nested parens in (Id_num Id_ans E_combine) when defining sexpToExp and expToSexp. For example, the factorial of 5 is calculated by (simprec 1 (i ans (* i ans)) 5), but (simprec 1 i ans (* i ans) 5) (without the nested parens around (i ans (* i ans)) would be a syntax error.
  
  Another way to think of this is as follows. Let’s study the structure of the Sexp instance created by Simprex.stringToSexp "(simprec 1 (i ans (* i ans)) 5)":
```
- Control.Print.printDepth := 100; (* change printDepth to show all details *)
... lots of printout omitted ...
val it = () : unit

- Simprex.stringToSexp "(simprec 1 (i ans (* i ans)) 5)";
val it =
  Seq
    [Sym "simprec",Int 1,
     Seq [Sym "i",Sym "ans",Seq [Sym "*",Sym "i",Sym "ans"]],Int 5] : sexp
```
  Every parenthesized unit in a string representation of an s-expression is converted to a Seq (really Sexp.Seq) with a list of values of type sexp. The list for (simprec 1 (i ans (* i ans)) 5) has four elements: one for each of the four components simprec, 1, (i ans (* i ans)) and 5. The third component is itself a list of the three elements i, ans, and (* i ans).
  
  Suppose you attempt to use the pattern Seq [Sym "simprec", ezero, Sym idnum, Sym idans, ecombine, earg] to match the Seq returned by Simprex.stringToSexp "(simprec 1 (i ans (* i ans)) 5)". This match will fail because the Seq pattern has 6 components and the Seq value it is matched against only has 4 components. How can you fix the Seq pattern to match the Seq value?
- You can test your modifications of eval by loading yourAccounName-SimprexEnvInterp.sml into the *sml* buffer and evaluating the expression SimprexEnvInterp.testEval();. This will display the results of various test cases for eval.

4. Extending Valex with New Primitive Operators (18 points)

The Valex language implementation is designed to make it easy to add new primitive operators to the language. In this problem, you are asked to extend Valex with some new primitive operators.

The files ValexPS10.sml and ValexEnvInterpPS10.sml in the ps10 folder contain a copy of the Valex language implementation we study in class.

In this problem, you will add each of the following four primitive operators to ValexPS10.sml:

(3 points) (abs n): Returns the absolute value of the integer n. E.g.
```
- ValexEnvInterp.repl();

valex> (abs -17)
17
 
valex> (abs 42) 
42
```
For this and other primops, it’s common to get a type checking error like this one::
```
/tmp/sml29487C4O:114.17-243.4 Error: operator and operand do not agree [tycon mismatch]
  operator domain: ident * (value list -> value)
  operand:         string * (value list -> int)
  in expression:
    Primop ("abs",(checkOneArg checkInt) (fn <pat> => <exp>))
```
The problem here is not ident vs. string, which the SML type checker knows are synonyms. The problem is that the meaning of each primop is determined by a function whose type must be value list -> value and the function you’re specifying has type value list -> int. What can you do to change the int to a value?.
(4 points) (sqrt n): If n is a non-negative integer, returns the integer square root n. The integer square root of a non-negative integer is the largest integer i such that i² ≤ n. Signals an EvalError if n is negative. E.g.
```
- ValexEnvInterp.repl();

valex> (sqrt 25) 
5

valex> (sqrt 35) 
5

valex> (sqrt 36) 
6

valex> (sqrt 37) 
6

valex> (sqrt -4)
Error: negative sqrt argument ~4
```
Hint: The Real and Math structures contain helpful functions for this problem.
(4 points) (range lo hi): Assume lo and hi are integers. If lo < hi, returns a list of integers from lo (inclusive) to hi (exclusive). Otherwise, returns the empty list. For example:
```
- ValexEnvInterp.repl();

valex> (range 1 20)
(list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19)

valex> (range 3 8) 
(list 3 4 5 6 7)

valex> (range 8 3)
#e
```
*Hint:* TheUtils.range` function is helpful here.

(7 points) (shift n xs) Assume n is an integer and xs is a list. If xs is empty, returns the empty list. If n is a nonnegative integer, returns a list that results from moving the first n elements of the list to the end of the list. If n is greater than the length L of the list, uses (n mod L) instead. If n is a negative integer, raises an error. For example:

- ValexEnvInterp.repl();

valex> (shift 2 (explode "abcdefg"))
(list 'c' 'd' 'e' 'f' 'g' 'a' 'b')

valex> (shift 6 (explode "abcdefg"))
(list 'g' 'a' 'b' 'c' 'd' 'e' 'f')

valex> (shift 0 (explode "abcdefg"))
(list 'a' 'b' 'c' 'd' 'e' 'f' 'g')

valex> (shift 17 (explode "abcdefg")) 
(list 'd' 'e' 'f' 'g' 'a' 'b' 'c') (* same as shift 3 *)

valex> (shift 17 (list))
#e

valex> (shift -3 (explode "abcdefg"))
Eval Error: negative shift number ~3

Notes:

Begin this part by renaming the files ValexPS10.sml and ValexEnvInterpPS10.sml to be yourAccountName-ValexPS10.sml and yourAccountName-ValexEnvInterpPS10.sml. In the file yourAccountName-ValexEnvInterpPS10.sml, you also need to change the first line of the file from
```
use "../ps10/ValexPS10.sml";
```
to
```
use "../ps10/yourAccountName-ValexPS10.sml";
```
All four primitives above can be added to Valex by adding new Primop entries to the primops list in ps10/ValexPS10.sml right below the spot with this SML comment:
```
(* Put your new primops from PS10 here *)
```
Study the other primitives to see how primitives are declared.
Be careful to change the Valex implementation in the ps10 directory, not the one in the valex directory.
You should only change ValexPS10.sml and not ValexEnvInterpPS10.sml
For sqrt and shift, you can raise an EvalError using raise EvalError error-message-string-goes-here
To test your implementation after editing yourAccountName-ValexPS10.sml, first load yourAccountName-ValexEnvInterpPS10.sml (not yourAccountName-ValexPS10.sml) into a *sml* buffer, and then test your new primitives interactively in a Valex read-eval-print loop (REPL) launched by invoking ValexEnvInterp.repl().

Extra Credit: Partial Evaluation (25 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

Before beginning this part, you should rename the files BindexPartialEval.sml and BindexPartialEvalTest.sml to be yourAccountName-BindexPartialEval.sml and yourAccountName-BindexPartialEvalTest.sml. In the file yourAccountName-BindexPartialEvalTest.sml, you also need to change the first line of the file from

use "../ps10/BindexPartialEval.sml";

use "../ps10/yourAccountName-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:

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).
In order to test your partial evaluator, load yourAccountName-BindexPartialEvalTest.sml into an *sml* buffer, and evaluate BindexPartialEvalTest.testAll(). This applies your partial evaluator to all the test entries in the list testEntries in the file yourAccountName-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:
```
- BindexPartialEvalTest.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 BindexPartialEvalTest.testPartialEval function, which takes a string representation of a Bindex program. For example:

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

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

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

FP Notation	SML funForm Notation	S-expression notation
\(\mathrm{id}\)	`Id`	`id`
\(+\)	`Add`	`+`
\(-\)	`Sub`	`-`
\(\times\)	`Mul`	`x`
\(\div\)	`Div`	`-:`
\(\mathrm{distl}\)	`Distl`	`distl`
\(\mathrm{distr}\)	`Distr`	`distr`
\(\mathrm{trans}\)	`Trans`	`trans`
\(\overline{x}\)	`Const` \(x\)	`($`\(\ x\)`)`
\(i\)	`Sel` \(i\)	\(i\)
\(\alpha\,f\)	`Map` \(f\)	`(a`\(\ f\)`)`
\(/\,f\)	`Reduce` \(f\)	`(/` \(\,f\)`)`
\(\mathrm{bu}\ \,f\ x\)	`BinaryToUnary(`\(f\)`,`\(x\)`)`	`(bu`\(\ f\)\(x\)`)`
\(f_1 \circ\ f_2\)	`Compose(`\(f_1\)`,`\(f_2\)`)`	`(o`\(\ f_1\)\(f_2\)`)`
\([f_1 \dots\ f_n]\)	`FunSeq[`\(f_1\)`,`\(\dots\)`,`\(f_n\)`]`	`(`\(f_1\ \dots\ f_n\)`)`

FP Notation	SML obj Notation	S-expression Notation
\(i\)	`Int` \(i\)	\(i\)
\(\langle x_1, \dots, x_n\rangle\)	`Seq[`\(x_1\)`,`\(\ldots\)`,`\(x_n\)`]`	`(`\(x_1 \ldots\ x_n\)`)`
\(17\)	`Int 17`	`17`
\(\langle 8, -3, 6 \rangle\)	`Seq[Int 8, Int ~3, Int 6]`	`(8 -3 6)`
\(\langle 17, \langle 8, -3, 6\rangle \rangle\)	`Seq[Int 17, Seq[Int 8, Int ~3, Int 6]]`	`(17 (8 -3 6))`
\(\langle \langle 8, -3, 6\rangle, \langle 5, 1, 7\rangle\rangle\)	`Seq[Seq[Int 8, Int ~3, Int 6], Seq[Int 5, Int 1, Int 7]]`	`((8 -3 6) (5 1 7))`