CIS505 Assignment 3

10 points; due Wednesday, Oct. 1

You will extend the interpreter you built in Assigment 2. The extensions go in two parts.

Part C: add objects

First, you add object declarations and objects. The objects are "structs" that hold var and proc declarations, like we saw in Chapter 6 of the Lecture Notes. A sample program will look and work like this:

python run.py
Type program; OK to do it on multiple lines; terminate with  !
  as the first symbol on a line by itself:

int a = 1;
ob counter = new {int val = a;
                  proc inc(x) : val = ((val + x) + a);  print val; end;
                 };
proc p(): a = (a + counter.val)  end;
ob nothingyet = nil;

counter.inc(1);
p();
nothingyet = counter
!

Here is the execution of the above program:

Parse tree:
[[['int', 'a', '1'], ['ob', 'counter', ['new', ['struct', [['int', 'val', ['deref', 'a']], ['proc', 'inc', ['x'], [], [['=', 'val', ['+', ['+', ['deref', 'val'], ['deref', 'x']], ['deref', 'a']]], ['print', ['deref', 'val']]]]]]]], ['proc', 'p', [], [], [['=', 'a', ['+', ['deref', 'a'], ['deref', ['dot', 'counter', 'val']]]]]], ['ob', 'nothingyet', 'nil']], [['call', ['dot', 'counter', 'inc'], ['1']], ['call', 'p', []], ['=', 'nothingyet', ['deref', 'counter']]]]
Execution:
3
activation stack = ['h0', 'h4']
heap = {
  h0 : {'a': 1, 'parentns': 'nil', 'counter': 'h1', 'nothingyet': 'nil', 'p': 'h3'}
  h1 : {'parentns': 'h0', 'val': 3, 'inc': 'h2'}
  h2 : {'body': [['=', 'val', ['+', ['+', ['deref', 'val'], ['deref', 'x']], ['deref', 'a']]], ['print', ['deref', 'val']]], 'params': ['x'], 'type': 'proc', 'link': 'h1', 'locals': []}
  h3 : {'body': [['=', 'a', ['+', ['deref', 'a'], ['deref', ['dot', 'counter', 'val']]]]], 'params': [], 'type': 'proc', 'link': 'h0', 'locals': []}
  h4 : {'x': 1, 'parentns': 'h1'}
}
Successful termination.
activation stack = ['h0']
heap = {
  h0 : {'a': 4, 'parentns': 'nil', 'counter': 'h1', 'nothingyet': 'h1', 'p': 'h3'}
  h1 : {'parentns': 'h0', 'val': 3, 'inc': 'h2'}
  h2 : {'body': [['=', 'val', ['+', ['+', ['deref', 'val'], ['deref', 'x']], ['deref', 'a']]], ['print', ['deref', 'val']]], 'params': ['x'], 'type': 'proc', 'link': 'h1', 'locals': []}
  h3 : {'body': [['=', 'a', ['+', ['deref', 'a'], ['deref', ['dot', 'counter', 'val']]]]], 'params': [], 'type': 'proc', 'link': 'h0', 'locals': []}
  h4 : {'x': 1, 'parentns': 'h1'}
  h5 : {'parentns': 'h0'}
}

In the example, $h0$ is the handle to the global variables' namespace. Variable $counter$ is bound to the handle of a new namespace/object, $h1$, that holds $val$, $inc$, and $parentns$ (which is needed when evaluating the expressions that appear in the object's declarations).

When $counter.inc(1)$ is called, it works just as you implemented it in Assignment 2: a new activation record, $h4$, is constructed for the call to $inc$, and $h4$ is pushed onto the activation stack. Note that $h4$ holds a $parentns$ link that is set to $h1$, which is $inc$'s "parent object". (In Java and C#, the $parentns$ field inside $h4$ is called $this$.)

Once $inc$'s code finishes, the stack is popped. Then $p()$ gets called, and its activation, $h5$, is pushed then popped.

In Java/C#, $p$ is called a ``static method,'' and $inc$ is called an ``instance method.''

Your work is to implement these new parts of the language: D ::= ... | ob I = E E ::= ... | new T | nil T ::= { DL } L ::= ... | L . I Here is the complete syntax, with the new parts included:





P : Program
CL : CommandList
C : Command
DL : DeclarationList
D : Declaration
EL : ExpressionList



     



