Difference between revisions of "DynamicTypeSet"
m (→Dynamic type set algorithm) |
m (→Dynamic type set algorithm) |
||
| Line 8: | Line 8: | ||
====Dynamic type set algorithm==== | ====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 | + | 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: |
{|border="0" cellpadding="2" cellspacing="0" align="center" | {|border="0" cellpadding="2" cellspacing="0" align="center" | ||
|-valign="top" -halign="center" | |-valign="top" -halign="center" | ||
| | | | ||
| − | + | class | |
| − | class | + | LIST_ANY |
| − | + | ||
feature | feature | ||
| − | + | put (i: ANY) is | |
| + | do | ||
| + | item := i | ||
| + | end | ||
| + | item: ANY | ||
end | end | ||
| − | |||
| | | | ||
<code>[eiffel,N] | <code>[eiffel,N] | ||
| − | class | + | class |
| − | + | LIST_STRING | |
inherit | inherit | ||
| − | + | LIST_ANY | |
| + | redefine put, item end | ||
feature | feature | ||
| − | + | put (i: STRING) is | |
| − | + | ||
do | do | ||
| − | + | i.to_lower | |
end | end | ||
| + | |||
| + | item: STRING | ||
end | end | ||
</code> | </code> | ||
Revision as of 14:53, 10 November 2006
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.
An algorithm that makes errors of kind B is of no use. An algorithm that only makes errors of kind A leads to type safety. But too many errors of kind A limit its useless (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 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 |
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
