home—lectures—recipe—exams—hws—D2L—breeze (snow day)
Interpreting T
eval/parse basics; adding identifiers (v.2)
Deliverables:
-
If adding to an existing file,
add a comment “>>> T1” or “>>> T2”
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 T2 subsumes T1, you only need to submit T1 in one language, and T2 in the other.
(For example, T2.rkt and T1-java/*.java; or, T1.rkt and T2-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).
Due 2018-Nov-30 (Fri.) noon23:59
I strongly recommended
downloading the provided T0 and getting it running,
and then completing the
suggested test cases,
by Nov-26 (Mon),
and having T1 and part of T2 completed by class on Nov.28.
Note that T1 is “add code that is extremely similar to what already exists”,
but T2 isn't at all rote: it
requires a solid understanding of what the parse-tree representation
and how the functions work.
Over the course of several homeworks,
we'll implement a “tower” of languages (T0, T1, …, T6)
each language incorporating more features than the previous.
T0 is provided for you.
-
Download & get the provided T0 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,
and
-
eval, which actually interprets the program,
returning a value (a number for T0-T2, and a number-or-function in T3).
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 T1, 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.
(15pts) Implement T1 in racket and in Java, both.
T1 is just like T0, but with two additional
types of expressions:
Op ::= … | bae Interpretation: “mod”
Expr ::= … | IfGT
IfGT ::= abs Expr unit? Expr dope Expr nope Expr dawg Interpretation: “if-greater-than”
|
Be sure to write test cases first;
To ensure everybody makes test cases to cover the basics,
I've spelled out these strongly-suggested T2: initial tests.
-
Add the bae operator.
- 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.)
- 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.)
update eval to handle this new type of operator.
The semantics of #x bae 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 provided sufficient test cases for baes,
in the comments of the T0 test-case files.
-
Add the IfGT expression.
- update parse! (Java: Expr.parse) to handle this new type of expression (after writing test cases).
- update expr->string (Java: Expr.toString) to handle this
new type of expression (after writing test cases).
update eval to handle this new type of expression.
The semantics of
abs Expr0 unit? Expr1 dope Expr2 nope Expr3 dawg
is:
first evaluate just Expr0
and
Expr1;
if the first result is greater than the second,
then evaluate Expr2
and return its value;
otherwise evaluate Expr3 and return that value.
(Note how you are implementing short-circuit semantics for ifgt!)
You must make your own test cases for IfGTs;
include at least two as-simple-as-possible tests, and two tests with more deeply nested
Exprs.
I suggest including one where the
Ifgt is not the top-level comment
(e.g., a boii expression which contains a IfGT
as one of its operands).
-
(25pts) Implement T2 in either racket or Java (your choice).
T2 adds identifiers to T1:
Expr ::= … | Id | LetExpr
LetExpr ::= so Id be all Expr in 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 T3, 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:
- update expr->string (or, Expr.toString) to handle this new type of expression (after test cases)
- update parse! (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:
eval'ing just an identifier simply throws an error.
You don't 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:
- update expr->string (or, Expr.toString) to handle this new type of expression (after test cases)
- update parse! (or, Expr.parse) to handle this new type of expression (after test cases)
- 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
so Id be all E0 in E1:
-
Evaluate E0;
let's call the result v0.
-
Then,
substitute
v0
for
all occurrences
of
Id
inside
the tree E1;
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:
so x be all 5 in #x boii 3# ⇒ #5 boii 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) T2 program,
eval will never actually encounter an Id --
that Id will have been substituted out before
we ever recur down to it.
-
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.)
-
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.
home—lectures—recipe—exams—hws—D2L—breeze (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 |
|