Assignment 5 Scoped Simple PostScript Interpreter (SSPS) Solution

Assigned: Tuesday, November 30, 2021

Due: Friday, December 10, 2021

Weight: Assignment 5 will count for 5% of your course grade.

Your solutions to the assignment problems are to be your own work. Refer to the course academic integrity statement in the syllabus.

The Postscript is a dynamically scoped language. In this assignment, you will be modifying your SPS interpreter (Assignment 4 - Simple PostScript Interpreter) to handle a slightly different language which supports static scoping. We will call this language Scoped Simple PostScript - SSPS. SSPS has no dict, begin or end operations. Instead, each time a postscript function is called a new dictionary is automatically pushed on the dictionary stack. And when the function execution is complete, this dictionary will be popped out of the stack. The dictionary must be able to hold an arbitrary number of names.

Getting Started

Make a copy of your HW4_part2 folder and rename it as HW5. Download and copy the provided repl.py and load.py files from Canvas and copy them to your HW5 folder. These two files are already updated to support static scoping. Below is a summary of changes on these files. We will explain these further during class.

    1. load.py: interprets each test input first using static scoping , then using dynamic scoping.

    2. repl.py: expects an optional argument for defining the scoping rule.

In this assignment, you will start working with your HW4-part2 code and make changes in the following files:

    • psItems.py: You need to change the way function calls are applied. When `Name` object represents a function call (i.e., its value is a `FunctionValue`), before the `FunctionValue` is applied, a new Activation Record (AR) with an empty dictionary should be pushed onto the `dictstack` and when function execution is done, the AR should be popped from the `dictstack`. We will talk about how to represent the AR in the following sections.

    • psOperators.py: You need to make changes to the following methods: `lookup`, `define`, `stack`, `dictPush`,`psIf`,`psIfelse`,`repeat` and,`forall`. Also, you will remove the following operator methods from psOperators.py: `psDict`, `begin`, and `end`.

Turning in your assignment

All code should be developed in the directory HW5. To submit your assignment, zip all the files in HW5 folder as HW5.zip and turn in your zip file by uploading on the dropbox on Canvas. Please zip only the 8 Python files; not the HW5 directory. Also, exclude any binary python bytecode files (for example __pycache__).

The file that you upload must be named HW5.zip . At the top of the psOperators.py file in a comment, please include your name and the names of the students with whom you discussed any of the problems in this homework. This is an individual assignment and the final writing in the submitted file should be *solely yours*. You may NOT copy another student’s code or work together on writing code. You may not copy code from the web, or anything else that lets you avoid solving the problems for yourself.

You may turn in your assignment up to 3 times. Only the last one submitted will be graded.

Project Description

You will be modifying your SPS interpreter (HW4_part2) to handle a slightly different language which we will call Scoped Simple PostScript - SSPS. As explained above, SSPS has no `dict`, `begin`, and `end` operations. Instead, each time a function is called, a new AR is automatically pushed on the dictstack and when the function execution is complete, this AR will be popped out of the dictstack.

Compared to the `Operators` object in HW4, the HW5 `Operators` object will be initialized with a `scope` argument whose value will either be the string “static” or the string “dynamic”, to indicate whether it should behave using static scope rules or dynamic scope rules. For example:

class Operators:

def __init__(self,scoperule):
……

    • In load.py, we create the `psstacks_s` and `psstacks_d` objects that are initialized with ‘static’ and ‘dynamic’ string arguments, respectively.

psstacks_s = Operators("static") psstacks_d = Operators("dynamic")

To evaluate a list of expressions, i.e., `expr_list`, using static scoping, we pass `psstacks_s` to the `evaluate` method of the expressions:

for expr in expr_list: expr.evaluate(psstacks_s)

To evaluate `expr_list`, using dynamic scoping, we pass `psstacks_d` to the `evaluate` method of the expressions:

for expr in expr_list: expr.evaluate(psstacks_d)

    3. To run the REPL tool using stating scoping, you should execute repl.py using ‘--static’ command line argument, i.e.,

python repl.py --static

If ‘--static’ option is provided, the REPL interpreter will initialize the `Operators` object with 'static' argument.

