Ok

En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Ces derniers assurent le bon fonctionnement de nos services. En savoir plus.

Les fonctions

Après les catégories, les fonctions. 

Les fonctions

Une fonction c'est... 

Un être potentiel, défini par sa capacité à transformer n'importe quel élément issu d'un tas d'objets. 

Un tas d'objet, c'est un type d'objet, et une fonction transforme tout élément d'un tas en un élément d'un autre tas.

f: A -> B         après le ":" , la signature de la fonction. 

La définition de la fonction, c'est autre chose, elle s'exprime en général avec une "chose" supposée être mise à la place d'un élément quelconque de A. 

f = lambda a  EXPRESSION(a) 

Ici, EXPRESSION (a) désigne une formule avec a en variable libre et qui produit un B (bien sur).

Bon on attaque direct, on veut définir des fonctions en fonction d'autres fonctions, avec l'aide d'"opérateurs": 

f then g = lambda x g(f(x)) 

Une fonction, c'est une abstraction pour un "calcul", qui transforme une donnée. C'est un "pas" élémentaire dans une marche globale, mais abstrait: il faut appliquer la fonction pour qu'un travail soit fait. En attendant, c'est juste un plan, un ordre, une recette. 

On notera "id" la fonction identité. 

Au fait,

f then id == f 

id then f == f

Bien sur le "==" est assertif: il dénote l'égalité entre deux expressions définissant des fonctions. 

Le rêve, et fantasme assumé ici, est de ne jamais parler des fonctions à partir de leur définitions, la lambda pue. On veut parler de tout ça de haut, on n'est pas des programmeurs, nous, berk. 

La curryfication. 

Les fonctions de plusieurs arguments sont en fait des fonctions de un argument composées, qui se passent des fonctions. 

f: A , B -> C   se note en fait f: A -> B -> C

Haskell Curry a inventé tout ça. Au fait c'est le Curry de Curry Howard et le Haskell du langage de programmation... 

 

HaskellBCurry.jpg

 

Les foncteurs 

Les types d'objets peuvent être transformés. Par des "foncteurs". 

Les foncteurs les plus connus sont les "monades". On va bien sur considérer ici exclusivement les monades... 

En gros, un foncteur c'est une monade qui n'a que l'opérateur "map". Les monades ont des opérateurs supplémentaires.

Par exemple, Option (ou Maybe). 

OP(A) est un nouveau type construit à partir de A, avec un élément en plus, NONE. Cela permet d'exprimer des raisonnements en supposant (indument) que tout type possède une valeur supplémentaire "null", "none", "rien", "zéro pointé", qui exprime l'absence, la non présentabilité, l'impossible. Par exemple, lorsqu'une opération de recherche d'un objet de type "Personne" ne trouve rien, que doit retourner l'opération? Elle pourrait retourner une Personne particulière, la personne vide, mais cela serait paradoxal: s'il n'y a personne, il n'y a pas quelqu'un. On convient donc, trop souvent, de retourner une valeur unique, le fameux, l'infâme "null". C'est pour cela qu'une opération qui retourne soit disant une Personne et qui ose à son gré retourner parfois "null" ne peut prétendre être "typée". Elle est plutôt, et à strictement parler, "vérolée": tremble utilisateur ! On te ment.

C'est ainsi donc, finalement, pour cela que OP, comme type suprême, permet de rétablir l'honnête: tu recevra dans tous les cas un élément du type "OP[Personne]" et parfois, NONE, c'est à ça qu'on le reconnait. Voilà qui est propre. 

Mieux! OP permet d'appliquer à ce qu'il cache toute opération spécifique du scellé objet: avec une fonction.

p: OP[Personne]

p.map( x => x.désignetoi())  

La fonction "cachée" désignera toujours une personne, à moins qu'on lui donne NONE. Dans ce cas, map retournera DIRECTEMENT NONE, et donc évitera la confrontation de l'absence et de l'opération qui ne la supporterait pas. 

