You must implement in Scala the interpreter for the mini object language described in the Namespace notes augmented with parameterized procedures.
The interpreter you write is based on the semantics definition
provided in the Namespace notes, Sections 2.2 and 3.2.
Here is the syntax:
===================================================
CL: CommandList
D : Declaration
C : Command L : LefthandSide
E : Expression T : Template
I : Variable N : Numeral
IL: VariableList EL: ExpressionList
P ::= T
D ::= var I = E
| proc I ( IL ) : CL /? return E ?/ end
where /? ... ?/ means that ... is optional
C ::= D | L = E | L ( EL ) | if E : CL else CL end
| while E : CL end | print E
CL ::= sequence of zero or more C, separated by semicolons
E ::= N | ( E1 OP E2 ) | L | L ( EL ) | new T
where OP is '+' or '-'
and the outermost parens of a compound expression are optional
L ::= I | L . I
T ::= { CL }
IL ::= sequence of zero or more I, separated by commas
EL ::= sequence of zero or more E, separated by commas
N ::= string of digits
I ::= string of letters, not including keywords ('var', 'if', ..., 'this', ...)
===================================================
Here are the formats of operator trees (parse trees) that the
interpreter will process:
===================================================
CLIST ::= List( CTREE,* )
that is, a list of zero or more CTREEs
DLIST ::= List( DLIST* )
DTREE ::= Var( Iden, ETREE )
| Proc( Iden, ILIST, CLIST, Option( ETREE ) )
Coded like this in Scala:
sealed abstract class Dtree
case class Var(name: String, e: Etree) extends Dtree
case class Proc(name: String, params: List[String],
body: List[Ctree], result: Option[Etree] ) extends Dtree
CTREE ::= Dec( DTREE ) | Assign( LTREE, ETREE )
| CallProc( LTREE, ELIST )
| If( ETREE, CLIST, CLIST ) | While( ETREE, CLIST )
| Print( ETREE )
ETREE ::= Num( N ) | Binop( OP, ETREE, ETREE ) | Deref( LTREE )
| New( TTREE ) | CallFunc( LTREE, ELIST )
LTREE ::= Ref( Iden ) | Dot( LTREE, Iden )
TTREE ::= Template( None, List(), CLIST )
for this assignment, the first two args aren't used
OP ::= "+" | "-" | ...
ILIST ::= List( I,* ) that is, a list of zero or more Is
ELIST ::= List( ETREE,* )
===================================================
For example, the program,
{
var a = 2;
var b = new {var f = a };
a = b.f + 1;
print a;
proc plusone(a) : var y = a + 1;
print a;
return y end;
var clock = new {var time = a;
proc tick(i): time = plusone(a + i) end;
tick(1);
print time;
};
clock.tick(clock.time);
print 999;
}
parses to this operator tree:
Template(None, List(),
List(Dec(Var(a,Num(2))),
Dec(Var(b,New(Template(None,List(),
List(Dec(Var(f,Deref(Ref(a))))))))),
Assign(Ref(a),BinOp(+,Deref(Dot(Ref(b),f)),Num(1))),
Print(Deref(Ref(a))),
Dec(Proc(plusone, List(a),
List(Dec(Var(y,BinOp(+,Deref(Ref(a)),Num(1)))),
Print(Deref(Ref(a)))),
Some(Deref(Ref(y))))),
Dec(Var(clock,New(Template(None,List(),
List(Dec(Var(time,Deref(Ref(a)))),
Dec(Proc(tick,List(i),
List(Assign(Ref(time),CallFunc(Ref(plusone),List(BinOp(+,Deref(Ref(a)),Deref(Ref(i))))))),None)),
CallProc(Ref(tick),List(Num(1))),
Print(Deref(Ref(time)))))))),
CallProc(Dot(Ref(clock),tick),List(Deref(Dot(Ref(clock),time)))),
Print(Num(999)
))
Here is the output generated by the interpreter,
where I have rigged the semantics of the print E command to print the value
of its argument, E, and
then generate a dump of the virtual machine's state:
===================================================
Print: 3
actstack = h1
heap = Map(
h0 -> Map('a'-> 3, 'b'-> 'h2', 'parent'-> 'nil')
h1 -> Map('this'-> 'h0', 'parent'-> 'nil')
h2 -> Map('parent'-> 'h0', 'f'-> 2)
h3 -> Map('this'-> 'h2', 'parent'-> 'h1')
)
Print: 4
actstack = h11
heap = Map(
h0 -> Map('a'-> 3, 'b'-> 'h2', 'plusone'-> 'h4', 'parent'-> 'nil')
h1 -> Map('this'-> 'h0', 'parent'-> 'nil')
h10 -> Map('a'-> 4, 'y'-> 5, 'parent'-> 'h0')
h11 -> Map('this'-> 'h10', 'parent'-> 'h9')
h2 -> Map('parent'-> 'h0', 'f'-> 2)
h3 -> Map('this'-> 'h2', 'parent'-> 'h1')
h4 -> Map('type'-> 'proc', 'returns'-> 'y', 'code'-> [['var', 'y', ['+', 'a', '1']], ['print', 'a']], 'params'-> ['a'], 'parent'-> 'h0')
h5 -> Map('tick'-> 'h7', 'parent'-> 'h0', 'time'-> 3)
h6 -> Map('this'-> 'h5', 'parent'-> 'h1')
h7 -> Map('type'-> 'proc', 'returns'-> [], 'code'-> [['=', 'time', ['call', 'plusone', [['+', 'a', 'i']]]]], 'params'-> ['i'], 'parent'-> 'h5')
h8 -> Map('i'-> 1, 'parent'-> 'h5')
h9 -> Map('this'-> 'h8', 'parent'-> 'h6')
)
Print: 5
actstack = h6
heap = Map(
h0 -> Map('a'-> 3, 'b'-> 'h2', 'plusone'-> 'h4', 'parent'-> 'nil')
h1 -> Map('this'-> 'h0', 'parent'-> 'nil')
h10 -> Map('a'-> 4, 'y'-> 5, 'parent'-> 'h0')
h11 -> Map('this'-> 'h10', 'parent'-> 'h9')
h2 -> Map('parent'-> 'h0', 'f'-> 2)
h3 -> Map('this'-> 'h2', 'parent'-> 'h1')
h4 -> Map('type'-> 'proc', 'returns'-> 'y', 'code'-> [['var', 'y', ['+', 'a', '1']], ['print', 'a']], 'params'-> ['a'], 'parent'-> 'h0')
h5 -> Map('tick'-> 'h7', 'parent'-> 'h0', 'time'-> 5)
h6 -> Map('this'-> 'h5', 'parent'-> 'h1')
h7 -> Map('type'-> 'proc', 'returns'-> [], 'code'-> [['=', 'time', ['call', 'plusone', [['+', 'a', 'i']]]]], 'params'-> ['i'], 'parent'-> 'h5')
h8 -> Map('i'-> 1, 'parent'-> 'h5')
h9 -> Map('this'-> 'h8', 'parent'-> 'h6')
)
Print: 8
actstack = h15
heap = Map(
h0 -> Map('a'-> 3, 'b'-> 'h2', 'plusone'-> 'h4', 'parent'-> 'nil', 'clock'-> 'h5')
h1 -> Map('this'-> 'h0', 'parent'-> 'nil')
h10 -> Map('a'-> 4, 'y'-> 5, 'parent'-> 'h0')
h11 -> Map('this'-> 'h10', 'parent'-> 'h9')
h12 -> Map('i'-> 5, 'parent'-> 'h5')
h13 -> Map('this'-> 'h12', 'parent'-> 'h1')
h14 -> Map('a'-> 8, 'y'-> 9, 'parent'-> 'h0')
h15 -> Map('this'-> 'h14', 'parent'-> 'h13')
h2 -> Map('parent'-> 'h0', 'f'-> 2)
h3 -> Map('this'-> 'h2', 'parent'-> 'h1')
h4 -> Map('type'-> 'proc', 'returns'-> 'y', 'code'-> [['var', 'y', ['+', 'a', '1']], ['print', 'a']], 'params'-> ['a'], 'parent'-> 'h0')
h5 -> Map('tick'-> 'h7', 'parent'-> 'h0', 'time'-> 5)
h6 -> Map('this'-> 'h5', 'parent'-> 'h1')
h7 -> Map('type'-> 'proc', 'returns'-> [], 'code'-> [['=', 'time', ['call', 'plusone', [['+', 'a', 'i']]]]], 'params'-> ['i'], 'parent'-> 'h5')
h8 -> Map('i'-> 1, 'parent'-> 'h5')
h9 -> Map('this'-> 'h8', 'parent'-> 'h6')
)
Print: 999
actstack = h1
heap = Map(
h0 -> Map('a'-> 3, 'b'-> 'h2', 'plusone'-> 'h4', 'parent'-> 'nil', 'clock'-> 'h5')
h1 -> Map('this'-> 'h0', 'parent'-> 'nil')
h10 -> Map('a'-> 4, 'y'-> 5, 'parent'-> 'h0')
h11 -> Map('this'-> 'h10', 'parent'-> 'h9')
h12 -> Map('i'-> 5, 'parent'-> 'h5')
h13 -> Map('this'-> 'h12', 'parent'-> 'h1')
h14 -> Map('a'-> 8, 'y'-> 9, 'parent'-> 'h0')
h15 -> Map('this'-> 'h14', 'parent'-> 'h13')
h2 -> Map('parent'-> 'h0', 'f'-> 2)
h3 -> Map('this'-> 'h2', 'parent'-> 'h1')
h4 -> Map('type'-> 'proc', 'returns'-> 'y', 'code'-> [['var', 'y', ['+', 'a', '1']], ['print', 'a']], 'params'-> ['a'], 'parent'-> 'h0')
h5 -> Map('tick'-> 'h7', 'parent'-> 'h0', 'time'-> 9)
h6 -> Map('this'-> 'h5', 'parent'-> 'h1')
h7 -> Map('type'-> 'proc', 'returns'-> [], 'code'-> [['=', 'time', ['call', 'plusone', [['+', 'a', 'i']]]]], 'params'-> ['i'], 'parent'-> 'h5')
h8 -> Map('i'-> 1, 'parent'-> 'h5')
h9 -> Map('this'-> 'h8', 'parent'-> 'h6')
)
===================================================
(Note: the output from Scala will look slightly different from the above: strings won't be quoted, the Maps won't be sorted, and the
closures will be Maps whose 'code' entry maps to a list of operator trees. The above is patched from an earlier Python implementation.)
I have written the parser for the language, using the PLY parser-generator, which implements the domain-specific parser language, Yacc, in Python. The parser and PLY, along with the main driver (run.py, coded in Python), a Virtual Machine, and a skeletal interpreter (in Scala), are found in the folder with this assignment sheet on the CIS705a Assignments web page.
You write the interpreter as a faithful copy of the semantics definitions found in Sections 2.2 (the heap, activation stack, and core language) and 3.2 (for parameterized procedure declaration and invocation).
Before you code the interpreter, study the semantics definitions in Section 2.2 and 3.2. In addition to the computations defined in the semantics, your intepreter must generate useful error messages when the input program computes an error. (Examples are: trying to add an int to a handle; referencing a non-existant field name in an object.)
I have written a suite of test cases that you must use to validate your work. These test cases are in a file, tests.txt, saved with this assignment sheet. (Sample outputs for the first few tests are in testsScala.txt.) Copy-and-paste each test case into the window when you are running your interpreter, and copy-and-paste the results from your tests into a file named testcases.txt.
Also, include testcases.txt, which contains your successful test cases and their outputs.