Les Fonctions (Deux)

On avait parlé des fonctions, mais mal. 

On recommence avec un autre point de vue, orienté vers autre chose et qui reste néanmoins dans l'axe de ce qu'on disait, et qui est qu'on doit aller vers une abstraction supplémentaire. Haskell, ou sa version perso est utilisé.

Valeur

On commence par le bas. On a des valeurs, ou objets abstraits de base. 

Pour commencer la montée gentiment, on doit admettre qu'il y a différentes sortes de valeurs. Cela nous introduit aux "types". On a au moins les nombres, et il y a différent types de nombres, les chaines de caractères et les booléens ou bits qui prennent deux valeurs. Ca fait 3 types de valeurs simples au minimum.

Type

La première abstraction est donc le "type", rassemblement de valeurs possibles avec une identité. Il y a plusieurs sortes de types, et au combien. Pour définir des types, on va les combiner et la première forme du langage qu'on est en train de définir va consister à noter des "compositions" de types. 

A = Int String 

va être le type des tuples formés d'entiers et de chaines de caractères (String). On concatène un entier et une String. La conjonction, le "et". 

A = Int, String

va être le type des valeurs qui sont soit un entier soit une String. L'un ou l'autre, la disjonction, le "ou". 

Fonction

On passera sur l'"opération", équivalent de la valeur par sa simplicité nécessaire et qui permet de faire correspondre des valeurs à une autre. On abstrait tout ça en une fonction, définie plus précisément sur des types et à destination d'un type. 

On va alors ainsi passer aux fonctions, êtres complexes, autres sortes de valeurs, et définies en deux étapes: par leur types, et par leur comportement sur les différents composants de leurs types d'entrée. 

Type paramétré 

Pour définir des types, on va utiliser un autre moyen, le paramétrage. Cela permettra de définir des sortes de fonctions sur des types en tant que tels et pas simplement en tant qu'ensembles de valeurs... héhé. Cela permettra ainsi et aussi de "transformer" des types. On va voir. 

L'archétype du type transformé est l'"option". En gros on ajoute un élément à n'importe quel type existant. Cet élément additionnel, on va l'appeler "None", alors qu'on aurait pu l'appeler "something else" ou n'importe quoi d'autre, il est "en plus". 

Option A = none, Some A 

On aurait pu dire "Option A = none, A ", pour indiquer une fonction de A vers A "plus" l'ensemble formé de l'élément "none".  En fait c'est une question de syntaxe de langage. Un élément de "Option A", quand il n'est pas "none", sera noté "Some a", avec a élément de A. 

En gros, "a" élément de A ne peut pas être noté pareil que "a", élément de "Option A"... Même si on pourrait, en fait. Il suffirait de faire le malin avec une expression contextuelle alambiquée, avec des lettres hébraïques en exposant... 

Le paramétrage de type est en tout cas bien une abstraction différente de celle de la fonction, même si cela lui ressemble bigrement. "Option A" est bien un nouveau type, même si il n'est "que" l'ensemble de toutes les valeurs de toutes les applications sur A de toutes les fonctions possibles de A vers l'union de A et de none...

De ce point de vue, un type paramétré définit ainsi un ensemble de fonctions. Et dans la mesure ou une fonction représente une opération, un ensemble d'opérations, donc,  un type paramétré est un "type de calcul". Chaque calcul de l'ensemble ayant un résultat dans l'ensemble ainsi défini. On a abstrait ici l'opération, le calcul lui même...

On généralise immédiatement à la véritable abstraction et qui est l'ensemble pour tout type B, des fonctions de B vers Option A , et qui matérialise véritablement un calcul général, associant non pas A à B, comme le ferait une simple fonction bébête, mais Option A à B. Bien sur Option A est en fait un type, qu'on pourrait qualifier d'ordinaire, simplement ce qu'on veut dire avec mauvaise foi ici, c'est que le choix de ce type paramétré là caractérise le calcul exprimé par les fonctions en question sur le type paramètre: on a ici un calcul produisant un A qui s'exprime avec une caractéristique nouvelle, représenté par le type paramétré par A: il peut, c'est pour ça qu'on fait tout ça, "échouer". 

