A.5 exercices de la section , page 276

l’expression

B new a: 4; a

est clairement une cascade: B new crée une nouvelle instance de la classe B. Pour faciliter le discours, nommons cette instance b₁. Cette instance reçoit le message a: 4, qui a pour résultat l’initialisation de la variable d’instance a de cette instance b₁. À cette même instance est transmise ensuite, par cascade, le message a.

Rappellons l’implémentation de la méthode a:

a
  | x |
  ^super a <= 0
        ifTrue:[1]
        ifFalse:[x := B new.
                x a: super a.
                x a + 1]

Elle déclare une variable temporaire x, donc elle crée cette variable et elle retourne la valeur de l’évaluation du test qui compose son corps. Allons-y, et tournons le programme à la main, pas à pas:

tout d’abord b₁ recoit le message a – et puisqu’il y a la pseudo-variable super, nous savons que la méthode à exécuter ne peut pas être la méthode a de la classe B ci-dessus, mais ça doit être une méthode a d’une des sur-classes de B. La première telle méthode est celle de la classe A qui retourne la valeur de la transmission a - 2
la variable d’instance a de l’objet b₁ reçoit donc le message “-” avec l’argument 2. Etant donné que a est liée à l’entier 4, le résultat sera l’entier 2 qui,
à son tour, reçoit le message <= avec l’argument 0. L’entier 2 sait très bien qu’il n’est pas inférieur ou égal à 0, il répond donc avec la seule et unique instance de la classe False: false.
false reçoit alors le message ifTrue:ifFalse: avec les deux blocs arguments. false transmet, sans hésiter (cf page 173), le message value au bloc:
[x := B new. x a: super a. x a + 1]
la variable temporaire x reçoit comme nouvelle valeur le résultat de l’envoi du message new à la classe B. Nommons cette nouvelle instance de B ainsi créée b₂. Cette instance sera la valeur de x et elle reçoit le message a: avec comme argument le résultat de la transmission super a.
nous l’avons déjà vu: super désignant toujours l’objet b₁, cette transmission retourne, comme ci-dessus, l’entier 2.
aucun message a: se trouvant dans la classe B, ce sera encore le message a: de la classe A qui sera activé. Et, comme ci-dessus, elle ne fait rien d’autre que donner une valeur à la variable d’instance a de son receveur, qui, ici, est l’objet b₂. La variable d’instance a de l’objet b₂ aura donc la valeur du résultat de la transmission super a qui,
comme tout à l’heure, retourne l’entier 2.

FIG. A.13: Le diagramme de séquence (simplifié) de B new a: 4
x, donc b₂, reçoit ensuite le message a, correspondant à la méthode que nous sommes en train d’exécuter. C’est donc une méthode récursive. Allons-y, exécutons la à nouveau – mais n’oublions pas que le résultat de la transmission x a, donc de l’envoi du message a à l’objet b₂ devra recevoir ensuite le message + avec l’argument 1.
la méthode a débute par la déclaration d’une variable temporaire x. Créons alors cette variable, et puisqu’il existe déjà une autre telle variable du même nom (nous ne sommes toujours pas sortis de la première activation de la méthode a) nommons la x₂.
comme tout à l’heure, nous commonçons par évaluer la transmission de super a, sauf que maintenant super désigne l’objet b₂, dont la variable d’instance a a été initialisé à 2. Le résultat de cette transmission sera donc 2 - 2, l’entier 0.
cet entier 0 reçoit le message <= avec l’argument 0. Il répond par l’objet true, seule et unique instance de la classe True.
true reçoit le message ifTrue:ifFalse: avec les deux blocs en argument.
true envoie le message value au premier argument, le bloc [1], qui retourne l’entier 1. C’est la dernière expression à calculer dans la méthode a. On sort donc de l’activation actuelle: x₂ cesse d’exister et la valeur retournée est l’entier 1
comme dit dans le point 1.9 ci-dessus, cet entier reçoit le message + avec l’argument 1, ce qui livre l’entier 2 comme résultat de cette activation de la méthode a.
on sort donc de la méthode: x cesse d’exister et 2 est le résultat de la première activation de la méthode a, donc le résultat de toute l’expression B new a: 4; a.

La figure A.13, page 611, montre, en UML, un diagramme de séquence pour cette trace. Nous y avons gardé la même numérotation que dans le texte. La simplification concerne le groupement de plusieurs activités et la décision de ne pas dessiner tous les retours de méthodes: elles sont implicites.

