Instructions

  • Deadline: Friday Feb. 9 at 11:59PM
  • This quiz is to be completed on your own. Please do not consult with classmates. You are permitted to use the course notes and Dr Racket. Only ask questions relating to the quiz as private Piazza questions.
  • Upload a single file called code.rkt to Gradescope. Your upload should be valid Plait: be sure your upload runs in Dr Racket without errors. Use the provided starter code.
  • Use the following starter code: link
  • Note: The autograder score is not your final score.
  • The quiz is graded out of 100 points in total.

Problem 1: Short answer [25 Points]

Answer these questions by filling in the appropriate portion of the provided starter code.

Problem 1a

Recall the let abstract syntax tree from class:

(define-type Exp
  [numE (n : Number)]
  [plusE (left : Exp) (right : Exp)]
  [varE (name : Symbol)]
  [let1E (var : Symbol)
         (assignment : Exp)
         (body : Exp)])

Consider the following small expression:

(define my-exp (let1E 'x (numE 10)
         (plusE
          (let1E 'x (numE 20)
                 (plusE (varE 'x) (varE 'x)))
          (varE 'x))))

Define an expression my-exp-subst that is the result of substituting x in my-exp with num 30 (i.e., my-exp[x |-> (num 30)]).

Problem 1b

Recall the evaluator for if:

(define-type Exp
  [num (n : Number)]
  [bool (b : Boolean)]
  [plus (left : Exp) (right : Exp)]
  [cnd (test : Exp) (thn : Exp) (els : Exp)])

(define-type Value
  [vbool (v : Boolean)]
  [vnum (n : Number)])

(define (value->num v)
  (type-case Value v
   [(vbool b) (error 'value "invalid value")]
   [(vnum n) n]))

(define (value->bool v)
  (type-case Value v
   [(vnum n) (error 'value "invalid value")]
   [(vbool b) b]))


(define (add v1 v2)
  (+ (value->num v1) (value->num v2)))

(define (calc e)
  (type-case Exp e
    ([num n] (vnum n))
    ([bool b] (vbool b))
    ([plus l r] (vnum (add (calc l) (calc r))))
    ([cnd test thn els] (if (value->bool (calc test))
                            (calc thn)
                            (calc els)))))
  • Provide 3 examples of hypothetical changes to the host semantics that would affect the runtime behavior of if programs. There is no need to provide a new interpreter; you can describe your proposed changes in words. You are not required to preserve the original behavior of the interpreter (in fact, after changing the host semantics, your interpreter should do something different than before). The goal of this problem is to explore how the host semantics can affect what your interpreter does, and how changes to the host affect the interpreter. There are many valid answers, and your answers can be short; it is a conceptual question.

Problem 1c

Consider the following small program that uses cond:

#lang plait 

(define-type Pokemon
  (pre-evo (name : String) (evo : Pokemon))
  (final-evo (name : String)))

(define (evolve p)
  (cond 
    [(pre-evo? p) 
      (let ([next (pre-evo-evo p)])
        (cond 
          [(pre-evo? next) (pre-evo-name next)]
          [(final-evo? next) (final-evo-name next)]))]
    [(final-evo? p) 
      (error 'evolve (string-append (final-evo-name p) " cannot evolve!"))]))

Which has this behavior:

> (evolve (pre-evo "Pikachu" (final-evo "Raichu")))
- String
"Raichu"

Write an equivalent program that uses type-case instead of cond.

Problem 1d

Consider the following lambda terms:

image

Evaluate the following:

  • (succ z)
  • (succ (succ z))

(Ungraded) What do you think the pattern is?

Problem 2: Fix the code [25 Points]

Consider the following code. The function (has-pre-evo pkmn dex) looks for a Pokemon that evolves into pkmn in the Pokedex (list of Pokemon) dex.

(define-type-alias Pokedex (Listof Pokemon))

(define (has-pre-evo pkmn dex)
  (type-case Pokedex dex 
    [empty (error 'NoPkmn "dex is empty!!")]
    [(cons p l) (if (equal? (pre-evo-evo p) pkmn) p (has-pre-evo pkmn l))]))

What is wrong with this code? Briefly explain.

In code.rkt, fix has-pre-evo so that it is correct.

Problem 3: From parsing and back [50 Points]

Consider the data structure for a binary tree, as we’ve seen in Assignment 2.

(define-type Tree
  (leaf [val : Number])
  (node [val : Number]
        [left : Tree]
        [right : Tree]))

Problem 3a. Write a parser tree-parse of type S-Exp -> Tree that takes in an s-expression and outputs a binary tree data structure. You can assume that the s-expression is well-formed – that is, it follows the structure seen in the test cases. You are only allowed to use the following helper functions:

  • s-exp->number and s-exp->list, which takes an s-expression symbol and turns it into a number or list, if possible,
  • s-exp-number?, s-exp-list?, and
  • first, second, and third, which takes the first, second, and third elements of a list respectively.

Here are some test cases:

> (tree-parse `2)
- Tree
(leaf 2)

> (tree-parse `(2 (1 2 3) 3))
- Tree
(node 2 (node 1 (leaf 2) (leaf 3)) (leaf 3))

Problem 3b. Write a program pretty-print-tree that takes in a binary tree data structure and prints an s-expression. You must use type-case. You are only allowed to use the following helper functions:

  • number->s-exp and list->s-exp.

Here are some test cases:

> (pretty-print-tree (leaf 2))
- S-Exp
`2

> (pretty-print-tree (node 2 (node 1 (leaf 2) (leaf 3)) (leaf 45)))
- S-Exp
`(2 (1 2 3) 45)

Problem 3c. Define S-expressions my-sexp-1, my-sexp-2, my-sexp-3 such that the test

(test (pretty-print-tree (tree-parse x)) x)

passes when x is substituted for my-sexp-1, my-sexp-2, or my-sexp-3. Dually, define Trees my-tree-1, my-tree-2, my-tree-3 such that the test

(test (tree-parse (pretty-print-tree x)) x)

passes when x is substituted for my-tree-1, my-tree-2, or my-tree-3.

Are there test cases you can come up with that violate the above two test criteria? Why or why not? Briefly explain by referencing your code.