• l'expression contient une unique référence à la clause elle-même (ou une unique référence de profondeur supérieure ou égale à p dans le cas d'une normalisation partielle) et cette référence correspond à une dépendance uniforme (les paramètres de structure du programme sont considérés comme étant des constantes) ;
• il est possible de tirer de l'expression une fonction binaire associative.

Considérons le système suivant :

a : { i | 1 <= i <= n } of real ;
b : { i | 1 <= i <= n } of real ;
v : { i, j | 1 <= i <= n, 1 <= j <= 2 } of real ;
v[i,j] = case
           { i, j | j = 2 }          : a[i] ;
           { i, j | i = 1, j = 1 }   : b[1, 1] ;
           { i, j | i >= 2 , j = 1 } : v[i - 1, 2] + b[i] ;
         esac

La troisième clause de l'équation v semble définir une récurrence calculée suivant la première dimension. Ce n'est qu'une illusion vu que la référence à v dans cette clause désigne constamment la seconde clause de l'équation. D'ailleurs, si le graphe des clauses a été choisi pour la détection, cette clause n'est pas explorée puisqu'elle ne porte pas de boucle.

• le domaine d'accumulation D est l'enveloppe convexe de l'union de D_c avec son image par la translation de vecteur -e ;
• la direction e est calculée par la formule z-I(z), le point z peut être choisi de façon quelconque dans D_c puisque I est uniforme ;
• l'équation g est tout simplement une référence au tableau v avec une transformation d'indices égale à l'identité. Le domaine de définition de g est l'enveloppe convexe de l'intersection de D_c avec son image par la translation de vecteur -e.

Preuve:

Le tableau u calculé par l'opérateur est :

" zÎ D, u(z)=

ì ï í ï î

si z=min D   e (z) g(z) sinon f(z,u(z-e))  .

Démontrons tout d'abord que le domaine D est l'ensemble des points entiers contenus dans :

E={ z-l e  | zÎ D_c, lÎ[0,1] }  .

Cet ensemble contient tous les éléments de D_c et de son translaté par -e (il suffit de prendre l dans {0,1}). L'ensemble E est convexe car il contient le milieu de deux de ses éléments. En effet soient a et b ces éléments il existe deux points z et z' de D_c et deux réels l et µ dans [0,1] tels que :

a=z-l e  et  b=z'-µ e  .

Le milieu de a et b est :

a+b 2

=

z+z' 2

-

l+µ 2

e  .

Le milieu de z et z' est bien un point du convexe D_c et l+µ/2 est bien un réel de [0,1]. En conséquence D est inclus dans E. De plus tout point de E est un barycentre d'un z élément de D_c et de z-e élément de l'image translatée. Donc D est l'ensemble des points entiers de E. Ce résultat est important car il assure que min_e ^D(z) avec zÎ D_c est un élément de la translation de D_c par e. D'après la définition de min_e ^D c'est forcément un point de la translation de D_c qui n'est pas dans D_c. Donc D_c est inclus dans D-min_e ^D( D_c). Or sur ce domaine u(z)=f(z,u(z-e)). Comme, de plus, sur min_e ^D( D_c) l'équation d'initialisation est égale à v, il vient :

" zÎ D_c, u(z)=exp_c(z)  .

---

Nous allons montrer, à partir du programme ci-dessous, comment notre méthode prend en compte les scans uni-directionnels.

x(0)=0                    (v1)
DO i=1,2*n
 save(i)=x(2*n-i+1)       (v2)
 x(i)=x(i-1)+save(i)      (v3)
END DO

Le système automatiquement extrait de ce programme est (voir la section 7.1.1 pour plus de détails) :

v1 : real ;
v2 : { i | 1 <= i <= 2*n } of real ;
v3 : { i | 1 <= i <= 2*n } of real ;

v1 = 0 ;
v2[i] = case
         { i | 1 <= i <= n }     : x[2*n-i+1] ;
         { i | n+1 <= i <= 2*n } : v3[2*n-i+1] ;
        esac ;
