Recursion
Ce didacticiel est destiné aux nouveaux utilisateurs de la Simple Virtual Machine.
Dans ce didacticiel, vous allez mettre en place des fonctions récursives.
Le temps de lecture de ce didacticiel est estimé à 15 minutes si les fonctions ont été abordées.
Pour commencer, créez le canevas de l'application dans le fichier exécutable recursion.svm en utilisant ce code :
#!/usr/bin/env svm
DESCRIPTION
Recursion example
END
LOG
DEBUG "Recursion" STYLE "default"
PLUGIN "svmcom.so"
PLUGIN "svmint.so"
ARGUMENT INT nb
PROCESS "application"
CODE "main" INLINE
:debug BREAK
END
MEMORY nb
END
Modifiez le code pour ajouter une fonction récursive et son appel :
#!/usr/bin/env svm
DESCRIPTION
Recursion example
END
LOG
DEBUG "Recursion" STYLE "default"
PLUGIN "svmcom.so"
PLUGIN "svmint.so"
ARGUMENT INT nb
PROCESS "application"
CODE "main" INLINE
:debug BREAK
:memory (PTR, INT, INT)/parameters
[ , @&nb , ] -> parameters
:call f parameters
:com.message @(parameters/2)
:shutdown
# Function f: PTR, INT (input), INT (output)
:label f
:memory PTR, INT, INT, BLN -> &P
:int.cmp @(P/1) < 2 -> (@&P/3)
:goto f_end :when @(@&P/3) TRUE
@(P/1) -> (@&P/1)
:shift -1 (@&P/1)
:call f &@&P*3
:int.mul @(@&P/2) @(P/1) -> (P/2)
:return
:label f_end
1 -> (P/2)
:return
END
MEMORY nb
END
Avant de lancer l'application, observons la fonction :
Une telle fonction est dite "récursive".
Lancez l'application avec quelques valeurs :
./recursion.svm 0
1
./recursion.svm 1
1
./recursion.svm 2
2
./recursion.svm 3
6
./recursion.svm 4
24
./recursion.svm 5
120
Il s'agit de la célèbre fonction factorielle : elle renvoie le produit des nombres de 1 à la valeur d'entrée.
Lancez l'application avec la valeur 5 dans le débugueur et observez le déroulement de l'exécution instruction par instruction. Lorsque la fonction passe dans la branche sans appel récursif, la mémoire et le processeur ressemblent à :
Lorsque les appels récursifs se terminent, vous pouvez observer les différentes valeurs de la factorielle dans la mémoire.
Une fonction est dite récursive lorsqu'elle s'appelle elle-même. La récursion se termine lorsque la fonction passe par une branche de code qui ne l'appelle plus.
Les règles habituelles des fonctions s'appliquent toutes aux fonctions récursives.
Modifiez le code pour obtenir :
#!/usr/bin/env svm
DESCRIPTION
Recursion example
END
LOG
DEBUG "Recursion" STYLE "default"
PLUGIN "svmcom.so"
PLUGIN "svmint.so"
ARGUMENT INT nb
PROCESS "application"
CODE "main" INLINE
:debug BREAK
:memory (PTR, INT, INT)/parameters
[ , @&nb , ] -> parameters
:flag "main"
:interruption CASCADE NUMERIC stop
:call f parameters
:goto error :unless (parameters/2) INITIALISED
:com.message @(parameters/2)
:shutdown
:label error
:com.message "Error"
:shutdown
# Function f: PTR, INT (input), INT (output)
:label f
:memory PTR, INT, INT, INT, BLN -> &P
:int.cmp @(P/1) = 0 -> (@&P/4)
:goto f_end :when @(@&P/4) TRUE
:int.mod @(P/1) 2 -> (@&P/3)
:int.cmp @(@&P/3) = 0 -> (@&P/4)
:goto f_alter :when @(@&P/4) TRUE
:int.sub @(P/1) 1 -> (@&P/1)
:call f &@&P*3
:int.div 100 @(@&P/2) -> (P/2)
:return
:label f_alter
:int.div @(P/1) 4 -> (@&P/1)
:call f &@&P*3
:int.add @(P/1) @(@&P/2) -> (P/2)
:return
:label f_end
0 -> (P/2)
:return
# Interruption handler
:label stop
:return 0 :unless "main" RAISED
END
MEMORY nb
END
Puis lancez l'application avec quelques valeurs, en mode débugueur à votre convenance :
./recursion.svm 0
0
./recursion.svm 2
2
./recursion.svm 3
50
./recursion.svm 8
10
./recursion.svm 10
12
Dans tous ces cas, la fonction se déroule correctement, et les appels récursifs aboutissent pour donner le résultat.
Maintenant, lancez l'application avec ces autres valeurs :
./recursion.svm 1
Error
./recursion.svm 4
Error
./recursion.svm 6
Error
./recursion.svm 17
Error
./recursion.svm 70
Error
Cette fois, pour chacune de ces valeurs, un des appels récursif tombe sur une division par 0, ce qui génère une interruption NUMERIC.
Pour rattrapper cette interruption, le code appellant la fonction :
NUMERIC.Et la fonction associée au gestionnaire d'interruption contient une seule instruction qui permet de ressortir de tous les appels récursifs (jusqu'à détecter le drapeau "main") en une seule fois en libérant la mémoire.
Lancez l'application en mode débugueur avec la valeur 17, puis placez un point d'arrêt éphémère sur l'instruction :return 0 :unless "main" RAISED et lancez l'exécution du code :
Avant de poursuivre l'exécution du code, notez :
Puis exécutez uniquement l'instruction :return 0 :unless "main" RAISED et constatez le nouvel état : en une seule instruction, tous les appels récursifs sont immédiatement terminés, et la mémoire allouée par chaque appel est libérée.
L'instruction :return 0 associée à une condition permet d'interrompre proprement l'exécution d'une fonction récursive.
Les drapeaux peuvent être utilisés pour simplifier la condition de sortie de la fonction récursive.
Lorsqu'il s'agit d'une sortie anticipée suite à une interruption, ce mécanisme peut être mis en place indépendamment de la fonction récursive elle-même et peut varier d'un appel de la fonction à l'autre.
Vous venez de voir comment écrire des fonctions récursives dans une application.
Les fonctions récursives sont parfois un moyen élégant pour écrire certains calculs, mais comportent souvent une gestion d'erreur relativement complexe.
Avec l'argument 0 de l'instruction de retour de fonction et une condition, une fonction récursive peut être aisément terminée sans crainte de fuite mémoire.