If ‘--static’ option is not provided, by default, the interpreter will use dynamic scoping rule and will initialize the `Operators` object with 'dynamic' argument.
Static vs Dynamic Scoping

    1. To implement static scope rules, you need a static chain which is the set of dictionaries visited by following the static links we discussed in class.

    2. How can you implement the static links? You should change your dictstack and make it a stack of tuples (instead of just a stack of dictionaries) where each tuple contains an integer index and a dictionary, i.e., (static-link-index, dictionary). The integer index represents the static link that tells you the position of the parent scope in the list.

    3. Where do static-link values come from?

        ◦ As we saw in class, at the point when a function is called, the static link in the new stack entry (Activation Record (AR)) needs to be set to point to the stack entry where the function’s definition was found. Note that with the stack being a list, this “pointer” is just an index in the list.

        ◦ So when calling a function, in the beginning of the `apply` method of the `FunctionValue`, you will push a tuple including the static link and an empty dictionary onto the `dictstack` (see below). This tuple represents the AR for that function call.

(index-of-definition’s stack entry, {})

    • And when the execution of the function is complete (i.e., at the end of the `apply` method) this tuple will be popped from the `dictstack`.

    • In addition, when the bodies of `if`, `ifelse`, `repeat`, and `forall` operators are evaluated, a tuple representing the AR for the operator’s block will be pushed onto the stack. The static-link of the tuple should point to the top of the stack. (Note that these operators will be evaluated in the most recent referencing environment)

(index-of-top-of-the-stack, {})

        ◦ And when the execution of the operator is complete, this tuple will be popped from the `dictstack`.

    4. As discussed in class, variable lookups using static scope rules proceed by looking in the current dictionary at the top of the dictionary stack and then following the static-link fields to other dictionaries (instead of just looking at the dictionaries in order).

Note: In Lab3, you already implemented the lookup function using static scoping rule, where you search the dictionaries following the index links in the tuples (i.e., following the static links).

        ◦ Using dynamic scope rules, the lookup will behave very much like SPS lookup. Of course, you should change your lookup code for the new dictionary structure.

        ◦ The `dictstack` structure will be the same for both static and dynamic scope implementations.

            ▪ When the scoping rule is dynamic, the lookup should just look at the dictionaries on the `dictstack` starting from top (ignoring the static links).
            ▪ If the scoping rule is static, it should look up using static links.
Summary of the changes you need to make:

Remember that:

    • The `Operators` object is initialized with the scoping rule that will be used in interpreting SPS code. You should store the scope argument value in a local attribute in the `Operators` object (for example `scope`) . The `lookup`, and `define` methods will check this attribute value to identify the scoping rule (i.e., `self.scope`).

    • Your interpreter should store tuples in `dictstack` where first value in the tuple is the static-link-index and second value is the dictionary.

    • When a function body is applied (in `Name`s `evaluate` method) a new tuple (AR) will be pushed onto the `dictstack`. “Static-link-index” in that tuple is the index of the dictionary (in the dictstack) where the function is defined. We will discuss the

algorithm for finding this in class. When a function execution is done, remember to pop the tuple for that function call from the `dictstack`.

    • When an if, ifelse, repeat, or forall body is applied (in psIf, psIfelse, repeat, forall methods) a new tuple (AR) will be pushed onto the `dictstack`. “Static-link-

index” in that tuple is the index of the top of the stack. When the execution of the body is done, remember to pop that tuple from the `dictstack`.

    • Change your `lookup` function for static scoping. If the scoping rule is dynamic, perform lookup by searching the AR’s (tuples) top to down. If it is static, use static-links for the search. You should also change the `define` and `dictPush` functions and make them work with the new `dictstack` structure.

    • Change your `stack` operator implementation as explained below.


Output of the Interpreter

In our new SSPS Interpreter, whenever the `stack` operation is executed, the contents of the operand and dictionary stacks are printed. (Remember that stack only printed the contents of the operand stack in HW4).

    • Print a line containing "===**opstack**===" to mark the beginning of the opstack content.

    • Print the operand stack one value per line; print the top-of-stack element first.

    • Print a line containing "===**dictstack**===" to separate the stack from the dictionary stack.

    • Print the contents of the dictionary stack, beginning with the top-of-stack dictionary one name and value per line with a line containing {---- m---- n ----} before each dictionary. m is the index that will identify the dictionary printed (dictionary index) and n is the index that represents the static link for the dictionary printed. Please see next section for examples.

    • Print a line containing "=================" to separate the dictionary stack from any subsequent output.

