[EN] [IT]
[INFO] [ACQUÉRIR] [PLAN] [RESSOURCES]
CHAPITRE
APPRENDRE À PROGRAMMER AVEC FUTUREBASIC
NOTES

Les branchements V

Fonctions récursives
Prototypage de fonction

Leçon 14 : La puissance de LOCAL FN

Fonctions récursives
Sachez qu'autrefois, certains déconsidéraient le langage BASIC, car il ne permettait pas d'écrire des fonctions récursives. Une fonction récursive est une fonction qui s'appelle elle-même. Ceci est possible avec FutureBASIC parce qu'à chaque appel d'une fonction un nouveau jeu de variables qui lui est propre est créé. Certains problèmes sont mieux résolus à l'aide de fonctions récursives, toutefois elles ne sont pas très simples à concevoir et à réaliser. Voici un exemple possible d'une fonction récursive qui remplace toutes les occurrences d'une lettre à l'intérieur d'une chaîne Pascal par une autre lettre et qui retourne le nombre de remplacements effectués :

LOCAL MODE
LOCAL FN ChangerCaractere(chainePtr AS PTR, trouve AS CHAR
                          remplace AS CHAR, ou AS INT)
  DIM compteur AS INT

  compteur = 0
  IF ou = 0 THEN EXIT FN
  LONG IF
|chainePtr + ou| = trouve
    | chainePtr + ou, remplace
    compteur = 1
  END IF
  compteur += FN ChangerCaractere(chainePtr, trouve, remplace,ou - 1)
END FN = compteur

// Programme principal
DIM chaine AS STR255
DIM remplacements AS INT

chaine = "ABRACADABRA"
remplacements = FN ChangerCaractere(@chaine,_"A",_"I",chaine[0])
PRINT chaine,remplacements


Vous pouvez le constater, il n'est pas spécialement aisé de suivre le flux du programme avec de telles fonctions, elles sont souvent difficiles à comprendre et à expliquer. Que fait le programme exactement ?

Il commence par déclarer une chaîne Pascal (chaine) et une variable (remplacements) qui contiendra ultérieurement le résultat de notre fonction (le nombre de remplacements effectués). Ensuite, la chaîne est initialisée avec une valeur (ABRACADABRA) puis la fonction ChangerCaractere est appelée en lui passant 4 paramètres : l'adresse de la variable chaîne, le code ASCII du caractère à chercher dans la chaîne, le code ASCII du caractère pour la substitution et enfin la longueur de la chaîne.

Lorsque la fonction est exécutée un jeu de variables est créé pour recevoir les paramètres entrants, les variables chainePtr, trouve, remplace et ou recevront respectivement les valeurs envoyées. Nous déclarons ensuite la variable locale compteur qui servira à totaliser les remplacements, sa valeur est initialisée à 0.

La première chose à mettre en place dans une fonction récursive est de définir la condition de sortie de la fonction, cette condition doit être impérativement rencontrée à un moment où à un autre sinon la fonction continuerait à s'appeler sans fin ou presque et provoquerait une erreur de programmation et un crash de votre application. Si vous activez le Débogueur (menu Commande, article Utiliser le Débogueur) FutureBASIC ne manquera pas de vous signaler le problème lié à la profondeur de récursion, grâce à ce que la documentation appelle son renifleur de pile.

Chaque appel à la fonction crée un jeu de variables différent et un empilement s'ensuit en mémoire, lorsque la condition de sortie est rencontrée toutes les fonctions sont alors dépilées les unes après les autres en ordre inverse, jusqu'à la première qui a provoqué l'appel initial.

La condition que nous avons choisie est liée à la valeur de la variable ou, qui en fait indique la position du caractère que nous voulons examiner dans la chaîne. Lorsque la fonction est appelée pour la première fois cette valeur contient le nombre de caractères de la chaîne. Nous testerons donc les caractères en commençant par la fin de la chaîne. Quand la valeur atteindra 0, nous aurons alors testé tous les caractères et nous pourrons sortir de la fonction qui retournera alors la valeur de la variable compteur. Remarquez que la fonction ChangerCaractere retourne la valeur de cette variable (END FN = compteur)

