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.

31/03/2018

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). Supposons que ce deuxième calcul soit justement une fonction de A vers B suivie d'une bête construction d'option. 

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 sera bien sur alors la valeur finale du calcul. Mais c'est grâce à la monade, en fait à sa fonction flatmap, qu'on "peut" enchainer des blocs fonctionnels construits indépendamment. 

Pour finir, bien sur: 

OP.fm(OP.r) == id 

La notation ">>=" permet d'avoir un "flatMap" exprimé en notation infixe. 

 

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 fure 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)

 

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 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 : type(f)  B   List A  -> B 

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

fold f b (x s) =    x      f       foldr f b s 

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. 

 

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... 

 

(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

Les commentaires sont fermés.