Remember please the difference between a dictionary and a dictionary entry.
How can I tell if my static scoping code is working correctly?

Your own tests:

Below we provide several tests that you can use for testing your interpreter. Please create at least 3 additional test inputs and include them at the end of your solution file. When we grade your assignment, we will compare the outputs of your interpreter prints.

Given tests:

1)

testinput1 = """

/x 4 def
/g { x stack } def

/f { /x 7 def g } def
f

"""

The above SPS code will have 7 on the stack using dynamic scoping and 4 using static scoping when stack operator is called in “g”. The output from the stack operator in function g would look like this when using static scoping:

STATIC

===**opstack**===
4
===**dictstack**===

----2----0----
----1----0----

/x
7
----0----0----
/x
4
/g
<FunctionValue [Name('x'), Name('stack')]>
/f
<FunctionValue [Name('/x'), Literal(7), Name('def'), Name('g')]>
=================

And using dynamic scoping, the output from the stack operator will look like the following:

DYNAMIC

===**opstack**===
7
===**dictstack**===

----2----0----
----1----0----

/x
7
----0----0----
/x
4
/g
<FunctionValue [Name('x'), Name('stack')]>
/f
<FunctionValue [Name('/x'), Literal(7), Name('def'), Name('g')]>
=================
2)

testinput2 = """
/x 40 def

[1 2 3 4] dup 3 [x] putinterval /x exch def /g { x stack } def

/f { /x [10 20 30 40] def g } def
f

"""
Expected Output

STATIC
===**opstack**===

ArrayValue([1, 2, 3, 40])
===**dictstack**===

----2----0----
----1----0----

/x    ArrayValue([10, 20, 30, 40])
----0----0----
/x    ArrayValue([1, 2, 3, 40])

/g    <FunctionValue [Name('x'), Name('stack')]>

/f    <FunctionValue [Name('/x'), Array([Literal(10), Literal(20), Literal(30),

Literal(40)]), Name('def'), Name('g')]>
=================

DYNAMIC

===**opstack**===
ArrayValue([10, 20, 30, 40])

===**dictstack**===
----2----0----
----1----0----

/x    ArrayValue([10, 20, 30, 40])
----0----0----

/x    ArrayValue([1, 2, 3, 40])
/g    <FunctionValue [Name('x'), Name('stack')]>

/f    <FunctionValue [Name('/x'), Array([Literal(10), Literal(20), Literal(30),
Literal(40)]), Name('def'), Name('g')]>

=================
3)

testinput3 = """
/m 50 def

/n 100 def
/egg1 {/m 25 def n} def

/chic
{ /n 1 def

/egg2 { n stack} def
n m

egg1
m
egg2

} def
n

chic    """

Expected Output

STATIC
===**opstack**===

1
50

100
50

1
100

===**dictstack**===
----2----1----

----1----0----
/n    1
/egg2    <FunctionValue [Name('n'), Name('stack')]>

----0----0----
/m    50

/n    100
/egg1    <FunctionValue [Name('/m'), Literal(25), Name('def'), Name('n')]>

/chic    <FunctionValue [Name('/n'), Literal(1), Name('def'), Name('/egg2'),
Block([Name('n'), Name('stack')]), Name('def'), Name('n'), Name('m'),

Name('egg1'), Name('m'), Name('egg2')]>
=================

DYNAMIC
===**opstack**===

1
50

1
50

1
100

===**dictstack**===
----2----1----

----1----0----

/n 1 /egg2

<FunctionValue [Name('n'), Name('stack')]>
----0----0----
/m    50

/n    100
/egg1    <FunctionValue [Name('/m'), Literal(25), Name('def'), Name('n')]>

/chic    <FunctionValue [Name('/n'), Literal(1), Name('def'), Name('/egg2'),
Block([Name('n'), Name('stack')]), Name('def'), Name('n'), Name('m'),

Name('egg1'), Name('m'), Name('egg2')]>
=================

4)

testinput4 = """

/x 10 def
/A { x } def

/C { /x 40 def A stack } def
/B { /x 30 def /A { x 2 mul } def C } def

B
"""
Expected Output

STATIC

===**opstack**===
10

===**dictstack**===
----2----0----

/x    40
----1----0----

/x    30
/A    <FunctionValue [Name('x'), Literal(2), Name('mul')]>

