PS11: A Hofl Lot

• Notes:

  • This problem set contains only completely optional regular problems related to the last week of material in the course. These regular problems count as extra credit problems. You may do any subset of these problems (including the empty subset!)

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

  • Any of these problems (and all your other as-yet-incomplete CS251 work) can be submitted through the end of finals period (i.e., the end of Thu. Dec. 20). If you need to go beyond this date, please consult with Lyn.
• Submission:
  • In the yourFullName CS251 Fall 2018 Folder, create a Google Doc named yourFullName CS251 PS11.
  • 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.
  • Include all answers, including copies of relevant code from your .sml, .hfl and .java files in your PS11 Google Doc.
  • 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.
  • Seen individual problems for what you need to submit for that problem.

1. Desugaring classify (30 points)

The classify construct

You are a summer programming intern at Sweetshop Coding, Inc. Your supervisor, Dexter Rose, has been studying the syntactic sugar for Valex and is very impressed by the cond construct. He decides that it would be neat to extend Valex with a related classify construct that classifies an integer relative to a collection of ranges. For instance, using his construct, Dexter can write the following grade classification program:

; Classify Program 1
(valex (grade) 
  (classify grade
    ((90 100) 'A') 
    ((80 89) 'B')
    ((70 79) 'C')
    ((60 69) 'D') 
    (otherwise 'F')))

This program takes an integer grade value and returns a character indicating which range the grade falls in.

In general, the classify construct has the following form:

(classify E_disc
   ((Elo_1 Ehi_1) Ebody_1)
   ...
   ((Elo_n Ehi_n) Ebody_n)
   (otherwise E_default))

The evaluation of classify should proceed as follows.

First the discriminant expression E_disc should be evaluated to the value V_disc, which is expected to be an integer. Then V_disc should be matched against each of the clauses ((Elo_i Ehi_i) Ebody_i) from top to bottom until one matches. The value matches a clause if it lies in the range between Vlo_i and Vhi_i, inclusive, where Vlo_i is the integer value of Elo_i, and Vhi_i is the integer value of Ehi_i. When the first matching clause is found, the value of the associated expression Ebody_i is returned. If none of the clauses matches V_disc , the value of the default expression E_default is returned.

Here are a few more examples of the classify construct:

; Classify program 2 
(valex (a b c d)
  (classify (* c d)
    ((a (- (/ (+ a b) 2) 1)) (* a c)) 
    (((+ (/ (+ a b) 2) 1) b) (* b d)) 
    (otherwise (- d c))))

Program 2 emphasizes that any of the subexpressions of classify may be arbitrary expressions that require evaluation. In particular, the upper and lower bound expressions need not be integer literals. For instance, here are some examples of the resulting value returned by Program 2 for some sample inputs:

; Classify program 3
(valex (a)
  (classify a
    ((0 9) a)
    (((/ 20 a) 20) (+ a 1)) 
    (otherwise (/ 100 (- a 5)))))

Program 3 emphasizes that (1) ranges may overlap (in which case the first matching range is chosen) and (2) expressions in clauses after the matching one are not evaluated. For instance, here are here are some examples of the resulting value returned by Program 3 for some sample inputs:

Your Tasks

Dexter has asked you to implement the classify construct in Valex as syntactic sugar. You will do this in three phases.

1. (9 points) In your PS11 Google Doc, write down how you would like each of the three example programs above to be desugared into equivalent Valex programs that do not have classify. Your programs may include other sugar constructs, such as &&.

