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

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 :

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.

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