]>
In this exercise, you are asked to familiarize yourself with Scala by implementing an evaluator for arithmetic expressions. The grammar of expressions is repeated here (production E). An expression is sometimes also called term. Some terms are called values(prod. V) and of these, some are numeric values (prod. NV).
|
|
An evaluation means reducing terms until they are no longer reducible. If all goes well, the result is a value. If it is not a value, then evalation is stuck. The behaviour of an evaluator can be described concisely by writing deduction rules of the form
pre1 ... preN |
conc |
Such a rule says, that if all premises hold, than the conclusion holds. If there is just a conclusion and no premises, then the line is omitted. Here, we are interested in the reduction relation →. It is a binary relation on terms, where "a → b" says than we can reduce a to b.
The reduction relation for arithmetic expressions was given in the course . Let's repeat them here:
Computation | Congruence | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
The meta variables E, E', E1, E2, NV
stand for arbitrary terms generated by the corresponding grammar
production. Note that computation rules for isZero
and pred
are defined for numeric values, not arbitrary terms.
A partial implementation is provided. Download the source archive and unpack it with jar xf expr.jar
. compilation with scalac -d classes src/arithexpr/*.scala
, running with scala -cp classes arithexpr.Main
.
Write an evaluator that reduces terms according the reduction relation.
Start by completing method toString()
in arithexpr.Expr
, then proceed to the methods in arithexpr.Evaluator
Give one term that reduces to a value and one term whose evaluation gets stuck (which does not reduce to a value).