DynamicTypeSet

Author: Matthias Konrad

Warning: Warning: Article under development

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.

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])
   require
      f /= Void
      t /= Void
      --f.G <= t.G
   do
      from f.start until f.after loop
         t.extend (f.item) 
         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 be reported as invalid:

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.

Why does the DTSA fail for the merge methode

Proof obligation based algorithm

Feature merge works with lots of dynamic types. It depends on one thing tough, 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. In Eiffel an obligation made to a caller is a precondition.

Rule 1

For calls of the form:

t.f (a)

where feature the first formal argument of feature f is of generic type G the following obligation follows: a <= t.G, a needs to be more specific than the

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.

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
         item := i
      end	
   item: STRING
end