DynamicTypeSet

Author: Matthias Konrad

CAT-Call freeness detection algorithms

Finding out, whether any given Eiffel system contains a CAT call is undecidable. A CAT call finding algorithm will thus make one or both of the following error kinds:

• Kind A: Report a system that has no CAT-call as NOT CAT-call free.
• Kind B: Report a system containing CAT-calls as CAT-call free.

Algorithms making errors of kind B are of no use. An algorithm that only makes errors of kind A leads to type safety, but may be useless if it makes too many (the trivial algorithm, that reports every Eiffel system as NOT CAT-call free makes no errors of Kind B but is completely useless). The goal is thus to find the maximal (or most reasonable) subclass of the class of CAT-call free Eiffel systems that is decidable and fast enough to be used in practice.

Dynamic type set algorithm

The Dynamic type set algorithm (DTSA) as defined in ETL2 (combined with a system validity check) seems to make no errors of kind B (it remains to be proven) but certainly of kind A. By showing some of these errors we try to show what impact the DTSA has to the Eiffel language. The following system will be used for examples:

class
   LIST_ANY
feature
   put (i: ANY) is
      do
         item := i
      end
   item: ANY
end

class
   LIST_STRING
inherit
   LIST_ANY
      redefine put, item end
feature
   put (i: STRING) is
      do
         i.to_lower
      end	
   item: STRING
end

DTSA does not work well with generic algorithms. See feature merge, that merges the list f into the list t:

merge (f, t: LIST [ANY]) is
   do
      from f.start until f.after loop
         t.extend (f.item)   --f.G <= t.G
         f.forth
      end
   end

This feature might be used frequently in a bigger system. As a consequence, the dynamic type sets of both arguments become large. It is not the performance problem that interests us here, but the fact that the feature will become invalid very fast. A system containing the following two calls to merge (even if the calls are not in the same feature or even class) will invalidate the system:

merge (create {LINKED_LIST [STRING]}.make, create {LINKED_LIST [STRING]}.make)
merge (create {LINKED_LIST [ANY]}.make, create {LINKED_LIST [ANY]}.make)

I consider this a strong error of kind A, since it obviously takes power (genericity) from the language.

Feature merge works with lots of dynamic types. But it depends on one thing, the actual generic parameter of argument f needs to be equally or more specific compared to the actual generic parameter of argument t. This constraint should be detected by an algorithm and made an obligation for every caller of merge.

A better algorithm should detect what feature merge depends on to work properly.

One weakness of the DTSA is, that the dynamic type sets of arguments of often used types become huge. This indirectly leads to many errors of kind A as the following example shows:

foo is
   local
      l1: LIST_ANY
      l2: LIST_STRING
   do
      create l1
      l1.put ("")
      double_list (l1)
 
      create l2
      l2.put ("")
      double_list (l2)
   end

double_list (l: LIST_ANY) is  -- backward obligation: l.put.item >= l.item
   do
      l.put (l.item)          
   end
 
merge_list (from_list, to_list: LIST_ANY)   --backward obligation: to_list.put.item >= from_list.start
   do
      to_list.put (from_list.start)
   end
 
add_to_list (list: LIST_ANY; elem: ANY)   --backward obligation: list.put.item >= elem
   do
      list.put (elem)
   end

The dynamic type set of argument i of feature put of type LIST_ANY becomes {INTEGER, STRING}. Same thing for attribute item of type LIST_ANY. DTSA will thus fail to report this system as CAT-call free.

can make two kinds of errors

But it is easy to come up with an algorithm that detects for a subset of all CAT-call free Eiffel systems that they are CAT-call free 
  * detects a subset of all CAT-call free

But for some systems it is easy to show, that they are CAT call free.

The challenge is thus to find the So DTSA cannot do that, it will correctly declare some Eiffel systems as CAT call free