Programmation objet et géométrie/SmallTalk par l'exemple

Le logiciel Dr. Geo II illustre la notion de récursivité par l'exemple: Écrit en Smalltalk, il est aussi muni d'une console Smalltalk, ce qui permet d'utiliser DrGeoII pour regarder comment DrGeoII lui-même est fait! Ce qui permet (même si ce n'est pas nécessairement recommandé) de modifier DrGeoII depuis DrGeoII, un peu comme un Cyborg qui s'opère, ou comme le vivant! Mais sans aller jusqu'à de telles extrémités risquées, on va ici utiliser ce pouvoir d'introspection de DrGeoII pour regarder quels algorithmes sont utilisés par le logiciel, et le présent article peut être considéré comme une introduction mathématique (et surtout géométrique) au langage Smalltalk.

Pour consulter le code source de DrGeoII depuis DrGeoII, on clique depuis une figure DrGeoII sur modifer un script et là, on clique sur Browse. Il ne reste alors plus qu'à surfer...

Nombres

Les algorithmes numériques sont surtout groupés dans KernelNumbers

Entiers

Factorielle

Pour voir comment DrGeo calcule les factorielles, on regarde la liste des fonctions mathématiques qui s'appliquent à l'objet entier et on y trouve ceci:

factorial 
	self = 0
		ifTrue: [^ 1].
	self > 0
		ifTrue: [^ self * (self - 1) factorial].
	self error: 'Not valid for negative integers'

Ce qui peut se traduire ainsi: On commence par tester si l'entier en question est nul. Si le test réussit (c'est-à-dire si le nombre est effectivement nul), on renvoie 1, ce qui signifie que la factorielle de 0 est 1 par définition. Puis on lance un nouveau test sur le signe de l'entier. Si le test réussit (c'est-à-dire si l'entier est positif) on renvoie le produit de l'entier par la factorielle de son prédécesseur. Sinon on envoie un message d'erreur rappelant que seuls les nombres positifs ont une factorielle. On constate que cet algorithme est récursif.

PGCD

