Cours 1

Htmligure
Version & licenses
Creative Commons License

Fonctions, applications, et leurs types

Guyslain
Thursday, 21 July 2016

Retour au sommaire.

Fonctions et applications

Avec les variables, nous avons vu comment définir des expressions en utilisant des abstractions en place de valeurs explicites. L'étape suivante est de définir des expressions en utilisant des abstractions auxquelles aucune valeur n'a été attribuée, afin de faire la liaison plus tard (et avec différentes valeurs). C'est le principe des fonctions : définir une valeur dépendant d'autres valeurs qui seront fournis lors de l'application de la fonction à ses arguments. C'est donc seulement au moment de l'application que sont réalisées les liaisons entre arguments et valeurs des arguments.

Syntaxe

Il existe plusieurs syntaxes pour définir des fonctions en OCaml. De fait, les fonctions ont une place centrale en programmation fonctionnelle, il est donc utile d'avoir une marge de manœuvre pour les définir et les utiliser.

La syntaxe de base s'inspire des notations mathématiques. Les mathématiciens utilisent une flèche entre l'argument et l'expression utilisant l'argument pour définir une fonction. On retrouve cette flèche en OCaml, combiné avec le mot-clé fun rappelant qu'on définit ainsi une fonction (function en anglais).

  1. let increment = fun n -> n + 1
  2. let decrement = fun n -> n - 1

Ici nous avons créé deux fonctions, que nous avons abstraites par des variables module-locales increment et decrement. Dans chaque fonction, n est l'argument de la fonction. En fait n est une abstraction, dont la liaison est différée : c'est donc une variable qui sera liée à une valeur pas encore déterminée. L'expression suivant la flèche -> est la valeur prise par la fonction lorsque l'argument n sera lié par une application.

Pour appliquer la fonction, il suffit de la faire suivre par son argument, en séparant par un espace. Pas besoin de parenthèses pour marquer les arguments !

  1. let three = increment 2
  2. let four = decrement 5
  3. let six = (fun n -> 2 * n) 3

Dans le troisième cas de cet exemple, nous voyons qu'on peut directement appliquer l'expression de la fonction à son argument. Il n'est pas nécessaire de donner un nom à la fonction pour l'appliquer, une telle fonction est alors dite anonyme. C'est cependant presque toujours une bonne idée de nommer les fonctions, afin d'expliciter leurs rôles.

On peut bien sûr créer des fonctions à plusieurs arguments.

  1. let add = fun n p -> n + p
  2. let multiply = fun n p -> n * p

  3. let forty_two = multiply 7 6
  4. let twenty_three = add 18 5

À nouveau, les arguments sont donnés après le nom de la fonction, sans parenthèse inutile, et sont séparés par des espaces (ou des sauts de lignes) et non par des virgules. Si un argument est une expression complexe (ni un littéral, ni un identifiant), il est nécessaire de parenthéser cet argument, pour indiquer que tout le contenu de la parenthèse constitue un seul argument. Par exemple

  1. let seventeen = add (multiply 2 3) (3 + increment 7)

  2. let seventeen =
  3. let six = multiply 2 3 in
  4. let eleven = 3 + increment 7 in
  5. add six eleven

On peut considérer dans ce cas l'espace comme l'opérateur binaire infixe d'application, et que cet opérateur a la priorité maximale sur tous les autres opérateurs. Ainsi si on écrit l'expression :

  1. add multiply 2 3 3 + increment 7

le compilateur comprend que la fonction add est appliqué à 4 arguments : l'identifiant multiply, et les littéraux 2 , 3 et 3 . Le résultat serait le membre gauche de l'addition. Syntaxiquement, chaque argument doit apparaitre comme un identifiant, un littéral, ou une expression quelconque parenthésée. Le nombre d'espaces correspond donc au nombre d'arguments appliqués.

Liaisons des arguments

L'application s'évalue en liant les identifiants des arguments aux valeurs données comme arguments au moment de l'application. Nous avons mentionné que la création de variable est une abstraction avec liaison immédiate, alors que la création de fonction est une abstraction dont la liaison est différée au moment de l'application. Les mécanismes d'évaluations et de typage partagent donc de nombreux points communs dans les deux cas.