Bon on arrête là. OP, Maybe est le truc du fonctionnel pour en terminer avec les pointeurs nuls. Simple, efficace et qui aurait du être adopté bien plus tôt dans l'histoire, cela nous aurait fait perdre moins de temps... 

 

En fait, tout ce qu'on va dire s'applique à OP mais en fait à n'importe quel autre "foncteur". Imaginer qu'un foncteur est un truc aussi stupide que "Option", qui permet de représenter n'importe quel objet de type X, y compris son absence, qui plus est typée, m'a toujours ravi. Représenter l'absence par un élément supplémentaire est jouissif, désolé. Que la quintessence de la monade soit précisément cette construction est une bénédiction. Profitons en. 

L'opérateur "return"

Considérons la fonction "OP.r". Par définition, elle construit un objet de type OP(A) à partir d'un objet de A. Elle ne produit jamais "NONE". Un foncteur c'est pas bijectif, et au combien.

OP.r: A -> OP(A), et cela "pour tout" A.

En fait, OP.r marche pour n'importe quel objet, de n'importe quel type. Une fonction générique, en quelque sorte. 

Il s'agit du constructeur élémentaire, de l'application primale. On l'appelle "return", ou "point".  

Le "map"

Maintenant, prenons OP(A), et une fonction de A vers B. Et bien, 

OP.m: OP(A) -> (A->B) -> OP(B) 

OP.m la fonction "supérieure" de "mapping", va transformer OP(A) en OP(B).

On reconnaitra ici la célèbre "commutabilité" de la théorie des catégories: 

A partir d'un a dans A, je peux: 

- appliquer une fonction de type A->B, puis construire un OP(B) avec OP.r

- construire un OP(A) grâce à M.r, puis appliquer OP.m à la fonction et obtenir un OP(B)

Il va sans dire que les deux OP(B) que l'on va obtenir sont égaux, par définition. 

Si f: A->B, 

f then OP.r == OP.r then f 

 

Le "flatmap" et la monade 

Il y a un autre "opérateur" de foncteur, "flatmap", "bind" ou ">>="

OP.fm : OP(A)   -> (   A->OP(B)   )  -> OP(B)

On commence tout de suite à bétonner en reliant fm et m:

OP.fm(f then OP.r) == OP.m(f) 

C'est assez logique en fait: fm porte sur une fonction qui produit un OP(B), lui même construit par "r". Ce type d'assertions est assez naturel, et typique des catégories: tout ce qui est naturel se manifeste, c'est fait pour, c'est la nature... Il s'agit d'un raisonnement "aux dimensions": les lois de la nature c'est pareil, E = m * v^2, c'est pas dur à trouver. 

Commentons avec la sémantique de Option.

Soit un calcul qui donne une OP(A) et un calcul qui donne une OP(B). On veut séquencer les deux calculs, sachant que le deuxième s'exprime en fonction d'un "A". Le "then" ne marche pas: en effet, le deuxième calcul ne peut avoir lieu si le premier retourne NONE: un pointeur null ça fait planter. Il faut donc, pour séquencer correctement, tester le pointeur null, ici le NONE. Et  bien, imaginons un séquenceur intelligent, dépendant de OP, qui le fasse, bingo, c'est "fm". 

OP.fm( résultat du calcul1, fonction définissant le calcul2) = résultat du chainage du calcul1 et du calcul2

C'est cette expression qui fait dire que la monade est l'"essence du séquencement" en programmation: la présence du NONE, qui peut survenir dans n'importe quel calcul intermédiaire implique bien sur alors la valeur finale du calcul (NONE, bien sur). 

Mais c'est grâce au fait que OP est une monade, et donc en fait à sa fonction flatmap, qu'on "peut" enchainer des blocs fonctionnels construits indépendamment. 

La notation ">>=" permet d'avoir un "flatMap" exprimé en notation infixe. C'est le nouveau "then".

flatMap est une fonction de fonction étrange, qui connait intimement sa monade: elle plonge dedans, trouve l'objet encapsulé, et lui applique une fonction de création d'une autre monade. C'est pour cela que si la fonction de création est le "return", fonction de création de base, on obtient l'identité: 

