septembre
2010
Un article de bredelet
La construction if (condition) ... else ... se retrouve dans pratiquement tous les langages de programmation. Suivant la valeur de vérité de la condition (vrai ou faux), le premier résultat est retourné ou bien le second.
Que se passe-t-il dans un exemple simple?
Prenons le code suivant:
def f(n) =
if (n < 7)
1 + f(n+1)
else
n
Dodo est basé sur le passage de continuations. Ici les deux continuations pour le if sont:
1 + f(n+1)
et
n
Donc l’instruction if… else… doit examiner la condition (n < 7), et en fonction de son résultat choisir la continuation qui correspond.
La logique s'apparente à:
# Calculer la valeur de vérité
n résultat
# Choisir une continuation
match(résultat, true) ->
1 + f(n+1)
|
n;;
Mais on peut faire mieux. Imaginons que l’opération de comparaison < ne retourne pas une valeur de vérité, mais plutôt choisit une continuation. Transformer cela en valeur de vérité revient à:
n
true
|
false;
Voyez-vous où j’en viens? Pour la construction if… else… il suffit de remplacer les continuations dans l’expression ci-dessus. Soit:
n
1 + f(n+1)
|
n;
La construction if (a < b) ... else ... peut être traduit en forme avec continuations par une simple transformation, comme décrit ci-dessus.
Je vais appeler la fonction qui correspond à l'opérateur <, "lessThan". Le type de la fonction classique pour les entiers est:
Fun(int,int->bool)
Le type de la fonction basée sur les continuations est en dodo:
Fun(int,int->(),())
Et on pourrait l’écrire un peu comme:
def lessThan = fun (int a, b) -> yes(), no()
{
{- Code pseudo-assembleur -
COMPARE(a,b)
IFNEGATIVE yes()
no()
-}
}
C’est simple et efficace.