En fait, on peut aller plus loin et donner une définition de la création de variable en terme de création d'une fonction et son application immédiate. Comparons les deux codes suivants :

  1. let expression1 =
  2. let n = 21 in
  3. n * 2

  4. let expression2 =
  5. (fun n -> n * 2) 21

  6. let expression2_using_pipe = (* see below for what is |> *)
  7. 21 |> fun n ->
  8. n * 2

Les deux expressions sont parfaitement équivalentes ! et toute création de variable expression-locale peut se réécrire comme dans expression2. Bien sûr, la première forme est plus lisible, et c'est encore plus flagrant pour des programmes sérieux.

Ceci explique que les arguments sont des variables comme les autres (en fait ce sont plutôt les variables qui sont des arguments comme les autres, si on veut être pointilleux). Ils ont le même rôle et s'utilisent de la même manière, obéissent aux mêmes conventions lexicales et syntaxiques.

Syntaxe alternative pour la définition de fonctions

L'écrasante majorité des fonctions que nous écrirons seront nommées lors de la création par une abstraction

  1. let function_name = fun arg1 arg2 arg3 ->
  2. expression

Il est alors d'usage d'utiliser la syntaxe simplifiée suivante :

  1. let function_name arg1 arg2 arg3 =
  2. expression

Cette forme a l'avantage de rappeler la syntaxe de l'application, puisqu'on trouve les arguments immédiatement à la suite du nom de la fonction, sans parenthèses superflues et sans virgules. Notons que la définition de variable non-fonctionnelle correspond à celle de créer une fonction qui n'aurait pas d'arguments. On voit là l'unification des fonctions avec les variables non-fonctionnelles, le traitement des deux est indifférencié dans les langages fonctionnels, il est donc normal que la syntaxe ne fasse pas de distinction.

Un désavantage de cette notation est la disparition du mot-clé fun. Ce n'est pas dramatique, mais il faudra bien gardé à l'esprit que let n'est pas le mot-clé de création d'une fonction, mais celui de création d'une variable (qui peut être fonctionnelle). fun est ce qui permet de construire une expression fonctionnelle, même si la syntaxe le cache.

Il existe une troisième syntaxe, que nous introduirons plus tard.

Syntaxes alternatives pour l'application de fonctions

Il existe deux opérateurs pour l'application. Si la notation consistant à donner la fonction puis ses arguments sans syntaxe est pratique et suffit la plupart du temps, dans certains cas on peut avoir avantage à utiliser d'autres syntaxes.

Le premier opérateur @@ est un opérateur explicite de l'application. Plutôt qu'un simple espace, on marque ainsi de façon apparente l'application. Il a une priorité minimale (alors que l'application par espace a une priorité maximale). C'est donc utile lorsque le dernier argument d'une fonction est une expression complexe, et qu'on ne souhaite pas la parenthéser. Par exemple, si partant de la valeur $4$, on souhaite effectuer une suite d'incréments et de décrements, voici ce que donne la syntaxe classique :

  1. let increment n = n + 1
  2. let decrement n = n - 1

  3. let result =
  4. increment (increment (increment (decrement (increment 4))))

Avec l'opérateur @@ :

  1. let result =
  2. increment @@
  3. increment @@
  4. increment @@
  5. decrement @@
  6. increment @@
  7. 4

Ici l'expression se lit de bas en haut : partant de 4 , faire un incrément, un décrément, puis 3 incréments, pour obtenir le résultat. Un avantage évident est l'absence de parenthèses, ce qui rend l'expression plus lisible, même sur une expression très simple comme celle de l'exemple.

Le dernier opérateur permet de remettre l'expression dans le bon sens. Il s'agit de l'opérateur |>, dit pipe en anglais (tube en français ?), qui inverse le sens entre fonction et argument : on donne l'argument à gauche, la fonction à droite : arg |> funct. Dans notre exemple, on obtient :

  1. let result =
  2. 4
  3. |> increment
  4. |> decrement
  5. |> increment
  6. |> increment
  7. |> increment

