PS9: Extra Credit Problems
 Due: Monday, May 16
 Notes:
 This problem set contains some completely optional extra credit problems. You may do any subset of these problems (including the empty subset!)
 More problems are under development and will be added when finished.
 In addition to doing any of these problems, you can also submit extra credit problems from previous assignments.
 Any points from extra credit problems will simply be added to the point total of your problem set component of your course grade.
 Of course, partial credit will be awarded where appropriate for incomplete problems.
 Instructions for many of these problems are less explicit than previous problem set problems. Please email questions if there are apects that are unclear.
 Submission:
 In the yourFullName CS251 Spring 2016 Folder, create a Google Doc named yourFullName CS251 PS9.
 For each problem and subproblem, please indicate at the beginning of each writeup approximately how long that problem took you to solve and write up.
1. Safe Transformations (16 points)
A transformation that rewrites one expression to another is said to be safe if performing the transformation anywhere in a program will not change the behavior of the program . For each of the following transformations, indicate whether it is safe in (i) Hofl and (ii) Hoilec (a version of Hofl with explicit cells). Assume both languages are statically scoped and callbyvalue. For each transformation you specify as unsafe, give an example whose behavior is changed by the transformation. Changes in behavior include:
 the program returns different values before and after the transformation;
 the program loops infinitely or signals an error before the transformation, but returns a value after the transformation;
 the program returns a value before the transformation, but loops infinitely or signals an error after the transformation.
For the purposes of this problem, all errors are considered equivalent and programs that loop infinitely are considered equivalent to those that signal an error. In particular, the behavior of an expression should not be considered different if it signals an error both before and after the transformation, but the error messages are different.
In each expression, Id
stands for a variable reference and E
stands for an expression. You may assume that all subexpressions of an application are evaluated in lefttoright order.

(+ Id Id)
⇒(* 2 Id)

(+ E E)
⇒(* 2 E)

(+ E1 E2)
⇒(+ E2 E1)

(+ E1 E2)
⇒(bind x E1 (+ x E2))

(+ E1 E2)
⇒(bindpar ((x (fun () E1)) (y (fun () E2 ))) (+ (x) (y)))

