PS8: A Hofl Lot
- Due: Wednesday, May 4
-
Notes:
- Although the official deadline is Wed. May 4, I will accept this (and all other remaining CS251 work) until the end of finals period = 5pm Mon. May 16.
- This problem set is now complete. It has four problems worth 100 points.
- It has been designed in such a way that you can expect 10 points to require approximately 1 hour. Please let me know if this expectation is wrong on particular problems!
- Please keep track of the time estimates for each problem/subproblem.
- Submission:
- In the yourFullName CS251 Spring 2016 Folder, create a Google Doc named yourFullName CS251 PS8.
- 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 need to draw many environment diagrams in this pset. You can use Google Doc’s Insert Drawing feature to create an environment diagram to insert into your doc.
- 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.
1. 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.
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
,V-defn
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 values V_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 higher-order functions, which supports modularity better: lexical scope or dynamic scope? Explain your answer.
Note: You can use the Hofl interpreters to check your results to parts b and d by following these steps:
-
Copy the entire contents of the
cs251-download
directory oncs.wellesleley.edu
to your localcs251-download
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/cs251-download
-
If you don’t already have one, create a
*sml*
SML interpreter buffer within Emacs. All of the subsequent steps involve evaluating SML expressions in this buffer. -
Execute the following SML command to change the default directory:
- Posix.FileSys.chdir "/home/wx/cs251-download/hofl";
-
Load both the static and dynamic Holf interpreters as follows:
- use "load-hofl-interps.sml";
-
You can launch a REPL for the statically scoped Hofl interpreter and evaluate expressions and run programs as shown below:
- HoflEnvInterp.repl(); hofl> (bind a 5 (bind add-a (fun (x) (+ x a)) (bind a 100 (add-a 12)))) 17 hofl> (#run (hofl (a b c) (bind add-a (fun (x) (+ x a)) (bind a b (add-a c)))) 5 100 12) 17 hofl> (#quit) Moriturus te saluto! val it = () : unit -
Note that it is not possible to use Hofl’s
load
to evaluate an expression or run a program. -
Launching and using the dynamically scoped Hofl interpreter is similar:
- HoflEnvInterpDynamicScope.repl(); hofl-dynamic-scope> (bind a 5 (bind add-a (fun (x) (+ x a)) (bind a 100 (add-a 12)))) 112 hofl-dynamic-scope> (#run (hofl (a b c) (bind add-a (fun (x) (+ x a)) (bind a b (add-a c)))) 5 100 12) 112 hofl-dynamic-scope> (#quit) Moriturus te saluto! val it = () : unit -
2. 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 1.
3. 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:
-
Copy the entire contents of the
cs251-download
directory oncs.wellesleley.edu
to your localcs251-download
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/cs251-download
-
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-download/ps8";
Your Task
Create a file /home/wx/cs251-download/ps8/exp3.hfl containing a simple Hofl expression that evaluates to (sym static)
in a statically-scoped Hofl interpreter but evaluates to (sym dynamic)
in dynamically-scoped interpreter. The only types of values that your expression should should manipulate are symbols and functions; it should not use integers, booleans, characters, strings, or lists. You can test your expression in SML as follows:
- use "Problem3Tester.sml"; (* this only need be executed once *)
... lots of output omitted ...
- testProblem3(); (* 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:
- testProblem3();
/home/wx/cs251-download/ps8/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 exp3.hfl
to your PS8 doc. You needn’t submit anything to the drop folder.
4. Counters (40 points)
Recall that in Racket (1) every variable name is bound to an implicit cell; (2) references to a variable implicitly dereference (return the contents of) the cell; and (3) a variable Id can be assigned a new value via the assignment construct (set! Id E)
, which changes the contents of the implicit cell associated with Id to the value of E.
This problem involves the following Racket functions for implementing and testing various counter objects (which can be found in the file ps8/counters.rkt
):
(define make-counter1
(let ((count 0))
(λ ()
(λ ()
(begin (set! count (+ count 1))
count)))))
(define make-counter2
(λ ()
(let ((count 0))
(λ ()
(begin (set! count (+ count 1))
count)))))
(define make-counter3
(λ ()
(λ ()
(let ((count 0))
(begin (set! count (+ count 1))
count)))))
(define test-counter
(λ (make-counter)
(let ((a (make-counter))
(b (make-counter)))
(begin (println (a))
(println (b))
(println (a))))))
-
(30 points) For each of the following expressions, (1) show the values displayed when the expression is evaluated and (2) draw an environment diagram for the evaluation of the expression. In your diagram, be sure to show empty environment frames from invoking nullary functions.
(test-counter make-counter1)
(test-counter make-counter2)
(test-counter make-counter3)
For conventions on drawing environment diagrams with implicit cells, including empty environments, study this example of environment diagrams from Racket.
-
(10 points) Let i range over the numbers {1,2,3}. Then each of the Racket functions
make-counter
i can be modeled in Java by an instance of classCounter
i that implements theCounter
interface in the following code:interface Counter { public int invoke(); } class Counter1 implements Counter { // Flesh out this skeleton } class Counter2 implements Counter { // Flesh out this skeleton } class Counter3 implements Counter { // Flesh out this skeleton } public class Counters { public static void testCounters(Counter a, Counter b) { System.out.println(a.invoke()); System.out.println(b.invoke()); System.out.println(a.invoke()); } public static void main (String [] args) { System.out.println("testCounters(new Counter1(), new Counter1()):"); testCounters(new Counter1(), new Counter1()); System.out.println("testCounters(new Counter2(), new Counter2()):"); testCounters(new Counter2(), new Counter2()); System.out.println("testCounters(new Counter3(), new Counter3()):"); testCounters(new Counter3(), new Counter3()); } }
In this subproblem your task is to flesh out the definitions of the three
Counter
i classes in the above code so that they correctly model the behavior of the Racket functionmake-counter
i.The above code can be found in the file
ps8/CountersSkeleton.java
. Begin this problem by making a copy ofps8/CountersSkeleton.java
namedps8/Counters.java
, and flesh out the missing class definitions inps8/Counters.java
.Notes:
-
In addition to its single nullary instance method
invoke
, each classCounter
i should have a single class, instance, or local variable namedcount
. -
The
testCounters
method of theCounters
class takes two objects from classes satisfying theCounter
interface and tests them in a way similar to Racket’stest-counter
. The test expression(test-counter make-counter
i)
in Racket can be modeled by the Java statementtestCounters(new Counter
i, new Counter
i);
-
To compile and run the
Counters
program in the wx virtual machine, execute the following Linux shell commands:cd "~/cs251-download/ps8" javac Counters.java java Counters
This will display the result of testing the three
Counter
i classes. These results should be similar to calling Racket’stest-counter
function on the threemake-counter
i functions.
-