-
Notifications
You must be signed in to change notification settings - Fork 8
6.8 Emprunts à APL
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.
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.
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.
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))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.
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 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)))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)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- 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)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)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))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
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))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.027La 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.156Maintenant, les investissements exprimés en "valeurs futures" seraient :
(* Inv (\\ * (+ 1 (/ Inf 100))))
; ce qui donne
2052.00 5278.77 6549.90 4501.96 2311.76Enfin, 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.39Comme vous pouvez le constater, nous avons employé deux balayages dans la même expression.
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.