De coutume, résoudre certains problèmes avec une logique récursive s’avère la solution la plus directe et la plus évidente. Un exemple serait d’expliquer la factorielle ou de résoudre la suite fibonacci.
Projeter le monde des algèbres avec ses formules mathématiques dans le monde de l’informatique peut cacher des subtilités qu’il faut prendre en considération. L'erreur StackOverflowError est une Throwable qui pourrait transformer les rêves en cauchemars.
Dans cet article, nous allons essayer de résoudre cette problématique avec l’utilisation des trampolines.
StackOverflowError
StackOverflowError fait partie de la famille des Erreurs, plus précisément, attachées à des erreurs liées à la machine virtuelle Java. En général, une erreur indique qu’un problème sérieux vient de se produire suite à des conditions anormales. Il est déconseillé de capturer les Erreurs et en particulier les VirtualMachineError qui signalent que la machine virtuelle Java est rompue ou qu’elle est à court de ressources.
StackOverflowError est une erreur qui sera levée suite à un débordement de la pile lors d’un appel récursif très profond.
A titre d’exemple, la fonction factorielle :
factorial 0 = 1
factorial n = n * factorial (n - 1)
peut être écrite en Java :
Exemple 1
long factorial(int n) {
if (n < 2) return 1;
else return n * factorial(n - 1);
}
L’appel à cette fonction avec une valeur assez large est susceptible de produire un SOF.
L'exercice ci-dessous explique l'enchaînement des appels au sein de la JVM pour n = 4 :
f(4) = 4 * f (3)
= 4 * ( 3 * f(2) )
= 4 * ( 3 * (2 * f (1) )
= 4 * ( 3 * (2 * 1 ))
= 24
Pour calculer f(4), on était obligé d’attendre le retour des appels de f(3), f(2) et f(1).
Xss
Chaque Thread dans une application Java dispose de sa propre pile. La pile est utilisée pour maintenir les adresses de retour des fonctions, les arguments d'appel aux méthodes, ...etc. Ainsi, si notre Thread a tendance à traiter des algorithmes récursifs, il pourra avoir besoin d'une grande pile pour toutes les adresses de retour entre autres. Avec la JVM d’Oracle (Sun), il est possible de modifier la valeur par défaut de cette grandeur moyennant l’option -Xss.
L’utilisation de cette option permet de résoudre le problème dans certaines situations (comme dans le cas de l’utilisation des librairies externes qui traitent des appels récursifs). Par contre, elle n’élimine pas le problème mais ne fait que le retarder.
TailRec
Une des solutions pour ce type de problèmes est de transformer les appels récursifs en appels itératifs. Par contre, certains langages fonctionnels (en particulier les langages fonctionnels purs) interdisent la mutation des états et encouragent l’utilisation de la logique récursive.
Pour remédier à l'explosion de la pile, Scala, comme langage hybride, propose une solution élégante qu’on résume par le suivant :
Si le dernier appel dans la fonction serait un appel récursif de la même fonction, le compilateur transforme la méthode automatiquement en appel itératif.
Cette condition ne s’applique pas pour notre premier exemple étant donné que le dernier appel dans la fonction exécute la multiplication de n * f(n -1) calculée après que l’appel vers f(n-1) soit terminé.
Pour vérifier cette condition, on pourra changer notre méthode avec l’ajout d’un accumulateur comme :
Exemple 2
BigInteger go(int n, BigInteger acc) {
if (n < 2) return acc;
else return go(n - 1, acc.multiply(BigInteger.valueOf(n)));
}
public void factorial() {
go(N, BigInteger.ONE);
}
En version Scala, ça se traduit comme suit :
def factorial(n: Int): Int = {
def go(acc: Int, n: Int): Int = {
if (n <= 1) acc
else go(n * acc, n - 1)
}
go(1, n)
}
Les deux versions sont conformes à la condition "tailrec". Par contre, il y a deux points à souligner :
-
D’une part, le compilateur Scala détecte la présence d’un appel tailrec et transforme la récursivité de la méthode “go” en boucle itérative. Ce comportement peut être garanti par l’ajout de l’annotation @tailrec sur la méthode go (disponible depuis la version 2.8 de Scala). D’autre part, le compilateur javac ne transforme pas les appels récursifs, ce qui peut produire des erreurs SOF.
-
Bien que l'expression Scala est plus compacte avec l'utilisation des fonctions internes. La translation directe vers le langage Java n’est pas possible avec l’utilisation de fonction interne :
// Lève une erreur en compilation
BiFunction<Integer, BigInteger,BigInteger> go = (n, acc) -> go(n - 1, acc.multiply(BigInteger.valueOf(n)));
La solution proposée par Scala ainsi que d’autres langages fonctionnels permet de résoudre la moitié du problème. En effet, dans certains cas, les appels récursifs sont indirects (par alternance à titre d’exemple) :
boolean isOdd(long n) {
if (n == 0) return false;
else return isEven(n - 1);
}
boolean isEven(long n) {
if (n == 0) return true;
else return isOdd(n - 1);
}
Les trampolines représentent une des solutions destinées à résoudre cette problématique.
Trampoline
Un trampoline est une boucle qui exécute à plusieurs reprises des fonctions. Chaque fonction est appelée un thunk qui passe le relais à la fonction suivante. Le trampoline ne traite qu'un thunk à la fois, ce qui permet de diviser le programme en thunks assez petits et faire rebondir chacun sur le trampoline. Désormais, vous allez pouvoir dormir en toute tranquillité vu que vous êtes sûr que la pile ne va plus exploser.
Note : Le code source est disponible sous : https://github.com/ouertani/trampoline
Un trampoline peut se résumer en deux états et une moulinette :
-
L'état Done qui contient la valeur à la fin du calcul :
class Done<A> implements Bounce<A> {
private final A thunk;
private Done(A thunk) {
this.thunk = thunk;
}
@Override
public boolean terminated() {
return true;
}
public Bounce<A> next() { throw new Error("Don't call"); }
} -
L’état Call, qui contrairement à Done, référencie une fonction à invoquer au lieu d’une valeur de retour. L’état Call enregistre une closure permettant d'enchaîner avec l’état suivant :
class Call<A> implements Bounce<A> {
private final Supplier<Bounce<A>> thunk;
private Call(Supplier<Bounce<A>> thunk) {
this.thunk = thunk;
}
public Bounce<A> next() {
return thunk.get();
}
} -
Le trampoline. Cette méthode ne fait que boucler sur les objets états : (Done, Call) d’une manière
itérative et fait avancer les appels et le traitement jusqu'à atteindre l'état Done.public static <A> A trampoline(final Bounce<A> bounce) {
return Stream.iterate(bounce, Bounce::next)
.filter(Bounce::terminated)
.findFirst()
.map(x -> (Done<A>)x)
.get()
.thunk;
}Notre Interface Bounce qu’on vient d’équiper avec des méthodes statiques jouant le rôle de factories :
@FunctionalInterface
public interface Bounce<E> {
public Bounce<E> next();
public static <A> Bounce<A> Done(A thunk) {
return new Done(thunk);
}
public static <A> Bounce<A> Call(Supplier<Bounce<A>> thunk) {
return new Call(thunk);
}
public static <A> A trampoline(final Bounce<A> bounce) {
return Stream.iterate(bounce, Bounce::next)
.filter(Bounce::terminated)
.findFirst().map(x -> (Done<A>)x)
.get().thunk;
}
public default boolean terminated() {
return false;
}
class Done<A> implements Bounce<A> {
private final A thunk;
private Done(A thunk) {
this.thunk = thunk;
}
@Override
public boolean terminated() {
return true;
}
public Bounce<A> next() { throw new Error("Don't call"); }
}
class Call<A> implements Bounce<A> {
private final Supplier<Bounce<A>> thunk;
private Call(Supplier<Bounce<A>> thunk) {
this.thunk = thunk;
}
public Bounce<A> next() {
return thunk.get();
}
}
}
Transformation
Factorielle
Pour tester notre trampoline, la factorielle peut être traduit en :
Bounce<BigInteger> safeGo(int n, BigInteger acc) {
if (n < 2) return Done(acc);
else return Call(() -> safeGo(n - 1, acc.multiply(BigInteger.valueOf(n))));
}
trampoline(safeGo(N, BigInteger.ONE))
Paire/impaire
Or, la fonction even/odd est :
Bounce<Boolean> safeOdd(long n) {
if (n == 0) return Done(false);
else return Call(() -> safeEven(n - 1));
}
Bounce<Boolean> safeEven(long n) {
if (n == 0) return Done(true);
else return Call(() -> safeOdd(n - 1));
}
trampoline(safeEven(N))
Remarques :
-
Les exemples montrent que les signatures des méthodes ont été changées :
-
Les types de retour de T vers Bounce.
-
Les retours directs de T vers Done(T)
-
Les retours récursifs de f(t) vers Call (()-> f(t))
-
-
Le trampoline permet de résoudre le problème de SOF en gardant l’habillage récursif mais par contre :
-
Ils sont plus lents que leurs équivalents récursifs suite à la création intensive des objets contre les appels de fonctions (le garbage collector serait très sollicité au milieu des calculs)
-
Ils sont plus difficiles à lire et surtout à expliquer
-
Conclusion
Le Trampoline transforme les appels récursifs dans la pile vers des créations d’objects dans le heap.
Certes, les trampolines permettent de résoudre les effets de bord de SOF ; mais, en contre partie, ils ajoutent des lourdeurs de lecture de codes ainsi qu’un overhead de création/destruction des objects.
Il existe d’autres solutions permettant de contourner l'explosion de la pile d’exécutions comme les Free Monad ou les CPS dans d’autres langages.
D’autres solutions fonctionnent en mode hybride avec un fallback en Trampolines en cas d’exception SOF des appels récursifs.
Références
À propos de l'Auteur
Slim Ouertani est un Architecte logiciel avec une expérience dans le monde télécoms et systèmes d’information. Il a participé à la construction et la mise en place de plusieurs solutions, notamment au sein de multinationales. Certifié Java, Spring et MongoDB, Slim est passionné par Scala et JEE.
Vous pouvez en savoir plus sur ses récents travaux sur son blog et le suivre sur Twitter : @ouertani.