v3[i] = case
         { i | i = 1 }  : v1 + v2[i] ;
         { i | i >= 2 } : v3[i-1] + v2[i] ;
        esac ;

Pour cet exemple une normalisation moyennement efficace suffit. Nous allons donc travailler sur le graphe des équations et tenter une normalisation en une seule passe. Le graphe des équations du système est :

Tous les circuits passent par v3, la normalisation par substitutions va donc simplement consister à remplacer, dans v3 les références à v1 et v2 par les expressions de ces équations.

v3 : { i | 1 <= i <= 2*n } of real ;

v3[i] = case
         { i | i=1 }         : 0 + x[2*n-i+1] ;
         { i | 2<=i<=n }     : v3[i-1] + x[2*n-i+1] ;
         { i | n+1<=i<=2*n } : v3[i-1] + v3[2*n-i+1] ;
        esac ;

Ce système est fatalement normalisé puisqu'il ne contient plus qu'une seule équation. La détection des scans, par simple examen des clauses, peut être appliquée. La première clause ne contient pas d'auto-référence ; elle est éliminée. La seconde contient une unique référence à elle-même (i.e. à v3.1). De plus une fonction binaire et associative peut être extraite de la fonction de propagation : l'addition. La clause est donc bien un scan. La dernière clause aussi car elle contient une auto-référence (i.e. v3[i-1] référence v3.2) et une référence à une autre clause (i.e. v3[2*n-i+1] référence v3.1). Le système après introduction des opérateurs Scan s'écrit :

v3 : { i | 1 <= i <= 2*n } of real ;

