ITEC 380 2020spring ibarland

home—lectures—recipe—exams—hws—D2L—zoom (snow day)

Expr Trees
eval/parse W basics; adding identifiers

Due . 2020-Apr-18 (Sat.) 23:59
In addition, due Apr-16 (Thu) by the start of class: complete some initial W2 tests (and soln)

Note that W1 is “add code that is extremely similar to what already exists”, but W2 is not at all rote: it requires a solid understanding of the parse-tree representation and how the functions work.

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

1. Download & get the provided W0 running.
2. Each time we add new syntax to our language, we must update three methods:
   • parse!, which turns source-code into an internal representation,
   • expr->string which turns internal representation back into source-code,
   and
   • eval, which actually interprets the program, returning a value (a number for W0-W2, and a number-or-function in W3).
   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.
3. Your solution may be in Java or in Racket (or see me, if you want to use a different language). (The exception is W1, which you must implement in both Racket and Java.)
4. You do not need to worry about error-checking the programs we process — we will only concern ourselves with syntactically correct Vi programs.
   (As a matter of defensive programming, you might still want to add some assertions/sanity-checks in your code.)
5. Use the D2L discussion board for group questions and answers.
6. This project is based, in part, 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.

Deliverables:

• If adding to an existing file, add a comment “>>> W1” or “>>> W2” next to the area you are changing; when grading I will search for “>>>”. This helps me immensely, thanks.
• For the D2L dropbox, please submit all files individually (no .zip/.jar). I should be able to download your files and run your code from the download-directory. Thus, you should D2L-submit any necessary helper files like scanner.rkt and UtilIan.java.
• Since W2 subsumes W1, you only need to submit W1 in one language, and W2 in the other.
• Please use the exact filenames W2.rkt, W2-tests.rkt, and W1-java/*.java. or W1.rkt and W1-tests.rkt, and W2-java/*.java if you chose Java for W2. .

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

   Op ::= … | fish-paste Interpretation: “remainder”; see A.iii for details Expr ::= … | IfOdd IfOdd ::= ahoy Expr me Expr money Expr Interpretation: if 1st Expr evals to an odd number, result is the 2nd Expr, else the 3rd

   Be sure to write test cases first; To ensure everybody makes test cases to cover the basics, I've spelled out these strongly-suggested W2: initial tests.
   1. Add the fish-paste operator.
      1. update parse! (Java: Expr.parse) to handle this new operator (after writing test cases).
         (Or, if you don't need to update this function, understand why.)
      2. update expr->string (Java: Expr.toString) to handle this new operator (after writing test cases).
         (Or, if you don't need to update this function, understand why.)

      3. update eval to handle this new type of operator. The semantics of #x fish-paste y} is:

         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 - ⌊x/y⌋), where ⌊r⌋ means the the floor of r.

         Note that you are already provided sufficient test cases for fish-pastes, in the comments of the W0 test-case files.

   2. Add the IfOdd expression.
      1. update parse! (Java: Expr.parse) to handle this new type of expression (after writing test cases).
      2. update expr->string (Java: Expr.toString) to handle this new type of expression (after writing test cases).

      3. update eval to handle this new type of expression. The semantics of ahoy Expr₀ me Expr₁ money Expr₂ is:

         first evaluate just Expr₀ to get value v₀; if v₀ is an integer and is odd, then evaluate Expr₁ and return its value; otherwise evaluate Expr₂ and return that value.

         For example, ahoy 3.1 me 7.5 money 44 would evaluate to 44.
         (Note how you are implementing short-circuit semantics for IfOdds!)

         You must make your own test cases for IfOdds; include at least two as-simple-as-possible tests, and two tests with more deeply nested Exprs. I suggest including one where the IfOdd is not the top-level comment (e.g., a order-up expression which contains a IfOdd as one of its operands).

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

   Expr ::= … | Id | LetExpr LetExpr ::= sweet Id mother of Expr pearl Expr2

   where Id can be pretty much any string: it can be any token returned by our scanner that isn't already a reserved-token/punctuation. This simplistic³ definition lets us keep our code easy: if we get a token (via peek/UtilIan#hasNextSplittingBy), and it's not the start of any other expression, then it's an identifier! (Assume for now that any nested letExpr expressions will use different Ids. We'll handle shadowing in W3, later.)

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

   1. add Ids to your data-definition (after deciding what data-type will represent them); then:
      1. update expr->string (or, Expr.toString) to handle this new type of expression (after test cases)
      2. update parse! (or, Expr.parse) to handle this new type of expression (after test cases)
      3. update eval (or, Expr.eval) to handle this new type of expression:

         eval'ing an identifier simply throws an error.

         You don't need test cases for evaling Ids. Though if you want to be spiffy, you can use check-error in racket, or assertThrows in JUnit5. In JUnit4, the hack-ish approach is to put “ExpectedException.none().expect(RunTimeException.class)” on the line before the one that should trigger an error.

   2. Next, add LetExprs to your data-definition (after deciding what data-type will represent them); then:
      1. update expr->string (or, Expr.toString) to handle this new type of expression (after test cases)
      2. update parse! (or, Expr.parse) to handle this new type of expression (after test cases)
      3. Think about how to update eval to handle this new type of expression. Now we get to the heart of the issue! Write test cases, after reading the rest of this bullet.

         In order to write eval, we need to define the semantics of sweet Id mother of E₀ pearl E₁:

         • 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′.
         • Evaluate E′, and return that result.

         For example: sweet x mother of 5 pearl #x ah-shrimp 3} ⇒ #5 ah-shrimp 53} ⇒ 2⁴. 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.

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

      4. Now that 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. This function only does substition in a tree, and does not attempt to do any evaluating.
         Go and write substitute (after test cases for it), before implementing 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. Your simplest test-cases won't even contain a LetExpr — substitute is a function whose purpose-statement stands on its own, entirely independent of LetExprs and eval!

         Hint: Substituting a variable with a value in an syntax-tree is essentially the same as replacing every occurrence of one name with another in an anc-tree. (The only difference is that an anc-tree had only two cond-branches, while Expr has around five, though the code for most of those are very similar.)

         (Note: you must do substitution in the parse tree; no credit given for string-substitution ⁶.)

      5. Finally, with the substitute helper written, we're ready: write eval for LetExprs.

         Hint: Your code will correspond almost word-for-word to the semantics given above.

  eval(parse!("sweet x mother of 5 pearl #x ah-shrimp 3}"))
= eval(parse!("#5 ah-shrimp 3}"))
= eval(parse!("2"))
          

home—lectures—recipe—exams—hws—D2L—zoom (snow day)

This page licensed CC-BY 4.0 Ian Barland Page last generated

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