UP | HOME

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 (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 :

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.

Version history: v1: 2015-11-02; v2: 2016-10-24[update].
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.