Forget / Keep Mechanism

Warning: Warning: Article under development

Introduction

By allowing covariant feature redefinition and hiding of features, the Eiffel language introduces the problem of cat-calls (Changed Availability or Type). The forget / keep mechanism prevents this by introducing new derived types whenever a feature is covariantly redefined or the export status is restricted. These derived types are then used to prevent cat-calls through the conformance rules to the original types.

Example classes

The following classes will be used for illustration:

class ANIMAL
 
feature
 
  eat (f: FOOD)
 
  sleep
 
end

class CAT
 
inherit
 
  ANIMAL
    redefine
      eat
    export
      {NONE} sleep
    end
 
feature
 
  eat (f: CAT_FOOD)
 
end

class FOOD
 
end
 
 
class CAT_FOOD
 
inherit
 
  FOOD
 
end

class LIST [G]
 
feature
 
  has (g: G): BOOLEAN
 
  put (g: G)
 
  item: G
 
end

The problem

The problem of cat-calls has two variants, one because a feature is covariantly redefined:

local
  a: ANIMAL
  c: CAT
  food: FOOD
do
 
  a := c
    -- illegal since `eat' for type CAT takes arguments only of type CAT_FOOD
  a.eat (food)
 
end

And one because the visibility of features change:

local
  a: ANIMAL
  c: CAT
do
 
  a := c
    -- `sleep' is hidden for type CAT and should not be called
  a.sleep
 
end

The idea

To solve the problem of cat-calls, the idea is that whenever you covariantly redefine a feature of a parent type, you don't actually inherit this feature and redefine it, but you inherit from a parent type which does not have this feature at all. The same goes for changing the export status. When you restrict the export status of a feature, you don't inherit this feature from the parent but introduce it in the current type and inherit from a parent which does not know this feature at all.

As a consequence of this, the types as we know them don't necessarily conform to each other. If the type CAT inherits from the type ANIMAL but covariantly redefines the feature eat than the type CAT does not conform to ANIMAL anymore, but only to a type ANIMAL without the feature eat.

This gives two corner cases, the first one is a type which keeps all features even if they get covarianlty redefined by other types. We call this type the keep all type since it keeps all features. All features defined in the class can be called on an instance of this type, but all subtypes which have a covariantly redefined feature or change an export status of a feature don't conform to the keep all type anymore.

The second case is a type which looses all feature which get covariantly redefined later on or whose export status is restricted. This type is called the forget all type since it forgets all problematic features. All subtypes will conform to this type even if they covariantly redefine a feature or change the export status. Since this type forgets all of these features, they cannot be called on such an instance.

Forget mechanism

The forget mechanism introduces a new keyword forget which can be used to remove covarianlty redefined features and features which change the export status. By removing features, a new type is introduced. The new type has all features the original type has except those listed in the forget clause. If forget all is used, all features which are covariantly redefined or have a changed export status will be removed from the new type.

Default behavior

In the forget mechanism the normal declaration of a type will keep all covariantly redefined features or features whose export status is restricted (keep all type). This implies that all subtypes which change an export status or covariantly redefine a feature don't conform to this type anymore.

local
    -- normal declaration means 'keep all'
  animal: ANIMAL
  cat: CAT
do
    -- legal since the feature `eat' is kept in the normal type
  animal.eat (food)
 
    -- legal since the feature `sleep' is kept in the normal type
  animal.sleep
 
    -- illegal since CAT does not conform to ANIMAL (keep all) anymore
  animal := cat
end

Syntax

-- normal declaration is an object with all features (keep all) and no
  -- subtype which has a covariantly redefined feature conforms to this type
a1: ANIMAL
 
  -- a type which forgets all covariantly redefined features, thus all 
  -- subtypes conform to this type. This is also called a 'poly' type
a2: ANIMAL forget all end
 
  -- a type which only forgets the features `eat' and `sleep' but not other
  -- covarianlty redefined features or features whose export status is
  -- restricted. all subtypes which only redefine or change export status 
  -- of `eat' or `sleep' will conform to this type
a3: ANIMAL forget eat, sleep end

Conformance

The conformance between ANIMAL, ANIMAL forget eat, ANIMAL forget sleep and ANIMAL forget all is as follows:

local
  normal_animal: ANIMAL
  forget_eat_animal:   ANIMAL forget eat end
  forget_sleep_animal: ANIMAL forget sleep end
  forget_all_animal:   ANIMAL forget all end
 
    -- this is equivalent to the forget all clause as long as
    -- no other features of ANIMAL are covarianlty redefined
  forget_eat_sleep_animal: ANIMAL forget eat, sleep end
