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 incomplète, il est nécessaire d'utiliser la récursion pour réaliser 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 (non terminale)
    throw new UnsupportedOperationException();
  }
}

Lorsqu'on construit de manière répétée une union avec une branche gauche très longue, il devient impossible d'itérer : 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 renforcer l'interface pour permettre de coder une itération d'une manière non récursive.

Cf. l'interface 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 implémenter l'itérateur 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 courant = this; // Invariant : !courant.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.
      if(courant.estCons()){ 
        // Cons(e, r) décomposé en (e, r)
        this.reste = courant.reste();
        this.element = courant.element();
        return;
      }else{ // Union(g, d)
        if(courant.gauche().estVide()){ 
          courant = courant.droit(); 
          // g vide : passage à d
        }else if(courant.gauche().estCons()){ 
          // Union (Cons(e, r), d) décomposé en (e, Union(r, d))
          this.reste = courant.gauche().reste().union(courant.droit());
          this.element = courant.gauche().element();
          return;
        }else{
          // passage de Union(Union(g, d'), d) à Union(g, Union(d', d)) 
          courant = courant.gauche().gauche().union(
                       courant.gauche().droit().union(courant.droit()));
        }
      }
    }
  }
  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.

Remarque : 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.