Le petit bout de code suivant extrait un caractère (son code ASCII qui est de la taille d'un octet) et le compare au code ASCII du caractère que nous souhaitons remplacer. Grâce à la variable ou nous pouvons calculer l'adresse-mémoire d'un caractère donné, il nous suffit d'ajouter à l'adresse de départ de la chaîne, la valeur de la position du caractère.

Si le code ASCII extrait correspond au code ASCII du caractère que nous voulons changer, alors on écrit en mémoire et au même emplacement le code ASCII du caractère de remplacement et on incrémente notre variable compteur pour signaler qu'un remplacement à bien eu lieu.

Puis, on appelle à nouveau la fonction en repassant pour l'essentiel les paramètres qui ont été précédemment reçus à l'exception du dernier paramètre auquel nous retranchons 1. De cette manière à l'appel suivant la variable ou aura une valeur différente, et la fonction pourra examiner un caractère différent, en fait le caractère précédent dans la chaîne à examiner. Finalement, le résultat de cet appel est ajouté à la variable compteur. De cette manière, l'appel d'origine à la fonction totalisera les résultats de tous les autres appels lorsque le dépilement aura lieu.

Bien entendu, ce programme peut-être écrit de toute autre façon, et on peut arriver exactement au même résultat en empruntant d'autres stratégies. Parmi, toutes les possibilités en voici une autre, essayez d'en comprendre le raisonnement et les formes syntaxiques utilisées. Vous n'aurez pas droit à mon aide cette fois-ci :

LOCAL MODE
LOCAL FN
ChangerCaractere(@chainePtr AS ^STR255
                           trouve AS CHAR, remplace AS CHAR)
  DIM AS INT compteur, i

  compteur = 0
  IF chainePtr.nil$[0] = 0 THEN EXIT FN
  FOR i = 1 TO chainePtr.nil$[0]
    LONG IF chainePtr.nil$[i] = trouve
      chainePtr.nil$[i] = remplace
      compteur += 1
    END IF
  NEXT
END FN
= compteur

// Programme principal
DIM chaine AS STR255
DIM nombreRemplacements AS INT

chaine = "ABRACADABRA"
nombreRemplacements = FN ChangerCaractere(chaine,_"A",_"I")
PRINT chaine,nombre remplacements

Vous avez très certainement constaté que la fonction ChangerCaractere retourne une valeur mais aussi qu'elle modifie le contenu d'une des variables qui lui est passée en paramètre en travaillant à partir de son adresse en mémoire. C'est une façon possible de programmer une fonction pour qu'elle "retourne" de multiples valeurs. Une autre stratégie envisageable est de créer votre propre type de variable en définissant un record. En voici, un exemple avec cette fois-ci, pour varier les plaisirs, des instructions plus traditionnelles en BASIC.

BEGIN RECORD MaStructure
  DIM chaine   AS STR255
  DIM compteur AS INT
END RECORD

LOCAL MODE
LOCAL FN
ChangerCaractere(monPointeur AS ^MaStructure,¬
                        trouve AS CHAR, remplace AS CHAR)
  DIM i AS INT

  IF LEN
(monPointeur.chaine) = 0 THEN EXIT FN
  FOR i = 1 TO LEN(monPointeur.chaine)
    LONG IF MID$(monPointeur.chaine,i,1) = CHR$(trouve)
      MID$(monPointeur.chaine,i,1) = CHR$(remplace)
      monPointeur.compteur += 1
    END IF
  NEXT
END FN


// Programme principal
DIM maVariable AS MaStructure

maVariable.chaine   = "ABRACADABRA"
maVariable.compteur = 0
FN ChangerCaractere(maVariable,_"A",_"I")
PRINT maVariable.chaine,maVariable.compteur


On a vu précédemment que les variables de type record étaient toujours passées par adresse aux fonctions locales, si bien que la fonction modifie effectivement les champs de la variable originale. La fonction LEN du BASIC standard retourne le nombre de caractères qui composent une chaîne Pascal. MID$ est à la fois une fonction et une commande, utilisée comme fonction elle retourne une sous-chaîne d'une longueur donnée extraite de la chaîne qui lui est passée en paramètre à partir d'une position donnée; utilisée comme commande elle substitue une portion de la chaîne passée en paramètre, à partir d'une position donnée et d'un nombre de caractères donné avec une autre chaîne. Dans notre exemple, elle est utilisée une première fois en tant que fonction et la deuxième fois en tant que commande.

La fonction CHR$ convertit un code ASCII en une chaîne Pascal contenant un caractère.

Prototypage des fonctions dynamiques
Le flux d'un programme est dirigé par un simple appel à une fonction, à la manière d'un GOSUB/RETURN, mais il faut ajouter pour être complet à ce sujet, que ce flux peut être déterminé au moment de l'exécution du programme grâce à une forme particulière de prototypage des fonctions et aussi grâce à la vectorisation qui nous entraînera dans la programmation événementielle qui a été mise en vedette dès l'apparition du Macintosh.

Le prototypage d'une fonction à l'aide de la commande DEF FN nous permet de prédéclarer des fonctions locales comme nous l'avons déjà vu, toutefois, lorsqu'on associe à ce prototype le mot-clé USING suivi d'une variable, on indique au Compilateur d'utiliser l'adresse contenue dans cette variable comme étant l'adresse de la fonction à exécuter. Eh oui, les fonctions ont aussi une adresse en mémoire. En changeant l'adresse contenue dans la variable vous pourrez exécuter des fonctions différentes mais qui doivent cependant se conformer au prototype quant au nombre et au type des paramètres attendus et à la valeur retournée (s'il y en a une). L'exemple qui suit illustre le concept. Vous noterez la troisième utilisation de la commande DEF FN qui permet d'écrire des fonctions simples en une seule ligne de programme.

