ITEC 380 2015fall ibarland

home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)

hw07
Interpreting Q
project

The full Q1,Q2 (both racket and Java for Q1, plus any add'l tests) due Nov.30 (Mon) 14:00. It is strongly recommended to complete this before Thanksgiving break, so you can either not worry about it, or (if you really want to put in some hours over the break) get a head-start on hw08.
However, these test cases are due Nov.20 (Fri) 14:00.

Over the course of several homeworks, we'll implement a “tower” of languages (Q0, Q1, …, Q6) each language incorporating more features than the previous. Q0 is provided for you.

• For each language, you must implement three methods:
  • parse, which turns source-code into an internal representation,
  • toString which turns internal representation back into source-code,
  and
  • eval, which actually interprets the program, returning a value (a number for Q0-Q2, and a number-or-function in Q3).
  I recommend implementing and testing the methods in this order. See the provided test-cases, for examples. There might be other helper functions to implement as well.
• Your solution may be in Java or in Racket (or see me, if you want to use a different language). (The exception is Q1, which you must implement in both Racket and Java.)
• You do not need to worry about error-checking — we will only concern ourselves with syntactically correct Qi programs.
  (As a matter of defensive programming, you might still want to add some assertions/sanity-checks in your code.)
• Use the Desire2Learn discussion board for group questions and answers.
• This project is based on the first chapters of Programming Languages and Interpretation, by Shriram Krishnamurthi. As a result, this homework assignment is covered by the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License. Although we're using a different dialect of scheme/racket than that book, you might find it helpful to skim it.

1. (15pts) Implement Q1 in both racket, and Java. Q1 is just like Q0, but with two additional types of expressions:

   Expr ::= … | IfZeroExpr IfZeroExpr ::= if Expr is zero then Expr else Expr @ BinOp ::= … | mod

   Update parse, toString (a.k.a. expr->string), and eval appropriately, for both the racket and Java implementations. Be sure to write test cases first.

   The only method which cares what these new expressions mean (their semantics) is eval:

   • For the expression (x mod y), eval should evaluate to¹ x mod y, where the result is always between 0 (inclusive) and y (exclusive); in particular, the result should never be positive if y<0. Notice that this is slightly different behavior than either Java's built-in % (which behaves differently on negative numbers), and from Racket's built-in modulo (which only accepts integers). In both racket and Java, you can calculate this as y*(x/y-floor(x/y)).

     Note that you are provided sufficient test cases for modExprs, in the comments of the Q0 test-case files.

   • For if Expr₀ is zero then Expr₁ else Expr₂@, your eval should first evaluate just Expr₀; if that value is positivezero, then evaluate Expr₁ and return its value; otherwise evaluates Expr₂ and return that value. (Note how you are implementing short-circuit semantics for IfZeroExpr!)

     You must make your own test cases for IfZeroExprs; include at least two as-simple-as-possible tests, and two tests with more deeply nested Exprs. I suggest includine one where the IfZeroExpr is not the top-level comment (e.g., a add expression which contains a if … is zero as one of its operands).

   Complete two versions of Q1: both racket, and java. (For Q2 and beyond, you can choose which implementation to continue.)

2. (25pts) Implement Q2 in either racket or Java (your choice). Q2 adds identifiers to Q1:

   Expr ::= … | Id | LetExpr LetExpr ::= say Id be Expr in Expr matey // Subject to votes in class, for exact syntax.2

   where Id can be any series of letters and digits which isn't interpretable as a number³. (Assume for now that any nested let expressions use different Ids. We'll handle shadowing in Q3, later.)

   Update your three methods parse, toString (a.k.a. expr->string), eval.

   In order to write eval, we need to define the semantics of say Id be E₀ in E₁ matey:

   • Evaluate E₀; let's call the result v₀.
   • Then, substitute v₀ for all occurrences of Id inside the tree E₁; name the result of the substitution E′.
     (Note: you must do substitution in the parse tree; no credit given for string-substitution ⁵.)
   • Evaluate E′, and return that result.

   Observe that when evaluating a (legal) Q2 program, eval will never actually encounter an Id -- that Id will have been substituted out before we ever recur down to it.

   In order to make a substitution in an Expr parse-tree, write a helper function that does only substituting (and does not do any evaluating in any way). This task would be similar to taking an Ancestor-tree, and replacing every blue-eyed Child with a brown-eyed one. (The only difference is that an AncTree had only two cond-branches, while Expr has around seven, though the code for most of those are very similar.)

   For example: say x be 5 in (x add 3) matey ⇒ (5 add 3) ⇒ 8⁶. Be sure to write test cases for your substitution function before you write its code; include several trivial and easy tests, along with a couple of more complicated nestings and one deeply nested expression.

   You can choose implement Q2 in either in Racket, or in Java.

   ---

   Repeating the steps above in more words: For Q2, you will:

   • add Ids to your data-definition (after deciding what data-type will represent them); then:
     • update expr->string (or, Expr.toString) to handle this new type of expression (after test cases)
     • update string->expr (or, Expr.parse) to handle this new type of expression (after test cases)
     • update eval (or, Expr.eval) to handle this new type of expression As we said in class, eval'ing just an identifier causes an error. I recommend actually adding a case for eval that throws your own error (with an appropriate error-message), but it's okay to just leave this off [which will also cause an error, but it'll be an error about your code, rather than an error suited for the Q2 programmer].
   • Next, add LetExprs to your data-definition (after deciding what data-type will represent them); then:
     • update expr->string (or, Expr.toString) to handle this new type of expression (after test cases)
     • update string->expr (or, Expr.parse) to handle this new type of expression (after test cases)
     • update eval to handle this new type of expression.
       Oh right; for this one, after reading the hw we realize that eval will need to do substitution in a tree, and that's a smaller, simpler, self-contained task — perfect for its own helper-function substitute:
     • Go and write substitute (after test cases for it), before updating eval for LetExprs. (And when starting substitute, start from the template for Exprs.) For the test cases, think about exactly types you'll be wanting to sent to substitute.

  eval(parse("say x be 5 in (x add 3) matey"))
= eval(parse("(5 add 3)"))
= eval(parse("8"))

home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)

©2015, Ian Barland, Radford University Last modified 2015.Dec.05 (Sat)

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu