Notation pour calcul fonctionnel

Commençons par s’entendre sur une manière d’exprimer les concepts avec lesquels nous allons travailler. Il est question de décrire des algorithmes et des opérations de calcul. Par souci de simplicité, considérons que ces calculs manipulent des entiers naturels et des fonctions. Une fonction est l’expression d’un calcul qui transforme ses arguments en un résultat; tant les premiers que le second peuvent être des entiers que des fonctions. Toute fonction est décrite de la manière qui suit:

{|<paramètres>| <operation>}

Les paramètres de la fonction sont décrits à l’aide d’une liste d’identificateurs alphanumériques séparés par des blancs. Si la fonction ne comprend aucun paramètre, la séquence |<paramètres>| pourra être omise. Quant à l’<operation>, il s’agit de l’expression du calcul appliqué aux paramètres pour obtenir le résultat.

L’opération implique fréquemment l’application d’autres fonctions, c’est-à-dire l’exécution de l’opération encodée par cette fonction à partir d’arguments choisis. La syntaxe d’application d’une fonction f à une séquence d’arguments <args> est

[f <args>]

Les valeurs fournies en arguments sont séparées par des blancs. Finalement, introduisons la définition de fonctions, par lesquelles on donne un nom à une valeur. La syntaxe utilisée sera

<nom>: <valeur>

Exemples

Addition de deux entiers

[+ 5 6]
-> 11

La ligne commençant avec -> dénote le résultat de l’évaluation de l’expression. On voit que l’addition consiste ici en l’application de la fonction + aux arguments 5 et 6.

Opération arithmétique complexe

[* [- 8 5] [/ 50 [+ 7 3]]]
-> 15

Ici, on utilise les fonctions arithmétiques +, / (division), - (soustraction) et * (multiplication). Les applications doivent être calculées de l’intérieur vers l’extérieur; l’ordre d’évaluation des applications d’un même niveau est sans importance.

Application d’une fonction anonyme

[{|x y| [* x [- y x]]} 8 10]
-> 16

L’application d’une fonction implique de substituer à chacun de ses paramètres l’argument correspondant. Ici, on substitue donc 8 à x et 10 à y, de sorte qu’on évalue [* 8 [- 10 2]], d’où le résultat.

Fonction sans paramètre

{+ 8 9}
-> {+ 8 9}

La fonction sans paramètre énoncée ci-haut n’est pas appliquée, aussi son évaluation renvoit comme valeur la fonction elle-même. Par contre,

[{+ 8 9}]
-> 17

Définition d’une fonction

carre: {|x| * x x}
[carre 8]
-> 64

On associe le nom carre à la fonction qui calcule le carré d’un nombre passé en paramètre; on peut ensuite l’appliquer.

Fonction qui calcule une autre fonction

curry2: {|f| {|x| {|y| [f x y]}}}
ff: [curry2 {|x y| [+ 2 [* x [/ y 2]]]}]
ff
-> {|x| {|y| [{|x_ y_| [+ 2 [* x_ [/ y_ 2]]]} x y]}}
[ff 8]
-> {|y| [{|x_ y_| [+ 2 [* x_ [/ y_ 2]]]} 8 y]}
[[ff 8] 12]
-> 50

La fonction curry2 effectue la currification d’une fonction de deux paramètres donnée. Cette opération convertit la fonction passée en paramètre de manière à ce qu’elle puisse être appliquée partiellement, un paramètre à la fois.

Forme conditionnelle

pair?: {|n| [decide [z? [/ n 2]] {1} {0}]}
[pair? 8]
-> 1
[pair? 99]
-> 0

La fonction decide prend trois paramètres: une condition interprétée comme une valeur booléenne et deux fonctions sans paramètre. Si la condition est vraie (la condition est un entier strictement positif), le résultat de decide est l’application de la première des deux fonctions; sinon, c’est l’application de la deuxième. Notons que dans cet exemple, la fonction z? renvoit 1 si son argument est 0, et 0 sinon..

Définition d’une fonction récursive

fact: {|n| [decide [z? 0] {1} {[* n [fact [- n 1]]]}]}

Nous en venons finalement au but de ce texte: la récursivité. La fonction définie ci-haut est la factorielle de n, soit le produit de la séquence d’entiers de 1 à n, avec [fact 0] égal à 1 par définition. On voit que [fact n], pour n différent de 0, est défini en fonction de [fact [- n 1]]. La forme conditionnelle decide assure que le calcul n’est pas réitéré à l’infini.

