The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.

1. Consider the implementation of the ADT "simple list" seen in Lecture 10 (CSE 428 Spring 99, see LN). Assume that the data are somehow protected, so that it is possible to access to lists only via the operations of the ADT.
   1. Is it possible to create "circular lists", i.e. lists in which it is possible, following the links from an element, to come back to the element itself?
   2. Is it possible to create "shared lists", i.e. lists which have a part in common?
   3. Is it possible that an operation done on a list affects another list?

   Solution

   1. It's not possible to create circular lists. In fact, lists are created by the function "emptylist", which returns a null pointer, and are expanded by the function "cons", which adds a new element on the front and returns the pointer to this (newly allocated) element. Of course, this pointer could not be used before being created, hence it could not have been mentioned in previous operations on the same list.
   2. Is it possible to create "shared lists". For instance, the following two instructions create two lists, L1 and L2, which share the same tail (L).

         L1 := cons(1,L) ; L2 := cons(2,L)
      

      Note that if two lists have a common sublist, it is always the final part in both of them.
   3. Is it possible that a modification done on a list has a side effect on another list. In fact, if L1 and L2 are created with the two commands above, then the application of "tail" two times on L1 (i.e. "tail(tail(L1))") would deallocate the first element of L and leave dangling the pointer in the field "next" of the first element of L2.

      On the other hand, this is the only case of side-effect. If we modify the definition of "tail" by eliminating the instruction "dispose", then the implementation of the "simple lists" becomes "pure", i.e. no side-effects would be possible with the operations of the ADT.

2. Suppose that the above implementation of "simple lists" is done in a language like Pascal Standard or C, which do not offer a mechanism for data protection.
   1. Would the creation of circular lists, shared lists and side effects be possible?
   2. Would it be possible to create lists with multiple links in their elements, for instance tree-like structures or two-dimentional structures?

   Solution

   1. All of the above would be possible without data protection. In fact, nothing would prevent to access the elements via the usual operations on records. Thus for instance we could create a circular list with a command of the form

         L^.next := L
      

      We could also have different forms of side-effects. For instance, if we create L1 and L2 like above, with the commands:

         L1 := cons(1,L) ; L2 := cons(2,L)
      

      and then we perform the command

         L1^.next^.info := L1^.next^.info + 1 
      

      this would modify also the content of the field "info" of the second element of L2.
   2. In the given implementation it would not be possible to create lists containing elements with multiple links, since this would violate the type declared for the element of a list (a record with only one field of type pointer). Note that Pascal would allow for a different implementation of lists, using variant records, were the number of links in an element could vary.
3. Describe briefly the advantages of having a mechanism for data protection.

   Solution

   The main advantages are
   1. Independence from implementation of the ADT: Even if the implementation of the ADT will change, the programs which use the ADT need not to change.
   2. Preservation of the properties of the ADT described in the specification. This would be useful to study the correcteness of the program, i.e. to ensure that the program gives the expected results.
   (I have listed here the main advantages I know of, maybe there are other advantages too.)
4. What are the mechanism offered in Modula 2 and in C++ for data protection?

   Solution

   • In Modula 2 we have the possibility of encapsulating an ADT in a "module" specification. Such specification includes the declaration of the set of operations that can be performed on the elements of the ADT being defined (interface). The elements of the ADT cannot be accessed (externally to the module) in any other way.
   • In C++ we have the possibility of encapsulating an ADT in a "class" specification. For each member of the class, it is possible to declare whether the member is "public", "protected", or "private". Externally to the class, we cannot use the private and the protected members (unless we are in a friend class, or we are in a subclass and the member is protected).