Les fonctions du genre "B -> Option A" peuvent ainsi retourner none, et donc convoyer une sémantique d'"échec", ou d'"absence". On a réinventé le "pointeur Null". 

On a ainsi une sémantique (une signification) pour un typage de fonction qui serait "intelligent". On abstrait, on représente une signification supplémentaire associée à un sous ensemble de l'espace global des fonctions. C'est pour cela que la définition des ensembles supports d'une fonction ne suffisent pas pour "genrer" précisément une fonction. Une fonction peut aussi appartenir au type de fonction défini par un domaine de destination "du type" "Option X". Bref, les types de fonction c'est pas simple... 

Il y a bien sur d'autres types paramétrés... Autant qu'il y a de "types" de calcul. Cette adjonction là qui caractérise des ensembles variés de calculs qui se ressemblent s'appelle l'"effet". Un "effet" c'est ce qui type partiellement un calcul, et qui s'exprime par une transformation particulière apportée à un type. Pour enfoncer le clou, on veut dire que "Option A" c'est une modification de A, et pas simplement un type quelconque issu de A. 

La composition 

On connaissait la composition classique des fonctions. Les fonctions, ça se compose, merci. 

L'opération de composition dit "rond" : f o g = h , h(x) = f(g(x)) , comme "combinateur" de fonctions est le parangon des combinateurs, des fonctions sur fonctions. Au fait, on parle bien de programmation "fonctionnelle": les valeurs auxquelles on s'intéresse le plus, ce sont les fonctions. Et donc on cherche le "méta", le "combinateur".

Quand est il des fonctions vers des types à effet ? Et bien on peut pas. C'est tout le problème. Car une fonction est totale, elle prend et ne prend que ça, que les éléments de son type d'entrée. 

A -> Option B

B -> Option C 

parangons d'opérations "typées" par leur destination, ne sont pas composables simplement, point final. 

On aimerait donc une sorte d'opération, de "méta opération" sur fonctions, un combinateur... Cette sorte de combinateur, associé à l'effet permettrait de faire plusieurs choses: d'abord composer bien sur: 

X : (A -> Option B , B -> Option C ) -> A -> Option C

ensuite, si possible, encapsuler automatiquement l'effet et savoir quoi faire quand ses particuliarités se manifestent. Cela ferait une abstraction composable et aussi "additionnable". On profite pour faire la même chose aux choses qui se ressemblent. Ainsi, quand la fonction sur Option B  retourne un "None", et bien cet effet là  pourrait opportunément se propager tout seul comme un  grand et donner directement la valeur None à la composition. 

Evidemment, on pourrait imaginer des compositions qui ne supposerait pas comme suggéré de donner None comme résultat à toute application d'une fonction à destination de "Option X". Mais cela serait arbitraire, et tordu. Après tout, None est fait pour ça: modéliser l'échec, le trou noir, le nul. Et quand on a échoué, on a échoué. Exit.

Les classes de type

On va alors introduire l'abstraction inventée pour le langage Haskell pour regrouper les types et les améliorer sans y toucher: les "classes" de types. Alors qu'il s'agit programmatiquement d'une alternative complète à ce qu'on appelle l'"orienté objet"et même d'une technique supérieure de modularisation et de modélisation, les mêmes mots sont employés (classe, instance) et avec des significations comparables, mais radicalement autres. 

Une classe de type, c'est (déclarativement) tous les types pour qui existe un certaine ensemble de fonctions qui la définisse. Par exemple, on y va tout de suite, les types paramétrés M pour qui sont définis les fonctions "return" et "flatMap" dont les signatures respectives sont:

return : A ->  M A

flatMap: (A , A -> M B) -> M B

définiront des types à effets composables (ceux dont on parlait plus haut). On les appellera les "monades". 

Et hop, d'un coup, on a défini les classes de types, les compositions d'effets et les monades. L'essence du FP. 

