RU beehive logo ITEC dept promo banner
ITEC 380
2016fall
ibarland

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

hw07
Interpreting R
project

Due 2016-Nov-18 15:00 I strongly recommended downloading R0 and getting it running, and then completing the required test cases, by Nov-14 (Mon).

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

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

    Expr ::= … | IfZeroExpr
IfZeroExpr ::= [:0 Expr Expr Expr 0:]

Op ::= … | ;%     (“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; To ensure everybody makes test cases to cover the basics, I've spelled out these R2-test-requirements—R2: initial tests.

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

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

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

    Expr ::= … | Id | LetExpr

LetExpr ::= :o Id Expr :U 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 R3, 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 :o Id E0 :U E1:

    Observe that when evaluating a (legal) R2 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: :o x 5 :U |x 3 ;)| ⇒ |5 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 R2 in either in Racket, or in Java.

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

1 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.      ↩

2 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). Or, if we want to include emoji keywords, good candidates are the entries on this page which have the left-most column “native” filled in.

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.

     ↩

3 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 P is that implementing an intepreter for P doesn't get bogged down in minutae when using either Java or Racket.      ↩

5 For example: what if a R2 programmer uses a variable named “mod” or “say” or “fun” [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.      ↩

4 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 R3, and is in general fraught with error. A local-variable construct which requires globally-unique names isn't very impressive!      ↩

6 The notation “:o x 5 :U |x 3 ;)| ⇒ |5 3 ;)| ⇒ 8” is shorthand for 

  eval(parse!(":o x 5 :U |x 3 ;)|"))
= eval(parse!("|5 3 ;) |"))
= eval(parse!("8"))
Observe how we definitely don't write “":o x 5 :U |x 3 ;) |" = "|5 3 ;) |" = 8” since the two strings are not .equals(·) to each other, and strings are never ints. More specifically: we distinguish between “⇒” (“code evaluates to”) and “=” (“equals”, just as “=” has meant since kindergarten).      ↩

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

©2016, Ian Barland, Radford University
Last modified 2016.Nov.22 (Tue)		 Please mail any suggestions
(incl. typos, broken links)
to ibarlandradford.edu		 Rendered by Racket.