(if #t E1 E2)
⇒E1

(if E1 E2 E2)
⇒E2

(if (if E1 E2 E3) E4 E5)
⇒(if E1 (if E2 E4 E5) (if E3 E4 E5))
2 Partial Evaluation (30 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 pro gram 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
Begin this problem by performing the following steps:

Copy the entire contents of the
cs251download
directory oncs.wellesleley.edu
to your localcs251download
directory using the following command. This may overwrite some of your existing files in this directory, but that’s OK. (If you think it’s not OK, then save versions of files you care about elsewhere first!) Of course, as usual, here and elsewhere you should replace usernamegdome
by your own account name:scp r gdome@cs.wellesley.edu:/home/cs251/download/* /home/wx/cs251download

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

Make a copy of the file
ps9/BindexPartialEvalSkeleton.sml
namedps9/BindexPartialEval.sml
.
Your Task
In this problem, your task is to write 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.run
and BindexEnvInterp.eval
, partial evaluation can be peformed by a pair of functions:

val partialEval: Bindex.pgm > Bindex.pgm
Returns a partially evaluated version of the given Bindex program.

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.
Your goal is to implement simplification by fleshing out the above two function definitions 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:

Perform
use "loadpeval.ml"
to load the partial evaluator. 
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). 
You can use the
testPartialEval
function (which takes a string representation of a Bindex program) to test your partial evaluator. For example: testPartialEval "(bindex () (+ 1 2))"; (bindex () 3) val it = () : unit  testPartialEval "(bindex (a)\ = \ (bind b (* 3 4)\ = \ (bind c (/ b ( 12 b)) (* c b))))"; (bindex (a) (bind c (/ 12 0) (* c 12))) val it = () : unit  testPartialEval "(bindex (a)\ = \ (+ (* (+ 1 2) a)\ = \ (+ (* 3 4)\ = \ (+ (* 0 a)\ = \ (+ (* 1 a)\ = \ (+ 0 a))))))"; (bindex (a) (+ (* 3 a) (+ 12 (+ (* 0 a) (+ (* 1 a) (+ 0 a)))))) val it = () : unit
The last two examples show the SML conventions for entering multiline strings. Each nonterminal line must end with a backslash character, and the next line must begin with a backslash character.

You can also test your partial evaluator by evaluating
test()
. This applies your partial evaluator to all the test entries in the listtestEntries
in the fileBindexPartialEvalTest.sml
. The entries in this list are by no means exhaustive. You are strongly encouraged to add more entries to this list. test(); Add23  OK! Simple1  OK! Years  OK! Residuals1  OK! Residuals2  OK! Residuals3  OK!
3. Compex (35 points)
Background
In this problem, you will define a new language Compex that extends Bindex with a comp
construct:
(comp E_num E_pos E_zero E_neg)
This comp
expression evaluates E_num
to the integer value n_num
and then compares this with zero:
 if
n_num
is greater than zero, the value of the expressionE_pos
is returned.  if
n_num
is equal to zero, the value of the expressionE_zero
is returned.  if
n_num
is less than zero, the value of the expressionE_neg
is returned.
At most one of E_pos
, E_zero
, or E_neg
will be evaluated.
Here are some examples of programs using the comp
construct:
; ps9/pgm1.cpx
;
; An absolute value program
(compex (n) (comp n n 0 ( 0 n)))
; ps9/pgm2.cpx
;
; Given program arguments a and b:
; * return the square of their differences if a > b
; * return twice a if a = b
; * return the product of a and the difference if a < b
; Store this in ps9/abs.cpx
(compex (a b)
(bind diff ( a b)
(comp diff (* diff diff) (* 2 a) (* a diff))))
; ps9/pgm3.cpx
;
; Return the max of a, b, and c
(compex (a b c)
(comp ( a b)
(comp ( a c) a a c)
(comp ( a c) a a c)
(comp ( b c) b b c)))
; ps9/pgm4.cpx
;
; Test the interaction of comp with bind and itself
(compex (p q r)
(+ (bind s ( p q)
(bind t ( q r)
(* (comp s (+ p q) (+ p r) (+ q r))
(comp t ( p q) ( p r) ( q r)))))
(comp ( r q)
(bind u (+ p q) (comp u u (* 2 u) (* 3 u)))
(bind v (+ p r) (comp v (* 4 v) (* 5 v) (* 6 v)))
(bind w (+ q r) (comp w (* 7 w) (* 8 w) (* 9 w))))))
; ps9/pgm5.cpx
;
; If x > y > z, returns the sum of x, y, and z.
; If x = y = z, returns x
; If x < y < z, returns the product of x, y, and z.
; Otherwise gives a dividebyzero error.
; (tests that only one branch is evaluated)
(compex (x y z)
(comp ( x y)
(comp ( y z) (+ x (+ y z)) (/ y 0) (/ z 0))
(comp ( y z) (/ y 0) x (/ z 0)
(comp ( y z) (/ y 0) (/ z 0) (* x (* y z))))))
Setup
Begin this problem by performing the following steps:

Copy the entire contents of the
cs251download
directory oncs.wellesleley.edu
to your localcs251download
directory using the following command. This may overwrite some of your existing files in this directory, but that’s OK. (If you think it’s not OK, then save versions of files you care about elsewhere first!) Of course, as usual, here and elsewhere you should replace usernamegdome
by your own account name:scp r gdome@cs.wellesley.edu:/home/cs251/download/* /home/wx/cs251download

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

Make copies of
cs251download/bindex/Bindex.sml
,cs251download/bindex/BindexEnvInterp.sml
, andcs251download/ps9/CompexToPostFixSkeleton.sml
named (respectively)cs251download/ps9/Compex.sml
,cs251download/ps9/CompexEnvInterp.sml
, andcs251download/ps9/CompexToPostFix.sml
.[wx@wx cs251download]$ cd /home/wx/cs251development/ps9 [wx@wx ps9]$ cp ../bindex/Bindex.sml Compex.sml [wx@wx ps9]$ cp ../bindex/BindexEnvInterp.sml CompexEnvInterp.sml [wx@wx ps9]$ cp CompexToPostFixSkeleton.sml CompexToPostFix.sml
Your Tasks

(2 points) Change
Compex.sml
andCompexEnvInterp.sml
to handle the fact that the language keyword iscompex
rather thanbindex
. (Hint: use Mx replacestring in Emacs, but you wantuse "../ps9/Compex.sml"
, notuse "../bindex/Compex.sml"
.) 
(2 points) In
Compex.sml
extend theexp
datatype to have aComp
constructor forcomp
expressions. 
(2 points) Extend the definition of
sexpToExp
inCompex.sml
to correctly parsecomp
expressions. 
(2 points) Extend the definition of
expToSexp
inCompex.sml
to correctly unparsecomp
expressions. 
(2 points) Extend the definition of
freeVarsExp
inCompex.sml
to correctly determine the free variables of acomp
expression. 
(5 points) Extend the definition of
eval
inCompexEnvInterp.sml
to correctly evaluatecomp
expressions using the environment model. You should evaluateE_num
exactly once. Use the#run
functionality of the Compex REPL to test that your eval function works as expected. For example: use "CompexEnInterp.sml" ... lots of output omitted ...  CompexEnvInterp.repl() compex> (#run pgm1.cpx 42) 42 compex> (#run pgm1.cpx 17) 17 compex> (#run pgm1.cpx 0) 0 compex> (#run pgm2.cpx 6 2) 16 compex> (#run pgm2.cpx 3 3) 6 compex> (#run pgm2.cpx 2 6) ~8 compex> (#run pgm3.cpx 1 2 3) 3 compex> (#run pgm3.cpx 1 3 2) 3 compex> (#run pgm3.cpx 3 1 2) 3 compex> (#run pgm4.cpx 7 3 1) 68 compex> (#run pgm4.cpx 7 1 3) ~8 compex> (#run pgm4.cpx 3 7 1) 24 compex> (#run pgm4.cpx 3 1 7) ~20 compex> (#run pgm4.cpx 1 3 7) ~36 compex> (#run pgm4.cpx 1 7 3) 10 compex> (#run pgm5.cpx 4 3 2) 9 compex> (#run pgm5.cpx 3 3 3) 3 compex> (#run pgm5.cpx 2 3 4) 24 compex> (#run pgm5.cpx 4 2 3) Error: Division by 0: 3 compex> (#quit) Moriturus te saluto! val it = () : unit

(20 points) In this part, you will extend the Compex to PostFix translator in
CompexToPostFix.sml
to correctly handle the translation of thecomp
construct from Compex to PostFix. Do this by adding a clause to theexpToCmds
function that correctly translates thecomp
construct.Notes:

This is a challenging translation. Think carefully about it in the context of some concrete examples.

The PostFix
sel
,exec
, and executable sequence commands are all helpful in this translation. 
Performing
use "CompexToPostFix.sml"
will not only load this file, but will test it on the Compex programspgm1.cpx
throughpgm5.cpx
.
