Principles of Programming Languages — Homework 16

Due by class time Tuesday, November 19

Download the files assign16.scm and new-environment-representation.scm and use them as your starting point for this assignment. This is the version of the interpreter from class today, with support added for def, load, and or2. To use the autotester program for this assignment, download hw16-tester.scm (and auto-tester-base.scm if you need it) and put them in the same folder as assign16.scm. Then uncomment the line (require "hw16-tester.scm") at the top of assign16.scm.

  1. In class, we implemented the special form (or2 exp1 exp2) as a macro that expands into an equivalent if/else expression using the syntactic expansion rule: 

    (or2 exp1 exp2) → (if exp1 then True else exp2)

    Implement (and2 exp1 exp2) expressions as macros in the same way, using the code we wrote for or2 as a guide. More specifically, write a function (and2-expression? x) that checks if x is a valid and2 expression, and a function (and2-expander exp) that takes a valid and2 expression and returns an equivalent if/else expression that behaves in exactly the same way. The and2-expander function should not evaluate the expanded code. Instead, add a line to m so that when an and2 expression is encountered, it gets expanded into the equivalent if/else code and the new code is evaluated instead.

    Test cases:
    (test: and2-expression?)
    (test: and2-expander)
    (test: run 1 2 3 4 5 6 7 8)

  2. Add the special form (or exp1 exp2 exp3 ...), which can have one or more subexpressions, to your language by implementing it as a macro that expands into an equivalent if/else expression, according to the following syntactic expansion rules: 

    (or exp) → exp

(or exp1 exp2 exp3 ...) → (if exp1 then True else (or exp2 exp3 ...))
    To do this, write the functions (or-expression? x), which returns true when given a valid or expression as input, and (or-expander exp), which takes a valid or expression and fully expands it into the equivalent (possibly nested) if/else form, according to the above recursive expansion rules. The resulting expanded code should not contain any embedded or expressions. Finally, add code to m that expands and evaluates or expressions using your functions as helpers. Also, don't forget to make or a reserved keyword to avoid confusion with function applications! 
    (or-expander '(or ((1 + 1) == 2)))
  → ((1 + 1) == 2)

(or-expander '(or ((1 + 1) == 2) (pi > 3)))
  → (if ((1 + 1) == 2) then True else (pi > 3))

(or-expander '(or a b c))
  → (if a then True else (if b then True else c))

(or-expander '(or w x y z))
  → (if w then True else (if x then True else (if y then True else z)))

    Test cases:
    (test: or-expression?)
    (test: or-expander)
    (test: run 9 10 11 12 13 14 15 16 17 18 19)

  3. Add the special form (and exp1 exp2 exp3 ...), which can have one or more subexpressions, to your language by implementing it as a macro that expands into an equivalent if/else expression, like you did in the previous exercise for or. Here are the expansion rules for and expressions: 

    (and exp) → exp

(and exp1 exp2 exp3 ...) → (if exp1 then (and exp2 exp3 ...) else False)
    Write the functions (and-expression? x) and (and-expander exp), and add code to m that expands and evaluates and expressions using your functions as helpers.

    Test cases:
    (test: and-expression?)
    (test: and-expander)
    (test: run 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35)

  4. Add support to your interpreter for the special form (swap var1 var2). A swap statement simply swaps the values of the two variables (both of which must already exist in the environment). The value returned by the swap statement itself is the symbol done. This value, however, is not important, since we are only interested in the side-effects that swap has on the two variables. You should first define a function called (swap-statement? x) that checks if its input is a valid swap statement, and then add code to m to evaluate a swap. For example:

    ==> (list a b)
(1 2)
==> (swap a b)
done
==> (list a b)
(2 1)

    Test cases:
    (test: swap-statement?)
    (test: run 36 37 38 39 40)

  5. Add parallel assignment statements to your language, with the following syntax:

    ((var1 var2 ... varN) := exp1 exp2 ... expN)

    In a parallel assignment, the left side is a list of variables rather than a single variable. The number of variables on the left side must match the number of expressions on the right side (if not, an error message should occur). To evaluate a parallel assignment, all of the right-side expressions are evaluated within the current environment. The resulting values are then assigned to the corresponding variables on the left side, and the symbol done is returned as the final result. You should first define a function called (parallel-assignment? x) that checks if its input is a valid parallel assignment statement. Then add code to m to evaluate parallel assignments. Examples:

    ==> (print a b c d)
1 2 3 4
done
==> ((a b c d) := (5 * 2) (a + b) (c * 10) (b + c))
done
==> (print a b c d)
10 3 30 5
done
==> ((a b c d) := d c b a)
done
==> (print a b c d)
5 30 3 10
done
==> (with [x = 10] [y = 20] :
       (print x y)
       ((x y) := y x)
       (print x y))
10 20
20 10
done

    Test cases:
    (test: parallel-assignment?)
    (test: run 41 42 43 44 45)

Turning in Your Homework