do
    -- these assignments are legal since all features present in the
    -- forget types are also present in the normal type
  forget_eat_animal   := normal_animal
  forget_sleep_animal := normal_animal
  forget_all_animal   := normal_animal
 
    -- these assignment are illegal since the forget types lack
    -- at least one feature and thus cannot be used as an ANIMAL
  normal_animal := forget_eat_animal
  normal_animal := forget_sleep_animal
  normal_animal := forget_all_animal
 
    -- these assignments are legal since the forget all type
    -- has fewer or equal features than the other forget types
  forget_all_animal := forget_eat_animal
  forget_all_animal := forget_sleep_animal
 
    -- these assignments are illegal since the forget all type
    -- lacks one feature that the other types has (eat or sleep
    -- respectively)
  forget_eat_animal := forget_all_animal
  forget_sleep_animal := forget_all_animal
 
    -- these assignments are illegal since both types lack
    -- a feature which the other type has
  forget_eat_animal := forget_sleep_animal
  forget_sleep_animal := forget_eat_animal
 
end

Keep mechanism

The keep mechanism is the contrary to the forget mechanism. It introduces a new keyword keep which can be used to keep covarianlty redefined features and features which change the export status.

Default behavior

In the keep mechanism the normal declaration of a type will loose all covariantly redefined features or features whose export status is restricted (forget all type). This implies that all subtypes still conform to a normally declared type, but all covariantly redefined features will not be available.

local
    -- normal declaration means 'forget all'
  animal: ANIMAL
  cat: CAT
do
    -- illegal since the feature `eat' is covariantly redefined
  animal.eat (food)
 
    -- illegal since the feature `sleep' changes export status
  animal.sleep
 
    -- legal since animal has no problematic features
  animal := cat
end

Syntax

-- normal declaration is an object which forgets all covariantly
  -- redefined features. all subtypes conform to this type
b1: ANIMAL
 
  -- a type which keeps all features and looses conformance from subtypes which
  -- covariantly redefine features. this is also called 'mono'
b2: ANIMAL keep all end
 
  -- a type where all subtypes conform except those who covariantly redefine
  -- feature `eat'
b3: ANIMAL keep eat end

Conformance

The conformance between ANIMAL, ANIMAL keep eat, ANIMAL keep sleep and ANIMAL keep all is as follows:

local
  normal_animal: ANIMAL
  keep_eat_animal:   ANIMAL keep eat end
  keep_sleep_animal: ANIMAL keep sleep end
  keep_all_animal:   ANIMAL keep all end
 
    -- this is equivalent to the keep all clause as long as
    -- no other features of ANIMAL are covarianlty redefined
  keep_eat_sleep_animal: ANIMAL keep eat, sleep end
do
 
    -- these assignments are illegal since the normal ANIMAL type
    -- does not have the eat or sleep features
  keep_eat_animal   := normal_animal
  keep_sleep_animal := normal_animal
  keep_all_animal   := normal_animal
 
    -- these assignment are legal since the normal type has
    -- fewer features than the keep types
  normal_animal := keep_eat_animal
  normal_animal := keep_sleep_animal
  normal_animal := keep_all_animal
 
    -- these assignments are illegal since the keep all type
    -- has more features than the other keep types
  keep_all_animal := keep_eat_animal
  keep_all_animal := keep_sleep_animal
 
    -- these assignments are legal since the keep all type
    -- has more features than the other keep types
  keep_eat_animal := keep_all_animal
  keep_sleep_animal := keep_all_animal
 
    -- these assignments are illegal since both types lack
    -- a feature which the other type has
  keep_eat_animal := keep_sleep_animal
  keep_sleep_animal := keep_eat_animal
 
end

Covariant feature redefinition

Cat-call problem

With covariant feature redefinition you run into cat-call problems as this example shows:

local
  a: ANIMAL
  c: CAT
  food: FOOD
do
 
  a := c
    -- eat for type CAT takes arguments only of type CAT_FOOD
  a.eat (food)
 
end

With forget mechanism

With the forget mechanism the default behavior for a type is to keep all problematic features. Types which have covariant redefined features will not be conform to the normal type. A feature which is covariantly redefined changes its inherit clause implicitly to inherit from a parent class which has the redefined feature in a forget clause.

class CAT
 
inherit
 
  ANIMAL
    redefine
      eat
    end
 
feature
 
  eat (f: CAT_FOOD)
 
end

class CAT
 
inherit
 
  ANIMAL forget eat
    redefine
      eat
    end
 
feature
 
  eat (f: CAT_FOOD)
 
end

Now the cat-call example with the new forget types:

local
  a: ANIMAL
  c: CAT
do
    -- illegal assignment, ANIMAL and CAT don't conform
    -- since CAT implicitly inherits from ANIMAL forget eat
  a := c
  a.eat (food)
 
end

local
  a: ANIMAL forget all end
  c: CAT
do
    -- legal, CAT conforms to ANIMAL forget all
  a := c
 
    -- illegal, ANIMAL forget all doesn't have a feature eat
  a.eat (food)
 
end

With keep mechanism

With the keep mechanism the default behavior of a type is to loose all problematic features. Thus when a type covariantly redefines a feature, this implicitly changes the parent to loose this feature by default.

class CAT
 
inherit
 
  ANIMAL
    redefine
      eat
    end
 
feature
 
  eat (f: CAT_FOOD)
 
end

Now the cat-call example with the new types:

local
  a: ANIMAL
  c: CAT
do
  a := c
    -- illegal call since the type ANIMAL does not have a feature `eat' anymore
  a.eat (food)
 