De fait on a été un peu rapide. La première des classes de types, c'est Eq, qui fournit l'égalité aux objets. Pas mal, non?  Avec en plus la capacité de contrôler les types des éléments qu'on compare (ils doivent être les mêmes) et de la définir récursivement en fonction des types composites à comparer. Le reste à l'avenant, les classes de type s'étendent et un type peut ainsi être défini avec toutes les classes de types qu'il implémente. On modularise la notion de type, qui se trouve donc être composable, et capable d'agréger tout espèce de comportement.

Une alternative complète et puissante, en fait bien plus puissante que, à l'orienté objet traditionnel. La grande différence est que l'ajout, le comportement associé à la classe de type est d'emblée un module de comportement applicable à tout type, une sorte d'interface, comparable au trait Scala. Par contre, sémantiquement la classe de type est absolument intrusive, les types qu'elle commande sont soumis au contrat qu'elle transporte et impose, elle les définit, elle ne les fournit pas ! 

Les fonctions

Revenons aux fonctions. Elles ont bien des propriétés qui en font à la fois des éléments de choix pour programmer, mais aussi qui les rendent profondément (et paradoxalement) inaptes à cela. Précisons les grandes propriétés de ce qu'est la définition d'une fonction, en l'occurrence une "expression" forme syntaxique d'une reformulation avec des opérations d'une valeur issue de l'ensemble de départ, le domaine de la fonction. 

Ce n'est que cela, et à condition de n'utiliser comme opération que des fonctions au même sens, dans certains cas primitives de manière ultime, on a ce qu'on appelle la "transparence référentielle" qui fait que tout appel de fonction peut être remplacée par l'application de sa définition à ses paramètres sans changer le sens global du programme. La fonction ne fait qu'abstraire. 

La transparence référentielle s'applique ainsi aux programmes construit avec des fonctions "pures", c'est à dire RT pour leurs arguments RT. Cette "pureté" typique du fonctionnel, s'applique et s'exprime avec plus de détails selon les 3 modalités suivantes:

- pas de valeur nulle : une fonction est totale, soit exclusivement consommatrice et productrice de valeurs typées. 

- pas de lectures extérieures: à toute entrée une seule sortie, pas de demande cachée de lecture d'autres entrées.

- pas d'écritures extérieures: la seule sortie est la valeur de retour, pas d'effets de bords invisibles.

Cette pureté fait du fonctionnel une technique inutilisable dans son principe pour communiquer avec l'extérieur. Sauf si, et c'est la suite de l'histoire.  

Les effets 

On se permettra alors de sauter par dessus toute l'histoire récente des monades. La notion d'"effet" fut d'abord utilisée pour régler le premier problème. Il est parfaitement possible de se passer complètement de la valeur nulle, et la monade "option" est faite pour cela, utilisable et utilisée (par les happy few). 