v3[i] = case
         { i | i=1 }         : 0 + x[2*n-i+1] ;
         { i | 2<=i<=n }     : Scan( { i' | 1<=i'<=n }, ( [1] ),
                                     +, x[2*n-i'+1], v3 )[i] ;
         { i | n+1<=i<=2*n } : Scan( { i' | n<=i'<=2*n }, ( [1] ),
                                     +, v3[2*n-i'+1], v3 )[i] ;
        esac ;

Si ce résultat est transcrit en utilisant les notations standards (la transcription est manuelle mais pourrait facilement être automatisée), nous constatons que le programme calcule une somme pondérée :

v3

(2n)=

n å i=1

((n-i+2)×x(2n-i+1))  .

Donc le programme peut être utile pour calculer l'espérance d'une variable aléatoire discrète. De plus le programme séquentiel est efficace puisqu'aucune multiplication n'est utilisée. Les méthodes classiques de détection de réductions ne peuvent pas traiter cet exemple. En effet la dépendance i® 2n-i+1 inhibe la phase de normalisation des boucles de [47]. De plus l'évaluation symbolique ne permet pas d'éclater la boucle pour en tirer les réductions.

L'archétype de ces récurrences est la somme des éléments d'une matrice a. Une telle somme est implantée, en séquentiel, par quelques lignes :

s=0
DO i=1,n
  DO j=1,n
    s=s+a(i,j)
  END DO
END DO

Le graphe de dépendance de ce programme montre que la réduction est calculée suivant une ligne brisée dans l'espace d'accumulation :

Il est remarquable que cette ligne brisée est principalement constituée des droites (en traits pleins) suivant lesquelles sont calculées les réductions de la boucle interne. Ces droites sont reliées par des arcs (en traits pointillés) représentant les dépendances entre le résultat d'une réduction interne et la valeur initiale de la réduction suivante.

• il constitue à lui seul l'expression de la clause c (sinon il est impossible qu'il puisse se référencer directement) ;
• un nombre s' de clauses, compris entre 1 et s-1, sont de la forme f(z,v_c(I_j(z))) (la fonction f est l zx.b(x,d(z)), v_c désigne le tableau multi-dimensionnel calculé par la clause c et I_j est une fonction d'indices dénotant une dépendance de profondeur p) :
• une nouvelle direction e₀ doit pouvoir être extraite de ces s' clauses ;
• l'union des domaines des autres clauses de g doit correspondre au domaine de l'équation d'initialisation du nouvel opérateur. C'est à dire, en supposant que les s' premières clauses de g sont celles décrites plus haut :

  s È j=s'+1

  Djg= min

  Dj   e0,...,ek

  ( D)

Preuve:

Pour prouver cette affirmation, il faut revenir à la définition de l'opérateur Scan. La récurrence de la clause c (sans tenir compte de la transformation f) calcule le tableau multi-dimensionnel v suivant :

" zÎ D, v(z)=

ì ï ï ï ï ï ï í ï ï ï ï ï ï î

si z=min D   e1,...,ek (z) g(z) sinon si z=min D   e2,...,ek (z) f(z,v(max D   e2,...,ek (z-e1))) ... sinon si z=min D   ek (z) f(z,v(max D   ek (z-ek-1))) sinon f(z,v(z-ek))  .

Le premier cas de la définition de v éclate en deux sous-cas (g' est la restriction de g aux clauses s'+1 à s) :

ì ï ï í ï ï î

si z=min D   e1,...,ek (z) Ç s È j=s'+1 Djg g'(z) sinon si z=min D   e1,...,ek (z)Ç s' È j=1 Djg f(z,vc(Ij(z)))  .

De plus

" zÎ D_c, v_c(z)=v(f(z))  ,

d'où

" zÎ Ij-1( Dc), vc(Ij(z))=v(f(Ij(z))) =v(max

Dj   e1,...,ek

(z-e0))  .

Finalement, les deux sous-cas s'écrivent :

ì ï ï í ï ï î

si z=min D   e0,...,ek (z) g'(z) sinon si z=min D   e1,...,ek (z) f(z,v(max Dj   e1,...,ek (z-e0)))  .

Le nouvel opérateur est :

Scan( D

,(ei)

iÎ{0,...,k}

,b,d,g')° f  .

---

Considérons, par exemple, une fonction générique de recherche d'un élément particulier dans un tableau :

l ix.

case   a(i) ® b(i)   ¬  a(i) ® x esac ,

en devinant que les données associées doivent être des couples (a(i),b(i)) alors la fonction f' est forcément :

f'(d,x)=

case   d[1] ® d[2]   ¬  d[1] ® x esac .

Il reste à apparier

f'(di,f'(di-1,x))=

case   di[1] ® di[2]   ¬  di[1] Ù di-1[1] ® di-1[2]   ¬  di[1] Ù ¬  di-1[1] ® x esac ,

avec

f'(b(di-1,di),x)=

case   b(di-1,di)[1] ® b(di-1,di)[2]   ¬  b(di-1,di)[1] ® x esac .

Une solution est la fonction compagnon ci-dessous :

" (di-1,di), b(di-1,di)=

æ ç ç ç è

di-1[1]Ú di[1], ì ï í ï î case   di[1] ® di[2]   ¬  di[1] ® di-1[2] esac ü ï ý ï þ

ö ÷ ÷ ÷ ø

Dans la suite de ce texte nous appellerons cette fonction binaire la fonction search.

La fonction search est associative. Pour prouver ceci il faudrait que le système expert sache que deux instructions conditionnelles emboîtées donnent une autre instruction conditionnelle. Ensuite, il lui faudrait simplifier (en un sens difficile à déterminer) les différents cas pour montrer l'associativité. Grâce à la fonction binaire associative search, il est possible de présenter le système trouvé par le détecteur de réductions et de scans lorsqu'il est appliqué au test de l'Argonne décrit plus haut. Dans ce programme Alpha, il est supposé que N est l'ensemble des nombres naturels à partir de 1. Il est rappelé que x est un opérateur qui forme des couples à partir de deux vecteurs de scalaires et que proj est un opérateur de projection.

b : { i | 1 <= i <= n } of real ;
v2 : { i | 1 <= i <= n } of real ;
v4 : real ; 
v5 : real ;

v2[i] = Scan( { i' | 0<=i'<=n }, ( [1] ), max, b[i'], x )[i] ;
v4 = v2[n] ;
v5 = proj( Scan( { i' | 0<=i'<=n }, ( [1] ), search, ( b > v2 ) x N,
                 true x 0 )[n], 2 ) ;

Par exemple, les propriétés de commutativité et d'associativité de l'opérateur d'addition sont utilisées pour normaliser l'expression (a(i)+x)-b(i) en l'expression x+(a(i)-b(i)). Ainsi seule une expression générique x+exp est nécessaire.

Par exemple le programme ci-dessous définit une récurrence triviale.

a(0)=0                 (v1)
DO i=1,n
  a(i)=a(i-1)          (v2)
END DO

Plutôt que de générer un système avec un opérateur Scan

v1 : real ;
v2 : { i | 1 <= i <= n } of real ;

v1 = 0 ;
v2 = case
      { i | i = 1 }  : v1 ;
      { i | i >= 2 } : Scan( { i' | 0<=i'<=n }, ( [1] ), +, 0, v1 )[i] ;
     esac ;

il est préférable de remplacer directement la récurrence par l'expression de sa solution ;

v1 : real ;
v2 : { i | 1 <= i <= n } of real ;

v1 = 0 ;
v2 = case
      { i | i = 1 }  : v1 ;
      { i | i >= 2 } : v1 ;
     esac ;

Cet exemple n'est pas correctement traité par la méthode géométrique ; une analyse stricte des dépendances conduit à un code séquentiel. Par contre, toutes les méthodes de détection des réductions parviennent à traiter cet exemple. Ce n'est plus le cas si l'exemple se complexifie un peu :

DO i=1,n
  DO j=1,n
    a(i,j)=a(i,0)        (v1)
    IF (i.EQ.j) THEN
      a(i,i)=a(i-1,i-1)  (v2)
    END IF
  END DO 
END DO

L'effet de ce programme est d'initialiser chaque ligne de la matrice avec la valeur de la colonne 0, sauf pour la diagonale qui est initialisée avec la valeur a(0,0). Avec notre méthode de détection le système final est :

v1 : { i,j | 1<=i<=n, 1<=j<=n } of real ;
v2 : { i,j | 1<=i<=n, j=i } of real ;

v1[i,j] = a[i,0] ;
v2[i,j] = a[0,0] ;

Une méthode basée sur l'évaluation symbolique n'essayera pas de détecter de réduction dans la boucle sur j à cause des dépendances complexes entre les éléments du tableau a.

Notre phase de reconnaissance de formes est vraiment très réduite comme le montre la concision de la base de règles du prototype :

(defvar #:red:rules (list
   (#:pm:makeRule
      '(reference recur)
      '( ( reference ) recur reference )
      '#:red:propag)
   (#:pm:makeRule
      '(reference op exp1 exp2 recur)
      '( ( reference ) recur ( op exp1 exp2 ) )
      '#:red:associative)
   (#:pm:makeRule
      '(reference exp1 exp2 recur)
      '( ( reference ) recur (multaddform reference exp1 exp2))
      '#:red:multAddForm)
   (#:pm:makeRule
      '(reference condition exp1 exp2 recur)
      '( ( reference ) recur (if condition exp1 exp2))
      '#:red:select)
   (#:pm:makeRule
      '(reference1 reference2 exp recur)
      '( ( reference1 reference2 ) recur exp)
      '#:red:sndOrder)
   ))

La première règle traite les cas triviaux d'initialisation de tableaux avec une valeur propagée. La seconde traite les fonctions de propagation déjà exprimées avec un opérateur binaire. La troisième règle traite les fonctions de propagation de la forme a(i)*x+b(i) où x est la valeur précédente de la récurrence (pour l'instant seules les récurrences de ce type qui peuvent être résolues sont traitées). La quatrième règle traite les fonctions de propagation à base d'expressions conditionnelles. Enfin la dernière règle est prévue pour les récurrences d'ordre 2, pour l'instant seules les récurrences triviales sont prises en compte.

Ainsi la récurrence ci-dessous

a : { i | 1 <= i <= n } of real ;
v : { i | 1 <= i <= n } of real ;

v[i] = case
        { i | i = 0 }  :  a[0] ;
        { i | i >= 1 } :  a[i] / v[i-1] ;
       esac ;

peut s'écrire :

a : { i | 1 <= i <= n } of real ;
v : { i | 1 <= i <= n } of real ;

v[i] = case
        { i | i = 0 }  :  a[0] ;
        { i | i = 1 }  :  a[1] / a[0] ;
        { i | i >= 2 } :  ( a[i] / a[i-1] ) * v[i-2] ;
       esac ;

ce qui définit deux scans simples qui calculent le produit des éléments d'un vecteur.

a : { i | 1 <= i <= n } of real ;
v : { i | 1 <= i <= n } of real ;

v[i] = case
        { i | i = 0 }  :  cst ;
        { i | i >= 1 } :  a[i] * v[i-1] + b[i];
       esac ;

• permettre l'introduction d'un opérateur Scan lorsqu'une clause comporte plusieurs auto-références (autant que l'ordre de la récurrence, voir 10.1) ;
• prévoir des règles d'extraction de fonctions binaires pour ces récurrences, c'est-à-dire des fonctions opérant sur des matrices.

s=0                   (v1)
DO i=1,n
 DO j=1,i
  s=s+a(i,j)          (v2)
 END DO
END DO

a : { i,j | 1<=i<=n, 1<=j<=i } of real ;
v1 : real ;
v2 : { i,j | 1<=i<=n, 1<=j<=i } of real ;

v1 = 0 ;
v2[i,j] =
   case
    { i,j | j>1 }      : v2[i,j-1] + a[i,j] ;
    { i,j | i>1, j=1 } : v2[i-1,i-1] + a[i,j] ;
    { i,j | i=1, j=1 } : v1 + a[i,j] ;
   esac ;

a : { i,j | 1<=i<=n, 1<=j<=i } of real ;
v1 : real ;
v2 : { i,j | 1<=i<=n, 1<=j<=i } of real ;

v1 = 0 ;
v2[i,j] =
    case
      { i,j | j>1 }      : Scan( {i',j' | 1<=i'<=n, 1<=j'<=i'},
                                 ([0,1]), +, a[i',j'] , v2[i',j'] ) ;
      { i,j | i>1, j=1 } : v2[i-1,i-1] + a[i,j] ;
      { i,j | i=1, j=1 } : v1 + a[i,j] ;
    esac ;

a : { i,j | 1<=i<=n, 1<=j<=i } of real ;
v1 : real ;
v2 : { i,j | 1<=i<=n, 1<=j<=i } of real ;

v1 = 0 ;
v2[i] =
 case
 { i,j | j>1 } :
   Scan( { i',j' | 1<=i'<=n, 1<=j'<=i' }, ( [0,1] ), +, a[i',j'] ,
         case
           { k,l | k>1, l=1 } : v2[k-1,k-1] + a[k,l] ;
           { k,l | k=1, l=1 } : v1 + a[k,l] ;
         esac ; )
 esac ;

a : { i,j | 1<=i<=n, 1<=j<=i } of real ;
v1 : real ;
v2 : { i,j | 1<=i<=n, 1<=j<=i } of real ;

v1 = 0 ;
v2[i,j] =
 case
 { i,j | j>1 } :
   Scan( { i',j' | 1<=i'<=n, 1<=j'<=i' }, ( [1,0], [0,1] ), +, a[i',j'] ,
           v1 + a[i',j'] ) ;
 esac ;

a : { i,j | 1<=i<=n, 1<=j<=i } of real ;
v2 : { i,j | 1<=i<=n, 1<=j<=i } of real ;

v2[i,j] =
 case
 { i,j | j>1 } :
   Scan( { i',j' | 1<=i'<=n, 1<=j'<=i' }, ( [1,0], [0,1] ), +, a[i',j'] ,
           0 + a[1,1] ) ;
 esac ;