2. (9 points) In your PS11 Google Doc, write down incremental desugaring rules that desugar classify into other Valex constructs. These rules should be expressed as rewrite rules on s-expressions. For example, here are the desugaring rules for Valex’s sugared constructs except quote:

   (&& E_rand1 E_rand2) ↝ (if E_rand1 E_rand2 #f) 
   (|| E_rand1 E_rand2) ↝ (if E_rand1 #t E_rand2) 
   
   (cond (else E_default)) ↝ E_default
   (cond (E_test E_then) ...) ↝ (if E_test E_then (cond ...))
   
   (list) ↝ #e 
   (list E_head ...) ↝ (prep E_head (list ...))
   
   (bindseq () E_body) ↝ E_body
   (bindseq ((Id E_defn) ...) E_body) ↝ (bind Id E_defn (bindseq (...) E_body))
   
   (bindpar ((Id_1 E_defn_1) ... (Id_n E_defn_n)) E_body)
     ↝ (bind Id_list (* fresh variable name *)
             (list E_defn_1 ... E_defn_n) (* eval defns in parallel *)
             (bindseq ((Id_1 (nth 1 Id_list))
                       ...
                       (Id_n (nth n Id_list)))
                E_body))

   Note that ... means zero or more occurrences of the preceding kind of syntactic entity.

   NOTES:

   • Your desugaring rules may rewrite an s-expression into an s-expression that includes other sugar constructs, such as &&.

   • Your desugaring rules should be written in such a way that E_disc is evaulated only once. To guarantee this, you will need to name the value of E_disc with a “fresh” variable (one that does not appear elsewhere in the program).

   • Your desugaring rules should be written in such a way that the Elo and Ehi expressions in each clause are evaluated at most once.

   • You should treat differently the cases where E_disc is an identifier and when it is not an identifier.

   • Your rules should be designed to give the same output for the three sample programs as in part a.

3. (12 points) In this part, you will implement and test your desugaring rules from the previous part.

Begin this part by (1) renaming the files ValexPS11.sml and ValexEnvInterpPS11.sml to be yourAccountName-ValexPS11.sml and yourAccountName-ValexEnvInterpPS11.sml and (2) in yourAccountName-ValexEnvInterpPS11.sml, changing use "ValexPS11.sml"; to use "yourAccountName-ValexPS11.sml";.

NOTES:

• Be careful to change to yourAccountName-ValexPS11.sml, not any files in the valex directory.

• Use Utils.fresh to create a fresh variable.

• To test your implementation after editing yourAccountName-ValexPS11.sml, first load yourAccountName-ValexEnvInterpPS11.sml into a *sml* buffer, and then pay attention to the following:

  • In the ps11 directory, the files classify1.vlx, classify2.vlx, and classify3.vlx contain the three example classify programs from above. The file sort3.vlx contains a test file that not using classify that returns a sorted list of its 3 arguments.

  • Your implementation should give the same output for the three sample programs as in part a. For seeing the output of the desugaring of your classify construct for examples, use one of the following approaches:

    1. To desugar a file, use Valex.desugarFile to print the result of desugaring the program in the file. For example, supposed sort3.vlx contains this program:

       (valex (a b c)
         (cond ((&& (<= a b) (<= b c)) (list a b c))
               ((&& (<= a c) (<= c b)) (list a c b))
               ((&& (<= b a) (<= a c)) (list b a c))
               ((&& (<= b c) (<= c a)) (list c b a))
               ((&& (<= c a) (<= a b)) (list c a b))
               (else (list c b a))))

       Then here is the result of using Valex.desugarFile on this program:

       - Valex.desugarFile "sort3.vlx";
       (valex (a b c)
              (if (if (<= a b) (<= b c) #f)
                  (prep a (prep b (prep c #e)))
                  (if (if (<= a c) (<= c b) #f)
                      (prep a (prep c (prep b #e)))
                      (if (if (<= b a) (<= a c) #f)
                          (prep b (prep a (prep c #e)))
                          (if (if (<= b c) (<= c a) #f)
                              (prep c (prep b (prep a #e)))
                              (if (if (<= c a) (<= a b) #f)
                                  (prep c (prep a (prep b #e)))
                                  (prep c (prep b (prep a #e)))
                                  )
                              )
                          )
                      )
                  )
              )
       val it = () : unit

    2. To desugar an expression, one approach is to invoke the Valex.desugarString function on a string representing the expression you want to desugar. For example:

       - Valex.desugarString "(&& (|| a b) (|| c d))" 
       (if (if a #t b) (if c #t d) #f)
       - : unit = ()
       
       - Valex.desugarString "(list 1 2 3)"
       (prep 1 (prep 2 (prep 3 #e)))
       - : unit = ()

    3. To desugar an expression, another approach is to use ValexEnvInterp.repl() to launch a read-eval-print loop and use the #desugar directive to desugar an expression. For example:

       - ValexEnvInterp.repl();
       
       valex> (#desugar (&& (|| a b) (|| c d))) 
       (if (if a #t b) (if c #t d) #f)
       
       valex> (#desugar (list 1 2 3)) 
       (prep 1 (prep 2 (prep 3 #e)))

  • There are several ways to test the evaluation of your desugared classify construct:

    1. To run a program, one approach is to invoke ValexEnvInterp.runFile on the filename and a list of integer arguments. For example:

       - ValexEnvInterp.runFile "sort3.vlx" [23, 42, 17];
       val it = List [Int 17,Int 23,Int 42] : Valex.value

    2. To run a program, another approach is to use ValexEnvInterp.repl() to launch a read-eval-print loop and use the #run directive to run a fileon arguments. For example:

       - ValexEnvInterp.repl();
       
       valex> (#run sort3.vlx 23 42 17)
       (list 17 23 42)

    3. To evaluate an expression, use ValexEnvInterp.repl() to launch a read-eval-print loop and enter the expression. To evaluate an expression with free variables, use the #args directive to bind the variables. For example:

       - ValexEnvInterp.repl();
       
       valex> (#args (a 2) (b 3))
       
       valex> (bindpar ((a (+ a b)) (b (* a b))) (list a b))
       (list 5 6)
       
       valex> (bindseq ((a (+ a b)) (b (* a b))) (list a b))
       (list 5 15)

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

1. (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 an abs. That is, you should treat the evaluation of (bind I_defn E_defn E_body) in environment F as the result of evaluating Ebody in the environment frame F', where F' binds I_defn to V_defn, V-defn is the result of evaluating E_defn in F, and the parent frame of F' is F.

   • 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) the fun 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 frame F whose parent frame is F_creation and which binds the variables I_1 … I_n to the values V_1 … V_n.

2. (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.

3. (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].

4. (2 points) What is the final value of the program from part (c) in dynamically scoped Hofl?

5. (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:

1. If you don’t already have one, create a *sml* SML interpreter buffer within Emacs.

2. In a *sml* buffer, load both the static and dynamic Holf interpreters as follows:

   Posix.FileSys.chdir("/home/wx/cs251/sml/hofl");
   use "load-hofl-interps.sml";

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

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

3. 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)))

1. (6 points) Draw an environment diagram showing the environments created when E is evaluated in statically scoped Hofl, and show the final value of evaluating E.

2. (6 points) Consider the expression E' that is obtained from E by replacing bindrec by bindseq. Draw an environment diagram showing the environments created when E' is evaluated in statically scoped Hofl, and show the final value of evaluating E'.

3. (6 points) Draw an environment diagram showing the environments created when E' is evaluated in dynamically scoped Hofl, and show the final value of evaluating E'.

4. (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 2.

4. 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:

1. If you don’t already have one, create a *sml* SML interpreter buffer within Emacs.

2. In the *sml* buffer, execute the following SML command to change the default directory:

   - Posix.FileSys.chdir "/home/wx/cs251/sml/ps11";

Your Task

Create a file /home/wx/cs251/ps11/exp4.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 "Problem4Tester.sml"; (* this only need be executed once *)
... lots of output omitted ...

- testProblem4(); (* you can execute this multiple times *)

This evaluates the expression in the exp4.hfl file in both scoping mechanisms and displays the results. A correct solution should have the following output:

- testProblem4();
/home/wx/cs251/ps11/exp4.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 exp4.hfl to your PS11 doc. You needn’t submit anything to the drop folder.

5. 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 ps11/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))))))

1. (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.

2. (10 points) Let i range over the numbers {1,2,3}. Then each of the Racket functions make-counteri can be modeled in Java by an instance of class Counteri that implements the Counter 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 Counteri classes in the above code so that they correctly model the behavior of the Racket function make-counteri.

   The above code can be found in the file ps11/CountersSkeleton.java. Begin this problem by making a copy of ps11/CountersSkeleton.java named ps11/yourAccountName-Counters.java, and flesh out the missing class definitions in ps11/Counters.java.

   Notes:

   • In addition to its single nullary instance method invoke, each class Counteri should have a single class, instance, or local variable named count.

   • The testCounters method of the Counters class takes two objects from classes satisfying the Counter interface and tests them in a way similar to Racket’s test-counter. The test expression (test-counter make-counteri) in Racket can be modeled by the Java statement testCounters(new Counteri, new Counteri);

   • To compile and run the Counters program in the wx virtual machine, execute the following Linux shell commands:

     cd "~/cs251-download/ps11" 
     javac Counters.java 
     java Counters

     This will display the result of testing the three Counteri classes. These results should be similar to calling Racket’s test-counter function on the three make-counteri

6. A Hofl Interpreter in Hofl (35 points)

The Hofl Handout describes a Hofl program named bindex-interp.hfl that is a
Bindex interpreter written in Hofl. (This program can also be found in the
~/cs251/sml/hofl directory.)

Create a Hofl program named hofl-interp.hfl that is an interpreter for Hofl.
You can start by making hofl-interp.hfl be a copy of bindex-interp.hfl
and extend it to be a complete HOFL interpreter. Your program should have
a run function that can run a Hofl program on a list of integer arguments.

For this problem you do not need to implement a Read/Eval/Print Loop (REPL),
or handle loading of Hofl programs from a file.