Nous connaissons déjà le résultat de l’envoi du message a à une instance de la classe B, dont la variable d’instance a est initialisée à 4, c’est l’entier 2. Ici, nous collectons les résultats successifs de l’envoi de ce message à des instances de B dont les variables d’instances a sont initialisées respectivement à 1, 2, 3, etc. jusqu’à 10. Le résultat est alors le tableau #(1 1 2 2 3 3 4 4 5 5).

La méthode a de la classe B contient deux références à la pseudo-variable super. Les deux fois, le même message a lui est envoyé. Il suffit donc d’utiliser une deuxième variable temporaire dans laquelle le résultat de cette transmission est temporairement gardé. Ce qui donne la méthode ci-dessous:

a
  | x temp |
  temp := super a.
  ^temp <= 0
        ifTrue:[1]
        ifFalse:[x := B new.
                x a: temp.
                x a + 1]

La méthode b de la classe C contient trois références à la pseudo-variable super, les trois fois avec le même message:

b
        | c |
        ^ super b = 0
                ifTrue: [1]
                ifFalse: [c := C new.
                        c b: super b.
                        c b + super b + 1]

Une première solution est donc, comme dans l’exercice précedent, d’utiliser une variable temporaire supplémentaire pour garder des résultats intermédiaires. ce qui donne la méthode:

b
        | c temp |
        temp := super b.
        ^ temp = 0
                ifTrue: [1]
                ifFalse: [c := C new.
                        c b: temp.
                        c b + temp + 1]

Mais cette solution contient toujours une référence de trop à la pseudo-variable super: nous n’en voulions plus aucune.

Rappelons-nous que les variables d’instance sont connues et peuvent être utilisées à l’intérieur des méthodes d’instance de la classe les définissant. Sachant que la méthode b de la classe A ne fait rien d’autre que retourner b - 1, la valeur de la variable d’instance moins un, nous pouvons remplacer la transmission super b par l’instanciation du corps de la méthode b de A.⁵ Ce qui donne:

b
        | c |
        ^ b - 1 = 0
                ifTrue: [1]
                ifFalse: [c := C new.
                        c b: b - 1.
                        c b + b - 1 + 1]

qui peut, puisque “- 1 + 1” est égal à 0, évidemment être simplifié en:

b
        | c |
        ^ b - 1 = 0
                ifTrue: [1]
                ifFalse: [c := C new.
                        c b: b - 1.
                        c b + b]

Le résultat est la collection des résultats de l’envoi du message b aux instances de la classe C dont la variable d’instance b vaut respectivement 1, 2, 3, etc. jusqu’à 10. C’est le tableau #(1 3 6 10 15 21 28 36 45 55). Quelle est la régularité de cette suite?

Clairement la méthode a de la classe B livre en résultat la division par deux de l’entier contenu dans la variable d’instance a si cet entier est un nombre pair. Si cet entier est un nombre impair n, le résultat est (n+1) / 2 .

La méthode b de la classe C calcule la somme des nombres succéssifs allant de 1 à la valeur de la variable d’instance b.

Nous aurions aussi bien pu définir cette méthode comme:

b
(1 to: b) inject: 0
into: [:c :e | c + e]

La nouvelle définition de b:

b
        | c |
        ^ super b = 0
                ifTrue: [1]
                ifFalse: [c := C new.
                        c b: super b.
                        c b * super b + 1]

peut, par dépliage être reécrite comme:⁶

b
        | c |
        ^ b - 1 = 0
                ifTrue: [1]
                ifFalse: [c := C new.
                        c b: b - 1.
                        c b * (b - 1) + 1]

De la nous pouvons déduire que c b, avec la variable d’instance b de l’instance c de la classe C liée à l’entier n, notons cela C_n, peut être définie de manière récurrente comme:

{ 1 n = 1 Cn = C × (n - 1)+ 1 n /= 1 n-1

Pour une variable d’instance b liée à 3, C₃, le résultat de l’envoi du message b devrait alors être: C₂ * 2 + 1, où C₂ = C₁ * 1 + 1, et C₁, nous le savons, est égal à 1.

Par instanciation, nous pouvons alors substitué la valeur de C₁ dans la définition de C₂, ce qui donne C₂ = 1 * 1 + 1 = 2. Encore par instanciation, nous pouvons remonter ce résultat dans la définition de C₃, ce qui donne alors C₃ = 2 * 2 + 1 = 5. C₃ est donc égale à 5.

La figure A.14 montre un Workspace avec les premiers 20 nombres de cette série. À vous de vérifier que notre définition est correcte. Remarquez la croissance étonnante de cette série de nombres.

FIG. A.14:

Les premiers 20 éléments de notre série obtenue avec la méthode b modifiée

Pour modifier la méthode a de la classe B de manière qu’elle calcule la division par 3 de la valeur de la variable d’instance a, il suffit de voir que la division par 2 de la version actuelle est juste le résultat du lancement de la méthode a de la classe A. En effet, l’algorithme de la méthode b fonctionne de manière à commencer par un nombre n initialement associé à la variable a, et d’ajouter 1 au résultat obtenu en appliquant le même algorithme à l’entier n - 2 — en terme programmatoire: de demander à une nouvelle instance de B, qui a sa variable d’instance a initialisée à l’entier n - 2, de livrer le résultat de sa division par deux pour rajouter ensuite 1 à ce résultat, puisque n contient 2 surement une fois de plus que n - 2.

Nous en concluons qu’il n’a rien à changer dans la méthode b, mais qu’il faut juste modifier la méthode a, de la classe A, puisque c’est elle qui calcule la valeur de n - 2. La nouvelle version sera alors:

a
^ a - 3

et le tour est joué.

Rappelons d’abord la méthode a de la classe B:

a
  | x |
  ^super a <= 0
        ifTrue:[1]
        ifFalse:[x := B new.
                x a: super a.
                x a + 1]

Sachant que la division par 3 est accomplie par la méthode A»a⁷, nous devons juste trouver la partie où on calcule l’arrondi. Puisque dans cette version l’arrondie est vers l’entier supérieur, il suffit de modifier cette partie du programme afin qu’elle calcule l’arrondi vers l’entier inférieur.

Bien entendu, il n’y a pas de calcul explicite de l’arrondi, par exemple avec le message asInteger, floor ou ceiling.⁸ Le calcul de l’arrondi doit être alors une sorte d’effet de bord de l’algorithme utilisé dans la méthode B»a. Les seuls endroits possibles sont le test super a <= 0 et le paramètre du ifTrue:, le bloc [1].

En effet, si la valeur de la variable d’instance a est inférieure ou égale à 3, le résultat de cette méthode sera l’entier 1. C’est une bonne réponse pour la valeur 3, 3 3 est bien égale à 1, mais ce n’est plus une réponse correcte pour l’entier 1 et 2, puisque nous voulons maintenant que 2 3 et 1 3 retourne 0.

Ce raisonnement nous donne la solution: il suffit de changer le test < en un test <, et, dans le cas ou ce test est satisfait, de retourner 0. Ce qui donne la nouvelle méthode a ci-dessous:

a
  | x |
  ^super a < 0
        ifTrue:[0]
        ifFalse:[x := B new.
                x a: super a.
                x a + 1]

Après tout ce que nous avons vu jusqu’à maintenant, modifier la méthode b de manière qu’elle calcule la factorielle de la variable d’instance b ne devrait plus poser de problème.

Rappelons que le n^ième nombre factoriel, !n, est défini comme:

{ 1 n = 0 !n = !(n- 1) × n n > 0

Première manière:

Ceci ressemble beaucoup à la définition de notre nombre C_n ! Il suffit alors de prendre notre définition SMALLTALK de C_n, la méthode b

b
        | c |
        ^ b - 1 = 0
                ifTrue: [1]
                ifFalse: [c := C new.
                        c b: b - 1.
                        c b * (b - 1) + 1]

d’y remplacer le facteur b - 1 de la multiplication par le nouveau facteur b et d’éliminer la transmission de + 1. Ce qui donne la nouvelle méthode b que voici:

b
        | c |
        ^ b - 1 = 0
                ifTrue: [1]
                ifFalse: [c := C new.
                        c b: b - 1.
                        c b * b]

qui, en effet, calcule la factorielle de sa variable d’instance b.

Deuxième manière:
Sachant que dans notre programme, la variable ne s’appelle pas n mais b, nous pouvons reécrire notre définition comme:
${ 1 b = 0 !b = !(b- 1) × b b > 0$
Nous pouvons traduire ceci directement en:

b
   b  = 0
       ifTrue: [1]
       ifFalse: [(C new b: b - 1; b) * b]

Maintenant, rappelons nous que toute méthode dans laquelle on ne spécifie pas explicitement une valeur de retour, retourne le receveur du message qui a engendré l’activation de cette méthode. Ici, le receveur du message b est toujours une instance de la classe C. Ce n’est clairement pas cette instance que nous voulons retourner, mais la valeur numérique calculée par la méthode. Spécifions alors cette valeur de retour:

b
   ^ b  = 0
         ifTrue: [1]
         ifFalse: [(C new b: b - 1; b) * b]

et, voilà, nous avons une autre méthode SMALLTALK qui calcule la factorielle de sa variable d’instance b.

Ces deux méthodes, l’une se basant sur la transformation d’un programme, l’autre sur la transformation d’une spécification, sont très différentes, de même que nos deux approches de transformation ont été conceptuellement fort différentes.

Il n’est pas toujours facile de décider si c’est mieux de transformer un programme existant pour obtenir un programme modifié répondant aux nouvelles contraintes, ou s’il est mieux de reprendre – sorte de remise à plat – la spécification du problème et de la transformer, pas à pas, vers un programme exécutable. Les avis sont partagés, comme vous pouvez aisément vous convaincre en étudiant la littérature sur la transformation de programmes: commencez par lire le résumé donné par Partsch et Steinbrüggen dans [57], continuez avec l’excellente thèse de doctorat de Nachum Dershowitz [22] ou le cours de Wossner et co [85], ou la littérature sur les transformations de spécifications, en premier lieu le livre de Dijkstra [23], ou encore la littérature sur la rétro-ingénierie, et là, particulièrement les conférences annuelles de “Reverse Engineering” publiées par la IEEE Computer Society [35].

D’abord, réflechissons sur le lieu où nous pouvons mettre le dictionnaire. Puisque c’est un dictionnaire qui doit garder tous les résultats livrés par la méthode C»b, nous ne pouvons pas le mettre dans une variable d’instance: seulement l’instance a accès à ses variables d’instances. Nous avons besoin de quelque chose de plus globale, comme d’une variable globale, d’une variable de classe ou d’une variable de pool.

L’utilisation d’une variable globale est ici hors de question: quelques objets seulement ont besoin de savoir quelles sommes ont déjà été calculées, nulle besoin que tout objet en soit au courant. Optons alors pour la deuxième solution et utilisons une variable de classe, que nous pouvons mettre soit dans la classe A, la sur-classe de la classe C où notre méthode b est implémentée, soit directement dans la classe C.

Le programme est écrit de manière telle que toutes les variables d’instance sont déclarées dans la sur-classe. Ajoutons ce dictionnaire alors également à la classe A et modifions, en conséquence, la définition de cette classe vers:

Object subclass: #A
        instanceVariableNames: ’a b’
        classVariableNames: ’Somme’
        poolDictionaries: ’’
        category: ’Cours-Smalltalk-Exercices’

et ajoutons tout de suite une méthode de classe pour initialiser cette variable de classe Somme à un dictionnaire vide:

initSomme
Somme := Dictionary new

et une autre pour pouvoir voir le contenu du dictionnaire:

somme
^Somme

Nous pouvons alors initialiser ou reinitialiser cette variable de classe par la simple transmission:

A initSomme

Cette initialisation doit être faite au moins une fois avant toute utilisation de la variable Somme, sinon comment SMALLTALK saurait-il que Somme est le nom d’un dictionnaire?

Sous quels types de clef devront nous mémoriser les résultats de la méthode b? Si nous examinons cette méthode:

b
        | c |
        ^ super b = 0
                ifTrue: [1]
                ifFalse: [c := C new.
                        c b: super b.
                        c b + super b + 1]

et après tout ce que nous avons vu jusqu’ici, il apparaît clairement qu’elle calcule une valeur différente pour chaque valeur différente de la variable d’instance b. Ces valeurs semblent représenter des très bonnes clefs auxquelles on peut associer les résultats correspondants. Ainsi, à un certain instant, notre dictionnaire Somme pourrait contenir les associations suivantes:

(1->1 2->3 3->6 4->10 5->15)

montrant que b a déjà calculé les sommes des premiers cinq nombres. Rappelons que tout objet SMALLTALK peut être une clef, donc les entiers aussi.⁹

Maintenant, il ne nous reste qu’à écrire une méthode supplémentaire jouant l’interface entre notre méthode b et le dictionnaire. Voici une première version d’une telle méthode, nous l’appelons somme, de la classe C:

somme
        ^ Somme includesKey: b
                ifTrue: [Somme at: b]
                ifFalse: [Somme at: b put: self b]

Elle dit: chaque fois qu’on demande à une instance de la classe C de calculer sa somme, on devrait commencer par demander à la variable de classe Somme si le nombre entier correspondant à la valeur de sa variable d’instance b existe en tant que clef. Si oui, il suffit alors de retourner la valeur associée à cette clef dans le dictionnaire Somme. Si non, il faut ajouter au dictionnaire Somme l’association «valeur de la variable d’instance b» -> «valeur de retour de l’envoi du message b, la méthode qui effectivement calcule la somme». Cette valeur de retour sera le résultat de l’activation de la méthode somme, puisque la méthode at:put: retourne la valeur de son paramètre put:.

Juste pour la beauté: toute collection indexée SMALLTALK ne comprend non seulement le message at:, mais aussi le message at:ifAbsent:. Cette dernière retourne la valeur associée au paramètre at: si l’indice ou la clef existe et retourne la valeur du bloc donné en argument au paramètre ifAbsent: si cet indice ou cette clef n’existe pas.¹⁰ Ainsi, notre méthode somme peut être écrite plus élégamment comme:

somme
^ Somme at: b
ifAbsent: [Somme at: b put: self b]

La figure A.15 montre un Workspace avec quelques exemples commentés d’utilisation de nos nouvelles méthodes.

FIG. A.15:

Quelques exemples d’utilisation de mémorisations

La technique de garder des résultats de calculs, pour éviter de les récalculer par la suite, lors d’une demande ultérieure du même calcul, est très souvent utilisée dans des écriture de programme très récursifs et engendrant une grande masse de calcul. Elle joue un rôle similaire aux variables temporaires. Pendant que ces variables gardent les résultats de calculs intermédiares, comme leur nom l’indique, temporairement, pour n’être réutilisées qu’à l’intérieur de l’exécution actuelle d’un programme, ici nous gardons des résultats complets pour toute réutilisation future du programme. La transformation d’un programme ordinaire vers un programme mémorisant ses résultats peut être automatisée (tiens, voila un bon exercice!). Les routines, fonctions ou méthodes ainsi obtenues s’appellent des memo-routines, memo-fonctions ou memo-méthodes.

Après avoir résolu l’exercice précédent, celle-ci ne devrait poser aucun problème: il faut déclarer une variable de classe, nommons-la Division; il faut des méthodes d’initialisation et de consultation de cette variable de classe, et il faut construire une méthode d’interface entre le dictionnaire et la méthode a.

Voici alors les quelques modifications et ajouts, d’abord la redéfinition de la classe A:

Object subclass: #A
        instanceVariableNames: ’a b’
        classVariableNames: ’Somme Division’
        poolDictionaries: ’’
        category: ’Cours-Smalltalk-Exercices’

Ensuite les deux méthodes de classe pour l’accès au dictionnaire:

initDivision
Division := Dictionary new

division
^Division

Ensuite la méthode B»division jouant l’interface entre dictionnaire et calcul:

division
^ Division at: a
ifAbsent: [Division at: a put: self a]

C’est tout. Vous voyez bien que cette transformation se fait tout mécaniquement: aucun problème pour l’automatiser.

Maintenant, après avoir exécuté les deux transmissions ci-dessous:

A initDivision.
B new a: 10; division

le dictionnaire Division contient l’association (10->5).

Imaginons alors, que nous avions encore beaucoup d’autres mémorisations à faire dans les sous-classes de A. Pour chacune des activités à mémoriser nous devrions créer une nouvelle variable de classe contenant un dictionnaire. C’est l’instant d’utiliser une variable de pool: c’est la variable de pool qui contiendra tous ses dictionnaires. Pour cela, redéfinissons la classe A en enlevant toutes les variables de classe et en ajoutant une variable de pool nommée Dictionnaires:

Object subclass: #A
        instanceVariableNames: ’a b’
        classVariableNames: ’
        poolDictionaries: ’Dictionnaires’
        category: ’Cours-Smalltalk-Exercices’

Ensuite, ajoutons une méthode de classe pour l’initialisation de notre dictionnaire de pool et de nos variables du pool:

initDictionnaires
Dictionnaires at: #Somme put: Dictionary new;
at: #Division put: Dictionary new

La transmission

A initDictionnaires

crée alors deux variables de pool, Somme et Division, qui sont accéssibles de la même manière que nos anciennes variables de classes Somme et Division.

Nous n’avons plus rien à changer dans notre programme: toutes les transmissions que nous avons testées plus haut marchent à nouveau, cette fois elles n’utilisent plus des variables de classe mais de pool. Et si nous avons besoin de mémoriser des résultats d’autres activités, il suffit d’ajouter des variables de pool supplémentaires avec la méthode de classe A»ajoutDictionnaire: que voici:

ajoutDictionnaire: newDict
Dictionnaires at: newDict put: Dictionary new.

A.5 exercices de la section 4.4.9, page 276