Programming Languages assignment IV

Assignment V

Due date Tuesday November 6.

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:

                                     /  \
                                    /    \
                                   7     23

1. Write the expression that creates such a tree, using the subprograms
declared in package Trees.

2. Suppose we call Print_Tree on this tree. Draw the organization of the stack
(activation records for various procedures) 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 picture for part 2.

4. Suppose we use a display instead of a static link. 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