Pour les petits entiers, SmallTalk utilise l'algorithme d'Euclide (la version avec les divisions) en affectant simultanément (avec :=) le plus grand entier avec le plus petit et le plus petit avec le reste de la division euclidienne (l'opération est notée \\ en SmallTalk):

gcd: anInteger 
	"See SmallInteger (Integer) | gcd:"
	| n m |
	n := self.
	m := anInteger.
	[n = 0]
		whileFalse: 
			[n := m \\ (m := n)].
	^ m abs

La syntaxe est donnée sur la première ligne, et est à lire pgcd avec anInteger. Les traits verticaux de la deuxième ligne encadrent la liste des variables, il y en a donc 2 ici. Elles sont initialisées avec les deux entiers (self et anInteger) dont on veut le pgcd, puis on lance un test de nullité sur n. Tant que ce test échoue (c'est-à-dire tant que n n'est pas nul), on remplace n par le reste euclidien et m par n. Puis (c'est-à-dire quand le test de nullité sur n réussit) on renvoie la valeur absolue de m. On voit donc que Smalltalk sait calculer le pgcd de deux entiers relatifs.

Conversion en fraction

asFraction
	"Answer a Fraction that represents the value of the receiver."

	^Fraction numerator: self denominator: 1

Pour convertir un entier en fraction, on considère son dénominateur comme égal à 1.

Fractions

Propriétés

Simplification

Pour simplifier une fraction, Smalltalk utilise trois variables, la première pour le pgcd du numérateur et du dénominateur, la seconde pour le quotient du numérateur par le pgcd et la troisième, pour le quotient du dénominateur par le pgcd. L'algorithme renvoie 0 si la fraction est nulle, la fraction avec les nouveaux numérateur et dénominateur sinon:

reduced

	| gcd numer denom |
	numerator = 0 ifTrue: [^0].
	gcd := numerator gcd: denominator.
	numer := numerator // gcd.
	denom := denominator // gcd.
	denom = 1 ifTrue: [^numer].
	^Fraction numerator: numer denominator: denom

En bref, pour simplifier une fraction, on divise son numérateur et son dénominateur par leur pgcd.

Inverse

Si la fraction est l'inverse d'un entier, son inverse est cet entier. Sinon on échange les rôles du numérateur et du dénominateur:

reciprocal
	numerator abs = 1
		ifTrue: [^ denominator * numerator].
	^ self class numerator: denominator denominator: numerator

Carré d'une fraction

Pour élever une fraction au carré, DrGeoII élève son numérateur et son dénominateur au carré:

squared
	^ Fraction numerator: numerator squared denominator: denominator squared

Réels

Inverse

L'inverse d'un réel est le quotient de 1 par celui-ci:

reciprocal
	^ 1.0 / self

Nombre pseudo-aléatoire

Comme souvent dans la programmation objet, l'essentiel se passe lorsqu'on crée l'objet (instantiation ou ici, initialisation). La première fois qu'on cherche un nombre aléatoire, DrGeoII convertit la date courante en millisecondes, puis annule certains de ses chiffres binaires, et réalise une opération ou exclusif chiffre à chiffre, avec la valeur qu'on a fournie à la méthode. Ceci pour avoir un nombre difficilement prévisible, et donc apparemment aléatoire (mais non nul). Puis on donne aux constantes a et m deux valeurs constantes. Enfin q et r sont le quotient et le reste euclidiens de m par a.

initialize
	super initialize.
	[seed := (Time millisecondClockValue bitAnd: 1073741823)
				bitXor: self hash.
	seed = 0] whileTrue.
	a := 16807 asFloat.
	m := 2147483647 asFloat.
	q := (m quo: a) asFloat.
	r := (m \\ a) asFloat

Le code ci-dessus suggère que le générateur pseudo-aléatoire utilisé par DrGeoII est congruentiel linéaire ce qui nécessite

1. que le nombre m=2147483647 soit premier, ce qui est le cas;
2. que le nombre a=16 807 soit une racine primitive de 1 modulo m, ce dont la vérification est laissée en exercice (ce nombre est égal à $7^{5}$).

Fonctions trigonométriques et exponentielles

L'examen des fonctions trigonométriques, logarithmes, exponentielles et racine carrée prendrait bien trop de place pour figurer ici, mais on peut les résumer à une combinaison de formules (par exemple, les formules trigonométriques) et de calcul de séries entières.

Géométrie analytique

En Smalltalk, les coordonnées d'un point ou d'un vecteur sont écrites sans parenthèses mais séparées par un arobase qui, en anglais, signifie at (jusqu'à). Donc quand on parle du point de coordonnées (3;2), on le note 3@2 qui peut se lire de 3 jusqu'à 2. Cette formule résume assez bien le mouvement des yeux lorsqu'on veut placer ce point dans un graphique: On part de la graduation 3 sur l'axe des abscisses, puis depuis cette graduation, on va vers la hauteur 2 en suivant la parallèle à l'axe des ordonnées.

Points

Milieu

Pour construire le milieu d'un segment à partir de ses extrémités (deux points), DrGeoII fait ainsi:

update
	self doParentsExist ifTrue:
		[self point: (parents first point + parents second point) / 2].

Reste à savoir ce que représente l'addition de deux points pour DrGeoII! C'est l'addition des coordonnées:

+ arg 
	"Answer a Point that is the sum of the receiver and arg."

	arg isPoint ifTrue: [^ (x + arg x) @ (y + arg y)].
	^ arg adaptToPoint: self andSend: #+

Et la division d'un point par 2?

/ arg 
	"Answer a Point that is the quotient of the receiver and arg."

	arg isPoint ifTrue: [^ (x / arg x) @ (y / arg y)].
	^ arg adaptToPoint: self andSend: #/

C'est plus compliqué: Le nombre 2 est d'abord transformé en le point de coordonnées (2,2) puis la division coordonnées par coordonnées est effectuée entre les deux points. Au final, les deux coordonnées sont divisées par 2. Donc on retrouve le fait que l'abscisse du milieu est la moyenne des abscisses, mais avec plus de puissance (la division d'un point par un point ressemble à ce qu'on fait avec un tableur).

Distance

Pour calculer la distance entre le point courant et un autre point t1, DrGeo a besoin de deux autres variables dx et dy, où sont stockées respectivement la différence des abscisses et la différence des ordonnées. La fonction retourne la racine carrée de la somme de leurs produits par eux-mêmes (à lire de droite à gauche; on notera que Smalltalk ne connaît pas les règles de priorité opératoire, ce qui oblige à mettre le second produit entre parenthèses):

dist: aPoint 
	"Answer the distance between aPoint and the receiver."
	| dx dy |
	dx := aPoint x - x.
	dy := aPoint y - y.
	^ (dx * dx + (dy * dy)) sqrt

On reconnaît là le théorème de Pythagore.

Vecteurs

Vecteur défini par deux points

DrGeoII soustrait deux points pour avoir un vecteur: Pour l'objet DrGVector2ptsItem la méthode update donne

update
	self doParentsExist ifTrue:
		[self direction: (parents at: 2) point - (parents at: 1) point].

Reste à voir ce que, pour DrGeoII, signifie une soustraction de points; ce qu'on peut voir dans Graphics-Primitives:

- arg 
	"Answer a Point that is the difference of the receiver and arg."

	arg isPoint ifTrue: [^ (x - arg x) @ (y - arg y)].
	^ arg adaptToPoint: self andSend: #-

En bref, pour obtenir l'abscisse du vecteur joignant deux points, DrGeoII soustrait les abscisses de ces deux points.

translaté d'un point

Pour calculer les coordonnées du translaté d'un point par un vecteur, DrGeoII additionne les coordonnées du vecteur à celles du point:

translateBy: delta 
	"Answer a Point translated by delta (an instance of Point)."

	^(delta x + x) @ (delta y + y)

Colinéarité

Deux vecteurs sont considérés par DrGeoII comme colinéaires si leur déterminant est proche de 0:

isCollinearWith: aVector
	^ (vector crossProduct: aVector) closeTo: 0

Ce qui n'explique rien tant qu'on ne sait pas comment DrGeoII calcule le fameux déterminant:

crossProduct: aPoint 
	"Answer a number that is the cross product of the receiver and the 
	argument, aPoint."

	^ (x * aPoint y) - (y * aPoint x)

(différence entre les produits en croix)

Produit scalaire

Le produit scalaire est appelé dot product:

dotProduct: aPoint 
	"Answer a number that is the dot product of the receiver and the 
	argument, aPoint. That is, the two points are multipled and the 
	coordinates of the result summed."

	^ (x * aPoint x) + (y * aPoint y)

L'esprit de Smalltalk demande qu'on considère le produit scalaire comme infixé: Pour calculer le produit scalaire du point courant avec t1, on multiplie leurs x respectifs (leurs abscisses) et leurs y respectifs, on additionne les deux produits, et on retourne la somme.

Droites

DrGeoII gère les droites par leur représentation paramétrique, une droite étant définie par un point et un vecteur. Ce qui facilite la construction de la parallèle à une droite donnée par un point donné, et la gestion des segments (seul l'intervalle du paramètre est différent). La description par point et vecteur facilite aussi le calcul de l'image de la droite par une isométrie: On calcule séparément les effets de l'isométrie sur le point et sur le vecteur. Le détail serait trop long à déployer ici.