Principles of Programming Languages — Homework 15

Due by class time Tuesday, November 23

Reading

Tester Program

To use the auto-tester program for this assignment, download the files hw15-tester.scm and auto-tester.scm and put them in the same folder as your Scheme file. If you've already downloaded auto-tester.scm before, you don't need to download it again. Then put (require "hw15-tester.scm") at the top of your Scheme file.

Exercises

  1. Add the logical special form (and exp1 exp2 exp3 ...) to your language by implementing it as a macro that expands to an equivalent if/else expression, according to the following syntactic expansion rules: 

    (and exp) → exp

(and exp1 exp2 exp3 ...) → (if exp1 then (and exp2 exp3 ...) else False)
    To do this, you should define the function (and-expression? exp), which returns true when given a valid and-expression, and (and-expander exp), which takes a valid and-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 and-expressions. Examples: 
    (and-expander '(and ((1 + 1) == 2)))
  → ((1 + 1) == 2)

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

(and-expander '(and a b c))
  → (if a then (if b then c else False) else False)

(and-expander '(and w x y z))
  → (if w then (if x then (if y then z else False) else False) else False)

(run '(and ((1 + 1) == 2) (pi > 3)))
  → #t

  2. Add a new "shorthand" version of def expressions to your language. Shorthand definitions are only used for defining functions, and have the following syntactic form: 

    (def (name param1 param2 ...) :
  body1 body2 ...)
    which is equivalent to: 
    (def name
  (function (param1 param2 ...) :
    body1 body2 ...))
    For example, the following function definitions are equivalent: 
    Standard syntax                     Shorthand syntax

(def even?                          (def (even? n) :
  (function (n) :                     (if (n == 0)
    (if (n == 0)                          then True
        then True                         else (odd? (n - 1))))
        else (odd? (n - 1)))))

(def hello                          (def (hello x y z) :
  (function (x y z) :                 (print "Hello" x)
    (print "Hello" x)                 (print "Hello" y)
    (print "Hello" y)                 (print "Hello" z))
    (print "Hello" z)))
    The shorthand version saves a line of code (and an extra set of parentheses), and may be easier to read. Implement the shorthand version of def as a macro in your interpreter, according to the above expansion rule. To do this, define two new functions: (def-shorthand-expression? exp), which tests if exp is a valid shorthand def-expression, and (def-shorthand-expander exp) that takes a valid shorthand expression and expands it into the standard form. Then add a line to m to handle shorthand definitions. For example: 
    ==> (def (fact n) :
      (if (n == 0)
          then 1
          else (n * (fact (n - 1)))))
==> (fact 5)
120

Turning in Your Homework