CIS705 Assignment 2

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.)

Implementing the interpreter

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.)

Testing

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.

Submission

Submit to K-State Online a folder saved as a .zip file containing the finished system. So not alter run.py, ex23lex.py, and ex23parse.py. Alter package VM at your own risk.

Also, include testcases.txt, which contains your successful test cases and their outputs.