Assignment 5 (Static Scoping PostScript Interpreter(SSPS) Solution

Project Description

You will be modifying your SPS interpreter (Assignment 2 - Simple Post Script Interpreter) to handle a slightly different language which we will call 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. The dictionary must be able to hold an arbitrary number of names (a Python dictionary is just what is needed!).

Compared to your SPS interpreter function, the SPSS interpreter will take an addition argument whose value will be either the string “static” or the string “dynamic”, to indicate whether it should behave using static scope rules or dynamic scope rules.

    • Each time a postscript function is about to be called push a new dictionary and when a postscript function is about to return pop the dictionary.

    • Using dynamic scope rules, the SPSS interpreter will behave very much like SPS except that it won't support dict, begin or end operations in programs (indeed, there will be no implementation of these operations in SSPS).

    • To implement static scope rules you need a static chain which is the set of dictionaries visited by following the static links (also called the access links) we discussed in class. You already have a stack of dictionaries, probably implemented as a list, so you don’t have explicit control links (also called dynamic links). The dynamic chain is implicit in the order of the dictionaries in the list. To search for a declaration you search from the top of the stack (and push and pop at that end as well).

    • How can you implement the static chain? I suggest making the stack be a stack of tuples (instead of just a stack of dictionaries) where each tuple contains an integer index and a dictionary. The integer index represents the static link that tells you the position in the list of the (dictionary, static-link) tuple for the parent scope.

    • 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 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 postscript function you create a new dictionary automatically and what you push on the dictionary stack is a pair (dictionary, index-of-definition’s stack entry).

        ◦ Hint: In an effective implementation this should all take only a handful of lines of new code but it is tricky to get all the pieces right. My advice is think more, write less for this part of the project. Note: If you want to explore python’s object facilities and create a class for the objects on the dictionary stack, feel free to do that. The code will be a little cleaner, but using objects is not required as we have not discussed Python objects.

        ◦ 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 all the dictionaries on the stack in turn, which gives dynamic scope rules).
Output of the 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 Assignment-2)

    • Print a line containing "==============” to separate the stack from what has come before.

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

    • Print a line containing “==============” 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 that follows (dictionary index) and n is the index that represents the static link for the dictionary that follows (in the case that static scoping is being used). Please see below for an example. If you use a “system dictionary” at the base of the dictionary stack, whose contents never change, as part of your implementation of the basic interpreter, do not print it.

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

Remember please the difference between a dictionary and a dictionary entry.

What if my SPS interpreter didn’t work correctly?
You will need to fix it so it works. You can visit with the TA or me for help. We may provide you a skeleton code to start with.

How can I tell if my static scoping code is working correctly?

You will have to create some test cases for which you can predict the correct answers. We covered one simple example in class. Translated to SSPS and simplified a bit that example looks like:

/x 4 def
/g { x stack } def
/f { /x 7 def g } def
f

which when it ends will leave 7 on the stack using dynamic scoping and 4 using static scoping. The output from the stack operator in function g would look like this when using static scoping:

==============
4

==============
----2
----0----
----1
----0----
/x
7
----0----0----
/x
4
/g
['x', 'stack']
/f
['/x', 7, 'def', 'g']
==============
For the values of m and n you may use anything you like as along as it is possible to tell where the static links point. For printing code array values, I suggest using [] around the values in the array, but I don’t care about details as long as it is easy to see which things that you print for dictionaries are names and which are values (be careful that it is possible to make this distinction even when a code array is very large and wraps onto another line). Remember that testing to the specification is your responsibility. We read your code looking for bugs in addition to running it on some tests. Tests can only show the presence of bugs, never their absence!

Additional Test Case:
/m [25 50] 1 get    def

/n [100 1] 0 get    def

/egg1 {/m 25 def n} def

/chic {

/n 1 def

/egg2 { n } def

    m n egg1 egg2
stack  } def

n

chic

Expected Output
Using static scoping

Static
==============
1

100
1

50
100
==============

----1----0----
/n
1
/egg2
['n']
----0----0----
/m
50
/n
100
/egg1
['/m', 25, 'def', 'n']
/chic
['/n', 1, 'def', '/egg2', ['n'], 'def', 'm', 'n', 'egg1', 'egg2',
'stack']
==============

Using dynamic scoping
Dynamic
==============
1

1
1

50
100
==============
----1----0----

/n
1

/egg2
['n']

----0----0----

/m
50

/n
100
25, 'def', 'n']
/egg1
['/m',

/chic
['/n',
1, 'def', '/egg2', ['n'], 'def', 'm', 'n', 'egg1', 'egg2',
'stack']

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