La définition ci-haut a quelque chose d’inconfortable d’un point de vue mathématique: si je n’avais pas ajouté le système de définition à ma notation de calcul fonctionnel, serait-il possible d’exprimer un algorithme récursif? L’application répétée d’une opération jusqu’à ce qu’une condition soit remplie apparaît pourtant très naturelle. Il m’apparaît bien embêtant qu’il soit essentiel de recourir à un dictionnaire de définitions pour exprimer un tel calcul.

La suite du texte montre comment, en fait, le système de définition n’est pas nécessaire pour exprimer un calcul récursif, grâce au combinateur Y. Nous allons découvrir cet opérateur fonctionnel par une stratégie chère aux programmeurs: la refactorisation.

Construction du combinateur Y

La construction qui suit est une ré-écriture d’une partie du chapitre 9 du livre The Little Schemer. Les étapes de construction du combinateur sont les mêmes, mais le développement est basé sur la fonction factorielle plutôt que sur un calcul de liste, et le sujet est traité dans un style prosaïque distinct.

Écrire la récursion

Nous cherchons donc à écrire la fonction fact définie ci-haut sans recourir au système de définition. Limitons dans un premier temps nos attentes: écrivons une fonction qui renvoit une résultat correction pour n = 0, mais qui génère une erreur en d’autres cas. On utilise dans ce dernier cas la fonction erreur, qui prend un paramètre sans l’utiliser.

{|n|
  [decide [z? n]
    {1}
    {[* n [erreur [- n 1]]]}]}

On peut utiliser cette factorielle-pour-0 pour écrire une version améliorée, qui renvoit le bon résultat pour n <= 1 et génère une erreur pour les autres valeurs de n.

{|n|
  [decide [z? n]
    {1}
    {[* n [{|n|
             [decide [z? n]
               {1}
               {[* n [erreur [- n 1]]]}]}
           [- n 1]]]}]}

On peut appliquer cette fonction à 0 et à 1 et on obtient le bon résultat (soit 1 dans les deux cas). On peut même améliorer encore la version ci-haut en s’en servant pour décrire une factorielle qui renvoit le bon résultat pour n <= 2:

{|n|
  [decide [z? n]
    {1}
    {[* n [{|n|
             [decide [z? n]
               {1}
               {[* n [{|n|
                        [decide [z? n]
                          {1}
                          {[* n [erreur [- n 1]]]}]}
                      [- n 1]]]}]}
           [- n 1]]]}]}

C’est vraiment fastidieux, il est impensable de définir la factorielle ainsi pour un entier n arbitraire.

Sortir la récursion de la forme conditionnelle

Le but ici est de factoriser l’écriture de nos factorielles partielles de manière à éliminer autant que possible les répétitions. Une première approche en ce sens vient de l’observation que dans chaque forme conditionnelle rencontrée, on écrit une nouvelle factorielle plus restreinte. On pourrait donc tenter de sortir cette définition de facto de la forme conditionnelle. Pour factorielle-0, ça donne:

[{|f|
   {|n| [decide [z? n]
          {1}
          {[* n [f [- n 1]]]}]}}
 erreur]

C’est une forme un peu surprenante pour écrire une fonction: la fonction factorielle-0 résulte de l’application d’une fonction parent. Mettons en oeuvre le même principe pour écrire factorielle-1. Cette fois-ci, la fonction à appliquer à la fonction parent est factorielle-0:

[{|f|
   {|n| [decide [z? n]
          {1}
          {[* n [f [- n 1]]]}]}}
 [{|f|
    {|n| [decide [z? n]
           {1}
           {[* n [f [- n 1]]]}]}}
  erreur]]

On peut répéter l’opération pour écrire factorielle-2, où la fonction à appliquer à la fonction parent est factorielle-1:

[{|f|
   {|n| [decide [z? n]
          {1}
          {[* n [f [- n 1]]]}]}}
 [{|f|
    {|n| [decide [z? n]
           {1}
           {[* n [f [- n 1]]]}]}}
  [{|f|
     {|n| [decide [z? n]
            {1}
            {[* n [f [- n 1]]]}]}}
   erreur]]]

Factoriser la fonction parent

On a encore un élément répété! Cette fois-ci, c’est la fonction parent, qui est ré-écrite pour chacune de ces applications, jusqu’à finalement lui appliquer erreur. Nous allons donc ré-écrire factorielle-0 en donnant un nom à cette fonction parent, de manière à éviter de la répéter.

[{|y| [y erreur]}
 {|f|
   {|n|
     [decide [z? n]
       {1}
       {[* n [f [- n 1]]]}]}}]

Si ça ne semble pas beaucoup améliorer factorielle-0, voyons ce que ça donne avec factorielle-1:

[{|y| [y [y erreur]]}
 {|f|
   {|n|
     [decide [z? n]
       {1}
       {[* n [f [- n 1]]]}]}}]