end

local
  a: ANIMAL keep all end
  c: CAT
do
    -- illegal, CAT does not conform to ANIMAL keep all
  a := c
 
    -- legal, ANIMAL keep all still has the feature `eat'
  a.eat (food)
 
end

Feature hiding

Cat-call problem

By restricting the export status of features, a cat-call problem is introduced:

local
  a: ANIMAL
  c: CAT
do
 
  a := c
    -- sleep is hidden for type CAT and should not be called
  a.sleep
 
end

With forget mechanism

With the forget mechanism the default behavior for a type is to keep all problematic features. Types which change the export status of features will not be conform to the normal type. A feature which has a restricted export status changes its inherit clause implicitly to inherit from a parent class which has the feature in a forget clause.

class CAT
 
inherit
 
  ANIMAL
    export
      {NONE} sleep
    end
 
end

class CAT
 
inherit
 
  ANIMAL forget sleep
    export
      {NONE} sleep
    end
 
end

Now the cat-call example:

local
  a: ANIMAL
  c: CAT
do
    -- illegal assignment, ANIMAL and CAT don't conform
    -- since CAT implicitly inherits from ANIMAL forget sleep
  a := c
  a.sleep
 
end

local
  a: ANIMAL forget all end
  c: CAT
do
    -- legal, CAT conforms to ANIMAL forget all
  a := c
 
    -- illegal, ANIMAL forget all doesn't have a feature sleep
  a.sleep
 
end

With keep mechanism

With the keep mechanism the default behavior of a type is to loose all problematic features. Thus when a type changes the export status of a feature, this implicitly changes the parent to loose this feature by default.

class CAT
 
inherit
 
  ANIMAL
    export
      {NONE} sleep
    end
 
end

Now the cat-call example:

local
  a: ANIMAL
  c: CAT
do
  a := c
    -- illegal call since the type ANIMAL does not have a feature `sleep' anymore
  a.sleep
 
end

local
  a: ANIMAL keep all end
  c: CAT
do
    -- illegal, CAT does not conform to ANIMAL keep all
  a := c
 
    -- legal, ANIMAL keep all still has the feature `sleep'
  a.sleep
 
end

Generics

Conformance of generics - two generic conform if their generic parameters conform - introduce another kind of covariantly redefined features. Every feature which has a generic argument, e.g. put (g: G) in class LIST [G] can be regarded as covariantly redefined since put in LIST [ANY] takes an argument of type ANY and put in LIST [ANIMAL] takes an argument of type ANIMAL. But LIST [ANIMAL] conforms to LIST [ANY], thus the feature put is actually covariantly redefined in LIST [ANIMAL].

Cat-call problem

The conformance rules of generics alos introduce cat-call problems:

local
    -- feature `put' has argument type ANY
  any_list: LIST [ANY]
    -- feature `put' has argument type ANIMAL
  animal_list: LIST [ANIMAL]
do
    -- animal_list conforms to any_list, but arguments of the feature
    -- `put' are different
  any_list := animal_list
 
    -- since any type can be put into any_list this will add
    -- an integer to the animal_list
  any_list.put (5)
 
end

With forget mechanism

Default is keep all types and features with generic arguments are treated as covariantly redefined.

local
  any_list: LIST [ANY]
  animal_list: LIST [ANIMAL]
do
    -- illegal since animal_list does not conform to any_list anymore
  any_list := animal_list
 
  any_list.put (5)
 
end

local
  any_list: LIST [ANY] forget all end
  animal_list: LIST [ANIMAL]
  animal: ANIMAL
do
    -- legal since animal_list conforms to LIST [ANY] forget all
  any_list := animal_list
 
    -- illegal since the forget all list does not have any features
    -- with generic arguments anymore
  any_list.put (5)
 
    -- illegal, same reason as above
  any_list.has (animal)
 
end

With keep mechanism

Default is forget all types and features with generic arguments are treated as covariantly redefined.

local
  any_list: LIST [ANY]
  animal_list: LIST [ANIMAL]
  animal: ANIMAL
do
    -- legal since any_list is 'forget all' and has no problematic features
  any_list := animal_list
 
    -- illegal since the feature 'put' is treated as covariantly redefined
    -- and thus not present in the 'forget all' type
  any_list.put (5)
 
    -- illegal, same reason as above
  any_list.has (animal)
 
