PS10: Extra Credit Problems

Due: I will accept all work through the end of finals period = 5pm Thu. Dec. 21. If you need to go beyond that, there is some flexibility; please contact me to discuss options.
 Notes:
 This problem set contains some completely optional extra credit problems related to the last week of material in the course. You may do any subset of these problems (including the empty subset!)
 There are 110 total points in the five problems here.
 In addition to doing any of these problems, you can also submit extra credit problems from previous assignments.
 Any points from extra credit problems will simply be added to the point total of your regular problem component of your course grade. So you could use some of these problems to replace other regular problems during the semester.
 Of course, partial credit will be awarded where appropriate for incomplete problems.
 Recall that there is a limit of 100 extra credit points that can be earned.
 Submission:
 In the yourFullName CS251 Fall 2017 Folder, create a Google Doc named yourFullName CS251 PS10.
 For each problem and subproblem, please indicate at the beginning of each writeup approximately how long that problem took you to solve and write up.
 You will flesh out the following code file in this pset:
 Problem 4:
Counters.java
 Problem 4:
 Include all answers, including copies of relevant code from your
.hfl
and.java
files in your PS8 Google Doc.  Drop a copy of your
Counters.java
file in your~/cs251/drop/ps08
drop folder oncs.wellesley.edu
. (You need not drop a copy ofexp3.hfl
in your drop folder.
Starting this Problem Set
Problems 1 and 2 involve starter files in the ~wx/cs251/sml/ps10
directory in your wx Virtual Machine.
To create this directory, execute the following two commands in a wx VM shell:
cd ~/cs251/sml
git add A
git commit m "my local changes"
git pull origin master rebase
Several students have encountered problems when executing this steps. If you have problems, please contact lyn.
1. Partial Evaluation (20 points)
Avoiding Magic Constants
It is good programming style to avoid “magic constants” in code by explicitly calculating certain constants from others. For instance, consider the following two Bindex programs for converting years to seconds:
; Program 1
(bindex (years)
(* 31536000 years))
; Program 2
(bindex (years)
(bind 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
Begin this problem by making a copy of the file ps10/BindexPartialEvalSkeleton.sml
named ps10/BindexPartialEval.sml
, and use this latter file for all of your work in this problem.
[wx@wx ~]$ cd /home/wx/cs251/sml/ps10
[wx@wx ps10]$ cp BindexPartialEvalSkeleton.sml BindexPartialEval.sml
Your Task
In this problem, your task is to flesh out the definition of a function partialEval
that performs partial evaluation on a Bindex program. Given a Bindex program, partialEval
should return another Bindex program that has the same meaning as the original program, but which also satisfies the following properties:

The program should not contain any
bind
expressions in which a variable is bound to an integer literal. 
The program should not contain any binary applications in which an arithmetic operator is applied to two integer literals. There are two exceptions to this property: the program may contain binary applications of the form
(/ n 0)
or(% n 0)
, since performing these applications would cause an error in the partial evaluation process.
It is possible to write separate functions that perform the constant propagation, constant folding, and 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:

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

Use
BindexEnvInterp.binopToFun
as part of applying an operator to two integers. 
Divisions and remainders whose second operands are zero must be left in the program. Such programs will encounter 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 also test your partial evaluator by evaluating
testAll()
. 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. If all tests succeed, you will see this: 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
testPartialEval
function, which takes a string representation of a Bindex program. For example: testPartialEval "(bindex () (+ 1 2))"; (bindex () 3) val it = () : unit  testPartialEval "(bindex (a)\ = \ (bind b (* 3 4)\ = \ (bind c (/ b ( 12 b)) (* c b))))"; (bindex (a) (bind c (/ 12 0) (* c 12))) val it = () : unit  testPartialEval "(bindex (a)\ = \ (+ (* (+ 1 2) a)\ = \ (+ (* 3 4)\ = \ (+ (* 0 a)\ = \ (+ (* 1 a)\ = \ (+ 0 a))))))"; (bindex (a) (+ (* 3 a) (+ 12 (+ (* 0 a) (+ (* 1 a) (+ 0 a)))))) val it = () : unit
The last two examples show the SML conventions for entering multiline strings. Each nonterminal line must end with a backslash character, and the next line must begin with a backslash character.
2. Compex (30 points)
Background
In this problem, you will flesh out details of a new language Compex that extends Bindex with a comp
construct:
(comp E_num E_pos E_zero E_neg)
This comp
expression evaluates E_num
to the integer value n_num
and then compares this with zero:
 if
n_num
is greater than zero, the value of the 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:
; ps10/pgm1.cpx
;
; An absolute value program
(compex (n) (comp n n 0 ( 0 n)))
; ps10/pgm2.cpx
;
; Given program arguments a and b:
; * return the square of their difference if a > b
; * return twice a if a = b
; * return the product of a and the difference if a < b
(compex (a b)
(bind diff ( a b)
(comp diff (* diff diff) (* 2 a) (* a diff))))
; ps10/pgm3.cpx
;
; Return the max of a, b, and c
(compex (a b c)
(comp ( a b)
(comp ( a c) a a c)
(comp ( a c) a a c)
(comp ( b c) b b c)))
; ps10/pgm4.cpx
;
; Test the interaction of comp with bind and itself
(compex (p q r)
(+ (bind s ( p q)
(bind t ( q r)
(* (comp s (+ p q) (+ p r) (+ q r))
(comp t ( p q) ( p r) ( q r)))))
(comp ( r q)
(bind u (+ p q) (comp u u (* 2 u) (* 3 u)))
(bind v (+ p r) (comp v (* 4 v) (* 5 v) (* 6 v)))
(bind w (+ q r) (comp w (* 7 w) (* 8 w) (* 9 w))))))
; ps10/pgm5.cpx
;
; If x > y > z, returns the sum of x, y, and z.
; If x = y = z, returns x
; If x < y < z, returns the product of x, y, and z.
; Otherwise gives a 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 making copies of files in the ps10
directory:
[wx@wx ~]$ cd /home/wx/cs251/sml/ps10
[wx@wx ps10]$ cp CompexSkeleton.sml Compex.sml
[wx@wx ps10]$ cp CompexEnvInterp.sml CompexEnvInterp.sml
[wx@wx ps10]$ cp CompexToPostFixSkeleton.sml CompexToPostFix.sml
Note that CompexSkeleton.sml
and CompexEnvInterpSkeleton.sml
are just copies of Bindex.sml
and BindexEnvInterp.sml
from the Bindex language. You will need to modify them as described below to extend Bindex to Compex.
Your Tasks

(2 points) Change
Compex.sml
andCompexEnvInterp.sml
so that all occurrences ofBindex
andbindex
are changed, respectively, toCompex
andcompex
in in structure definitions, datatype declarations, patterns, strings, etc. (Hint: use Mx replacestring in Emacs.) 
(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.You can test that the above parts work by loading
Compex.sml
into an*sml*
buffer and trying the following tests in this buffer: Control.Print.printDepth := 100; (* ... lots of output omitted ... *) val it = () : unit  val exp1 = Compex.stringToExp("(comp ( a b) (+ a c) (/ b d) (% d e))"); val exp1 = Comp (BinApp (Sub,Var "a",Var "b"),BinApp (Add,Var "a",Var "c"), BinApp (Div,Var "b",Var "d"),BinApp (Rem,Var "d",Var "e")) : Compex.exp  Compex.expToString(exp1); val it = "(comp ( a b) (+ a c) (/ b d) (% d e))" : string  val pgm5 = Compex.fileToPgm("pgm5.cpx"); val pgm5 = Compex (["x","y","z"], Comp (BinApp (Sub,Var "x",Var "y"), Comp (BinApp (Sub,Var "y",Var "z"), BinApp (Add,Var "x",BinApp (Add,Var "y",Var "z")), BinApp (Div,Var "y",Int 0),BinApp (Div,Var "z",Int 0)), Comp (BinApp (Sub,Var "y",Var "z"),BinApp (Div,Var "y",Int 0),Var "x", BinApp (Div,Var "z",Int 0)), Comp (BinApp (Sub,Var "y",Var "z"),BinApp (Div,Var "y",Int 0), BinApp (Div,Var "z",Int 0), BinApp (Mul,Var "x",BinApp (Mul,Var "y",Var "z"))))) : Compex.pgm  print(Compex.pgmToString(pgm5)); (compex (x y z) (comp ( x y) (comp ( y z) (+ x (+ y z)) (/ y 0) (/ z 0)) (comp ( y z) (/ y 0) x (/ z 0)) (comp ( y z) (/ y 0) (/ z 0) (* x (* y z))) ) )val it = () : unit

(2 points) Extend the definition of
freeVarsExp
inCompex.sml
to correctly determine the free variables of acomp
expression.You can test that
freeVarsExp
works by loadingCompex.sml
into an*sml*
buffer and trying the following tests in this buffer: StringSetList.toList(Compex.freeVarsExp(Compex.stringToExp("(comp ( a b) (+ a c) (/ b d) (% d e))"))); val it = ["a","b","c","d","e"] : string list  Compex.varCheck(Compex.fileToPgm("pgm5.cpx")); val it = true : bool

(5 points) Extend the definition of
eval
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: CompexEnvInterp.repl() compex> (#run pgm1.cpx 42) 42 compex> (#run pgm1.cpx 17) 17 compex> (#run pgm1.cpx 0) 0 compex> (#run pgm2.cpx 6 2) 16 compex> (#run pgm2.cpx 3 3) 6 compex> (#run pgm2.cpx 2 6) ~8 compex> (#run pgm3.cpx 1 2 3) 3 compex> (#run pgm3.cpx 1 3 2) 3 compex> (#run pgm3.cpx 3 1 2) 3 compex> (#run pgm4.cpx 7 3 1) 68 compex> (#run pgm4.cpx 7 1 3) ~8 compex> (#run pgm4.cpx 3 7 1) 24 compex> (#run pgm4.cpx 3 1 7) ~20 compex> (#run pgm4.cpx 1 3 7) ~36 compex> (#run pgm4.cpx 1 7 3) 10 compex> (#run pgm5.cpx 4 3 2) 9 compex> (#run pgm5.cpx 3 3 3) 3 compex> (#run pgm5.cpx 2 3 4) 24 compex> (#run pgm5.cpx 4 2 3) Error: Division by 0: 3 compex> (#quit) Moriturus te saluto! val it = () : unit

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

Think carefully about this translation in the context of some concrete examples.

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

3. Static and Dynamic Scope in Hofl (30 points)
Before starting this problem, study Sections 8 (Static Scoping) and 9 (Dynamic Scoping) in the Hofl notes.

(12 points) Suppose that the following program is run on the input argument list
[5]
.(hofl (a) (bind linear (fun (a b) (fun (x) (+ (* a x) b))) (bind line1 (linear 1 2) (bind line2 (linear 3 4) (bind try (fun (b) (list (line1 b) (line2 (+ b 1)) (line2 (+ b 2)))) (try (+ a a)))))))
Draw an environment diagram that shows all of the environments and closures that are created during the evaluation of this program in statically scoped Hofl. You can use Google Doc’s Insert Drawing feature to create a drawing to insert into your doc. Alternatively, you can draw diagrams on paper and scan the paper or take photos of them.
In order to simplify this diagram:

You should treat
bind
as if it were a kernel construct and ignore the fact that it desugars into an application of anabs
. That is, you should treat the evaluation of(bind I_defn E_defn E_body)
in environmentF
as the result of evaluatingEbody
in the environment frameF'
, whereF'
bindsI_defn
toV_defn
,Vdefn
is the result of evaluatingE_defn
inF
, and the parent frame ofF'
isF
. 
You should treat
fun
as if it were a kernel construct and ignore the fact that it desugars into nested abstractions. In particular, (1) the evaluation of(fun (I_1 ... I_n) E_body)
should be a closure consisting of (a) thefun
expression and (b) the environment of its creation and (2) the application of the closure< (fun (I_1 ... I_n ) E_body ), F_creation >
to argument valuesV_1
…V_n
should create a new environment frameF
whose parent frame isF_creation
and which binds the variablesI_1
…I_n
to the valuesV_1
…V_n
.


(2 points) What is the final value of the program from part (a) in statically scoped Hofl? You should figure out the answer on your own, but may wish to check it using the statically scoped Hofl interpreter.

(10 points) Draw an environment diagram that shows all of the environments created in dynamically scoped HOFL when running the above program on the input argument list
[5]
. 
(2 points) What is the final value of the program from part (c) in dynamically scoped Hofl?

(4 points) In a programming language with higherorder functions, which supports modularity better: lexical scope or dynamic scope? Explain your answer.
Note: You can use the Hofl interpreters to check your results to parts b and d by following these steps:

If you don’t already have one, create a
*sml*
SML interpreter buffer within Emacs. 
In a
*sml*
buffer, load both the static and dynamic Holf interpreters as follows:Posix.FileSys.chdir("/home/wx/cs251/sml/hofl"); use "loadhoflinterps.sml";

You can launch a REPL for the statically scoped Hofl interpreter and evaluate expressions and run programs as shown below:
 HoflEnvInterp.repl(); hofl> (bind a 5 (bind adda (fun (x) (+ x a)) (bind a 100 (adda 12)))) 17 hofl> (#run (hofl (a b c) (bind adda (fun (x) (+ x a)) (bind a b (adda c)))) 5 100 12) 17 hofl> (#quit) Moriturus te saluto! val it = () : unit 
Note that it is not possible to use Hofl’s
load
to evaluate an expression or run a program. 
Launching and using the dynamically scoped Hofl interpreter is similar:
 HoflEnvInterpDynamicScope.repl(); hofldynamicscope> (bind a 5 (bind adda (fun (x) (+ x a)) (bind a 100 (adda 12)))) 112 hofldynamicscope> (#run (hofl (a b c) (bind adda (fun (x) (+ x a)) (bind a b (adda c)))) 5 100 12) 112 hofldynamicscope> (#quit) Moriturus te saluto! val it = () : unit 
4. Recursive Bindings (20 points)
Before starting this problem, study Sections 8 (Static Scoping), 9 (Dynamic Scoping), and 10 (Recursive Bindings) in the Hofl notes.
Consider the following Hofl expression E
:
(bind f (abs x (+ x 1))
(bindrec ((f (abs n
(if (= n 0)
1
(* n (f ( n 1)))))))
(f 3)))

(6 points) Draw an environment diagram showing the environments created when
E
is evaluated in statically scoped Hofl, and show the final value of evaluatingE
. 
(6 points) Consider the expression
E'
that is obtained fromE
by replacingbindrec
bybindseq
. Draw an environment diagram showing the environments created whenE'
is evaluated in statically scoped Hofl, and show the final value of evaluatingE'
. 
(6 points) Draw an environment diagram showing the environments created when
E'
is evaluated in dynamically scoped Hofl, and show the final value of evaluatingE'
. 
(2 points) Does a dynamically scoped language need a recursive binding construct like
bindrec
in order to support the creation of local recursive procedures? Briefly explain your answer.
Note: You can use the Hofl interpreters to check your results to parts a, b, and c by following the testing steps from Problem 3.
5. Distinguishing Scopes (10 points)
In this problem, you will write a single expression that distinguishes static and dynamic scope in Hofl.
Setup
Begin this problem by performing the following steps:

If you don’t already have one, create a
*sml*
SML interpreter buffer within Emacs. 
In the
*sml*
buffer, execute the following SML command to change the default directory: Posix.FileSys.chdir "/home/wx/cs251/sml/ps10";
Your Task
Create a file /home/wx/cs251/ps10/exp5.hfl
containing a simple Hofl expression that evaluates to (sym static)
in a staticallyscoped Hofl interpreter but evaluates to (sym dynamic)
in dynamicallyscoped interpreter. The only types of values that your expression should should manipulate are symbols and functions; it should not use integers, booleans, characters, strings, or lists. You can test your expression in SML as follows:
 use "Problem5Tester.sml"; (* this only need be executed once *)
... lots of output omitted ...
 testProblem5(); (* you can execute this multiple times *)
This evaluates the expression in the exp3.hfl
file in both scoping mechanisms and displays the results. A correct solution should have the following output:
 testProblem5();
/home/wx/cs251/ps10/exp3.hfl contains the expression:
... details omitted ...
Value of expression in static scope: (sym static)
Value of expression in static scope: (sym dynamic)
val it = () : unit
To submit the solution to this problem, just copy the expression in exp5.hfl
to your PS10 doc. You needn’t submit anything to the drop folder.