Pour les IOs, on (je parle d'Haskell) inventa un type spécial paramétré nommé "IO", qu'il suffisait aux fonctions de retourner. A partir de là, une fonction spéciale dite "main" à qui on passait une telle fonction se chargeait de procéder aux entrés sorties effectives en combinant les effets, devenus "effets de bords" mais contrôlés et exclusivement contenus dans l'exécution de fonction "main" à travers la monade IO.  

Y a pas que les monades

Les monades, du moins leur utilisation, ne sont pas "issues de la théorie des catégories". Elles sont générées par des besoins concrets exprimés par les programmeurs et se rattachent aux maths par la bande en fait... Et puis il y a les "arrows" (1) qui se manifestent, et sont utilisées pour  améliorer certaines implémentations. Tout continue bien de partir de préoccupations locales. 

Les étapes de calcul

Pour finir il y a bien une sorte de valeur qui nous échappe encore: le "statement", l'étape élémentaire de calcul, l'étape de calcul. Le corps de la définition d'une fonction est typiquement faite d'un enchainement de ces étapes, séquencées, testées, répétées. Au point que programmer consiste  à combiner ces étapes, voire à les définir, puis à les combiner. 

On en vient alors à vouloir définir ce qu'il y a à faire comme des combinaisons, non pas d'appels de fonctions et d'expressions variées sur des données, mais de fonctions elles mêmes, les ensembles de données variées à considérer étant rendus invisibles. 

Par exemple, l'addition de n sempiternellement exprimée comme une fonction à deux paramètres, dont évidemment le point d'entrée: addn = x, n: x + n , pourrait se décrire aussi comme addn = f , n : f (andThen inc) * n  . 

Bref, une "algèbre" d'opérateurs, qui combinerait directement les opérations considérées comme des valeurs. 

Un tel style de programmation est à portée et se trouve peu ou prou ce qu'offre Haskell, même si conceptuellement le pas ne semble pas franchi. On peut pourtant abstraire l'étape de calcul et directement passer à  l'après calcul, le calcul du calcul, donc.   

Le principe est de se ramener à IO, qui va devenir le type de la valeur qui représente le "statement". Ce type, pratiquement d'usage universel, sera le codomaine (le type de destination) de toute fonction fabriquant une opération de calcul élémentaire. 

Les "algèbres"

Une algèbre, c'est un ensemble sur lequel existe des opérateurs, un opérateur combinant des élements de l'ensemble pour en obtenir d'autres... Ca va mieux en le disant. 

Les modifications à l'identique des programmes ou "refactoring"  ou "recomposition"

Modifier un programme après coup, pour qu'il soit plus court, plus lisible, ou plus apte à subir encore d'autres modifications, c'est le pain blanc du programmeur. Une telle activité est extraordinairement simplifiée si les fonctions qu'il a utilisé pour faire le programme à modifier sont totales et sans effets de bords en lecture ou écriture. 

Prenons quelques exemples: 

1) ré-ordonner

val a = f(x); val b = g(x) 

Si f et g font des effets de bord en écriture, c'est impossible.

Si f et g font des effets de bord en lecture sur des données pour lesquelles elles sont de effets en écriture, non plus.

Les statements d'un programme sans effets de bord ne sont PAS séquencés implicitement. On peut les mélanger, ou les exécuter en parallèle, bref en faire ce qu'on veut. 

2) Dé-dupliquer

{ val a = f(x); val b = f(x) ; g(a, b) }  est il équivalent à { val a = f(x) ; g (a,a) }  ? 

Si la fonction f fait un effet de bord, évidemment non. Alors qu'un appel (conjonction d'une fonction et d'une valeur) est UNIQUE, et peut être caché pendant toute la durée du programme. 

3) Effacer 

{ f(x) ; def g (x) = ... ; val a = g(x) ; g(x) ; a  } est il équivalent à { def g (x) = ... ; g(x) }  ? 

Si la fonction f fait un effet de bord, non. Un appel de fonction n'a pas d'existence si on ne le mémorise pas.  

On notera la différence entre "def g = " et " val a = ". Alors qu'une affectation est gratuite et ne consomme pas de ressources de calcul, un appel de fonction est "cher" et se doit d'être "caché". "def" n'est PAS une abstraction de l'effet de bord et ne peut pas l'être (une fusée ne peut être lancée deux fois). 

4) Abstraire

{val a = g(x) ; val b = h(x) ;  f (a); f( b) } est il équivalent à  {  f(g(x)) ; f( h(x))  }  ? 

Et bien NON en général, si "f" est capable d'attendre la terminaison d'une activité lancée par l'appel de g ou h... 

En effet,  il y aura séquencement dans le deuxième cas, et pas dans le premier, où les deux activités seront lancées en parallèle. 

On notera le caractère non évident de l'impossibilité de la recomposition du dernier exemple: il faut raisonner sur tout, et savoir les natures des effets de bords de tout avant de décider toute modification. Avec l'assurance de l'absence d'effets de bords ET de lancement d'activités "par derrière", le code très plastique, peut être changé à loisir. Viva la liberta. 

 

 

 

(1) On peut lire au moins le début de : http://www.cse.chalmers.se/~rjmh/Papers/arrows.pdf