E : Expression
T : TypeTemplate
L : LefthandSide
IL : VariableList
I : Variable
N : Numeral





P ::=  DL CL

DL ::=  D;*
D ::=  int I = E  |  ob I = E  |  proc I ( IL ) : CL end 

CL ::=  C;*
C ::=  L = E  |  if E : CL1 else CL2 end  |  print E  |  L ( EL )

EL ::=  E,*
E ::=  N  |  ( E1 OP E2 )  |  L  |  new T  |  nil
    where  OP ::=  +  |  -
T ::=  { DL }
L ::=  I  |  L . I

N ::=  string of digits
IL ::=  I,*
I ::=  strings of letters, not including keywords

The parser you used for Exercise 2 already implements the above constructions, so you reuse the parser you already have.

Interpreter input format

The input to the interpreter is the list-based parse tree constructed by the parser. The new constructions are: DTREE ::= ... | ["ob", ID, ETREE] ETREE ::= ... | "nil" | ["new", TTREE] TTREE ::= ["struct", DLIST] LTREE ::= ... | ["dot", LTREE, ID] The syntax of all forms of parse trees goes like this:

PTREE ::=  [DLIST, CLIST]
DLIST ::=  [ DTREE* ]
           where  DTREE*  means zero or more DTREEs
DTREE ::=  ["int", ID, ETREE]  |  ["proc", ID, IDLIST, CLIST, DLIST]  |  ["ob", ID, ETREE]

CLIST ::=  [ CTREE* ]
CTREE ::=  ["=", LTREE, ETREE]  |  ["if", ETREE, CLIST, CLIST]
        |  ["print", ETREE]  |  ["call", LTREE, ELIST]

ELIST ::=   [ ETREE* ]
ETREE ::=  NUM  |  [OP, ETREE, ETREE] |  ["deref", LTREE]  |  "nil"  |  ["new",  TTREE]
      where  OP ::=  "+"  | "-"
TTREE ::=  ["struct", DLIST]
LTREE ::=  ID  | ["dot", LTREE, ID]

NUM   ::=  a nonempty string of digits
IDLIST ::= [ ID+ ]
ID    ::=  a nonempty string of letters

Interpreter operation

You start from the interpreter you built for Assignment 2. (If you didn't complete at least Assignment 2, Part A, you must finish Part A before you start this one --- please see the instructor as soon as possible to make an appointment to fix your Assignment 2 submission. Sorry, but it's useless to do this assignment without learning how to do Assignment 2, Part A.)

You have these structures to implement: $"nil"$, $["new", TTREE]$, $["ob", ID, ETREE]$, $["struct", DLIST]$, and $["dot", LTREE, ID]$.

Within $interpretETREE$, implement $"nil"$ to have itself as its value. Implement $["new", T]$ to call $interpretTTREE(T)$, whose job is to allocate an object, fill it with $T$, and return the object's handle.
You define $def interpretTTREE(ttree)$. It receives arguments of the form, $["struct", DLIST]$. The function does this: (i) allocates a new namespace and pushes the namespace's handle on the activation stack; (ii) evaluates $DLIST$; (iii)pops the activation stack and returns the popped handle as its answer.
Within $interpretDTREE$, implement $["ob", I, E]$, which (i) computes the meaning of $E$, (ii) validates that $E$ is either a handle to an object or is $nil$, and (iii) binds $I$ to the meaning in the active namespace (provided that $I$ is not already declared there).
Within $interpretLTREE$, implement $["dot", L, I]$. This means you compute the handle named by $L$, call it $h$, and then check if the pair, $(h,I)$ is a valid L-value (that is, variable $I$ is a field inside the object named by $h$). Big Hint: read the code for the virtual machine in Chapter 2, Section 2.2.1.

