Question 2

The addition of the operation add_attribute requires the ability to redefine a class. Various choices have to be made:

• How does the addition of the new attribute impact the subclasses of the given class? The natural answer is to allow inheritance to operate as usual. This means that also all the subclasses inherit the new attribute as well--i.e., the whole subtree rooted at such class receive the new attribute.
• How does the addition affect existing instances? This is a more delicate issue. We have two alternative views that can be taken:
  • we propagate the effects also to the existing instances. Thus all the instances receive the new attribute.
  • we allow existing instances to maintain their original structure--the new attribute will appear only in the class instances created after the add_attribute operation was performed.
  The first scheme seems logically better founded, but is clearly more difficult to implement. The second scheme is easier to implement but less clear--as it allows instances of the same class to have a different structure.

Assuming that we aim at the simpler non well-founded approach, then we need to explicitly maintain the tree structure of the hierarchy in order to identify which are the subclasses that depends on the class being modified. Thus the function-based representation of the hierarchy used in the part 1 is not anymore suitable to our needs. We can rely on an algebra of trees for encoding the hierarchy. Let us assume that we have the semantic domain construction Tree(TYPE) whose domain is composed by all trees having elements belonging to the domain TYPE as nodes.

Hierarchy = Tree(Class $\times$ Id)

Each node of the tree stores the description of the class (Class) as well as the name of the class (Id). The functions for accessing the description of a class (e.g., for creating a new instance) will require traversing the tree structure in search of the class with the given name. Furthermore, in order to determine the actual structure of a class we need to identify the class and traverse the branch of the tree from the class up to the root, merging all the description encountered along the path. This can be encoded (intuitively) as:

$$\begin{array}{ll} \mbox{\em access} = & \lambda id. \lambda t... ...ox{\em access\_child}(id,\mbox{\em children}(tree)) \end{array}$$

where access_child repeats the access operation on each of the children of the node. Given the node of the class we are interested in, we can detect the actual structure of the class by doing:

$$\begin{array}{ll} \mbox{\em struct} = &\lambda node. \lambda ... ...s}(node,\mbox{\em struct}(\mbox{\em parent}(node))) \end{array}$$

where the update_class is defined as:

$$\mbox{\em update\_class}(f_1,f_2)(id) = \left\{ \begin{array... ...rrValue}$ }\\ f_2(id) & \mbox{otherwise} \end{array} \right.$$

This will allow to dynamically recompute the structure of the class everytime we create a new instance.

The well-founded approach instead requires recomputing the structure of each instance every time the instance is accessed. If the structure of the class has been modified, then the instance has to be modified as well before performing any further operation. This can be achieved by maintaining together with each object a reference to the corresponding class (e.g., its name). Every time we analyze a construct of the type Id₁.Id₂ in the denotational semantics, we need to add a call to a function which compares the structure of the instance with the structure of its class. Any difference (i.e., there is an attribute in the instance which has value UndefAttr while the corresponding attribute in the class has ErrValue value) will lead to the update of the instance (i.e., the new attribute is added to the instance).