L’écriture est prodigieusement abrégée! C’est encore mieux pour factorielle-2:

[{|y| [y [y [y erreur]]]}
 {|f|
   {|n|
     [decide [z? n]
       {1}
       {[* n [f [- n 1]]]}]}}]

Décider de l’exécution d’une autre étape du calcul

Il demeure une répétition dans l’expression de nos factorielles partielles: l’application [y ... [y erreur]...]. Cette application articule les étapes successives du calcul. En effet, chaque application de y donne un {|n| ...} respectivement appliqué à n, n-1 … 0.

Donc, bien que l’articulation d’une étape à l’autre soit faite par l’application répétitive [y ... [y erreur]...], la décision d’exécuter ou non une autre étape du calcul est prise ailleurs: dans la forme conditionnelle decide de la fonction passée en paramètre. Changeons donc cela: au lieu de forcer un nombre fixe d’étapes de calcul, calculons l’étape suivante après avoir décidé d’arrêter ou de continuer. En d’autres mots, si n est 0, c’est bon, on arrête. Dans le cas contraire, on calcule alors la fonction à exécuter pour poursuivre le calcul. Cette idée s’exprime sous la forme suivante:

[{|y| [y y]}
 {|f|
   {|n|
     [decide [z? n]
       {1}
       {[* n [[f f] [- n 1]]]}]}}]

Cette application donne un calcul récursif! L’application de la fonction {|y| [y y]} amorce ce calcul, en prenant dès lors la décision de faire une étape de plus (e.g. calculer [y y]); c’est une décision facile, puisque le calcul du résultat nécessite au minimum une étape! Ensuite, le contrôle est donnée à la fonction {|n|...} obtenue par cette application de {|f|...} avec lui-même en paramètre. Quand une étape de plus est nécessaire pour compléter le calcul, la fonction à exécuter pour calculer cette étape est générée par l’application [f f]. En passant la fonction f en paramètre de la fonction f, on s’assure que cette génération peut être répétée au besoin.

On a donc atteint l’objectif énoncé au départ, soit d’exprimer un calcul récursif sans recourir à un système de définition. Cependant, la fonction

{|f|
  {|n|
    [decide [z? n]
      {1}
      {[* n [[f f] [- n 1]]]}]}}

demeure très différente de la forme rédigée dans la définition de fact. Peut-on modifier le calcul récursif énoncé ci-haut de manière à exprimer la fonction factorielle avec la même forme exactement?

Séparer le mécanisme de récursion de l’algorithme à exécuter

Pour cela, il faut remarquer que [f f] est la fonction factorielle appelée en récurrence (qui correspond à l’appel récursif de fact dans la définition de fact). Puisqu’il s’agit d’une fonction, on peut l’exprimer par une forme {...}:

[{|y| [y y]}
 {|f|
   {|n|
     [decide [z? n]
       {1}
       {[* n [{|m| [[f f] m]} [- n 1]]]}]}}]

Factorisons la fonction {|m| ...} hors du calcul de factorielle, et renommons les paramètres fonctionnels de manière à éviter d’avoir une application [f f] en plus d’une application [y y], sachant que ces deux applications réalisent le même calcul.

[{|y| [y y]}
 {|y|
   [{|f|
      {|n|
        [decide [z? n]
          {1}
          {[* n [f [- n 1]]]}]}}
    {|m| [[y y] m]}]}]

On peut compléter la séparation du mécanisme de récursion de l’algorithme qu’on cherchait à exprimer au départ (ici, la factorielle). Il suffit de factoriser notre fonction factorielle, dont la forme correspond maintenant tout à fait à la définition fact, hors de l’application par {|m|...}.

[{|c|
   [{|y| [y y]}
    {|y|
      [c {|m| [[y y] m]}]}]}
 {|fact|
   {|n|
     [decide [z? n]
       {1}
       {[* n [fact [- n 1]]]}]}}]

L’argument de l’application externe correspond, encore une fois, à la définition de fact présentée à la fin de la première section. Cette fonction représente donc l’algorithme de calcul de la factorielle qu’on voulait encoder. La fonction de cette application externe, quant à elle, définit complètement le mécanisme par lequel l’algorithme passé en paramètre peut s’enchaîner en un nombre arbitraire d’étapes récursives. Cette fonction se nomme le combinateur Y exprimé en ordre applicatif.

Le combinateur Y est donc un opérateur fonctionnel qui donne une base théorique solide pour l’expression de calculs récursifs. Les dictionnaires d’environnement mis en oeuvre par essentiellement tous les interpréteurs peuvent être vus comme un effort crucial d’optimisation en faveur de la performance et de la simplicité d’implantation.