As usual, enforce declaration checking --- the same name cannot be declared twice in the same namespace and no name can be referenced or assigned to if it is undeclared (this includes fields within objects). Also enforce type checking in commands and expressions: Only a handle (or $nil$) can be assigned to an object variable, and only an int can be assigned to an int variable. (Hint: use Python's $instanceof$ or $type$ operator to check types. See the notes, Terse notes on lists and dictionaries on the CIS505 web page.) Only ints can be used in arithmetic; only procs can be called; and only objects can be indexed with dot notation.

Remember to document appropriately your modified interpreter.

Testing

The $Ex3$ folder contains a file of test cases that you should use for testing Part C. Use at least these tests to check your implemetation. You should also devise 2-3 additional tests to see if the interpreter detects program errors and prints appropriate messages.

Place all the test cases and their output in a file named $tests.txt$

Part D: add classes

Don't start this part unless you have built and tested successfully Part C.

Now you extend the interpreter with classes. A sample program looks like this:

python run.py
Type program; OK to do it on multiple lines; terminate with  !
  as the first symbol on a line by itself:

int a = 2;
class counter : {int val = a; 
                 proc inc(x) : val = (val + x); end;
                };
ob c = new counter;
proc p(): a = (a + c.val)  end;
c.inc(1);
p();
!

Here is the execution of the above program:

Parse tree:
[[['int', 'a', '2'], ['class', 'counter', ['struct', [['int', 'val', ['deref', 'a']], ['proc', 'inc', ['x'], [], [['=', 'val', ['+', ['deref', 'val'], ['deref', 'x']]]]]]]], ['ob', 'c', ['new', ['call', 'counter']]], ['proc', 'p', [], [], [['=', 'a', ['+', ['deref', 'a'], ['deref', ['dot', 'c', 'val']]]]]]], [['call',['dot', 'c', 'inc'], ['1']], ['call', 'p', []]]]
Execution:
Successful termination.
activation stack = ['h0']
heap = {
  h0 : {'a': 5, 'parentns': 'nil', 'c': 'h2', 'counter': 'h1', 'p': 'h4'}
  h1 : {'body': ['struct', [['int', 'val', ['deref', 'a']], ['proc', 'inc', ['x'], [], [['=', 'val', ['+', ['deref', 'val'], ['deref', 'x']]]]]]], 'link': 'h0',
 'type': 'class'}
  h2 : {'parentns': 'h0', 'val': 3, 'inc': 'h3'}
  h3 : {'body': [['=', 'val', ['+', ['deref', 'val'], ['deref', 'x']]]], 'params': ['x'], 'type': 'proc', 'link': 'h2', 'locals': []}
  h4 : {'body': [['=', 'a', ['+', ['deref', 'a'], ['deref', ['dot', 'c', 'val']]]]], 'params': [], 'type': 'proc', 'link': 'h0', 'locals': []}
  h5 : {'x': 1, 'parentns': 'h2'}
  h6 : {'parentns': 'h0'}
}

The syntax has these two additions: D ::= ... | class I : T T ::= ... | L That is, we can declare a class and call it. The parser already implements the new constructions.

Interpreter input format

You must implement in your interpreter, DTREE ::= ... | ["class", ID, TTREE] TTREE ::= ... | ["call", LTREE]

Interpreter operation

There are two steps:

Within $interpretDTREE$, implement $["class", I, T]$, which behaves like procedure declaration, that is, $I$ is bound to a closure containing $T$ and its link to global variables. Please study the above example program.
Within $interpretTTREE$, implement $["call", L]$. This works like procedure call, where $L$ is computed to a handle, the closure labelled by the handle is extracted from the heap, and provided that the closure holds a class, the $TTREE$ within the closure is extracted and executed. There are no parameters to worry about this time.

Testing

The $Ex3$ folder contains a file of test cases that you should use for Part D. Use at least these tests to check your implemetation. Place your tests and their outputs in your $tests.txt$ file. You should also devise additional tests to see if the interpreter detects program errors and prints appropriate messages.

Teamwork possible this time only

I will give you the option of working with a partner on this assignment only. If you wish to have a partner for this exercise, please notify the instructor in person or by email by Weds., September 24, 5pm.

Submission and grading

Place your versions of $heapmodule.py$, $interpret.py$, and $tests.txt$ in the folder $YourFirstNameYourLastName3$. (Don't alter and don't submit the other files.) You get credit for completing the test cases only if the cases and their outputs are included in $tests.txt$.

Zip the folder into a $.zip$ file and submit the $.zip$ file to the CIS505 site on K-State Online. If you are working with a partner, both you and your partner each upload the same zipped folder to K-State online.

The teaching assistants will study your work and your tests and apply some additional tests before scoring the submission.

Final Comment

You have implemented C#-style ``instance methods.'' If we would add subclasses to the language, we would have the option of allowing virtual methods as well. (You use the $virtual$/$override$ keywords in C# to declare a virtual method.) See the explanation in the Lecture Notes, Section 6.6.