On peut donc lire le code dans le sens de lecture (de haut en bas), comme une série d'actions effectuées successivement sur la valeur de départ. (|>) peut se lire puis : pars de 4 puis incrémente puis décrémente puis... Dans cet exemple, si la lisiblité est bien meilleure que dans le premier cas, on peut tout de même se demander si cela vaut vraiment le coup d'introduire des syntaxes supplémentaires. Mais la réponse deviendra vite évidente sur des exemples de codes plus complexes comme nous en verrons par la suite, il est donc préférable de s'habituer au plus vite à utiliser cette forme aussi.

Enfin, notons que l'opérateur pipe joue un rôle semblable au pipe des bash, un opérateur de séquencement d'actions.

Types des fonctions

Les fonctions sont des valeurs comme les autres en programmation fonctionnelle, elles doivent donc avoir un type. Il est assez naturel de penser que le type d'une fonction doit tenir compte du type des arguments et du type du résultat de la fonction : en effet, si deux fonctions ont les mêmes types d'arguments et de retour, alors on peut interchanger l'utilisation de l'une par l'autre, et cela ne créera pas d'incohérence pour les autres types dans le programme.

Fonctions à un seul argument

Commençons donc avec le cas des fonctions à un seul argument, nous généraliserons ensuite. Considérons les fonctions suivantes :

  1. let double n = 2 * n
  2. let triple n = 3 * n
  3. let increment_twice n = n + 2

On peut ensuite utiliser une de ces fonctions, par exemple comme ceci :

  1. let result = 4 + double 19

Dans l'expression définissant result, nous aurions très bien pu utiliser n'importe laquelle des trois fonctions plutôt que double, cela aurait défini un résultat valide (pas le même dans chaque cas bien sûr). Par contre, on n'aurait pas pu utiliser la fonction suivante :

  1. let double_float x = 2. *. x

Pour deux raisons. Dans la définition de result,

  1. la fonction double prend un entier en argument,
  2. la fonction double doit retourner un entier pour qu'il soit additionné à $4$.

Pour empêcher ce type d'erreur, il faut donc bien que le type de la fonction encode à la fois le type de l'argument, et le type de la valeur retournée. C'est donc très exactement ce que nous allons faire, en utilisant une notation spéciale : arg -> result est le type des fonctions prenant des arguments de type arg et retournant des valeurs de types result.

Par exemple, les fonctions double, triple et increment_twice ont le type int -> int, alors que double_float a le type float -> float.

Dans l'univers des types, la flèche -> permet de créer des types pour les fonctions, à partir d'autres types. Bien sûr cette flèche rappelle celle utilisée pour créer l'expression d'une fonction. Nous avons donc ici un exemple de type construit à partir d'autres types. En fait, pour tout type arg et tout type result, on peut créer le type arg -> result. En particulier, arg et result peuvent eux-même être des types de fonctions.

Règles de typages des fonctions, des applications

L'expression

  1. (fun arg -> expression)

a pour type arg_type -> result si expression a le type result lorsque arg a le type arg_type.

C'est en fait une règle assez naturelle : on cherche un type pour l'argument tel que l'expression du résultat soit aussi typé, les deux types nous donne alors le type de la fonction. Par exemple :

  1. fun n -> n + 3