----0----0----
/x    10
/A    <FunctionValue [Name('x')]>
/C    <FunctionValue [Name('/x'), Literal(40), Name('def'), Name('A'),
Name('stack')]>
/B    <FunctionValue [Name('/x'), Literal(30), Name('def'), Name('/A'),
Block([Name('x'), Literal(2), Name('mul')]), Name('def'), Name('C')]>
=================

DYNAMIC

===**opstack**===
80

===**dictstack**===
----2----0----
/x    40

----1----0----
/x    30

/A    <FunctionValue [Name('x'), Literal(2), Name('mul')]>
----0----0----

/x    10
/A    <FunctionValue [Name('x')]>
/C    <FunctionValue [Name('/x'), Literal(40), Name('def'), Name('A'),
Name('stack')]>
/B    <FunctionValue [Name('/x'), Literal(30), Name('def'), Name('/A'),

Block([Name('x'), Literal(2), Name('mul')]), Name('def'), Name('C')]> =================
5)

testinput5 = """
/x 2 def

/n 5    def
/A { 1    n {x mul} repeat} def

/C { /n 3 def /x 40 def A stack } def
/B { /x 30 def /A { x } def C } def

B
"""
Expected Output

STATIC

===**opstack**===
32

===**dictstack**===
----2----0----

/n    3
/x    40
----1----0----

/x    30
/A    <FunctionValue [Name('x')]>

----0----0----
/x    2

/n    5

/A    <FunctionValue [Literal(1), Name('n'), Block([Name('x'), Name('mul')]),

Name('repeat')]>
/C    <FunctionValue [Name('/n'), Literal(3), Name('def'), Name('/x'),

Literal(40), Name('def'), Name('A'), Name('stack')]>
/B    <FunctionValue [Name('/x'), Literal(30), Name('def'), Name('/A'),
Block([Name('x')]), Name('def'), Name('C')]>

=================

DYNAMIC
===**opstack**===

40
===**dictstack**===

----2----0----
/n
3
/x
40
----1----0----
/x
30
/A
<FunctionValue [Name('x')]>
----0----0----
/x
2
/n
5
/A
<FunctionValue [Literal(1), Name('n'), Block([Name('x'), Name('mul')]),
Name('repeat')]>
/C
<FunctionValue [Name('/n'), Literal(3), Name('def'), Name('/x'),
Literal(40), Name('def'), Name('A'), Name('stack')]>
/B
<FunctionValue [Name('/x'), Literal(30), Name('def'), Name('/A'),

Block([Name('x')]), Name('def'), Name('C')]> =================
6)

testinput6 = """
/myfalse {1 2 eq} def

/out true def

/xand { true eq {pop myfalse} {pop true} ifelse dup /x exch def stack} def /myput { out dup /x exch def xand } def /f { /out myfalse def myput } def

myfalse    f    """
Expected Output

STATIC
===**opstack**===

False
===**dictstack**===

----3----0----
/x
False
----2----0----
/x
True
----1----0----
/out
False
----0----0----
/myfalse
<FunctionValue [Literal(1), Literal(2), Name('eq')]>
/out
True
/xand

<FunctionValue [Literal(True), Name('eq'), Block([Name('pop'),
Name('myfalse')]), Block([Name('pop'), Literal(True)]), Name('ifelse'),
Name('dup'), Name('/x'), Name('exch'), Name('def'), Name('stack')]>
/myput
<FunctionValue [Name('out'), Name('dup'), Name('/x'), Name('exch'),
Name('def'), Name('xand')]>
/f
<FunctionValue [Name('/out'), Name('myfalse'), Name('def'), Name('myput')]>
=================

DYNAMIC

===**opstack**===
True

===**dictstack**===
----3----0----

/x
True
----2----0----
/x
False
----1----0----
/out
False
----0----0----
/myfalse   <FunctionValue [Literal(1), Literal(2), Name('eq')]>
/out
True
/xand
<FunctionValue [Literal(True), Name('eq'), Block([Name('pop'),

Name('myfalse')]), Block([Name('pop'), Literal(True)]), Name('ifelse'), Name('dup'), Name('/x'), Name('exch'), Name('def'), Name('stack')]>

/myput <FunctionValue [Name('out'), Name('dup'), Name('/x'), Name('exch'), Name('def'), Name('xand')]>

/f <FunctionValue [Name('/out'), Name('myfalse'), Name('def'), Name('myput')]> =================
7)

