Impact de la définition d'une interface sur l'itération

Pour réaliser un itérateur sans utiliser la récursion, il est nécessaire d'avoir une interface suffisamment complète. C'est un impératif en Java qui n'optimise pas la récursion terminale.

Cf. Wikipedia pour la définition de la récursion terminale ("tail recursion" en anglais).

Exemple : implémentation d'ensembles. Cf. le paquet ensembles.

Dans le premier exemple avec une interface rudimentaire, il est extrêmement simple d'utiliser la récursion pour réaliser la décomposition permettant l'itération.

class Union1 implements Ensemble1 {
  private Ensemble1 gauche;
  private Ensemble1 droit;
  ...
  public int element() {
    if(!this.gauche.estVide())
      return this.gauche.element(); // Récursion (terminale)
    if(!this.droit.estVide())
      return this.droit.element(); // Récursion (terminale)
    throw new UnsupportedOperationException();

  }
  public Ensemble1 reste() {
    if(!this.gauche.estVide())
      return new Union1(this.gauche.reste(), this.droit); 
        // Récursion (non terminale)
    if(!this.droit.estVide())
      return this.droit.reste();
        // Récursion (terminale)
    throw new UnsupportedOperationException();
  }
}

Cependant, lorsqu'on construit de manière répétée une union avec une branche gauche très longue, il devient impossible de décomposer : lors de l'exécution, la taille maximale de la pile est atteinte, car la machine virtuelle de Java empile tous les appels, y compris lorsque la récursion est terminale, où elle pourrait simplement remplacer le précédent appel par le nouveau.

La solution est de transformer la récursion en une itération, qui ne fait pas grossir la taille de la pile. Cependant, avec une interface rudimentaire, il n'est pas simple de programmer itérativement et non récursivement la décomposition, beaucoup moins simple que récursivement. En effet, la récursion bénéficie de sélecteurs implicites grâce à la liaison dynamique : lors d'un appel, le code est choisi suivant le type dynamique de l'objet cible, réalisant ainsi la sélection. Itérativement, il est nécessaire de programmer la sélection manuellement. On aboutit ainsi à du code qui contient de nombreuses maladresses pouvant conduire à des erreurs et à un manque de modularité :

utilisation de instanceof, ce qui impose de mentionner les classes d'implémentation,
utilisation de conversions d'un type vers un sous-type, qui ne sont pas sûres, sont peu lisibles et imposent de mentionner les classes d'implémentation.

Il est donc particulièrement utile de compléter l'interface pour permettre de coder la décomposition d'une manière non récursive.

Cf. les interfaces Ensemble1 et Ensemble2 dans l'unité de compilation EnsemblesIterables.

L'interface peut se construire d'une manière systématique à partir de la définition inductive. Il suffit d'y ajouter tous les sélecteurs, destructeurs et constructeurs (méthodes de fabrication) induits par la définition inductive du type.

Ensemble ::= Vide | Cons(Element, Ensemble) | Union(Ensemble, Ensemble)

Interface Ensemble
Trois classes d'implémentation, une par cas

Interface Ensemble :

des méthodes de fabrication : une par cas

Ensemble vide();
Ensemble cons(int n, Ensemble ens);
Ensemble union(Ensemble ens);

des sélecteurs : un par cas
```
boolean estVide();
boolean estCons();
boolean estUnion();
```
En théorie, les sélecteurs s'excluent mutuellement. Cependant, le sens intuitif de estVide() correspond plutôt à la vacuité de l'ensemble sous-jacent. Or une union peut être vide : il n'y a plus exclusion mutuelle. Dans l'exemple, on choisit l'interprétation intuitive, implémentée en utilisant une autre méthode taille(), calculant la taille de l'ensemble. Les trois sélecteurs s'excluant mutuellement s'obtiennent finalement ainsi :
```
estVide() && !estUnion(),
estCons(), 
estUnion().
```

des destructeurs : un destructeur par argument d'un cas

// Cas Cons
int element();
Ensemble reste();
// Cas Union
Ensemble gauche();
Ensemble droit();

Avec cette définition, on peut facilement implémenter la décomposition sans recours à la récursion.

class Union implements Ensemble {
  private Ensemble gauche;
  private Ensemble droit;
  private int taille;
  // Nouveaux attributs utilisés pour mémoriser la décomposition
  //   (à réifier et externaliser en utilisant le patron Itérateur) 
  private int element;
  private Ensemble reste;
  ...
  // Décomposition avec mémorisation pour éviter de refaire ce long calcul
  private void decomposer(){
    // Precondition : !this.estVide()
    Ensemble unionCourante = this; // Invariant : !unionCourante.estVide()
    while(true){
      // A chaque itération, 
      // - on préserve la valeur ensembliste de courant, et
      // - ou bien on réduit l'expression décrivant l'ensemble,
      // - ou bien on réduit l'expression gauche, après réorganisation
      //   de l'expression.
      // unionCourante = Union(g, d)
      if(!unionCourante.gauche().estVide()){
        Ensemble courant = unionCourante.gauche(); // courant = g (non vide) 
        if(courant.estCons()){ // courant = Cons(e, r)
          this.reste = courant.reste().union(unionCourante.droit()); // this.reste = Union(r, d) 
          this.element = courant.element(); // this.element = e
          return; // FIN
        }else{ // courant.estUnion() courant = Union(gg, gd) 
           unionCourante = courant.gauche().union(courant.droit().union(unionCourante.droit()));
             // unionCourante = Union(gg, Union(gd, d) (= Union(g, d))
        }
      }else if(!unionCourante.droit().estVide()){ // unionCourante = Union(Vide, d)
        Ensemble courant = unionCourante.droit(); // courant = d (non vide)
        if(courant.estCons()){ // courant = Cons(e, r)
          this.reste = courant.reste(); // this.reste = r
          this.element = courant.element(); // this.element = e
          return; // FIN
        }else{ // courant.estUnion() courant = Union(dg, dd)
          unionCourante = courant; // unionCourante = d
        }
      }
    }
  }
  public int element() {
    if(this.estVide()){
      throw new UnsupportedOperationException();
    }
    if(this.reste != null){
      return this.element;
    }
    decomposer(); 
    return this.element;
  }
  public Ensemble reste() {
    if(this.estVide()){
      throw new UnsupportedOperationException();
    }
    if(this.reste != null){
      return this.reste;
    }
    decomposer();
    return this.reste;
  }

On peut conclure en incluant dans l'interface une méthode retournant un itérateur. Cf. l'unité de compilation EnsemblesIterablesAvecIterateur.

Comparaison avec les langages fonctionnels. Dans un langage fonctionnel, l'interface d'un type inductif est complète par construction. Les sélecteurs et les destructeurs sont inclus dans le mécanisme de filtrage ("pattern matching") alors que les constructeurs sont inclus dans la définition du type de données. La récursion terminale est généralement optimisée. La question peut alors se ramener à celle de l'élimination de la récursion non terminale, qui doit être transformée en récursion terminale. Il existe des méthodes générales pour cette transformation, fondées sur des continuations : le principe est d'empiler successivement les traitements à réaliser au retour de chaque appel récursif puis de réduire la pile en dépilant chaque traitement pour l'appliquer.

Cf. fonctions.EliminationRecursion pour un exemple.

Recommandation finale.

A partir d'une définition inductive d'un type, construire une interface complète, formée des sélecteurs, des destructeurs et des constructeurs.
Programmer de manière récursive.
En cas de problème d'efficacité (dépassement de la taille maximale de la pile), définir une implémentation itérative, sans récursion.
Utiliser l'implémentation récursive comme un oracle pour les tests.