Programming Languages assignment IV

Assignment IV

Due date Tuesday March 20.


The purpose of this assignment is to understand the implementation of non-
local references in block-structured languages. The test case is the Print_Tree
procedure in page 201 of Barnes . This procedure contains three local
procedures: Num_Size, Put, and Do_It, two of which are recursive. Do_It modifies
the array A, which is declared in the enclosing Print_Tree procedure. For
purposes of this assignment you need to look at the package Trees, which defines
a simple binary tree data type, the rest of the code is not relevant. In what
follows, assume that T is a tree with the following structure:

                                      10
                                     /  \
                                    /    \
                                   7     23

1. Write the expression that creates such a tree.

2. Draw the organization of the stack (activation records for various proce-
dures) when procedure Put is called on the node that holds the value 23. You
might want to execute the procedure Print_Tree (suitably augmented with various
print statements) to see what is going on, or you might just trace its
execution by hand.

3. Indicate how the static link is set when Do_It calls Put, and when Do_It
calls itself. Show this in your drawing for part 2.

4. Suppose we use a display instead of a static link (you might want to review
the description of displays on p. 196 of the Sethi text). Explain how the 
contents of the display are updated when Do_It calls Put, when Put calls
Num_Size, and when Do_It calls itself recursively.

5. A "leaf" subprogram is a subprogram that does not contain any local ones (it
is a leaf in the tree of nested declarations). When we use a display for
accessing non-local objects, a very important optimization is available:
a call to a leaf subprogram does not need to update the display. Explain
why, by examining what happens when a leaf calls a sibling, and when it calls
an ancestor (This is one reason why displays are more efficient than static
links).