Skip to content

6.8 Emprunts à APL

Claude Roux edited this page Jan 30, 2022 · 1 revision

APL

English Version

APL fait certainement partie des langages les plus cryptiques et les plus surprenants qui aient jamais été créés. Né des notations mathématiques de Kenneth Iverson à Harvard, pour manipuler des tableaux et des listes, ce langage permet d'écrire un code d'une rare sobriété. APL arrive souvent en quelques symboles à implanter des manipulations complexes de matrices là où des langages pourtant établis requièrent des lignes et des lignes de code.

L'exemple suivant montre par exemple comment on peut implanter la multiplication de deux matrices en trois symboles:

 M +.× N   

Le '.' est appelé: produit interne. A chaque itération, il multiplie une ligne de M par une colonne de N, puis effectue la somme de chacun des éléments du vecteur ainsi obtenu.

APL définit à lui tout seul un paradigme qui lui est propre, où l'efficacité de la formulation rend, en comparaison, la plupart des autres langages horriblement verbeux et lourds. Mais, même si nous n'avons pas la prétention de construire ici un interpréteur APL, il nous a semblé qu'un langage comme LispE qui a mis les listes au coeur de son fonctionnement, ne pouvait que bénéficier de la puissance et de la richesse de quelques unes de ces instructions.

Infuser, en quelque sorte, la magie d'APL dans Lisp.

Adaptations

Mais avant d'entrer plus avant dans la façon dont nous nous sommes inspirés d'APL, nous allons décrire quelques uns des concepts que nous avons intégré dans LispE pour rendre cet enrichissement possible.

Nouveaux conteneurs: numbers, matrix et tensor

Nous avons rajouté trois nouveaux types de conteneurs de façon à rendre l'utilisation de ces nouvelles instructions aussi transparente et simple que possible.

  • numbers : il s'agit d'une liste qui ne contient que des valeurs flottantes doubles: (0.1 1.2 1.4)
  • matrix: il s'agit d'une matrice NxM dont chaque ligne est un numbers: ( (numbers) (numbers)... (numbers))
  • tensor: il s'agit d'une matrice N1xN2x..xNn, les lignes les plus profondes sont aussi des listes numbers

Notons que les tenseurs et les matrices sont par défaut des objets list auxquels on a adjoint des dimensions. Notons de plus, que numbers, matrix et tensor sont aussi des instructions qui peuvent transformer une liste en l'objet correspondant:

