Assignment 2: Interpreters

Parameters:

• Due date: Thursday Sept 19, 11:59PM EST
• Use the following code template here
• Upload a code.rkt solution to Gradescope. It will give you a score, but this is not your final score; some of the test cases will be kept private. You should test all your code thoroughly.
• Ask questions on Piazza or during office hours.
• Perform all the work for this project by yourself. You may discuss with your classmates, but you must write your own code.

Resources:

• Install Racket
• The Racket Guide
• The Design Recipe

Problem 1 [30 Points]: cond

Recall the ite language from class:

;;; type expr =
;;;   | add of expr * expr
;;;   | mul of expr * expr
;;;   | num of number
;;;   | bool of bool
;;;   | ite of expr * expr * expr
(struct eadd (e1 e2) #:transparent)
(struct emul (e1 e2) #:transparent)
(struct enum (n) #:transparent)
(struct ebool (n) #:transparent)
(struct eite (guard thn els) #:transparent)


;;; type value =
;;;    | vnum of number
;;;    | vbool of bool
(struct vbool (b) #:transparent)
(struct vnum (n) #:transparent)

;;; to-num : value -> number
;;; converts a value to a number or raises a runtime error
(define (to-num v)
  (match v
    [(vnum n) n]
    [_ (error "runtime")]))

;;; to-num : value -> bool
;;; converts a value to a bool or raises a runtime error
(define (to-bool v)
  (match v
    [(vbool b) b]
    [_ (error "runtime")]))


;;; interp : expr -> value
;;; evaluates an expression to a value
(define (interp e)
  (match e
    [(eadd e1 e2)
     (let [(n1 (to-num (interp e1)))
           (n2 (to-num (interp e2)))]
       (vnum (+ n1 n2)))]
    [(emul e1 e2)
     (let [(n1 (to-num (interp e1)))
           (n2 (to-num (interp e2)))]
       (vnum (* n1 n2)))]
    [(ebool b) (vbool b)]
    [(eite guard thn els)
     (let [(vguard (to-bool (interp guard)))]
       (if vguard (interp thn) (interp els)))]
    [(enum n) (vnum n)]))

In this exercise you will develop a new language that replaces if with cond. You will use the following abstract syntax:

;;; type arm : expr * expr
(struct arm (guard body))

;;; type expr =
;;;    | enum of number
;;;    | ebool of boolean
;;;    | eadd of expr * expr
;;;    | emul of expr * expr
;;;    | econd of arm list
(struct enum (n) #:transparent)
(struct ebool (b) #:transparent)
(struct eadd (l r) #:transparent)
(struct emul (l r) #:transparent)
(struct econd (arms) #:transparent)

The semantics of econd is given as follows:

• Each arm should be evaluated in the order it appears in the list.
• An arm is a pair (guard, body):
  • If guard evaluates to (vbool #t) then body should be evaluated and returned. The remaining arms need not be evaluated–this is what is called a short-circuiting operation.
  • If guard evaluates to (vbool #f), then the next arm should be evaluated. If there is no next arm, an error should be raised.
• If guard evaluates to something that is not a Boolean, then an error should be raised by calling the Racket error function with a useful error message.
• If the list of arms is empty, then an error should be raised.

Your task: Implement the interp-cond function that evaluates cond programs with the above syntax and semantics.

Example usage:

>(interp-cond
  (econd (list (arm (ebool #f) (enum 10))
               (arm (ebool #t) (enum 20)))))
(vnum 20)

Problem 2: Scope and substitution [30 points]

Recall the let language from class that implements lexical scope:

;;; type letexpr =
;;;   | elet of string * letexpr * letexpr
;;;   | eident of string
;;;   | enum of number
;;;   | eadd of letexpr * letexpr
;;;   | emul of letexpr * letexpr
(struct elet (id assignment body) #:transparent)
(struct eident (id) #:transparent)

;;; subst : letexpr -> string -> letexpr -> letexpr
;;; performs the substitution expr[id |-> e]
;;; i.e., substitutes e for id in expr
(define (subst expr id e)
  (match expr
    [(eadd e1 e2) (eadd (subst e1 id e)
                        (subst e2 id e))]
    [(emul e1 e2) (emul (subst e1 id e)
                        (subst e2 id e))]
    [(enum num) (enum num)]
    [(elet letid assignment body)
     (if (equal? letid id)
         (elet letid assignment body) ; shadowing case, do nothing
         (elet letid assignment (subst body id e))) ; not shadowing
     ]
    [(eident x)
     ;; if x = id, then we perform substitution. otherwise, do nothing
     (if (equal? id x) e (eident x))]
    ))

;;; interp-let : letexpr -> number
;;; evaluates a letetxpr to a number
(define (interp-let expr)
  (match expr
    [(eadd e1 e2) (+ (interp-let e1) (interp-let e2))]
    [(emul e1 e2) (* (interp-let e1) (interp-let e2))]
    [(eident x) (error "runtime error: unbound identifier")]
    [(elet id binding body)
     (let* [(vbinding (enum (interp-let binding)))
            (substbody (subst body id vbinding))]
       (interp-let substbody))]
    [(enum n) n]))

In this problem we you will implement an alternative version of substitution that has different scoping rules. Your “broken” substitution has the following signature:

;;; broken-subst : letexpr -> string -> letexpr -> letexpr
;;; performs a strange substitution
(define (broken-subst expr id e)
  (error "implement me"))

You are provided with a version of interp that makes use of broken-subst:

;;; broken-interp-let : letexpr -> number
;;; runs a `letexpr` program using `broken-subst`
(define (broken-interp-let expr)
  (match expr
    [(eadd e1 e2) (+ (broken-interp-let e1) (broken-interp-let e2))]
    [(emul e1 e2) (* (broken-interp-let e1) (broken-interp-let e2))]
    [(eident x) (error "runtime error: unbound identifier")]
    [(elet id binding body)
     (let* [(vbinding (enum (broken-interp-let binding)))
            (substbody (broken-subst body id vbinding))]
       (broken-interp-let substbody))]
    [(enum n) n]))

Your task is to implement broken-subst so that the following two tests pass:

(check-equal?
 (broken-interp-let
  (elet "x" (enum 10)
        (elet "x" (enum 20) (eident "x")))) 10)

(check-equal?
 (broken-interp-let
  (elet "x" (enum 10)
        (elet "x" (eadd (eident "x") (enum 15)) (eident "x")))) 10)

We will also test your solution on some other hidden programs that have the same scoping rules as here: you will need to identify what the new scoping rule of this program is based on these examples.

Problem 3: Uniqify [40 Points]

You are tired of dealing with shadowing, so you’ve decided to implement a function called uniqify that, when given an abstract syntax tree for the let language, renames all shadowed variables to unique names. This way, you can tell a variable’s scope just by looking for its unique binding in the program!

Problem 3a: Rename [10 Points]

You run into a challenge almost immediately: even if we generate unique names, we need a way to replace the existing name in your abstract syntax tree with your newly generated unique one. Notice how our current subst function does not do that yet.

Write function update-names with type letexpr -> string -> string -> letexpr such that (update-names e id id2) replaces all instances variables with name id in e with the name id2 regardless of scoping rules (i.e., ignoring shadowing). You can assume that id2 will never appear in e.

Example behavior:

(check-equal?
 (update-names (elet "x" (enum 10) (eident "x")) "x" "y")
 (elet "y" (enum 10) (eident "y")))

(check-equal?
 (update-names (elet "x" (enum 10) (elet "x" (enum 20) (eident "x"))) "x" "y")
 (elet "y" (enum 10) (elet "y" (enum 20) (eident "y"))))

Problem 3b: Uniqify [30 Points]

If we assume all variables have unique names, we can simplify our interpreter and substitution function as follows:

;;; uniq-subst : letexpr -> string -> letexpr -> letexpr
;;; performs substitution assuming all names are unique (i.e., there is no possible shadowing)
(define (uniq-subst expr id e)
  (match expr
    [(eadd e1 e2) (eadd (uniq-subst e1 id e)
                        (uniq-subst e2 id e))]
    [(emul e1 e2) (emul (uniq-subst e1 id e)
                        (uniq-subst e2 id e))]
    [(enum num) (enum num)]
    [(elet letid assignment body)
     (elet letid (uniq-subst assignment id e) (uniq-subst body id e))]
    [(eident x)
     ;; if x = id, then we perform uniq-substitution. otherwise, do nothing
     (if (equal? id x) e (eident x))]
    ))

;;; uniq-interp-let : letexpr -> string -> letexpr -> letexpr
;;; evaluates letexpr terms using uniq-subst
(define (uniq-interp-let expr)
  (match expr
    [(eadd e1 e2) (+ (uniq-interp-let e1) (uniq-interp-let e2))]
    [(emul e1 e2) (* (uniq-interp-let e1) (uniq-interp-let e2))]
    [(eident x) (error "runtime error: unbound identifier")]
    [(elet id binding body)
     (let* [(vbinding (enum (uniq-interp-let binding)))
            (substbody (broken-subst body id vbinding))]
       (uniq-interp-let substbody))]
    [(enum n) n]))

Your task is to write a function uniqify so that we can run let programs using uniq-interp-let without changing their semantics (meaning, they still obey lexical scope). Concretely, you will have the following signatures:

;;; uniqify : letexpr -> letexpr
(define (uniqify e)
  (error "implement me"))

;;; interp-uniqify : expr -> number
;;; run a letexpr program using uniqify and uniq-interp-let
(define (interp-uniqify e)
  (uniq-interp-let (uniqify e)))

Then, your solution should satisfy that for any letexpr expression e, it is the case that (interp e) = (interp-uniqify e). For example, the following tests should pass:

(check-equal? (interp-uniqify (elet "x" (enum 10) (eident "x"))) 10)

(check-equal?
 (interp-uniqify
  (elet "x" (enum 10)
        (elet "x" (enum 20) (eident "x")))) 20)