ITEC380 AncTrees and Expr Trees

AncTrees and Expr Trees
eval/parse U basics; adding identifiers

Due 2019-Apr-19 (Fri.) 23:59 5% for completing by this deadline; still accepted through Apr-20 (Sat.) 23:59
I strongly recommended downloading the provided U0 and getting it running, and then completing the suggested test cases, by Apr-16 (Tue), and having U1 and U2's Identifiers, substitute completed by class on Apr-18 (Thu).
Note that U1 is “add code that is extremely similar to what already exists”, but U2 isn't at all rote: it requires a solid understanding of what the parse-tree representation and how the functions work.

(5pts) Write the function count-name, which takes in an AncTree (as in lecture) and a string, and returns how many times that name occurs as a name in the anc-tree. For this problem and the next: Do not try to make this tail-recursive, or use an accumulator variable. A linear loop fundamentally can't process a branching tree ¹!

(5pts) Write a function that takes in an anc-tree, and returns a similar anc-tree where eye-colors might be changed: In particular, brown eyes have been changed to green, except that if you reach an ancestors with red eyes then don’t change the eye-colors of them or their ancestors. Call your function brown->green/stop-at-red³.

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

Download & get the provided U0 running.

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,
eval, which actually interprets the program, returning a value (a number for U0-U2, and a number-or-function in U3).

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 U1, which you must implement in both Racket and Java.)

You do not need to worry about error-checking the programs we process — we will only concern ourselves with syntactically correct Ti programs.
(As a matter of defensive programming, you might still want to add some assertions/sanity-checks in your code.)

Use the D2L 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.

Deliverables:

If adding to an existing file, add a comment “>>> U1” or “>>> U2” 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 helper files like scanner.rkt and UtilIan.java.

Since U2 subsumes U1, you only need to submit U1 in one language, and U2 in the other. (For example, U2.rkt and U1-java/*.java; or, U1.rkt and U2-java/*.java.)

For the hardcopy, you need only print out those files that changed, and even (if you want) only the parts of the files that changed (w/ a brief indication of which function the changed-code is from). This is quick, since you tagged your changes with “>>>”.

Hardcopy, as always, is due at the first class after the due-date (or, at the due-date).

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

Op ::= … | rmd     Interpretation: “remainder”

Expr ::= … | IfEven
IfEven ::= iph Expr evn Expr thn Expr els Expr hpi    Interpretation: “if-even”

Be sure to write test cases first; To ensure everybody makes test cases to cover the basics, I've spelled out these strongly-suggested U2: initial tests.

Add the rmd 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 rmd 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 rmds, in the comments of the U0 test-case files.
Add the IfEven 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 iph Expr₀ evn thn Expr₁ els Expr₂ hpi ~~abs Expr₀ unit? Expr₁ dope Expr₂ nope Expr₃ dawg~~ is:
  first evaluate just Expr₀; if it is even, then evaluate Expr₁ and return its value; otherwise evaluate Expr₂ and return that value.
  For example, iph 5 evn thn -7.5 els -8.5 hpi would evaluate to -8.5. A non-integer is not considered even, of course. (Note how you are implementing short-circuit semantics for IfEvens!)
  
  You must make your own test cases for IfEvens; include at least two as-simple-as-possible tests, and two tests with more deeply nested Exprs. I suggest including one where the ~~Ifgt~~IfEven is not the top-level comment (e.g., a sbt expression which contains a IfEven as one of its operands).

(25pts) Implement U2 in either racket or Java (your choice).
U2 adds identifiers to U1:

Expr ::= … | Id | LetExpr

LetExpr ::= let Id get Expr for Expr⁵

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

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

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.
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 let Id get E₀ for 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.
  (Note: you must do substitution in the parse tree; no credit given for string-substitution ⁸.)
  
  For example: let x get 5 for [x sbt 3] ⇒ [5 sbt 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.
  
  Observe that when evaluating a (legal) U2 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.)
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.

¹ You might make code that looks like it's a loop, and uses a stack or queue—but that just moves the space-usage from pending-recursive-stack-calls to your own data-structure. ↩

³ Well, more seriously: we’ll do an equivalent tree-traversal in the future, when working with parse-trees for a programming-language:
we’ll want to re-name all occurrences of a variable x, but if we come across a new variable-declaration named x, that’s making a new, different variable — so don’t change that x, nor any x in sub-trees of that declaration. We say that the newly-declared x is shadowing the original x being re-named. ↩

² People sometimes wonder what possible use-case such a function could have. Well: Sometimes you want to doctor an ancestor-tree, to make yourself appear to be irish. But if you have an ancestor who cried so much that their eyes were red — probably on hearing how you seem to be ashamed of your heritage — we won’t modify their ancestors out of respect.³ ↩

⁴ Because we don't need to check for bad inputs, it's fine to have your interpreter crash if y=0. If you prefer to "control" crash — creating a meaningful error message and calling error or throw yourself — you are also welcome to do that. ↩

⁵ For comparison, here is what comparable constructs look like in other languages:

ML-like:	let x = 2+3 in x*9 end;
lisp-like:	(let {[x (+ 2 3)]} (* x 9))
lisp-like, simplified:	(let x (+ 2 3) (* x 9))
C#-like:	using (var x = 2+3) { return x*9; }
javascript-like:	var x = 2+3; return x*9;
Java-like:	{ int x = 2+3; return x*9; }
Haskell-like:	* x 9 \n where x = + 2 3 \n

Another option for the assignment-character is “:=” (Ada,Pascal), or “←” (indicating which way the data flows), or even something like “Expr → Id { … }” (which might make CS1 students happier — the processing happens left-to-right, just like we read the statement).

Note that you can (and should) test and write a “substitute” function w/o worrying about the exact syntax of a LetExpr. Substituting one thing in a tree for another is its own independent task, de-coupled from eval’ing a local-binding statement.

↩

⁶ Note that our different implementations are now varying by more than just precision of arithmetic: in a Java implementation, NaN is a Num, and in a racket implementation it's an Id. We won't use any test cases involving such subtle differences. However, note how our choices in designing a new language are being influenced by the language we're trying to easily implement it in! This stems from the fact that a primary design constraint on U2 is that implementing an intepreter for U2 doesn't get bogged down in minutae when using either Java or Racket. ↩

⁸ For example: what if a U2 programmer uses a variable named “add” or “iph” or “let” [which we might make into a keyword in the future]? While it's not advisable for somebody to do this, and perhaps our parse should disallow this, our eval shouldn't give wacky results in this situation. ↩

⁷ All our real code should work on the parse tree itself. String-substitution (like C pre-processor macros) can't be generalized to handle shadowed variables (scope) for U3, and is in general fraught with error ⁸. A local-variable construct which requires globally-unique names isn't very impressive! ↩

⁹ The notation “let x get 5 for [x sbt 3] ⇒ [5 sbt 3] ⇒ 8” is shorthand for

  eval(parse!("let x get 5 for [x sbt 3]"))
= eval(parse!("[5 sbt 3]"))
= eval(parse!("8"))

Observe how we definitely don't write “"let x get 5 for [x sbt 3]" = "[5 sbt 3]" = 8” since the two strings are not .equals(·) to each other, and strings are never equal to ints. More specifically: we distinguish between “⇒” (“code evaluates to”) and “=” (“equals”, just as “=” has meant since kindergarten). ↩

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

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

AncTrees and Expr Trees eval/parse U basics; adding identifiers

AncTrees and Expr Trees
eval/parse U basics; adding identifiers