OP.fm(OP.r) == id 

La séquence 

On en vient à la séquence "monadique", qui permet de chainer des calculs en se ramenant, cela m'avait perturbé au début, tant je trouvais cela ridicule: quoi ? Tous ces efforts pour se ramener à de l'impératif ? 

En gros, on peut archiver dans un contexte (un "for" scala, typiquement, ou un "do" haskell), plusieurs objets d'un type de monade donné (une seule, pas de mélange), les nommer, appeler des fonctions avec ces noms, puis finalement générer une expression de sortie avec ces noms. Et bien le résultat sera une instance de ce type monadique, construit avec l'expression de sortie. 

La construction fonctionnelle est une suite de flatMap emboités (c'est pour cela qu'on l'appelle "bind") représentant chaque extraction monadique nommée, finalisée par un map.

Toute les utilisations des monades mettent en valeur cette construction. Par exemple, si des "get" dans des hashtables retournent des OP, on peut faire avec profit: 

for ( x<- OP(1) ; y <- OP("foo")) yield x + y.length 

retourne OP(4)

 

Le Kleisli 

Un autre opérateur c'est K: 

f K g = f then OP.fm(g) 

K est une manière de faire des flatmaps dans l'ordre, et donc permet d'exprimer "naturellement" (au fur et à mesure qu'on le fait) des calculs. 

Ici, la notation fait que "K" trouve tout seul le bon fm à appliquer suivant les types des valeurs de retour des fonctions. 

K est l'opérateur "fish" noté ">=>"

f : A -> OP(B) 

g: B -> OP(C) 

et donc f >=> g : A -> OP(C)

 

Le Kleisli a bien sur de super bonnes propriétés, par exemple: 

f K OP.r == f      (bien sur ici,  la deuxième fonction a pour domaine le type d'option...

OP.r K f == f

f K g K h == (f K g) K h == f K (g K h)

 

La monade STATE

On va se permettre (après coup) un petit ride sur la monade STATE. 

Pour commencer, le type de la monade STATE est un type FONCTIONNEL, un type de fonction. 

STATE(S,A) = S =>(S, A) 

A partir de là, on va pouvoir élaborer... S est le type de stockage du "state", et A son expression. Le type de A peut être quelconque pour un STATE donné, et c'est là une première source d'obscurité, ou de compréhension profonde.

Prenons un state qui serait une pile (par exemple). Une liste d'entiers. 

STATE n'exprime pas une structure de données, mais ce qu'on peut faire avec, en fait TOUTES les opérations possibles sur le type de stockage qu'il/elle encapsule. 

pop = s == Nil => (Nil, None) , s == h::t => (h, t) 

push a =  s => (a::s, Unit) 

Les deux opérations expriment des opérations possibles et retournent des STATES (des objets de type STATE, c'est à dire des fonctions). Ainsi, pop() (  List(1,2) )  retournera  (List(2), 1)  comme de bien entendu.

 

On a donc bien ici un principe de construction de programme, et non pas de la simple programmation... 

Mieux que ça, 

map state: STATE  f: A => B =   s => ( state(s).S, f ( state(s).A )  ) 

flatMap state: STATE f: A => STATE(S,B)  =  s =>   f (state(s).A)   (state(s).S) 

On va utiliser Kleisli et donc construire un programme, complètement abstrait: 

pop() >=> x => if (x.isempty) push(1) else push(2) ) >=> x => push(33) 

Dans ces chaines d'instructions, le "state" est passé magiquement de manière invisible, chaque fonction

intermédiaire prenant en paramètre la valeur calculée précédemment. 

 

Types algébriques

Il nous faut parler des types dits "algébriques" car défini suivant les cas... Il faut bien pouvoir aussi définir les types en les composant, et ici on exprime qu'un élément est d'une type donné quand il est "ça" ou (|) "ça". "ça" cela peut être une suite fini de cas. 

L'arbre "ou/et" de définition fait ainsi toute l'algèbre de la définition des types. Ah que c'est bon que de calculer sur autre chose que des nombres...

List(A) = NIL | A  List (A)

en gros une liste de "A" (on a bien un foncteur pour commencer) et bien c'est soit NIL , soit  la concaténation d'un objet de type A et d'une liste de A... La définition est "récursive", y a pas que les fonctions. 

Un point: y a pas non plus que Haskell dans la vie et ma syntaxe c'est celle qu'est à moi.

De plus, deux listes se concatènent avec l'opérateur (de liste) "++". 

Il faut comprendre que List est un "foncteur", et que le type algébrique est un constructeur de type paramétré par un type. Nous voilà avec un langage de programmation qu'est déjà bien puissant... 

Folding

Les fonctions récursives, c'est bien et les schémas de récursion encore mieux. Ce sont des fonctionnelles, des fonctions de fonctions et l'incontournable "foldr" (ou "reduce") se doit d'être décrit. 

Soit une fonction à deux arguments, qui donne un résultat, par exemple l'addition des entiers: 

f: A -> A -> B

"foldr" se définit sur une liste comme donnant ce résultat, à partir d'une fonction comme ça, et d'une valeur initiale du résultat. Il s'agit de se déplacer sur la liste, et d'accumuler.  

foldr : fonction  valeur_initiale_de_type_B    List A  -> B 

foldr f b NIL = b   // b est bien une valeur initiale, fin de récursion, la valeur initiale est le résultat. 

fold f b (h:t) =   f   h     (foldr f b t )    // on extrait la tête de liste et on récurse... 

On a bien le "schéma" général de calcul qui consiste à prendre le premier élément de liste, et l'additionner au "reste", qui une application récursive sur le reste de la liste...

Grâce à foldr, on a bien des expression purement fonctionnelle de calculs récursifs variés: 

sum = foldr + 0 

filter g = foldr ((lambda x if (g x) (List x ) else NIL )  then ++ )  NIL 

En effet,

    filter (lambda x x == 1) NIL == NIL 

    filter (lambda x x == 1) List(1) == 1  (...)  foldr (...) NIL NIL == List 1 ++ NIL 

Bien évidemment, ces schémas de récursion, sortes de méta programme, se trouvent à faire pour tous les types qu'on peut définir. Faut abstraire dans la vie.

 

LES folds

Il y a en fait plusieurs folds... 

La définition de "sum" faite ici avec foldr est consommatrice de "pile": 

sum (1 2) = 1 + (foldr '+  0 (2)) = 1 + 2 + (foldr '+ 0 ()) = 1 + 2 + 0

Il faut attendre la toute fin de l'exploration récursive pour enfin pouvoir additionner quelquechose...

C'est pour ça qu'on a fait foldl (fold left):

foldl f b nil = b        // comme pour foldr

foldl f b (h:t) =  foldl f ( f b h) t        // on calcule DABORD  une operation binaire) 

Ainsi donc   foldl + 0 (1,2) = foldl f (0 + 1=1) (2) = foldl  f  3 () = 3

Pas de mémorisation inutile en apparence, pourtant, la fonction est bien récursive et consomme de la pile aussi...

Folding généralisé

On peut folder n'importe quoi. Par exemple des arbres. 

On reprend. 

Tree(A) = NIL | Tree(A)     A      Tree(A)

tfold : B -> f -> Tree(A) -> B       (avec f : B -> A -> B -> B)

tfold b _ NIL = b ; tfold b f  (l x r) = f ( tfold b f l ) x (tfold b f r) 

Alors, on peut lister les valeurs des noeuds d'un arbre: 

flatten (NIL) = NIL ; flatten l x r = flatten (l) ++ List(x) ++ flatten (r)

Autrement dit: 

flatten = tfold NIL (lambda ( l x r )  l ++ List(x) ++ r)

 

Les schémas de récursion sont importants, tu parles. Revenons sur le plus simple d'entre eux

 

Super Types

Un type a un type, on dit une "sorte" (kind). Integer a pour sorte "*", et OP, "* -> *". 

Un Functor, c'est donc un "* -> *", mais avec une methode, dite "fmap" en fait ici "m".

F.m : (A -> B) -> F(A)  ->  F(B) presque comme on avait dit... 

Les "classifications"

List est bien sur une monade. List(A) un type intéressant, vraiment pas en bijection avec A puisqu'exprimant n'importe quelle multiplicité de A... On avait parlé de "++". Il vient d'autre chose qu'un type algébrique, qui n'a pas d'opérateurs à priori. Et bien pour introduire des opérateurs, on va appliquer des foncteurs, les différents types de foncteurs portant des opérateurs particuliers. 

On a vu les opérateurs m et fm, spécialisés selon les foncteurs et notés comme tels plus haut, par exemple "OP.m".

Avant de nous lancer dans l'apprentissage des syntaxes diverses de Haskell ou Scala (ce qu'on ne veut pas faire), disons qu'on peut regrouper les opérateurs et les "projeter" sur un type algébrique avec un foncteur.

Par exemple, il existe un foncteur super utile qui s'appelle le "monoïde", noté ici MON. Il a pour opérateurs 0 et + avec bien sur les signatures suivantes: 

MON(m) = 0 : m      ,    + : m -> m -> m

C'est un foncteur avec ses lois, et donc sa fonction MON.m ou fmap... 

La "freeness" ou "libertitude"

Prenons la liste, est bien on peut lui appiquer le foncteur Monoïde sur les types, et cette application est dite "libre" ("free") dans la mesure où elle est triviale, évidente. La liste est le "free monoïd" sur les types... Le "plus" monoïdal est bien sur le "++" des listes. Le Monoïde engendre la multiplicité. Notons ici que le free monoïde a pour caractéristique de NEPAS modifier ce qu'il transforme: les listes concaténées restent là. Cette interprétation de l'addition est distinguée (c'est ça la libertitude) de l'addition arithmétique, qui elle "détruit" ses entrées... 

Cette notion de libertitude (freeness) est la source d'un concept de haute volée en fonctionnel: la "free monad", parangon de la modernité en programmation.

En gros, la monade libre, c'est la libertitude que donne un foncteur spécial, nommé Free, et appliqué, c'est ça le truc, à un foncteur particulier.  Le résultat est une monade spéciale, tout comme la liste est un ensemble spécial... Etant "free" la transformation ne va pas perdre ou détruire les données d'entrée. Celles ci étant des instructions, on ne va pas "exécuter" le programme, mais en garder la représentation intacte.  

Il faut bien comprendre que Free est la concaténation d'un foncteur et d'un type. C'est sur ce type là que l'on a une monade... 

Free F A = A |   F (   Free F A   ) 

charmant emboitement, quasiment naturel, on dirait (tu parles comme c'est un hasard) une expression du point fixe (comme en (3), pardon de me citer moi même). On a une structure récursive d'application du foncteur, se terminant sur un type donné. 

Pour illustrer les propriétés de la bête, prenons OP.m définie sur OP(A). Trivialement: 

OP(A) = NONE | OP(a)  // on le rappelle

Voyons voir une expression de la fonction m dans mon langage à moi, on distingue les cas plus haut: 

OP.m f NONE  = NONE   |   OP.m f OP(a)  = OP (  f( a))      // f est bien sur une fonction de A vers B

 

Pour List c'est pareil: 

List(A) = NIL  | A List(A) 

List.m NIL f = NIL

List.m f (A LIST (A))   = List.m f ( List(a) ++ s )  = List(f(a))  ++  List.m f s   

 

Pour Free, c'est pareil:

Free F A = A | F ( Free F A )

Free.m  f  A =  Free.m  f  a = f(a)  ;    Free.m  f  F(x)   =  F ( F.m ( Free.m f) F(x)  )  

  

On continue avec les opérateurs de monade: 

Free.r  Free F(a) = a 

Free.fm  f  a = f(a)

Free.fm f Free F(X) = Free( F(X).m (Free.fm f) F(X) ) 

On a donc bien une monade, avec la flatmap définie de manière récursive... 

Pour finir, on a un operateur spécial supplémentaire pour Free, dit "lift", pour "pousser vers le haut" un bête foncteur et le transformer en monade. 

Free.lift: F(A) -> Free F A

 

Definir un DSL à partir d'un type algébrique

On en vient alors à ce qu'on fait de tout ça. 

Soit le type "Move" paramétré par "Position". On a: 

Move [Position] = Forward [Position] | Backward [Position]

L'idée est de travailler dans le monde "Free", qui va nous faire une monade de tout cela (c'est l'intérêt). 

Les fonctions forward et backward prenant Position en paramètre, au lieu de bêtement changer de position, vont retourner une monade libre en liftant l'instruction correspondante paramétrée par leur paramètre: 

def forward: Position -> Free Move Position = p -> Free.lift ( Forward (p) ) 

A partir de là, on peut appliquer le langage des monades, et enchainer les opérations: 

forward (p1) >=> backward(p2) ...

Le résultat sera l'accumulation non destructive de toutes les opérations faites, c'est à dire le programme prêt à être exécuté, complètement représenté. Le langage de programmation est donc ici utilisé d'une manière spéciale avec un "cran en plus": les structure de données sont utilisées pour représenter non pas le monde qu'on souhaite modifier, mais la machinerie qui sera utilisée pour changer le monde... Et bien ce type de programmation là, il est "post von neumann" (je me lance), quasiment gödelien, auto codé. 

Programmer avec les monades libres.

La programmation avec les monades libres se fait donc en deux temps. Typiquement en codant d'abord avec l'image par Free des types algébriques qu'on pourrait définir, et qui sont, comme de juste des foncteurs. Le résultat sera une structure de données qu'on pourra introspecter en la matchant avec les transformés par Free des différents types, laissés intacts. On peut alors soit les afficher au mur, soit les exécuter, avec l'efficacité que l'on veut... 

Une telle programmation est dite "interprétative": on code la sémantique de son programme, charge ensuite à un exécuteur d'en faire ce qu'il veut. Cette disjonction coordonnée entre les deux phases du plus beau métier du monde a peut être un avenir, mais reste suspendue à la qualité des exécuteurs. Ah la belle sémantique qui rendrait évidente les parallélismes vrais, ceux qui seraient quantisables... L'histoire n'est donc pas finie, tiens tiens... 

Le pattern "interpréteur"

Tout ça est en fait une manière convoluée et un peu prétentieuse d'appliquer le patter "interpréteur", comme expliqué avec enthousiasme au paragraphe précédent. Un autre exemple est la monade "Reader". Elle prend en paramètre une fonction dite "run" (tiens, tiens) qui à un objet configuration indéterminé associe une donnée à lire...

Reader.m (f) = run then f   // mapper c'est transformer

Reader.fm (f)  = lambda c (run then f)(c).run (c)    

2 choses ici.

- Un Reader "calculé", comme par exemple ici '(run then f)(c)'    (f ayant pour domaine un Reader), contient une fonction. On l'obtient conventionnellement ici en appliquant la méthode "run", qui retourne une fonction. Fonction que l'on peut appliquer.

On peut alors utiliser les Reader pour configurer un programme, celui n'étant exécuté QUE quand la configuration sera disponible, typiquement en appelant la méthode "run" et en lui passant en paramètre, (on dit aussi "injecter") une configuration particulière...

On commence par construire une abstraction du programme.

monprogramme = for ( x<- Reader(c-> c.get) ) yield program(x)

Cela utilise le "for" monadique, qui permet de chainer tout ce qu'on veut, le résultat est une monade Reader, qu'il n'y a plus qu'à exécuter dans le contexte de son choix. 

Par exemple

maconfig = anykindofconfig

puis

monprogramme.run(maconfig)

 

 

 

(1) https://wiki.haskell.org/Monad

(2) http://www.cis.upenn.edu/~cis194/spring13/lectures.html

(3) http://francoiscarmignola.hautetfort.com/archive/2017/08/26/les-types-5974046.html

(4) https://markkarpov.com/post/free-monad-considered-harmful.html

Écrire un commentaire

Optionnel