BEGIN ENUM
  _addition
  _soustraction
  _multiplication
  _division

END ENUM

BEGIN GLOBALS
  DIM
gAdresseFonction AS PTR
END GLOBALS

// Fonction protoType
DEF FN
operation(val1 AS INT, val2 AS INT) USING gAdresseFonction

// Fonctions macros
DEF FN additionner(param1 AS INT, param2 AS INT) = param1 + param2
DEF FN soustraire (param1 AS INT, param2 AS INT) = param1 - param2
DEF FN multiplier (param1 AS INT, param2 AS INT) = param1 * param2
DEF FN diviser    (param1 AS INT, param2 AS INT) = param1 / param2
DEF FN nullifier  (param1 AS INT, param2 AS INT) = 0

// Fonction locale
LOCAL FN calculer(type AS INT, nombre1 AS INT, nombre2 AS INT)

  SELECT
type
    CASE _addition       : gAdresseFonction = @FN additionner
    CASE _soustraction   : gAdresseFonction = @FN soustraire
    CASE _multiplication : gAdresseFonction = @FN multiplier
    CASE _division       : gAdresseFonction = @FN diviser
    CASE ELSE            : gAdresseFonction = @FN nullifier
  END SELECT
END FN
= FN operation(nombre1, nombre2)

// Programme principal
PRINT FN calculer(_addition,8,2)
PRINT FN calculer(_soustraction,8,2)
PRINT FN calculer(_multiplication,8,2)
PRINT FN calculer(_division,8,2)


Le programme ci-dessus commence par définir des constantes à l'aide de la structure d'énumération. Une énumération commence à partir de la valeur 0, à moins que vous ne spécifiez une autre valeur de départ, les constantes listées ensuite reçoivent la valeur de la constante qui la précède incrémentée d'une unité, à moins que vous ne forciez explicitement une valeur précise. Voici un autre exemple d'énumération possible :

BEGIN ENUM 5
  _kCinq
  _kSix
  _kSept
  _kNeuf
= 9
  _kDix
END ENUM


Dans notre exemple, les valeurs des constantes n'ont pas une importance en soi, il suffit qu'elles aient une valeur différente, car elles ne sont là essentiellement que pour apporter une meilleure lisibilité au code source.

La variable gAdresseFonction est ensuite déclarée comme variable globale, c'est elle qui contiendra l'adresse de la fonction à exécuter le moment venu. Ensuite, un prototype de fonction est déclaré indiquant que la fonction à exécuter réellement sera trouvée à l'adresse contenue dans notre variable globale.

Viennent ensuite une série de fonctions courtes qui peuvent être écrites en une ligne (on aurait pu aussi bien définir des fonctions locales à la place).

Le programme principal se contente d'afficher le résultat de la fonction calculer à laquelle il passe trois paramètres, une constante qui permettra de déterminer l'opération à effectuer avec les deux autres valeurs passées à la fonction.

La fonction calculer examinera le paramètre indiquant l'opération à réaliser, et en fonction de sa valeur, elle affectera à notre variable globale l'adresse de la fonction de calcul appropriée. Par convention, on appelle ce paramètre un sélecteur. Finalement, la fonction locale calculer se termine par un appel à notre fonction prototype et ce, quelle que soit l'opération à effectuer.

Cette technique puissante puisqu'elle permet de déterminer dynamiquement la fonction qui sera réellement appelée dans telle ou telle circonstance du programme est cependant assez rarement utilisée.

Note: Le manuel de Référence a longtemps stipulé de manière erronée que la variable utilisée pour contenir l'adresse des fonctions devait être déclarée en tant que variable globale. Cette résurgence des anciennes versions de FutureBASIC n'a plus cours avec FutureBASIC^3. En réalité, vous pouvez utiliser une variable locale. La seule restriction étant que la variable doit être déclarée en mémoire et non pas dans un registre. Le code ci-dessous est parfaitement fonctionnel.

LOCAL FN calculer(type AS INT, nombre1 AS INT, nombre2 AS INT)
  DIM @ adresseFonction AS PTR

  DEF FN
operation(val1 AS INT, val2 AS INT) USING adresseFonction

  SELECT
type
    CASE _addition       : adresseFonction = @FN additionner
    CASE _soustraction   : adresseFonction = @FN soustraire
    CASE _multiplication : adresseFonction = @FN multiplier
    CASE _division       : adresseFonction = @FN diviser
    CASE ELSE            : adresseFonction = @FN nullifier
  END SELECT
END FN
= FN operation(nombre1, nombre2)



[Precédent] [Table des Matières] [Suivant]
{Note}
© 2000 Pix&Mix
Tous droits réservés

FutureBASIC est une marque déposée appartenant à Staz Software, Inc et utilisée avec permission.