Quiz 3: Control

Instructions:

  • Due Date: Monday, Nov. 25, 11:59PM EST
  • You must complete this quiz on your own. Do not consult with others. You are encouraged to use the course notes (posted on this webpage) as your main resource when solving these quiz questions.
  • All quiz solutions are uploaded to gradescope. There will be two submissions
    1. A code upload for the programming assignment. Upload two files: a file called break.rkt and a file called tail-form.rkt.
    2. A file upload where you upload your written solutions. This can be a PDF, photos of paper, etc.
  • Quiz-related questions will not be answered on Piazza or during office hours. Logistics-related questions (like “how do I turn in the quiz?” or “the autograder does not terminate or errors”) are OK.

Starter code: break.rkt tail-form.rkt

Question 1: Concept Check [10 Points]

State whether each of the following is true or false. If it is false, provide a brief explanation for why. Upload your solutions as written solutions.

  1. The following program does not grow the call stack during its execution:
    (define (foo k)
  (if (< 3 k)
   (foo 25)
   (+ (foo 30) 15)))
  2. It is possible to translate any function into one that is in tail form by using continuations.
  3. The only way to translate a program into tail form is to use continuations.

Question 2: Tail Form [30 Points]

We’ve seen converting functions into tail-recursive form both in class and in a homework. For each of the two functions, write an equivalent implementation in tail-recursive form. Do not remove the original program. Do not change name, arguments or contract of the tail functions, you can only modify the body of them. Only recursive functions need to be transformed into tail recursive form. Starter code is provided in the tail-form.rkt file.

1.

