CS 4536 Homework 2: Extended Basic Interpreter

Due: Thursday Jan 24, 11:59pm via turnin (assignment name hwk2)
Collaboration Policy: Solo

Write a parser and interpreter for the FWAE language (discussed in class), with eager semantics and deferred substitutions, extended with the following two language features.

  1. Conditionals

    To save the trouble of having to add boolean values and operators over them, create the construct if0 using the syntax described by the grammar below. Note that if0 has three parts:

    Evaluation should signal an error for non-numeric test values.

  2. Multi-argument fun

    Extend the fun language feature described in lecture so that functions can accept a list of zero or more arguments instead of just one. All arguments to the function must evaluate with the same deferred substitutions. To simplify your program, you may assume that the number of arguments in a function invocation always matches the number in the procedure definition. For example:

    {{fun {x y} {* x y}} 2 3}

    evaluates to 6. Specifically, this means that you do not need, nor will we try, test cases that violate this assumption.

    The following grammar gives the concrete syntax of the resulting language, CFWAE: 

    <CFWAE> ::= <num>
          | {+ <CFWAE> <CFWAE>}
          | {- <CFWAE> <CFWAE>}
          | {* <CFWAE> <CFWAE>}
          | {/ <CFWAE> <CFWAE>}
          | <id>
          | {if0 <CFWAE> <CFWAE> <CFWAE>}
          | {with {{<id> <CFWAE>} ...} <CFWAE>}
          | {fun {<id> ...} <CFWAE>}
          | {<CFWAE> <CFWAE> ...}
where an id is not +, -, *, /, with, if0, or fun.

    In this grammar, the ellipsis (...) means that the previous non-terminal is present zero or more times.

    Your solution should define at least the following two functions: (1) parse, which consumes an expression in the language's concrete syntax and returns the abstract syntax representation of that expression, and (2) interp, which consumes an abstract syntax expression (as returned by the parse function) and returns a CFWAE-value. Include a contract for every function that you write and test cases that amply exercise all of your code. Use PLAI-Pretty big as the language level for this assignment.

    For full points, your parser should rewrite with expressions as combinations of app and fun. Get your code working without this optimization first, then address this if you have time.

    Use the following define-types and function headers in your code. {Note: once you rewrite with into app and fun you will not use the Binding type or the with clause of CFWAE. You may eliminate these from your code file once you no longer need them.)

    (define-type Binding
  [binding (name symbol?) (named-expr CFWAE?)])

(define-type CFWAE
  [num (n number?)]
  [binop (op procedure?) (lhs CFWAE?) (rhs CFWAE?)]
  [with (lob (listof Binding?)) (body CFWAE?)]
  [id (name symbol?)]
  [if0 (c CFWAE?) (t CFWAE?) (e CFWAE?)]
  [fun (params (listof symbol?)) (body CFWAE?)]
  [app (f CFWAE?) (args (listof CFWAE?))])

(define-type Env
  [mtEnv]
  [anEnv (name symbol?) (value CFWAE-Value?) (env Env?)])

(define-type CFWAE-Value
  [numV (n number?)]
  [closureV (params (listof symbol?))
            (body CFWAE?)
            (env Env?)])

;; parse : expression -> CFWAE
;; This procedure parses an expression into a CFWAE
(define (parse sexp)
  ...)

;; interp : CFWAE -> CFWAE-Value
;; This procedure interprets the given CFWAE and produces a result
;; in the form of a CFWAE-Value (either a closureV or a numV)
(define (interp expr)
  ...)

    Standard error messages:

    Jousting

    For test-jousting, submit tests for the parse and interp functions only, not any internal functions that you wrote.

    Given that some people will be rewriting with and others won't, please don't upload any parse tests on with for this assignment. By all means, upload tests of the form (interp (parse '(with ...))), as those won't depend on which concrete syntax you used for with expressions.

    What to Turn In

    Turn in two files: one containing your parser, interpreter and tests of helper functions, and another containing your parse and interp tests. We will run the second file against everyone else's first file during grading. Code that does not run against our test suite will not be graded!! This should be a good incentive to run your code through the jousting server at least once before submitting.

    You must submit your final files via turnin. We will not take your tests or code from the jousting server.

    FAQ