Programming Languages assignment IV
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).