;;; type tree =
;;;   | node of int * (ListOf tree)
;;;   | leaf
(struct node (children) #:guard (struct-guard/c (listof (recursive-contract tree/c))) #:transparent)
(struct leaf (val) #:guard (struct-guard/c integer?) #:transparent)

(define tree/c (or/c node? leaf?))

;;; tree-preorder : tree -> ListOf int
;;; Traverse the tree in left to right order and produce
;;; a list of values in the order they were visited.
;;; * do not modify *
(define/contract (tree-preorder tree)
  (-> tree/c (listof integer?))
  (match tree
    [(leaf val) (list val)]
    [(node children) (foldr append '() (map tree-preorder children))]))

2.

;;; type lexpr =
;;; | ident of string
;;; | lam of string * lexpr
;;; | app of lexpr * lexpr
;;; | add of lexpr * lexpr
;;; | num of int
(struct ident (s) #:guard (struct-guard/c string?) #:transparent)
(struct lam (id body) #:guard (struct-guard/c string? (recursive-contract expr/c)) #:transparent)
(struct app (e1 e2)
  #:guard (struct-guard/c (recursive-contract expr/c) (recursive-contract expr/c))
  #:transparent)
(struct num (n) #:guard (struct-guard/c integer?) #:transparent)
(struct add (e1 e2)
  #:guard (struct-guard/c (recursive-contract expr/c) (recursive-contract expr/c))
  #:transparent)

(define expr/c (or/c ident? lam? app? num? add?))
;;; type value =
;;; | vlam of string * lexpr * environment
;;; | vnum of number
(struct vlam (id body closure)
  #:guard (struct-guard/c string? expr/c (hash/c string? (recursive-contract value/c)))
  #:transparent)
(struct vnum (n) #:guard (struct-guard/c integer?) #:transparent)

(define value/c (or/c vlam? vnum?))

;;; get−num : value -> number
;;; extracts a number from a value or errors
(define (get-num v)
  (match v
    [(vnum n) n]
    [_ (error "not a number")]))

;;; eval−lam−env : lexpr -> (hash-table string value) -> value
;;; Evaluates the given lexpr into a value
;;; *do not modify*
(define/contract (eval-lam-env e env)
  (-> expr/c (hash/c string? value/c) value/c)
  (match e
    [(ident x) (if (hash-has-key? env x) (hash-ref env x) (error "unbound identifier"))]
    [(lam id body) (vlam id body env)]
    [(num n) (vnum n)]
    [(add e1 e2) (vnum (+ (get-num (eval-lam-env e1 env)) (get-num (eval-lam-env e2 env))))]
    [(app e1 e2)
     (match (eval-lam-env e1 env)
       [(vlam id body closure)
        (let* ([arg-v (eval-lam-env e2 env)] [extended-env (hash-set closure id arg-v)])
          (eval-lam-env body extended-env))])]))

Question 3 [60 Points]

Imperative languages usually use constructs like for and while loops to express iteration. An important part of those constructs is break, that allows you to ‘break out’ of the loop. In this exercise you will make an interpreter for a small language with while loops and breaks called implang.

;;; type expr =
;;;   | eident of string
;;;   | eadd of expr * expr
;;;   | elt of expr * expr - means < operator
;;;   | eeq of expr * expr - means == operator
;;;   | enum of integer
(struct eident (id) #:guard (struct-guard/c string?) #:transparent)
(struct eadd (e1 e2)
  #:guard (struct-guard/c (recursive-contract expr/c) (recursive-contract expr/c))
  #:transparent)
(struct elt (e1 e2)
  #:guard (struct-guard/c (recursive-contract expr/c) (recursive-contract expr/c))
  #:transparent)
(struct eeq (e1 e2)
  #:guard (struct-guard/c (recursive-contract expr/c) (recursive-contract expr/c))
  #:transparent)
(struct enum (n) #:guard (struct-guard/c integer?) #:transparent)

(define expr/c (or/c eident? eadd? elt? eeq? enum?))

;;; type statement =
;;;   | sassign of string * expr - id = e
;;;   | swhile of expr * statement
;;;   | sbreak-if of expr
;;;   | sseq of statement * statement
(struct sassign (id e) #:guard (struct-guard/c string? expr/c) #:transparent)
(struct swhile (guard body)
  #:guard (struct-guard/c expr/c (recursive-contract statement/c))
  #:transparent)
(struct sbreak-if (e) #:guard (struct-guard/c expr/c) #:transparent)
(struct sseq (s1 s2)
  #:guard (struct-guard/c (recursive-contract statement/c) (recursive-contract statement/c))
  #:transparent)

(define statement/c (or/c sassign? swhile? sbreak-if? sseq?))

;;; type prog = statement * expr
;;; Represents a program in implang that consists of a statement and a return expression.
(struct prog (body ret) #:guard (struct-guard/c statement/c expr/c) #:transparent)

The semantics of the language:

  • (eident id) evaluates to the value bound to a variable with that id. Raise runtime error if the variable is unbound.
  • (eadd e1 e2) adds the results of two sub-expressions. Both sub-expressions have to evaluate to numbers, otherwise a runtime error is raised.
  • (elt e1 e2) compares the results of evaluating two sub-expressions. Let v1 be the result of evaluating e1, and v2 of e2. v1 and v2 have to evaluate to a number, otherwise a runtime error is raised. Return (vbool #t) if v1 < v2, and (vbool #f) otherwise.
  • (eeq e1 e2) compares the results of evaluating two sub-expressions. Let v1 be the result of evaluating e1, and v2 of e2. v1 and v2 have to evaluate to a number, otherwise a runtime error is raised. Return (vbool #t) if v1 = v2, and (vbool #f) otherwise.
  • (enum n) evaluates to (vnum n)
  • (sassign id e) mutates the value of the variable. Let v be the value e evaluates to. Then set the value of variable id to that v. Do not check that the type of variable is the same as the type of e.
  • (swhile guard body) runs the guard. If it evaluates to (vbool #t), then it runs the (sseq body (swhile guard body)). If guard returns (vbool #f), then do nothing.
  • (sbreak-if e) - If e evaluates to (vbool #t), then terminate the innermost loop only. If e evaluates to (vbool #f), then do nothing. Does nothing outside swhile loop.
  • (sseq s1 s2) first evaluates s1, and then evaluates s2.
  • (prog body ret) first evaluates statement body, and then evaluates expression ret and returns the result of running ret.

Some examples:

> (interp/p (prog (sassign "x" (enum 10)) (eident "x")))
(vnum 10)

> (interp/p (prog (sseq (sassign "x" (enum 0))
                        (swhile (elt (eident "x") (enum 5))
                                (sassign "x" (eadd (eident "x") (enum 1)))))
                  (eident "x")))
(vnum 5)

> (interp/p (prog (sseq (sassign "x" (enum 0))
                        (swhile (elt (eident "x") (enum 5))
                                (sseq (sbreak-if (elt (enum 3) (eident "x")))
                                      (sassign "x" (eadd (eident "x") (enum 1))))))
                  (eident "x")))
(vnum 4)

Your task is to implement the interpreter by filling the bodies of functions interp/p, interp/s and interp/e. Do not change the names, arguments or contracts of those functions (contracts and arguments serve as hints as to how you should set up your solution).