end

local
  any_list: LIST [ANY] keep all end
  animal_list: LIST [ANIMAL]
do
    -- illegal since animal_list does not conform to 
    -- any_list keep all anymore
  any_list := animal_list
 
  any_list.put (5)
 
  any_list.has (animal)
 
end

Conformance

class A end
 
class B 
inherit A redefine x (covariantly) end
end
 
class C
inherit A
end

a: LIST [A]
b: LIST [A forget all end]
c: LIST [A] forget all end
d: LIST [A forget all end] forget all end
 
e: LIST [B]
f: LIST [B forget all end]
g: LIST [B] forget all end
h: LIST [B forget all end] forget all end
 
i: LIST [C]
k: LIST [C forget all end]
l: LIST [C] forget all end
m: LIST [C forget all end] forget all end

do
    -- illegal
  a := b
  b := a
 
  ...

The Java solution

With Java 1.5, generics were introduced in the language. A mechanism to prevent cat-calls with generics was introduced as well:

A tutorial

Official Sun tutorial (PDF)

An example

Consequences

Arguments with like

A declaration like Current is a covariant redefinition for all subtypes. Thus the mechanism affects all types which have such arguments and their subtypes (see also next section):

With the forget mechanism the normal type keeps all features (keep all type) but subtypes with covariant feature redefinitions will loose conformance to this type. Thus with a like Current argument in a feature f, no subtype will conform to it's parent anymore unless the parent is declared forget f.

With the keep mechanism the normal type forgets all problematic features (forget all type) and subtypes will still conform to this type. But this means that a feature f with a like Current argument will always be forgotten in a normal type and can only be used in keep f types.

ANY

ANY has the features ANY.is_equal and ANY.copy with a like Current argument:

class ANY
 
feature
 
  is_equal (other: like Current): BOOLEAN
 
  copy (other: like Current)
 
end

Since all types are descendants of ANY, all types have covariantly redefined features. Thus the both mechanisms - forget and keep - have an impact on the whole type hierarchy:

As discussed in the previous section, the forget mechanism defaults to keep all types but the subtypes don't conform to their normal parents anymore. Since ANY introduces these features, no type will conform to any parent unless the parent is declared forget is_equal, copy.

With the keep mechanism and forget all types as default, all types still conform to their parents, but the features is_equal and copy cannot be used unless a type is declared as keep is_equal, copy. This declaration allows use of the features, but you will loose conformance of all subtypes.

Solution: Remove the like Current arguments from ANY. Change the argument of is_equal and copy to type ANY. Then either introduce a precondition to require conformance of argument and object or add a type checks to the actual implementation of the features. This is actually done in the ECMA standard but not yet implemented in EiffelBase.

COMPARABLE

In the class COMPARABLE all features are defined with a like Current argument.

With the forget mechanism this means that when a class inherits from COMPARABLE, no subtype will conform to this class anymore, unless all the compare features are forgotten.

export {NONE} all

With a declaration

class A
 
inherit
 
  B
    export
      {NONE} all
    end
 
end

the type A restricts the visibility of all features of ANY through restricting the features of B.

With the forget mechanism the type A will not conform to neither B nor ANY. Moreover the types B forget all and ANY forget all will not have any features since all features are affected by a change in export status.

With the keep mechanism and the default type being forget all type, any declaration of ANY somewhere will not have any features since all features are affected by an export status restriction in the declaration of A.

Solution: Introduce the inherit {NONE} construct since most declarations of the type export {NONE} all are actually meant as non-conforming inheritance in the first place. Since no conformance between parents from a inherit {NONE} clause exists anyway, the forget / keep mechanism is not applied to these cases.

Algorithms

...

Generics

...

SET.has

...

Various problems

Let's say the class ANIMAL has some other features as well and a class SNAKE is introduced:

class ANIMAL
 
feature
 
  eat (f: FOOD)
 
  a: ANIMAL
 
  feed_a
    local
      f: FOOD
    do
      a.eat (f)
    end
 
  x
    local
      f: FOOD
    do
      eat (f)
    end
 
  y
    local
      a: ANIMAL
      f: FOOD
    do
      a.eat (f)
    end
 
  z
    local
      a: ANIMAL
    do
      a := Current
    end
 
end
 
class SNAKE
 
inherit
 
  ANIMAL
    redefine
      a
    end
 
feature
 
  a: CAT
 
end

If now CAT covariantly redefines eat the features x, y and z in class CAT are problematic. Depending on the default type (keep all or forget all) the features are not valid anymore and have to be forgotten in class CAT as well.

In class SNAKE the feature feed_a of class ANIMAL will become invalid by the redefinition of the feature a.

Conclusion