Solutions: Programming language principles, part 1, CS 288, May 11, 2005

a) No in both cases. The package body is the implementation of a specification defined in the header, and the user should need to care only about the specification and not the implementation.
b) Yes in both cases. A change to the public part of a package header is a change in the interface.
c) The user code need not change, but recompilation may be necessary. Although the user interface has not changed, the user code still depends on the header.
d) Because the compiler needs access to this and other private information in the header. When compiling user code, the compiler will access the package header but not the package body.

a) The parse tree without attributes is given below

                   E
                /     \
               T       TT
             /  \       |
            F    FT     ∊
          / | \   |
         (  E  )  ∊
          /   \
         T    TT
        / \  / | \
       F FT +  T  TT
       |  |   / \  |
       1  ∊  F  FT ∊
             |  |
             2  ∊

b) In the trees of (b)-(d), attributes whose values are in any way constrained are have these values represented by bracketed integers. Values that are represented by the same bracketed integer are shared. Values that are not represented by bracketed integers are unconstrained. The annotated tree for (b) is given below. In this tree, none of the values represented by [1], [2], or [3] is known yet.

                   E {ptr:[2], st:}
                /                   \
               T {ptr:[1], st:}      TT {ptr:[2], st:[1]}
             /                 \       
            F {ptr:[3], st:}   FT {ptr:[1], st:[3]}
          /        |         \   
         (  E {ptr:[3], st:}  )

c) Here the value represented by [4] is a leaf representing the literal 1, and the value represented by [6] is a tree whose root is +, whose first child is [4] and whose second child is [7]. Except for the shared values represented by indexing, no other constraints on values are known. There is no [5] in the tree, since it has already been identified with [4].

                                  E {ptr:[2], st:} 
                               /                    \
                             T {ptr:[1], st:}       TT {ptr:[2], st:[1]}
                             /              \       
                         F {ptr:[3], st:}     FT {ptr:[1], st:[3]}
                    /           |         \   
                  (     E {ptr:[3], st:}    )
                     /                    \
      T {ptr:[4], st:}                      TT {ptr:[3], st:[4]}
     /               \                       /       |          \
    F {ptr:[4], st:} FT {ptr:[4], st:[4]}   +  T {ptr:[7], st:}  TT {ptr:[3], st: [6]}

d) Here the values represented by [4] and [7] are leaves representing the respective literals 1 and 2, and the value represented by [6] is a tree whose root is +, whose first child is [4] and whose second child is [7]. The value of [6] is shared with the values [1], [2], and [3] of the earlier trees.

                                  E {ptr:[6], st:} 
                               /                    \
                             T {ptr:[6], st:}       TT {ptr:[6], st:[6]}
                             /              \       
                         F {ptr:[6], st:}     FT {ptr:[6], st:[6]}
                    /           |         \   
                  (     E {ptr:[6], st:}    )
                     /                    \
      T {ptr:[4], st:}                      TT {ptr:[6], st:[4]}
     /               \                       /       |          \
    F {ptr:[4], st:} FT {ptr:[4], st:[4]}   +  T {ptr:[7], st:}  TT {ptr:[6], st: [6]}
                                              /                \ 
                                       F {ptr:[7], st:} FT {ptr:[7], st:[7]}

a) That portions of memory that are inaccessible to a program and thus cannot be used, can also be inaccessible to the routine that allocates free storage. This part of memory is called garbage. If there is no way of making garbage available to the free space allocation routine, then the amount of garbage will increase over time, and the amount of available memory will shrink. Sometimes this is described as a memory leak.
b) C programmers are expected to determine when an entity allocated from the heap is about to become inaccessible, and explicitly make its storage available to the free space allocation routine.
c) The advantage of garbage collection is that it frees a programmer from the rather severe burden of responsibility described in (b). One disadvantage is that garbage collection can be fairly slow.
d) The mark-and-sweep algorithm, the stop-and-copy algorithm, and a pointer-reversal algorithm due to Schorr and Waite are described in Section 7.7.3 of Scott.