home—lectures—recipe—exams—hws—D2L—breeze (snow day)
hw06
Interpreting O
project
These test cases are due Nov.11 (Mon) 23:59.
The full O1,O2 (both racket and Java, plus any add'l tests) due Nov.13 (Wed) 23:59.
Over the course of several homeworks,
we'll implement a “tower” of languages (O0, O1, …, O6)
each language incorporating more features than the previous.
O0 is provided for you.
You'll implement O1 in both Racket and Java;
after that you choose which of the two languages you'll use
to complete O2, …, O6.
-
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 O0-O2, and a number-or-function in O3).
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 O1, which you must implement in both Racket and Java.)
-
You do not need to worry about error-checking --
we will only concern ourselves with syntactic O0 (etc.) 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.
The language O0
Expr ::= Num | ParenExpr | BinExpr | Is0Expr
ParenExpr ::= ( Expr )
BinExpr ::= ( Expr BinOp Expr )
Is0Expr ::= if Expr is0 then Expr else Expr ;
BinOp ::= add | sub | mul
|
where
Num is any numeric literal
(as written in either Java or Racket, your choice1)
and
Var is string with no whitespace
or punctuation (parentheses, “;”)
and is not otherwise a reserved word in O0
(i.e. a terminal in the above grammar -- “if”,
“plus”,
“is0”,
etc.).
Whitespace is required between all terminals/non-terminals,
with the exception of punctuation.
Here is
a Racket interpreter for O0
along with
helper functions for
a scanner for racket
and
an optional test harness.
Here is
a java interpreter for O0
(O0-java.jar or browse);
it includes unit tests,
and
helpful Java parsing functions.
(15pts) Implement O1 in both racket, and Java.
O1 is just like O0, but with two additional
types of expressions:
Expr ::= … | IsNegExpr
IsNegExpr ::= if Expr isNeg 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:
if Expr0 isNeg then Expr1 else Expr2;
first evaluates just Expr0;
if that value is negative, then it evaluates Expr1
and returns its value;
otherwise it evaluates Expr2 and returns its value.
(Note how you are implementing short-circuit semantics for isNegExpr!)
(a mod b) should evaluate to2
a mod b,
where the result is always between 0 (inclusive) and b (exclusive);
in particular, the result is never positive if b<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 Java, you can use
a%b (if b>0
a and b have the same sign3 or a%b=0),
and
a%b+b (otherwise).
In racket or Java, you can use
b*(a/b-floor(a/b)).
Note that you are provided sufficient test cases for modExprs,
except that you have to translate it proper O0.
You must make your own test cases for ifNegExprs;
include at least two as-simple-as-possible tests, and two tests with more deeply nested
Exprs.
Complete two versions of O1: both racket, and java.
(For O2 and beyond, you can choose which implementation to continue.)
-
(25pts) Implement O2 in either racket, and Java (your choice).
O2 adds identifiers to O1:
Expr ::= … | Id | LetExpr
LetExpr ::= let Id := Expr in Expr end; // orange updates are as chosen Monday, as a class.4
|
where Id can be
any series of letters and digits which isn't interpretable as a number5.
(Assume for now that any nested let
expressions
use different Ids.
We'll handle that possibility in O3, later.)
Update your three methods
parse,
toString (a.k.a. expr->string),
eval.
We now need to define the semantics of
let Id := (E0) in E1 end;:
-
Evaluate E0,
calling the result v0.
-
Then, substitute
v0
for
all occurrences
of
Id
inside
the tree E1;
name the result of the substitution
E′.
(Note: you must do substitution in the parse tree;
no credit given for string-substitution
7.)
-
Evaluate E′,
and return that result.
Observe that when evaluating a (legal) O2 program,
eval will never actually encounter an Id --
that Id will have been substituted out before
we ever recur down to it.
The code to make a substitution in an Expr
parse-tree
is 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:
let x = 5 in (x plus 3) ⇒ (5 plus 3) ⇒ 88.
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 O2 in either in Racket, or in Java.
In future homeworks, we will add
shadowing variables (O3),
functions and function-application (O4),
allow recursion and mutation (O5, O6).
1
This is so we can just use our language's built-in number-parsing functions,
without getting bogged down in tokening input.
So racket implementations will allow exactly those strings recognized by number?,
(including +nan.0, -inf.0, and 2+3i).
Similarly,
if using Java,
the semantics of O0's arithmetic will be similar
to IEEE floating point arithmetic
(rather than perfectly-correct arithmetic).
Don't confuse O0's class Num (which extends Expr)
with the
existing java.lang.Number, which doesn't extend Expr.
↩2
Because we don't need to check for bad inputs,
it's fine to have your interpreter crash if b=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.
↩
3See java.lang.Math#signum. ↩
4
In class on Monday, we will choose one of the following or (most likely) a variant, as a class:
| 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; } |
Note that you can (and should) test and write a “substitute” function w/o
worrying about the exact syntax of a LetExpr.
Substituing one thing in a tree for another is its own independent task,
de-coupled from eval'ing a local-binding statement.
↩5
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 O1 is that
implementing an intepreter for O1 doesn't get bogged down in minutae when using
either Java or Racket.
↩
7
For example: what if a O2 programmer uses a variable
named “mod”
or “let”
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.
↩
6
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 O3,
and is in general
fraught with error7.
A local-variable construct which requires
globally-unique names isn't very impressive!
↩
8
The notation
“let x = 5 in (x plus 3);
⇒ 5 plus 3 ⇒ 8”
is shorthand for
eval(parse("let x = 5 in (x plus 3);"))
= eval(parse("(5 plus 3)"))
= eval(parse("8"))
|
Observe how we definitely don't write
“"let x = 5 in (x plus 3)" = "(5 plus 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)
radford.edu