A Solutions to the Excercises

 

This section presents example solutions to the excercises of the previous lectures.

A.1 Procedural Programming

1. Integer lists.
   1. What follows is the first sketch of the interface definition file. It is similar to the general list definition file:

        #ifndef __INTLIST_H
        #define __INTLIST_H
      
        typedef intlist_handle_struct *intlist_handle_t;
      
        intlist_handle_t intlist_create();
        void intlist_destroy(intlist_handle_t this);
        int intlist_append(intlist_handle_t this, int data);
        int intlist_getFirst(intlist_handle_t this);
        int intlist_getNext(intlist_handle_t this);
        #endif

      As some of you already figured out, the type definition is not really necessary. We could rather use the already known list_handle_t definition and just define new access methods. This interface looks exactly the same as that shown above besides that:

      • the line with the typedef is deleted and
      • every occurrence of intlist_handle_t is replaced by list_handle_t.
   2. Consequences for intlist_append(). The excercise wants the append method to take an integer by value as its argument. However, the list is only able to store pointers to elements. Consequently, intlist_append() must allocate memory for each element, assign the value to the newly created pointer and appends the pointer to the list:

        int intlist_append(list_handle_t this, int data) {
          int *elementp = (int *) malloc(sizeof(int));
          *elementp = data;
          return list_append(this, elementp);
        }

      Note the use of list_append() to append the newly created element. One could say, that this new integer appending method adds additional functionality to list_append().
   3. Consequences to other methods. Problems arise with getFirst() and getNext() since it is not possible to define a termination criterion.

      One possibility is to define a special value, say -1, to fulfill the function of a ``terminator''. However, this implies that this special value cannot be used as a normal value in the list.

      Another approach is to change the prototypes of both functions to explicitly indicate the end of the list:

        int intlist_getFirst(list_handle_t this, int *data);
        int intlist_getNext(list_handle_t this, int *data);

      Both functions should return 0 (zero) as long as a value could be obtained and stored in *data. They return -1 otherwise.

      Another method which is affected by this interface choice is intlist_destroy(). This function must now release the allocated memory prior to deleting the ``raw'' list:

        void intlist_destroy(list_handle_t this) {
          int *elementp = (int *) list_getFirst(this);
          while (elementp) {
            free(elementp);
            elementp = (int *) list_getNext(this->_list);
          }
          list_destroy(this); /* Delete list portion */
        }

      Again notice the use of the general list methods list_getFirst(), list_getNext() and list_destroy().
   4. Use of a macro mechanism. One could try to imitate the call of integer list methods with macros and hide the necessary casting operations. For example, an append() method might be defined like this (due to formatting reasons this is written on two lines):

        #define intlist_append(this, data) 
          list_append(this, (void *) &data)

      This assumes, that data is of an arbitrary type. However, the replaced method must be able to build an address of the provided data element (as indicated by the ``&'' in front of data). We could now use this macro to append integer variables to the list:

        int data = 1;
        list_handle_t intlist;
        intlist_append(intlist, data);

      However, this approach introduces at least the following problems:

      • As macros are just textual replacements of their occurrences, there is no type checking performed. Thus, we could easily use another type for data without any problems.
      • The provided data items must be variables. You cannot use the macro as follows:

          intlist_append(intlist, 2);

        This is not possible due to the address operator used in the macro: What is the address of a number? (Always remember the textual replacement definition of macros!)
      • As with the general list the data items must ``live'' at least as long as the list. Otherwise a bad side effect might happen. Consider the following code fragment where the locally defined data is appended to a global list alist:

          void foo() {
            int data = 0;
            intlist_append(alist, data); 
          } /* data is destroyed! */

        When function foo() terminates, the locally allocated memory is released, hence, the memory of data is lost. Consequently, the stored pointer points to memory which is no longer valid!
2. Queue with help of general list module.
   1. The queue interface definition file is similar to the list interface definition file:

        #ifndef __QUEUE_H
        #define __QUEUE_H
      
        typedef queue_handle_struct *queue_handle_t
      
        queue_handle_t queue_create();
        void queue_destroy(queue_handle_t this);
        void *queue_get(queue_handle_t this);
        int queue_put(queue_handle_t this, void *data);
        #endif

   2. The implementation of the structure makes use of the already existing list module. However, the queue is different to the previous excercise in that it should not offer functionality of a list. Therefore, we make the list a member of the newly defined queue structure and allow access only through the use of the methods of the queue module:

        struct queue_handle_struct {
          list_handle_t _list;  /* A list is the queue */
        };

   3. The queue methods get() and put() are now implemented with help of the list methods:

        void *queue_get(queue_handle_t this) {
          void *datap = list_getFirst(this->_list);
          list_delFromFront(this->_list);
          return datap;
        }
      
        int queue_put(queue_handle_t this, void *data) {
          return list_append(this->_list, data);
        }

A.2 Abstract Data Types

