PS10: Open to Interpretation

Dueish: Tue. Dec 11
 Notes:
 The originally planned Solo Problem 5 has been cancelled.
 This is the last required pset, which covers material through the lecture on Fri. Dec. 07. It will be followed by a PS11 that contains only completely optional extra credit problems.
 Although formally “due” on Tue. Dec. 11, this (and all your other asyetincomplete CS251 work) can be submitted through the end of finals period (i.e., the end of Tue. Dec. 20). If you need to go beyond this date, please consult with Lyn.
 This pset has 105 points total: 33 for one solo problems and 72 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 Fall 2018 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 fixedwidth 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 yourcsenv
/wx
Virtual Machine: Problem 1:
yourAccountNameMiniFP.sml
,yourAccountNameMiniFPInterp.sml
,yourAccountNameMiniFPTest.sml
 Problem 2:
yourAccountNameBindexToPostFix.sml
 Problem 3:
yourAccountNameSimprex.sml
andyourAccountNameSimprexEnvInterp.sml
 Problem 4:
yourAccountNameValexPS10.sml
andyourAccountNameValexEnvInterpPS10.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
andF_sx
from Problem 1a.  The result of hand translating the Bindex program in Problem 2a into PostFix (use sexpression syntax).
 The results of evaluating the sample Simprex programs in Problem 3a.
 The definitions of

Drop a copy of your entire
ps10
directory into your~/cs251/drop/ps10
drop folder oncs.wellesley.edu
by executing the following (replacing both occurrences ofgdome
by your cs server username):scp r ~/cs251/sml/ps10 gdome@cs.wellesley.edu:/students/gdome/cs251/drop/ps10
 Problem 1:
Starting this Problem Set
Problems 1–4 all 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 sexpression notation. In the table, \(i\) denotes an integer and \(x\) denotes an object.
FP Notation  SML obj Notation  Sexpression 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 sexpression 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, sexpressions, 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 sexpression notation. In the table, \(i\) denotes an integer, \(x\) denotes an object, and \(f\) denotes a functional form.
FP Notation  SML funForm Notation  Sexpression 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, sexpressions, 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 yourAccountNameMiniFP.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 yourAccountNameMiniFP.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
yourAccountNameMiniFP.sml
buffer into the*sml*
interpreter buffer:../utils/Utils.sml:35.48 Warning: calling polyEqual

After you sened your
yourAccountNameMiniFP.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 yourAccountNameMiniFPInterp.sml
and yourAccountNameMiniFPTest.sml
. Additionally:

In the file
yourAccountNameMiniFPInterp.sml
, change the first line of the file fromuse "../ps10/MiniFP.sml";
to
use "../ps10/yourAccountNameMiniFP.sml";

In the file
yourAccountNameMiniFPTest.sml
, change the first line of the file fromuse "../ps10/MiniFPInterp.sml";
to
use "../ps10/yourAccountNameMiniFPInterp.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 yourAccountNameMiniFPInterp.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:

You can test your interpreter by sending your
yourAccountNameMiniFPInterp.sml
to the*sml*
buffer. After youopen MiniFPInterp;
, you can interactively test yourapply
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
yourAccountNameMiniFPInterp.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.

Below are numerous examples of the correct behavior of MiniFP’s
apply
function. Yourapply
function should behave the same way. 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/emacsregion1678BTc:17.1021.15
The issue here is an indexoutofbounds 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
yourAccountNameMiniFPTest.sml
buffer to your*sml*
interpreter buffer. This will load theMiniFPTest
structure defined in this file and invokeMiniFPTest.test()
, which will test your interpreter on about 100 test cases.The test cases are defined in a variable
testSuite
, each of whose entries has the form:((
functionformstring, objectstring)
, resultstring)
The tester first parses functionformstring and objectstring 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 resultstring, 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
yourAccountNameMiniFPTest.sml
. In order to do this, you will have to make the error messages in anyEvalError
exceptions you raise match the ones in the testing suite.You are encouraged to add additional test cases to
yourAccountNameminiFPTest.sml
2. Bindex To PostFix (20 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 sexpression 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 adepth
argument toexpToCommands
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 (6 points) To get a better sense for the issues involved, give the PostFix program (in sexpression 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)))
As in the the IntextoPostFix translator studied in class, your translation should have the following properties:

When the commands translated from an expression are executed on a stack of values, they should have the effect of pushing the value of that expression onto the stack.

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.
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 return16
. 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 command42
:fun makeArgEnv args = Env.make args (Utils.range 1 ((length args) + 1)) (* returned env associates each arg name with its 1based 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 beyourAccountNameBindexToPostFix.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 ofexpToCmds
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 theEnv
structure inutils/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 functionsmakeArgEnv
,envPushAll
, andenvPush
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 valuev
from aSOME(v)
value. 
The
BindexToPostFix
structure contains atestTranslator
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 sexpression string, (2) displays the PostFix program resulting from the translation as an sexpression 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) 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 (36 points)
Background
Rae Q. Cerf of ToyLanguagesя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(n1)), if n > 0
Here, z
is an integer that defines the value of f
for any nonpositive 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(n1, 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^{n}, 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 righttoleft vs. lefttoright evaluation, A simple example of that is
z_sub = 0
c_sub(i, a) = ia
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 righttoleft vs. lefttoright evaluation is using Horner’s method to calculate the value of the polynomial x^(n1) + 2*(x^(n2)) + 3*(x^(n3)) + ... + (n1)*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 twoargument 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
.
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:
;; Program that calculuates the factorial of n
(simprex (n) (simprec 1 (i a (* i a)) n))
;; Exponentiation program raising base b to power p
(simprex (b p) (simprec 1 (i ans (* b ans)) p))
;; Program summing the squares of the numbers from 1 to hi
(simprex (hi) (simprec 0 (i sumSoFar (+ (* i i) sumSoFar)) hi))
;; Program distingishing righttoleft and lefttoright evaluation via subtraction
(simprex (n) (simprec 0 (i ans ( i ans)) n))
;; Calculating x^(n1) + 2*(x^(n2)) + 3*(x^(n3)) + ... + (n1)*x + n via Horner's method
(simprex (n x) (simprec 0 (i a (+ i (* x a)) n)))
Your Tasks
After completing her design, Rae is called away to work on another language design problem. ToyLanguagesя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 thesimprec
construct. Her modified files, which are namedSimprex.sml
andSimprexEnvInterp.sml
, can be found in theps10
folder.Finish Rae’s implementation of the Simprex language by completing the following four tasks, which Rae has listed in her memo:

(2 points) Extend the definition of
sexpToExp
inSimprex.sml
to correctly parsesimprec
expressions. 
(2 points) Extend the definition of
expToSexp
inSimprex.sml
to correctly unparsesimprec
expressions. 
(3 points) Extend the definition of
freeVarsExp
inSimprex.sml
to correctly determine the free variables of asimprec
expression. 
(12 points) Extend the definition of
eval
inSimprexEnvInterp.sml
to correctly evaluatesimprec
expressions using the environment model.
Notes:
Begin this part by renaming the files
Simprex.sml
andSimprexEnvInterp.sml
to beyourAccountNameSimprex.sml
andyourAccountNameSimprexEnvInterp.sml
. In the fileyourAccountNameSimprexEnvInterp.sml
, you also need to change the first line of the file fromuse "../ps10solns/Simprex.sml";
to
use "../ps10solns/yourAccountNameSimprex.sml";

This problem is similar the the Sigmex (= Bindex +
sigma
) language extension we implemented in lecture. You may wish to study the solution filesbindex/Sigmex.sml
andbindex/SigmexEnvInterp.sml
as part of doing this problem. 
In
Simprex.sml
, theexp
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 sexpression notation
(simprec E_zero (I_num I_ans E_combine) E_arg)
is represented in SML asSimprec (<exp for Ezero>, <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 asSimprec(Int 1, "x", "a", BinApp(Mul, Var "x", Var "a"), Var "n")

You can test your modifications of
sexpToExp
,expToSexp
, andfreeVarsExp
by loadingyourAccountNameSimprex.sml
into the*sml*
buffer, and evaluating the expressionSimprex.testSyntax();
. This will display the results of various test cases forfreeVarsExp
, and indirectly will also testsexpToExp
andexpToSexp
. UntilsexpToExp
is correctly defined, evaluatingSimprex.testSyntax();
will raiseuncaught exception SyntaxError
. 
A common error in this problem is to neglect the nested parens in
(Id_num Id_ans E_combine)
when definingsexpToExp
andexpToSexp
. 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. 
You can test your modifications of
eval
by loadingyourAccounNameSimprexEnvInterp.sml
into the*sml*
buffer and evaluating the expressionSimprexEnvInterp.testEval();
. This will display the results of various test cases foreval
.

4. Extending Valex with New Primitive Operators (15 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
:

(2 points)
(abs n)
: Returns the absolute value of the integer n. E.g.valex> (abs 17) 17 valex> (abs 42) 42

(3 points)
(sqrt n)
: If n is a nonnegative integer, returns the integer square root n. The integer square root of a nonnegative integer is the largest integer i such that i^{2} ≤ n. Signals an error if n is negative. E.g.valex> (sqrt 25) 5 valex> (sqrt 35) 5 valex> (sqrt 36) 6 valex> (sqrt 37) 6
Hint: The
Real
andMath
structures contain helpful functions for this problem. 
(4 points)
(range lo hi)
: Assumelo
andhi
are integers. Iflo
<hi
, returns a list of integers fromlo
(inclusive) tohi
(exclusive). Otherwise, returns the empty list. For example: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:* The
Utils.range` function is helpful here. 
(6 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: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
andValexEnvInterpPS10.sml
to beyourAccountNameValexPS10.sml
andyourAccountNameValexEnvInterpPS10.sml
. In the fileyourAccountNameValexEnvInterpPS10.sml
, you also need to change the first line of the file fromuse "../ps10/ValexPS10.sml";
to
use "../ps10/yourAccountNameValexPS10.sml";

All four primitives above can be added to Valex by adding new
Primop
entries to theprimops
list inps10/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 thevalex
directory. 
You should only change
ValexPS10.sml
and notValexEnvInterpPS10.sml

To test your implementation after editing
yourAccountNameValexPS10.sml
, first loadyourAccountNameValexEnvInterpPS10.sml
(notyourAccountNameValexPS10.sml
) into a*sml*
buffer, and then test your new primitives interactively in a Valex readevalprint loop (REPL) launched by invokingValexEnvInterp.repl()
.
5. Compex (35 points)
This problem description is still being edited. Lyn will email the class when it has been posted.
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 secondsperminute 60
(bind minutesperhour 60
(bind hoursperday 24
(bind daysperyear 365 ; ignore leap years
(bind secondsperyear (* secondsperminute
(* minutesperhour
(* hoursperday daysperyear)))
(* secondsperyear 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^{7}. So a century is approximately π × 10^{9} seconds, which means that π seconds is approximately one nanocentury!)
The second program shows how this constant is calculated from simpler constants. By showing the process by which secondsperyear is calculated, the second program is a more robust and welldocumented 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 socalled “constants” built into a program that change over its lifetime. For instance, the size of word of computer memory, the price of a firstclass stamp, and the rate for a certain tax bracket are all numbers that could be hardwired 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 runtime 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 secondsperminute 60
(bind minutesperhour 60
(bind hoursperday 24
(bind daysperyear 365 ; ignore leap years
(bind secondsperyear (* 60 (* 60 (* 24 365)))
(* secondsperyear years)))))))
Next, we eliminate the nowunnecessary first four bindings via a step known as dead code removal:
(bindex (years)
(bind secondsperyear (* 60 (* 60 (* 24 365)))
(* secondsperyear years)))
We can now perform the three multiplications involving manifest integers in a step known as constant folding:
(bindex (years)
(bind secondsperyear 31536000
(* secondsperyear 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 yourAccountNameBindexPartialEval.sml
and yourAccountNameBindexPartialEvalTest.sml
. In the file yourAccountNameBindexPartialEvalTest.sml
, you also need to change the first line of the file from
use "../ps10/BindexPartialEval.sml";
to
use "../ps10/yourAccountNameBindexPartialEval.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 deadcode 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 environmentenv
, 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 dividebyzero 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 to0
, because it does not preserve the meaning of the program in the case whereb
is 0 (in which case evaluating the expression should give an error). 
In order to test your partial evaluator, load
yourAccountNameBindexPartialEvalTest.sml
into an*sml*
buffer, and evaluateBindexPartialEvalTest.testAll()
. This applies your partial evaluator to all the test entries in the listtestEntries
in the fileyourAccountNameBindexPartialEvalTest.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(); Add23  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.