(range 0 1 0.1) ; crée une liste de type numbers: (0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1)
(numbers '(1 2 3 4)) ; transforme cette liste en une liste de double
(numbers 1 2 3 4) ; génère directement une liste de double
(matrix '((1 2 3) (4 5 6)) ) ; crée la matrice correspondante
(tensor '( ( (1 2 3) (3 4 5) ) ( (6 7 8) (9 10 11)) ))

L'ensemble des instructions que nous allons présenter s'applique sur ces conteneurs.

Extension du domaine des opérateurs numériques

Par défaut désormais, les opérateurs numériques tels que + - * / % ~ & &~| % s'appliquent aussi bien à des scalaires qu'à des listes ou même des listes de listes.

(+ 1 2 3) ; donne 6
(+ '(1 2 3)) ; donne 6
(+ '(1 2 3) 10) ; donne (11 12 13)
(+ '(1 2 3) '(1 2 3)) ; donne (2 4 6)
(+ '((1 2 3) (4 5 6)) 10) ; donne ((11 12 13) (14 15 16))
(+ '((1 2 3) (4 5 6) (6 7 8)) '(10 20 30)) ; donne ((11 12 13) (24 25 26) (36 37 38))

La philosophie de APL

APL fournit une liste d'opérateurs dont l'objectif principal est de manipuler des vecteurs, des matrices ou des tenseurs. La plupart de ces opérateurs ont une double interprétation selon qu'ils sont utilisés avec un argument (monadique) ou deux arguments (dyadique). Ainsi, l'opérateur rho:⍴ rend les dimensions d'une matrice en mode monadique ou construit une matrice lorsque le nombre d'arguments est supérieur.

Nous n'avons implanté qu'une toute petite partie de tous les opérateurs du langage, et nous n'avons donc pas la prétention ici d'offrir un interpréteur complet du langage. Il est possible que nous rajoutions au gré de nos besoins de nouveaux opérateurs dans le futur, mais pour le moment la liste est limitée aux instructions qui nous ont semblé les plus intéressantes, et ce de façon purement subjective.

⍳: iota, iota0

La première de ces instructions est iota dont on peut dire qu'elle est au coeur de la plupart des exemples en APL. iota est une fonction monadique qui rend une liste d'entiers bornée par la valeur fournie. La version iota0 commence cette liste à 0 alors que iota la commence à partir de 1.

(iota 10) ; donne (1 2 3 4 5 6 7 8 9 10)
(iota0 10) ; donne (0 1 2 3 4 5 6 7 8 9)

Nous avons implanté cette fonction de façon à garder une certaine homogénéité avec APL, mais il faut avouer qu'elle fait doublon avec range.

⍴: rho

rho est de loin la méthode la plus puissante du langage. Utilisé avec un conteneur, elle rend ses dimensions. Utilisé avec des dimensions et une liste plate de valeurs, elle construit la matrice ou le tenseur correspondant en puisant dans la liste pour son initialisation. Notons que lorsque la liste contient moins de valeurs que le conteneur à construire, on recommence depuis le début de la liste pour continuer l'initialisation.

(rho '((1 2) (3 4))) ; donne (2 2)
(rho 2 2 (iota 4)) ; donne ((1 2) (3 4))
(rho 2 2 2 (iota 4)) ; donne (((1 2) (3 4)) ((1 2) (3 4)))
(rho 3 3 3 (gamma_distribution 30 1 0.4))
; donne (((0.432632 0.0582416 0.133275) (0.201316 0.251462 0.325018) (0.0110476 0.853308 1.30962)) ((0.152873 0.588721 0.898728) (0.0208302 0.142427 0.350234) (0.123387 0.582459 0.243948)) ((0.233026 0.829267 0.161644) (0.151935 0.286315 0.00731607) (0.0511841 0.273263 0.509721)))

// : opérateur de réduction

Remarquons que la version APL ne contient qu'un seul /, ce qui dans notre cas aurait été ambigu avec l'opérateur de division. C'est d'ailleurs pour la même raison que nous avons aussi appelé l'opérateur de balayage: \\ (voir ci-dessous).

Notons que cet opérateur porte aussi un nom alphabétique: reduce que l'on peut utiliser à la place de //.

  • Cet opérateur permet d'appliquer une opération entre tous les éléments d'une liste.
  • Il permet encore d'éliminer ou de démultiplier des éléments d'une liste en fournissant une liste de d'entiers.
(// '+ '(1 2 3)) ; donne 6
(// '(1 0 2) '(1 2 3)) ; donne (1 3 3)

or -// : réduction depuis la fin

Il existe une version de cet opérateur qui applique les opérations depuis la fin de la liste.

Notons que cet opérateur porte aussi un nom alphabétique: backreduce que l'on peut utiliser à la place de -//.

On peut voir la différence immédiatement sur l'exemple suivant:

(// '- '(1 2 3)) ; donne -4
(-// '- '(1 2 3)) ; donne 0
(⌿ - '(1 2 3)) ; donne 0 aussi

\\: opérateur de balayage

  • Cet opérateur est utilisé pour balayer une liste et appliquer entre chaque élément un opérateur donné. On conserve chacun des résultats intermédiaires dans une liste.
  • Il peut aussi être utilisé en conjonction avec une liste de valeurs numériques pour étendre une liste.

Notons que cet opérateur porte aussi un nom alphabétique: scan que l'on peut utiliser à la place de \\.

(\\ '+ '(1 2 3)) ; rend (1 3 6) [1 (1+2) ((1+2)+3)
(\\ '(1 0 1) '(4 6)) ; rend (4 0 6)

or -\\: opérateur de balayage depuis la fin

Cet opérateur fonctionne de la même façon que \\, à la différence qu'il applique les opérateurs à partir de la fin de la liste.

Notons que cet opérateur porte aussi un nom alphabétique: backscan que l'on peut utiliser à la place de -\\.

; Si l'on compare les deux lignes, on voit immédiatement la différence

(\\ '- '(1 2 3)) ; donne (1 -1 -4)
(⍀ '- '(1 2 3)) ; donne (3 1 0)

Produit Externe: (° L1 opérateur L2)

Cet opérateur applique une opération entre chaque élément de L1 et chaque élément de L2.

'(2 3 4) '* '(1 2 3 4)) ; donne ((2 4 6 8) (3 6 9 12) (4 8 12 16))

Produit Interne : (. M1 opérateur_réduction opérateur_colonne M2)

Le produit interne applique d'abord l'opérateur de colonne entre une ligne de M1 et une colonne de M2, puis il applique une réduction en utilisant l'opérateur de réduction sur le vecteur ainsi obtenu.

On peut par exemple de cette façon effectuer une multiplication de deux matrices:

(.  '((1 2) (5 4) (3 0)) '+ '* '((6 2 3 4) (7 0 1 8)))

; ce qui nous donne:

((20 2 5 20) (58 10 19 52) (18 6 9 12))

Autrement dit:

  TABLE1           TABLE2            TABLE
  1    2         6  2  3  4       20  2  5 20 
  5    4         7  0  1  8       58 10 19 52
  3    0                          18  6  9 12

Et plus encore

Nous avons aussi implanté d'autres opérateurs tels que:

  • transpose: transposition d'une matrice ligne/colonne
  • rank: extraction d'une sous-matrice depuis un tenseur selon des lignes et des colonnes
  • invert: inversion d'une matrice
  • solve: résolution d'un jeu d'équations à plusieurs inconnues
  • reverse: transposition d'une matrice ou d'un tenseur selon un axe donné

Voici quelques exemples:

(setq m (rho 3 2 (iota 6))) ; m est désormais ((1 2) (3 4) (5 6))
(reverse m) ; donne ((2 1) (4 3) (6 5)). l'axe par défaut est 1
(reverse m 0) ; donne ((5 6) (3 4) (1 2))

(setq m (rho 3 4 5 (iota 60)))
;(((1 2 3 4 5) (6 7 8 9 10) (11 12 13 14 15) (16 17 18 19 20)) 
;((21 22 23 24 25) (26 27 28 29 30) (31 32 33 34 35) (36 37 38 39 40)) 
;((41 42 43 44 45) (46 47 48 49 50) (51 52 53 54 55) (56 57 58 59 60)))

(rank m 1) ; donne ((21 22 23 24 25) (26 27 28 29 30) (31 32 33 34 35) (36 37 38 39 40))
(rank m 1 1) ; donne (26 27 28 29 30)
(rank m -1 1) ; donne ((6 7 8 9 10) (26 27 28 29 30) (46 47 48 49 50))
(rank m -1 -1 1) ; donne ((2 7 12 17) (22 27 32 37) (42 47 52 57))

(invert (rho 2 2 (iota 4))) ; donne ((-2 1) (1.5 -0.5))

Un exemple un peu plus riche

Une personne prévoit des investissements dans un pays étranger pour les 5 prochaines années :

(setq Inv (numbers 2000 5000 6000 4000 2000))

Mais le pays en question souffre d'inflation, et les taux d'inflation sont prévus comme suit :

(setq Inf (numbers 2.6 2.9 3.4 3.1 2.7))

Nous pouvons facilement normaliser ces valeurs:

(+ 1 (/ Inf 100))

; ce qui donne
  1.026 1.029 1.034 1.031 1.027

La conséquence cumulée de ces taux d'inflation peut être calculée de la façon suivante avec un balayage :

(\\ * (+ 1 (/ Inf 100)))

; ce qui donne:
  1.026 1.056 1.092 1.125 1.156

Maintenant, les investissements exprimés en "valeurs futures" seraient :

(* Inv (\\ * (+ 1 (/ Inf 100))))

; ce qui donne
  2052.00 5278.77 6549.90 4501.96 2311.76

Enfin, l'investissement cumulé année après année peut être obtenu par un balayage avec addition :

(\\ + (* Inv (\\ * (+ 1 (/ Inf 100)))))

; ce qui donne
  2052.00 7330.77 13880.67 18382.63 20694.39

Comme vous pouvez le constater, nous avons employé deux balayages dans la même expression.

Conclusion

Il est clair que nous sommes loin d'atteindre la sobriété et l'efficacité du véritable langage APL. En revanche, certains des opérateurs que nous avons emprunté à ce langage apportent un vrai plus à LispE, en lui permettant de manipuler listes et matrices de façon simple et concise.

Clone this wiki locally