1. ADT Integer.
   1. Both operations add and sub can be applied for whatever value is hold by N. Thus, these operations can be applied at any time: There is no restriction to their use. However, you can describe this with a precondition which equals true.
   2. We define three new operations as requested: mul, div and abs. The latter should return the absolute value of the integer. The operations are defined as follows:

        mul(k)
        div(k)
        abs()

      The operation mul does not require any precondition. That's similar to add and sub. The postcondition is of course res = N*k. The next operation div requires k to be not 0 (zero). Consequently, we define the following precondition: k not equal 0. The last operation abs returns the value of N if N is positive or 0 or -N if N is negative. Again it does not matter what value N has when this operation is applied. Here is its postcondition:

      if N >= 0 then

      abs = N

      else

      abs = -N

2. ADT Fraction.
   1. A simple fraction consists of numerator and denominator. Both are integer numbers. This is similar to the complex number example presented in the section. We could choose at least two data structures to hold the values: an array or a record.
   2. Interface layout. Remember that the interface is just the set of operations viewable to the outside world. We could describe an interface of a fraction in a verbal manner. Consequently, we need operations:
      • to get the value of nominator/denominator,
      • to set the value of nominator/denominator,
      • to add a fraction returning the sum,
      • to subtract a fraction returning the difference,
      • ...
   3. Here are some axioms and preconditions for each fraction which also hold for the ADT:
      • The denomitator must not equal 0 (zero), otherwise the value of the fraction is not defined.
      • If the nominator is 0 (zero) the value of the fraction is 0 for any value of the denominator.
      • Each whole number can be represented by a fraction of which the nominator is the number and the denominator is 1.
3. ADTs define properties of a set of instances. The provide an abstract view to these properties by providing a set of operations which can be applied on the instances. It is this set of operations, the interface, which defines properties of the instances. The use of an ADT is restricted by axioms and preconditions. Both define conditions and properties of an environment in which instances of the ADT can be used.
4. We need to state axioms and to define preconditions to ensure the correct use of instances of ADTs. For example, if we do not declare 0 to be the neutral element of the addition of integers, there could be an ADT Integer which do something weird when adding 0 to N. This is not what is expected from an integer. Thus, axioms and preconditions provide a means to ensure that ADTs ``function'' as we wish them to.
5. Description of relationships.
   1. An instance is an actual representative of an ADT. It is thus an ``example'' of it. Where the ADT declare to use a ``signed whole number'' as its data structure, an instance actually holds a value, say, ``-5''.
   2. Generic ADTs define the same properties of their corresponding ADT. However, they are dedicated to another particular type. For example, the ADT List defines properties of lists. Thus, we might have an operation append(elem) which appends a new element elem to the list. We do not say of what type elem actually is, just that it will be the last element of the list after this operation. If we now use a generic ADT List the type of this element is known: it's provided by the generic parameter.
   3. Instances of the same generic ADT could be viewed as ``siblings''. They would be ``cousins'' of instances of another generic ADT if both generic ADTs share the same ADT.

A.3 Object-Oriented Concepts

1. Class.
   1. A class is the actual implementation of an ADT. For example, an ADT for integers might include an operation set to set the value of its instance. This operation is implemented differently in languages such as C or Pascal. In C the equal sign ``='' defines the set operation for integers, whereas in Pascal the character string ``:='' is used. Consequently, classes implement operations by providing methods. Similarly, the data structure of the ADT is implemented by attributes of the class.
   2. Class Complex

        class Complex {
        attributes:
          Real real,
               imaginary
      
        methods:
          :=(Complex c)    /* Set value to the one of c */
          Real realPart()
          Real imaginaryPart()
          Complex +(Complex c)
          Complex -(Complex c)
          Complex /(Complex c)
          Complex *(Complex c)
        }

      We choose the well-known operator symbols ``+'' for addition, ``-'' for subtraction, ``/'' for division and ``*'' for multiplication to implement the corresponding operations of the ADT Complex. Thus, objects of class Complex can be used like:

        Complex c1, c2, c3
        c3 := c1 + c2

      You may notice, that we could write the addition statement as follows:

        c3 := c1.+(c2)

      You may want to replace the ``+'' with ``add'' to come to a representation which we have used so far. However, you should be able to understand that ``+'' is nothing more than a different name for ``add''.

2. Interacting objects.
3. Object view.
4. Messages.
   1. Objects are autonomous entities which only provide a well-defined interface. We'd like to talk of objects as if they are active entities. For example, objects ``are responsible'' for themselves, ``they'' might deny invocation of a method, etc.. This distinguishes an object from a module, which is passive. Therefore, we don't speak of procedure calls. We speak of messages with which we ``ask'' an object to invoke one of its methods.
   2. The Internet provides several objects. Two of the most well known ones are ``client'' and ``server''. For example, you use an FTP client (object) to access data stored on an FTP server (object). Thus, you could view this as if the client ``sends a message'' to the server asking for providing data stored there.
   3. In the client/server environment we really have two remotely acting entities: the client and server process. Typically, these two entities exchange data in form of Internet messages.