testinput7 = """
/x [1 2 3 4] def

/A { 0    x {add} forall } def

/C { /x [10 20 30 40 50] def A stack } def /B { /x [6 7 8 9] def /A { x } def C } def B

"""
Expected Output

STATIC
===**opstack**===

10
===**dictstack**===

----2----0----
/x    ArrayValue([10, 20, 30, 40, 50])

----1----0----
/x    ArrayValue([6, 7, 8, 9])
/A    <FunctionValue [Name('x')]>

----0----0----
/x    ArrayValue([1, 2, 3, 4])

/A    <FunctionValue [Literal(0), Name('x'), Block([Name('add')]),
Name('forall')]>

/C    <FunctionValue [Name('/x'), Array([Literal(10), Literal(20), Literal(30),
Literal(40), Literal(50)]), Name('def'), Name('A'), Name('stack')]>

/B    <FunctionValue [Name('/x'), Array([Literal(6), Literal(7), Literal(8),
Literal(9)]), Name('def'), Name('/A'), Block([Name('x')]), Name('def'),

Name('C')]>
=================

DYNAMIC
===**opstack**===

ArrayValue([10, 20, 30, 40, 50])
===**dictstack**===

----2----0----
/x    ArrayValue([10, 20, 30, 40, 50])

----1----0----
/x    ArrayValue([6, 7, 8, 9])

/A    <FunctionValue [Name('x')]>
----0----0----
/x    ArrayValue([1, 2, 3, 4])

/A    <FunctionValue [Literal(0), Name('x'), Block([Name('add')]),
Name('forall')]>

/C    <FunctionValue [Name('/x'), Array([Literal(10), Literal(20), Literal(30),
Literal(40), Literal(50)]), Name('def'), Name('A'), Name('stack')]>

/B    <FunctionValue [Name('/x'), Array([Literal(6), Literal(7), Literal(8),
Literal(9)]), Name('def'), Name('/A'), Block([Name('x')]), Name('def'),

Name('C')]>
=================
8)

testinput8 = """
/x [2 3 4 5] def

/a 10 def
/A { x } def

/C { /x [a 2 mul a 3 mul dup a 4 mul] def A    a x stack } def
/B { /x [6 7 8 9] def /A { x } def /a 5 def C } def

B
"""
Expected Output

STATIC

===**opstack**===
ArrayValue([20, 30, 30, 40])

10
ArrayValue([2, 3, 4, 5])

===**dictstack**===
----2----0----
/x    ArrayValue([20, 30, 30, 40])

----1----0----
/x    ArrayValue([6, 7, 8, 9])

/A    <FunctionValue [Name('x')]>
/a    5

----0----0----
/x    ArrayValue([2, 3, 4, 5])

/a    10
/A    <FunctionValue [Name('x')]>

/C    <FunctionValue [Name('/x'), Array([Name('a'), Literal(2), Name('mul'),
Name('a'), Literal(3), Name('mul'), Name('dup'),

Name('a'), Literal(4), Name('mul')]), Name('def'), Name('A'), Name('a'), Name('x'), Name('stack')]>

/B <FunctionValue [Name('/x'), Array([Literal(6), Literal(7), Literal(8), Literal(9)]), Name('def'), Name('/A'), Block([Name('x')]), Name('def'), Name('/a'), Literal(5), Name('def'), Name('C')]> =================


DYNAMIC
===**opstack**===

ArrayValue([10, 15, 15, 20])
5
ArrayValue([10, 15, 15, 20])

===**dictstack**===
----2----0----

/x    ArrayValue([10, 15, 15, 20])
----1----0----

/x    ArrayValue([6, 7, 8, 9])
/A    <FunctionValue [Name('x')]>

/a    5
----0----0----

/x    ArrayValue([2, 3, 4, 5])
/a    10
/A    <FunctionValue [Name('x')]>

/C <FunctionValue [Name('/x'), Array([Name('a'), Literal(2), Name('mul'), Name('a'), Literal(3), Name('mul'), Name('dup'), Name('a'), Literal(4), Name('mul')]), Name('def'), Name('A'), Name('a'), Name('x'), Name('stack')]> /B <FunctionValue [Name('/x'), Array([Literal(6), Literal(7), Literal(8),

Literal(9)]), Name('def'), Name('/A'), Block([Name('x')]), Name('def'), Name('/a'), Literal(5), Name('def'), Name('C')]>