pour que n + 3 soit typée, il faut que n soit de type int (membre gauche de l'addition), dans ce cas n + 3 prend le type int. Il faut donc que le type de l'argument soit int, et le résultat a alors le type int, donc la fonction a pour type int -> int.

La définition de cette règle de typage laisse penser que plusieurs types pour l'argument pourrait permettre à l'expression du résultat d'être bien typé. Dans ce cas, la fonction aurait plusieurs types simultanément. Ce qui contredit que chaque expression possède un et un seul type. Effectivement, ce cas peut arriver, considérons un cas très simple (nous verrons des cas plus intéressants par la suite) :

  1. let identity = fun x -> x

Pour tout type t, si l'argument x a le type t, alors l'expression du résultat t a le type t, donc par notre règle, identity a le type t -> t. Ce qui va nous sauver, c'est que si deux types distincts sont possibles pour l'argument (ou le résultat), alors en fait tous les types sont possibles, comme c'est le cas ici. Du coup, identity aura le type " pour tout type t, t -> t" , nous le définirons plus tard lorsque nous aborderons le polymorphisme.

Passons à la règle de typage de l'application. Considérons une expression fct arg

  1. Si fct a le type arg_type -> result_type
  2. et arg a le type arg_type,
  3. alors fct arg a le type result_type.

Cette règle permet simplement de vérifier que le type de l'argument est bien celui attendu par la fonction, et que le résultat a bien le type de ce que retourne la fonction.

Fonctions à plusieurs arguments

Les règles sont similaires pour les fonctions à plusieurs arguments. fun arg1 arg2 arg3 -> expression a pour type arg1_type -> arg2_type -> arg3_type -> result_type si expression a le type result_type lorsque arg1, arg2, arg3 ont respectivement pour types arg1_type, arg2_type et arg3_type.

On note que le nombre de flèches est alors égal au nombre d'arguments, les types des arguments sont donnés dans l'ordre séparés par des flèches. Pour comprendre cette notation, il faut remarquer qu'une fonction à deux arguments peut être considéré comme une fonction à un seul argument, dont le résultat est une fonction à un argument. Effectivement, les deux fonctions suivantes sont identiques :

  1. let add = fun n p -> n + p
  2. let result = add 18 24

  3. let add = fun n -> fun p -> n + p
  4. let result = add 18 24

Le type de la deuxième version s'obtient simplement : on commence par trouver le type de l'expression fun p -> n + p. Il faut que p soit de type int, alors l'expression n + p a le type int. Donc fun p -> n + p a le type int -> int, sous contrainte que n soit aussi de type int. Donc add est de type int -> (int -> int). Maintenant, on considère que la flèche est associative à droite, ce qui permet de faire disparaître les parenthèses.

Notons que les types int -> (int -> int) et (int -> int) -> int ne sont pas les mêmes. Dans le deuxième cas, la fonction attend un argument, qui doit être une fonction, et retourne un entier. C'est le cas de cette fonction par exemple :

  1. let apply_to_42_and_increment fct = 1 + fct 42

On a ici l'exemple d'une fonction prenant une autre fonction en argument, puisque fct est appliqué à 42. Le résultat de cette application doit être de type int, puisque membre droit d'une addition, donc fct doit avoir le type int -> int. On en déduit que la fonction apply_to_42_and_increment a le type (int -> int) -> int.

L'application d'une fonction à plusieurs arguments se type aussi assez naturellement : f arg1 arg2 arg3 a le type result_type si f a le type arg1_type -> arg2_type -> arg3_type -> result_type avec arg1_type, arg2_type, arg3_type les types des arg1, arg2 et arg3 respectivement.

Ce qui est peut être moins évident est qu'il est autorisé d'appliquer une fonction partiellement : c'est-à-dire de ne pas appliquer tous les arguments. Considérons cet exemple :

  1. let add n p = n + p
  2. let increment = add 1
  3. let result = increment 41

La fonction add n'est appliquée qu'à un seul argument pour définir l'abstraction increment. En y repensant, le type de add est int -> int -> int, ce qui s'écrit sans omettre les parenthèses int -> (int -> int). Dans cette forme parenthésée, il s'agit d'une fonction à un seul argument, dont le résultat est une fonction. C'est bien ainsi que nous définissons increment qui est donc bien de type int -> int.

En fait, il est pratique de manipuler des fonctions à plusieurs arguments, mais on peut retenir que ces fonctions sont toutes formées de fonctions à un seul argument imbriquées, ce qui justifie l'application partielle.

Fonctions récursives

Si on essaie de définir une fonction récursive, par exemple un grand classique comme la fonction factorielle, voici ce qu'OCaml en pense :

  1. let fact n =
  2. if n = 0 then
  3. 1
  4. else
  5. n * fact (n-1)

  6. >> Error: Unbound value fact

C'est le fameux message d'erreur qui dit que l'identifiant fact n'est pas lié, autrement dit il ne connait pas de variable dont l'identifiant est fact.

La raison est que fact n'est pas encore défini au moment où sa définition est vérifiée par le compilateur. Les variables module-locales sont lues et interprétés dans l'ordre du module, de haut en bas, et une expression ne peut utiliser que des variables définies au-dessus.

Il est cependant possible de définir des fonctions récursives. Il suffit de rajouter le mot-clé rec juste après le let, pour signaler une variable définie par une expression utilisant la variable elle-même.

  1. let rec fact n =
  2. if n = 0 then
  3. 1
  4. else
  5. n * fact (n-1)

  6. >> val fact : int -> int = <fun>
  7. (* ce message de l'interpréteur signifie :
  8. la valeur [fact] est maintenant définie,
  9. a le type [int -> int] et sa valeur est une fonction
  10. *)

On peut même définir des fonctions mutuellement récursives, en utilisant le mot-clé and qui permet de définir plusieurs valeurs simultanément :

  1. let rec is_even n =
  2. (n = 0) || is_odd (n-1)
  3. and is_odd n =
  4. not (is_even (n-1))

Bien sûr, pour qu'une fonction soit récursive, elle doit s'appeler elle-même, donc elle doit porter un nom. Il n'est donc pas possible de faire des fonctions récursives anonymes (ou du moins pas comme ça).

Enfin, il n'est pas possible d'écrire n'importe quoi :

  1. let rec f = f

  2. >> Error: This kind of expression is not allowed as right-hand side of `let rec'

Ici, le membre droit de l'égalité de définition de f n'est pas la construction d'une fonction, OCaml indique que ce n'est pas permis, il faut que le membre droit soit la création d'une fonction, autrement dit que f prenne au moins un argument. (Plus généralement, le membre droit peut aussi être un constructeur, une notion que nous aborderons plus tard).

Syntaxe avancée

Arguments nommés

La lisibilité des programmes au niveau des appels de fonctions est parfois de mauvaise qualité, lorsque les fonctions ont plusieurs arguments et qu'il est difficile de savoir dans quel ordre ils sont disposés. Supposons par exemple que nous voulons utiliser une fonction qui crée un cercle (d'un type circle défini par ailleurs). On nous donne donc une fonction :

  1. val circle : float -> float -> float -> circle

Cette fonction prend donc trois arguments. On se doute, avec un peu d'imagination que les trois arguments sont l'abscisse et l'ordonnée du centre du cercle, ainsi que le rayon du cercle. Dans le meilleur des cas, cela sera renseigné dans la documentation. On pourra donc utiliser la fonction ainsi, après avoir consulté la documentation :

  1. let my_circle =
  2. circle 1.2 0.5 3.4

Malheureusement, si quelqu'un vient relire le programme, il sera à son tour obligé d'aller voir la documentation pour savoir quel argument a quel rôle. Sur des programmes utilisant de nombreuses librairies externes, cela rend la relecture du code extrêmement pénible.

Pour pallier à ce problème, OCaml propose un mécanisme de nommage des arguments, chaque argument possède un nom, qui doit être donné explicitement lors de l'application de la fonction. On pourrait alors définir la fonction de création du cercle ainsi :

  1. let circle ~x ~y ~radius = expression

La fonction circle prend trois arguments, tous préfixés par le caractère ~, qui sert à marquer qu'il s'agit d'arguments nommés. On peut parfaitement mélanger des arguments nommés et non-nommés.

Le caractère nommé des arguments se réflète dans le type de la fonction :

  1. val circle : x:float -> y:float -> radius:float -> circle

L'identifiant de l'argument apparait explicitement dans le type, mais sans le tilde ~. Cela est nécessaire, puisque lors de l'appel de fonction, chaque argument devra être préfixé par son nom. Ainsi, la création du cercle du premier exemple se réécrirait :

  1. let my_circle =
  2. circle ~x:1.2 ~y:0.5 ~radius:3.4

On peut toujours faire des applications partielles :

  1. let circle_at_origin =
  2. circle ~x:0. ~y:0.

  3. let unit_circle = circle_at_origin ~radius:1.0
  4. let big_circle = circle_at_origin ~radius:42.

Les arguments nommés sont pûrement esthétiques, ils ne modifient pas la façon dont les fonctions sont typées ou évaluées. Ils permettent uniquement de rendre le code plus facile à lire, comme l'illustre un exemple même simple comme celui-ci.

Opérateurs

Nous avons vu plusieurs opérateurs, par exemple les opérateurs arithmétiques ou booléens. Pourquoi avoir une distinction entre opérateurs et fonctions : les opérateurs peuvent très bien se comprendre comme des fonctions, avec un ou deux arguments et retournant une valeur ?

Et bien de fait, les opérateurs sont des fonctions comme les autres, la seule différence est syntaxique : ils s'appliquent en position infixe, c'est-à-dire entre leurs deux arguments, et non en position préfixe, c'est-à-dire avant leurs deux arguments comme les autres fonctions.

D'ailleurs, il est possible d'utiliser les opérateurs comme des fonctions ordinaires, en position préfixe. Pour utiliser un opérateur comme un identifiant ordinaire, il suffit de l'écrire entre parenthèses. Ceci permet de faire une application avec la fonction en position préfixe, ou bien de faire référence à la fonction sans l'appliquer.

  1. let forty_two = (+) 19 23
  2. let increment = (+) 1
  3. let add = (+)
  4. let two = add 1 1

D'autre part, il est possible de définir nos propres opérateurs. La syntaxe est similaire, plutôt que donner un identifiant alphanumérique, il suffit de donner un opérateur constitué de symboles, entre parenthèses. Voici un opérateur pour calculer une moyenne :

  1. let (+-) n p = (n + p) / 2

  2. let mean_value = 31 +- 53

Le premier symbole encode si l'opérateur est unaire ou binaire, ainsi que sa priorité et son associativité. Tous les symboles ne sont pas autorisés. Les règles exactes sont données ici pour les priorités et l'associativité, là pour les caractères autorisés. Attention avec les symboles contenant un caractère *, (* et *) sont les marqueurs de début et de fin de commentaire, il ne faut donc pas en créer par erreur en parenthèsant un opérateur commençant ou finissant par *.

Les opérateurs infixes ont l'avantage de rendre plus lisibles certaines formes de constructions. Par contre, leur abus peut vite créer des séquences de signes cabbalistiques indéchiffrables. On les utilisera donc avec parcimonie.

Récapitulatif

  • Nous avons vu deux syntaxes équivalentes pour la création d'une fonction :
  1. let function_name = fun arg1 arg2 arg3 -> expression
  2. let function_name arg1 arg2 arg3 = expression
  • les fonctions peuvent avoir un nombre arbitraire d'arguments,
  • la syntaxe pour l'application est :
  1. let result = some_function arg1 arg2 arg3
  • le type d'une fonction est :

    1. arg1_type -> arg2_type -> arg3_type -> result_type

    Il tient compte du type de chaque argument et du type du résultat.

Nous avons aussi introduit quelques éléments syntaxiques supplémentaires :

  • les arguments nommés :
  1. let f ~arg = expression
  2. (* [f] has type [arg:arg_type -> result_type] *)
  3. let res = f ~arg:some_value
  • l'application explicite, normale ou inversée :
  1. (* These three expressions are equivalent. *)
  2. let result1 = f (g arg)
  3. let result2 = f @@ g @@ arg
  4. let result3 = arg |> g |> f
  • les fonctions récursives s'introduisent avec let rec,
  • on peut définir des opérateurs, en donnant les symboles entre parenthèses à la place de l'identifiant,
  • on peut appliquer une fonction partiellement, ce qui produit une fonction.

Retour au sommaire.