Wiki du LAMA (UMR 5127) - Contributions [fr]

Discussion utilisateur:Hyvernat

2013-02-12T19:08:04Z

Lachand : Page blanchie

Discussion utilisateur:Hyvernat

2013-02-12T19:07:10Z

Lachand : Page créée avec « Bonjour, le lien que vous avez mis au début du cours d'info 421 http://meta.wikimedia.org/wiki/Aide:Contenu est mort »

Bonjour, le lien que vous avez mis au début du cours d'info 421 http://meta.wikimedia.org/wiki/Aide:Contenu est mort

INFO421 : Programmation fonctionnelle

2013-02-12T18:58:19Z

Lachand : /* Les types algébriques */

Ce wiki est un complément de cours pour le cours « info-421 : programmation fonctionnelle ». La participation au wiki est fortement encouragée, et deviendra peut-être obligatoire...

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Je vous conseille d'aller voir [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

== Détails techniques ==

=== Compléments de cours, TD et TP ===

==== Installer Ocaml ====

Si vous voulez installer OCaml sur votre ordinateur :

* Sous Linux : c'est la solution idéale. Il existe probablement des paquets pour votre distribution. Pour Ubuntu, pour avoir un environnement similaire à ce que vous aurez dans les salles informatiques, installez les paquets <tt>ocaml</tt>, <tt>ocaml-core</tt>, <tt>ocaml-mode</tt>, <tt>tuareg-mode</tt> et <tt>emacs</tt>.
* Sous MacOS : il semblerait qu'il y ait des paquets MacPorts pour <tt>ocaml</tt>, <tt>emacs</tt> et <tt>tuareg-mode.el</tt>.
* Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : [http://deptinfo.unice.fr/~roy/CAML/Win/install-win.html Installation de OCaml (sur Windows XP)]. Je n'ai malheureusement (??) pas accès à une machine avec Windows (98/2000/XP/Vista/7), je ne pourrais donc pas beaucoup vous aider.

Contactez moi si vous avez des problèmes.

Pour les exemples simples, vous pouvez aussi utiliser [http://try.ocamlpro.com/ OCaml en ligne]

==== Références supplémentaires ====

* Le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : [http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/ Développement d'applications avec Ocaml]. (Ce livre utilise une vieille version de Ocaml, mais reste pertinent.)
* La documentation de Caml, version 3.09 (utilisé en TP) : [http://caml.inria.fr/pub/docs/manual-ocaml-309/ Documentation and user's manual].
* Le livre de Jason Hickey [http://files.metaprl.org/doc/ocaml-book.pdf Introduction to Objective Caml] (en anglais).

==== Cours ====

==== TD et TP ====

* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/1213/info421/td1.pdf TD1 : premières expressions en Caml (pdf)]

== Introduction ==

Pour paraphraser un collègue dont je ne retrouve pas le nom :

<blockquote>
''Attention :'' il ne s'agit pas d'un cours de programmation fonctionelle
</blockquote>

Il s'agit plutôt d'un cours de programmation '''fonctionnelle'''...

=== Petit historique censuré ===

Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)

D'après [http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm ce site], qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

* années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à ''porter''. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
* FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
* LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
* ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
* Pascal (1975).
* C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
* Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
* ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
* Smalltalk (fin des année 1983), début de la programmation objet.
* 1983 : ADA.
* année '80 : Caml (1987), puis CamlLight(1990), puis OCaml(1996), développé
à l'INRIA. (Dernière version en octobre 2012.)
* années '90 : Python (version 1.0 en 1994).
* années '90 : PHP (version 1.0 en 1995).
* années '90 : Java (version 1.0 en 1996).

Je vous conseille d'aller voir le graphique suivant : [http://www.levenez.com/lang/lang.pdf Computer Languages Timeline] (ou [http://www.levenez.com/lang/redirect_lang_a4_pdf.html découpé en pages A4]).

=== Fonctionnel ?? ===

L'adjectif ''fonctionnel'' a au moins deux sens :

# qui fonctionne, en état de marche,
# qui se rapporte aux fonctions.

Les langages fonctionnels sont bien entendus ''fonctionnels'' dans le premier sens, mais c'est surtout le second sens qui nous intéresse. Les langages tels que Pascal, Ada ou C sont qualifié, par opposition, d''''impératifs'''''.

Un des slogans de la programmation fonctionnelle en général est

<blockquote>
''Les fonctions sont des valeurs comme les autres''
</blockquote>

et c'est de là que vient la terminologie... En particulier, il n'y a pas de différence entre les ''instructions'' (qui ont un effet) et les ''expressions'' (qui ont une valeur). Par exemple, en Python,

<pre>
x = x+1
</pre>

ou

<pre>
if delta < 0:
print("Il n'y a pas de solution")
</pre>

sont des ''instructions'' : on ne peut pas les mettre dans une variable.

Comme nous le verront, cela a des conséquences sur l'expressivité du langage et la manière de programmer.

=== Le langage (O)Caml ===

Le langage OCaml est développé par l'INRIA (Institut national de recherche en informatique et automatique). C'est un successeur de CamlLight.

Le nom Caml est formé des initiales de "Categorical Abstract Machine Language", et le langage lui même appartient à la famille de ML ("Meta Language"). C'est un langage fonctionnel ''strict'' (nous verrons ce que cela veut dire), statiquement typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :

* fonctionnel bien sûr,
* mais aussi impératif,
* objet également (c'est le « O » de OCaml).

Dans ce cours, nous utiliserons principalement le style fonctionnel, et un peu le style impératif en fin de semestre.

Voici quelques aspects importants du langages que nous essayeront d'aborder pendant le cours :

* fonctions comme valeurs,
* types de données ''algébriques''
* polymorphisme,
* système d'exceptions,
* support pour des références et des données mutables (programmation « impure »),
* système de modules et de foncteurs,
* ...

La notion de ''récursivité'' sera fondamentale pendant toute la durée du cours...

Un aspect intéressant du langage est que c'est :

* un langage interprété (avec l'interpréteur OCaml),
* soit un langage compilé en bytecode (code binaire indépendant de l'architecture),
* soit un langage compilé optimisé en binaire (dépendant de l'architecture).

=== Autres langages fonctionnels ===

Il existe de nombreux autres langages fonctionnels. Par exemple :

* SML (Standard ML) : [http://en.wikipedia.org/wiki/Standard_ML Wikipedia], autre dialecte de la famille ML.
* LISP, dont les deux dialectes principaux sont :
** Common LISP : [http://en.wikipedia.org/wiki/Common_LISP Wikipedia],
** Scheme : [http://en.wikipedia.org/wiki/Scheme_%28programming_language%29 Wikipedia].
* Haskell : [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Wikipedia] (inspiré en grande partie de [http://en.wikipedia.org/wiki/Miranda_%28programming_language%29 Miranda]).

Plusieurs langages impératifs intègrent maintenant des aspects propres des langages fonctionnels : Python, Scala, ...

=== Applications concrètes ===

Voici quelques exemples de logiciels développés en OCaml :

* [http://ocsigen.org/ Ocsigen], un serveur web,
* [http://www.cis.upenn.edu/~bcpierce/unison/ Unison], un logiciel de synchronisation de fichiers entre ordinateurs,
* [http://mldonkey.sourceforge.net/Main_Page MLDonkey], un logiciel de Peer-to-peer multiréseaux,
* [http://pauillac.inria.fr/advi/ Active DVI] un visualisateur pour le format de fichier DVI,
* analyse de programmes critiques : [http://www.astree.ens.fr/ Astrée],
* informatique financiere : [http://www.janestreet.com Janestreet Capital] et [http://www.lexifi.com Lexifi].

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang ([http://fr.wikipedia.org/wiki/Erlang_%28langage%29 Wikipedia]), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

=== Objectifs du cours ===

# être capable de définir des fonctions récursives, et comprendre ce qu'elles font
# comprendre le typage, les types algébriques et le polymorphisme à la ML
# pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
# être capable de décomposer un problème
# commencer à réfléchir à la complexité de vos programmes

== Premiers pas en Caml ==

Un des slogans de la programmation fonctionnelle est ''tout est une valeur, ou plus précisément,

<blockquote>
''Toute expression a une valeur.''
</blockquote>

Cette idée n'est pas présente en Python où l'on distingue les ''expressions'' ("<tt>3*x+f(2)</tt>" par exemple) et les ''instructions'' ("<tt>if n>22: a=12 else: a=13</tt>" par exemple). En Python, les instructions sont en général séparées par des retours à la ligne et sont ''exécutées'' en séquence. Les expressions sont juste calculées, et ne peuvent pas être séquentialisées.

Dans un langage purement fonctionnel, le "<tt>;</tt>" n'existe pas, et il n'y a que des valeurs...

Les valeurs sont formées en utilisant :

* les fonctions du langage (addition, multiplication, opérateurs logiques),
* des constructions du langage (<tt>if ... then ... else ...</tt> par exemple),
* les relations mathématiques (égalité, plus grand), ... qui sont juste des fonctions renvoyant des booléens,
* les constantes du langage,
* les variables de l'environnement,
* ''les valeurs (en particulier les fonctions) définies par le programmeur''.

Bien entendu, comme Caml est typé, il faut respecter les types.

=== Les types atomiques ===

Caml (et les autres langages fonctionnels typés) possèdent plusieurs types de base tels que :

* les booléens : type <tt>bool</tt> (valeur <tt>true</tt> et <tt>false</tt>) et les opérations <tt>not</tt>, <tt>&&</tt> (et) et <tt>||</tt> (ou).
* Les entiers : type <tt>int</tt> pour les entiers signés compris entre <math>-230</math> et <math>230-1</math>. (Les entiers Caml sont stockés sur 31 bits...) Les opérations associés sont <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, <tt>/</tt> (pour la division entière) et <tt>mod</tt> (pour le modulo).
* Les flottants : type <tt>float</tt> pour les réels en virgule flottante. Les opérations usuelles sont <tt>+.</tt>, <tt>-.</tt>, <tt>*.</tt> et <tt>/.</tt>.
* Les caractères : type <tt>char</tt> (notés entre guillemets simples).
* Le type unité : type <tt>unit</tt>, dont l'unique valeur est <tt>()</tt>. (Nous verrons que ce type a une utilité...)

Même s'il ne s'agit pas vraiment d'un type atomique, nous pouvons également ajouter le type des chaînes de caractères : type <tt>string</tt> (notées entre guillemets doubles).

<source lang="ocaml">
(* exemples ... *)
</source>

'''Remarques :''' les opérations booléennes ("<tt>&&</tt>" pour le « et » et "<tt>||</tt>" pour le « ou ») fonctionnent de à gauche à droite, et l'argument de droite n'est évalué que si c'est nécessaire. Par exemple <tt>true || (0 = 1/0)</tt> donne la valeur <tt>true</tt>, alors que que <tt>false || (0=1/0)</tt> lève l'exception <tt>Division_by_zero</tt>.

=== définitions et environnement ===

Comme tous les langages de programmation, Caml garde en mémoire une liste de définitions. Chacune de ces définitions met en relation un nom ("<tt>x</tt>", "<tt>n</tt>", "<tt>length</tt>", ...) et une valeur ("<tt>3.7</tt>", "<tt>42</tt>", "<tt>fun s -> ...</tt>").

Lorsque l'on lance Caml, l'environnement contient déjà de nombreuse fonctions prédéfinies : <tt>max</tt>, <tt>min</tt>, <tt>mod</tt>, <tt>+</tt>, <tt>float_of_int</tt>, ...

Certaines des variables de l'environnement correspondent à des paramètres de fonction en cours de définition. Ces variables n'ont pas de valeur, mais seulement un type.

==== Environnement ====

* Liste de paires <tt>nom</tt> / <tt>valeur</tt>,
* une nouvelle definition remplace la précédente mais ne l'efface pas, (on ne met pas une valeur à jours)

==== Définitions ====

L'utilisateur peut rajouter des définitions dans l'environnement grâce au mot clé <tt>let</tt>

* <tt>let nom = expr</tt> permet de rajouter une définition simple dans l'environnement. Exemple : <tt>let n = 42</tt>
* <tt>let nom1 = expr1 and nom2 = expr2</tt> permet de rajouter plusieurs définitions simultanément. Exemple : <tt>let a=1 and b=2</tt>
* <tt>let rec nom1 = expr1 and nom2 = expr2</tt> permet de rajouter des définitions mutuellement récursives.

On peut toujours annoter la définition de types de données. Ceci évite à Caml d'avoir à deviner le type que l'on souhaite et permet de préciser la fonction :
<source lang="ocaml">
let n:int = 42
let rec f (n:int) : string = if (n<1) then "" else "*" ^ (f (n-1))
</source>

Si une définition utilise le même nom qu'une définition précédente, la nouvelle définition écrase l'ancienne. Par exemple :
<source lang="ocaml">
# let n=42 ;;
val n : int = 42
# let n=3.1415 ;;
val n : float = 3.1415
# n ;;

* : float = 3.1415
</source>

==== Définitions locales ====

Il est possible de modifier l'environnement de manière temporaire (''locale''). On utilise alors <tt>let nom = expr1 in expr2</tt>. Ceci ajoute la définition <tt>nom = expr1</tt> dans l'environnement, mais seulement pour l'évaluation de l'expression <tt>expr2</tt>.
<source lang="ocaml">
# let x =
let y = 42 in
y/2 ;;
val x : int = 21
# x ;;

* : int = 21
# y ;;
Unbound value y
</source>

=== Les fonctions ===

Caml utilise la notation mathématique pour écrire les types des fonctions. Si <tt>f</tt> est une fonction avec un seul argument de type <tt>string</tt> et dont la valeur de retour est de type <tt>int</tt> (la fonction <tt>length</tt> par exemple), le type de <tt>f</tt> est noté <tt>string -> int</tt>. Dans l'interprète Caml :
<source lang="ocaml">
# String.length ;;

* : string -> int = <fun>
</source>
Nous indique que la fonction <tt>length</tt> est bien de type <tt>string->int</tt>.

Une fonction est définie comme une variable avec un <tt>let</tt> et en utilisant le mot clé <tt>fun</tt> :
<source lang="ocaml">
# let f = fun n -> n+1;;
val f : int -> int = <fun>
# let racine = fun n -> int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
</source>

Une fonction avec plusieurs argument est définie de la même manière avec
<source lang="ocaml">
# let moyenne3 = fun x y z -> (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Le type d'une fonction à plusieurs argument est noté en mettant plusieurs types à gauche de la flèche <tt>-></tt>, comme ci dessus : <tt>type_arg1 -> type_arg2 -> type_arg3 -> type_resultat</tt>.

'''Remarques :'''

* notez l'absence de mot clé <tt>return</tt> et l'absence de virgules pour séparer les différents arguments !
* Le mot clé <tt>fun</tt> permet de définir des fonctions sans leur donner de nom, ce qui n'est pas possible dans les langages comme C ou Java...

On peut également utiliser un raccourci pour définir une fonction sans utiliser le mot clé <tt>fun</tt> : il suffit de mettre les arguments de la fonction avant le signe égal :
<source lang="ocaml">
# let f n = n+1;;
val f : int -> int = <fun>
# let racine n = int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
# let moyenne3 x y z = (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Pour appliquer une fonction à des arguments, on écrit simplement
<source lang="ocaml">
moyenne3 13.5 17.0 -0.333
</source>
Il n'y a ni parenthèse, ni virgule. Les parenthèses peuvent cependant être nécessaires pour différencier
<source lang="ocaml">
moyenne3 13.5 17.0 (-0.333 *. 6.)
</source>
et
<source lang="ocaml">
(moyenne3 13.5 17.0 -0.333) *. 6.
</source>
ou pour que Caml lise correctement
<source lang="ocaml">
moyenne3 13.5 (17.0 -. 12.0) -0.333
</source>

==== Fonctions récursives ====

Si on essaie de définir une fonction récursivement :
<source lang="ocaml">
let f n = if (n<1) then 0 else n + f (n-1)
</source>
Caml répond
<source lang="ocaml">
Error: Unbound value f
</source>
car <tt>f</tt> n'est pas présente dans l'environnement.

Pour rajouter <tt>f</tt> comme variable active (sans valeur) et pouvoir faire une définition récursive, il faut utiliser le mot clé <tt>rec</tt> :
<source lang="ocaml">
# let rec f n = if (n<1) then 0 else n + f (n-1);;
val f : int -> int = <fun>
</source>

Les définitions locales peuvent elles aussi être récursives (<tt>let rec ... in ...</tt>) ou mutuellement récursives (<tt>let rec ... and ... in ...</tt>). Elles acceptent également les annotations de type...

==== fonctions d'ordre supérieur ====

TODO

=== Les listes ===

Le type des listes est fondamental en programmation fonctionnelle. D'une certaine manière, on peut dire qu'ils remplacent les tableaux que l'on utilise constamment en programmation impérative.

Exercice : quels sont les différences importantes (utilisation, complexité, mémoire, ...) entre les tableaux et les listes ?

En Caml, une liste est représentée entre crochets, et les éléments sont séparés par des points-virgules :
<source lang="ocaml">
# let une_liste = [ 1 ; 2 ; 2 ; -1 ; 0 ] ;;
val une_liste : int list = [1; 2; 2; -1; 0]
# let une_autre_liste = [ "coucou" ; "je m'appelle" ; "Bob" ] ;;
val une_autre_liste : string list = ["coucou"; "je m'appelle"; "Bob"]
</source>

Comme vous pouvez le voir dans l'exemple au dessus, le type des listes d'entiers s'appelle "<tt>int list</tt>", le type des listes de flottants s'appelle "<tt>float list</tt>" et le type des listes de listes d'entiers s'appelle ... "<tt>int list list</tt>".

Contrairement au cas des tuples, les éléments d'une liste doivent tous avoir le même type :
<source lang="ocaml">
# let une_non_liste = [ 1 ; "Toto" ; 1.3 ] ;;
This expression has type string but is here used with type int
</source>

Attention : quel est le type de la liste suivante ?
<source lang="ocaml">
# let une_liste_bizarre = [ 1 , 2 , 3 ] ;;
</source>

On peut ajouter un élement devant une liste avec l'opérateur "<tt>::</tt>" et la concaténation des listes s'obtient avec l'opérateur "<tt>@</tt>".
<source lang="ocaml">
# 5::[1;2;3;4] ;;
- : int list = [5; 1; 2; 3; 4]
# [-1;-2;-3;-4] @ [1;2;3;4] ;;
- : int list = [-1; -2; -3; -4; 1; 2; 3; 4]
</source>
Attention : la complexité de l'opération "<tt>::</tt>" ne dépend pas de la taille des listes mises en jeux. Par contre, la complexité de l'opération "<tt>@</tt>" dépend proportionnellement de la taille de son premier argument. Il faut donc toujour privilégier "<tt>::</tt>" par rapport à "<tt>@</tt>". En particulier, il est en général mauvais de rajouter des élément en fin de liste en utilisant "<tt>l @ [e]</tt>".

=== Filtrage, première partie : tuples et listes ===

La notion de ''filtrage'', aussi appelé "pattern-matching" est un outils clé pour la programmation en Caml. L'idée est de décomposer une valeur en "sous-valeurs".

==== Filtrage sur les tuples ====

Comme une paire est de la forme <tt>(x,y)</tt>, on peut décomposer une valeur de type <tt>a*b</tt> en deux sous valeurs. Voici un exemple de syntaxe : le code de la fonction <tt>fst</tt> :
<source lang="ocaml">
let premier p = match p with
(x,y) -> x
</source>

Pour évaluer "<tt>premier e</tt>", Caml regarde le premier argument <tt>e</tt> et essaie de faire coïncider "<tt>(x,y)</tt>". S'il y arrive, alors il renvoie la valeur "<tt>x</tt>". Le typage de Caml inférera automatique que "<tt>p</tt>" doit être une paire, et il n'y a donc pas besoin de prévoir un cas par defaut.

On peut maintenant récupérer la deuxième composante d'un triplet de la manière suivante :
<source lang="ocaml">
let second3 t = match t with
(_, y, _) -> y
</source>
Notez l'utilisation de "<tt>_</tt>" pour donner la position d'une sous-valeur qui ne sert à rien.

Toutes les variables présentes dans le ''motif'' (la partie à gauche de la flèche) se retrouvent dans l'environnement avec pour valeur, la sous-valeur appropriée. Attention, ces variables ne se retrouvent dans l'environnement que dans la partie droite de la flèche.
Ces variables remplacent (temporairement) les variables de même nom qui pouvaient se trouver dans l'environnement. Par exemple, la fonction :
<source lang="ocaml">
let f x = match x with
(x,_) -> x
</source>
est exactement la fonction <tt>fst</tt>.

==== Filtrage sur les listes ====

On peut décomposer une liste en deux sous-valeurs :

* le premier élément de la liste,
* la suite de la liste.

Autrement dit, si la liste <tt>l</tt> n'est pas vide, on peut la décomposer en <tt>e::q</tt>. Comme il est possible que la liste <tt>l</tt> soit vide, il y a en fait deux manière de décomposer <tt>l</tt> :

* soit <tt>[]</tt> (sans aucune sous-valeur),
* soit <tt>e::q</tt> (avec deux sous-valeurs).

Par exemple, voici une manière de tester si une liste est vide :
<source lang="ocaml">
let vide l = match l with
[] -> true
| x::xs -> false
</source>
Les différents cas sont séparés par le symbole "<tt>|</tt>".

On peut également décomposer une liste en 3 sous-valeurs : le premier élément, le second élément et la suite de la liste. Dans ce cas, il a trois cas pour une liste arbitraire :

* elle est vide <tt>[]</tt> (aucune sous-valeur),
* elle ne contient qu'une seul élément <tt>[e]</tt> (une sous-valeur),
* elle contient un premier élément, un deuxième élément, et une suite <tt>a::b::q</tt> (trois sous-valeurs).

On peut par exemple écrire :
<source lang="ocaml">
let deux_elements_ou_plus l = match l with
[] -> false
| [a] -> false
| a::b::q -> true
</source>

Comme on peut toujours décomposer une valeur en une sous-valeur (la valeur elle même), on peut toujours avoir un motif de la forme <tt>x</tt>. Toutes les valeurs pourront être décomposées de cette manière, et il faut donc que ce motif soit le dernier. (Sinon, les motifs suivants ne servent à rien...) On parle de motif ''universel''. (On peut utiliser <tt>_</tt> comme motif universel.) Par exemple, on peut réecrire l'exemple précédent :
<source lang="ocaml">
let deux_elements_ou_plus
_::_::_ -> true
| _ -> false
</source>

==== Compléments ====

# On peut ajouter des constantes dans les motifs. Le motif ne sera utilisé que lorsque la sous-valeur correspondantes a la valeurs correspondante. Par exemple, si on modélise les entiers de Gauss (« entiers complexes ») par des paires d'entiers, on peut définir :
<source lang="ocaml">
let imaginaire_pur c = match c with
(0,0) -> false
| (0,_) -> true
| _ -> false
</source>
# On peut grouper des motifs différents pour faire la même chose. Il faut que les variables qui apparaissent dans les motifs soient les mêmes, et qu'elles aient le même type :
<source lang="ocaml">
let f x = match x with
0::l | 1::_::l | 2::_::_::l -> l (* on groupe 3 motifs en une seule ligne *)
| [] -> []
| x::_ -> [x]
</source>
# on peut « garder » les motifs" par une condition avec le mot clé "<tt>when</tt>"
<source lang="ocaml">
let g x = match x with
x::xs when (List.lenght (f xs) = 1) -> true
| _ -> false
</source>
Attention dans le cas où vous utilisez <tt>when</tt> : il est conseillé de terminer votre filtrage avec un motif universel pour être sûr que vous n'avez pas oublié de cas.
# comme on définit souvent des fonctions par filtrage, Caml autorise la syntaxe
<source lang="ocaml">
function
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
plutôt que
<source lang="ocaml">
fun x -> match x with
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
Remarquez que l'on ne peut faire ça que pour une fonction à une seule variable...
# fonction par filtrage : s'il n'y a qu'un seul motif, on peut alors utiliser le mot clé "<tt>fun</tt>" habituel, ce qui permet la définition d'une fonction à plusieurs arguments. (Mais dans ce cas, les parenthèses autour des tuples sont obligatoires.)
<source lang="ocaml">
# let h = fun (x,y) z (u,v,w) -> x+y+z+v ;;
val h : int * int -> int -> 'a * int * 'b -> int = <fun>
</source>

=== Le polymorphisme ===

=== Transparence référentielle ===

=== Les types algébriques ===

On peut défnir un synonyme de type avec le mot clef <tt>type</tt>
Exemple :
<source lang="ocaml">type point = float*float</source>

==== Types énumérés ====

On donne tous les éléments du type
Exemple :
<source lang="ocaml">type jours = Lundi | Mardi | Mercredi | ...</source>

Type avec 7 éléments. Les éléments commencent forcément par une majuscule.

On peut comparer des éléments avec "=", "<" et ">" (< et > sont à éviter, il vaut mieux
écrire une fonction pour comparer) On peut aussi faire du filtrage.

Exemple:
<source lang="ocaml">
let week_end j = match j with
Samedi -> true
| Dimanche -> true
| _ -> false
</source>

==== Construction de types paramètres ====

Exemple : type des transformations de l'espace avec :
- Translation
- Rotation
- Symetrie
On aura alors des constructeurs avec des paramètres :

<source lang="ocaml">
type transformation =
Rotation of int*point
| Translation of point
| SymCentrale of point
| Homothetie of float*point
</source>

On n'a pas donné explicitement tous les éléments, mais on les a donné implicitement.
Exemple :
<source lang="ocaml">
let rien = Translation (0.0,0.0)
</source>
Autre exemple :
<source lang="ocaml">
let fait quelquechose t=
match t with
Rotation(a, (x, y)− > a mod360! = 0
|T ranslation(x, y)− > x! = 0.0 && y! = 0.0
|SymCentrale(x, y)− > true
|Homotetie(x, (−, −))− > r! = 1, 0
</source>

==== Les types récursifs ====

En Caml
<source lang="ocaml">
type node = Node of int*node
| Vide
</source>
exemple d'éléments de "node" :
- Vide
- Node(0,Vide)
- Node(1,Node(2,Node(3, Vide)))

Le type "node" est un type récursif. Comme les fonctions récursivent doivent avoir des cas
de base, les types récursifs doivent avoir des constructeurs "de base" (non récursifs). On peut
comparer des éléments avec "=". On peut aussi utiliser le filtrage.

Exemple :
<source lang="ocaml">
let rec taille l = match l with
Vide -> 0
|Node(_,l)->1+taille l
</source>

La fonction taille sur les listes Caml suit le même schéma avec les abréviations Caml.
<source lang="ocaml">
let rec taille l = match l with
[]->0
| a ::l->1+taille
</source>
Ceci explique la différence entre :: (constructeur) et @ (fonction récursive)

Exemple de type récursif, les arbres binaires :
<source lang="ocaml">
type bin = Vide | Noeud of int*bin*bin
</source>
arbre naire :
<source lang="ocaml">
type arbre n_aire =
Vide|Node of int ∗ (arbre_naire list)(bancal)
</source>

== Les structures ==

== La récursivité terminale ==

== Les exceptions ==

== Aspects impératifs dans Caml ==

== Les modules ==

INFO421 : Programmation fonctionnelle

2013-02-12T18:39:30Z

Lachand : /* Les types algébriques */

Ce wiki est un complément de cours pour le cours « info-421 : programmation fonctionnelle ». La participation au wiki est fortement encouragée, et deviendra peut-être obligatoire...

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Je vous conseille d'aller voir [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

== Détails techniques ==

=== Compléments de cours, TD et TP ===

==== Installer Ocaml ====

Si vous voulez installer OCaml sur votre ordinateur :

* Sous Linux : c'est la solution idéale. Il existe probablement des paquets pour votre distribution. Pour Ubuntu, pour avoir un environnement similaire à ce que vous aurez dans les salles informatiques, installez les paquets <tt>ocaml</tt>, <tt>ocaml-core</tt>, <tt>ocaml-mode</tt>, <tt>tuareg-mode</tt> et <tt>emacs</tt>.
* Sous MacOS : il semblerait qu'il y ait des paquets MacPorts pour <tt>ocaml</tt>, <tt>emacs</tt> et <tt>tuareg-mode.el</tt>.
* Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : [http://deptinfo.unice.fr/~roy/CAML/Win/install-win.html Installation de OCaml (sur Windows XP)]. Je n'ai malheureusement (??) pas accès à une machine avec Windows (98/2000/XP/Vista/7), je ne pourrais donc pas beaucoup vous aider.

Contactez moi si vous avez des problèmes.

Pour les exemples simples, vous pouvez aussi utiliser [http://try.ocamlpro.com/ OCaml en ligne]

==== Références supplémentaires ====

* Le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : [http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/ Développement d'applications avec Ocaml]. (Ce livre utilise une vieille version de Ocaml, mais reste pertinent.)
* La documentation de Caml, version 3.09 (utilisé en TP) : [http://caml.inria.fr/pub/docs/manual-ocaml-309/ Documentation and user's manual].
* Le livre de Jason Hickey [http://files.metaprl.org/doc/ocaml-book.pdf Introduction to Objective Caml] (en anglais).

==== Cours ====

==== TD et TP ====

* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/1213/info421/td1.pdf TD1 : premières expressions en Caml (pdf)]

== Introduction ==

Pour paraphraser un collègue dont je ne retrouve pas le nom :

<blockquote>
''Attention :'' il ne s'agit pas d'un cours de programmation fonctionelle
</blockquote>

Il s'agit plutôt d'un cours de programmation '''fonctionnelle'''...

=== Petit historique censuré ===

Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)

D'après [http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm ce site], qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

* années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à ''porter''. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
* FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
* LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
* ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
* Pascal (1975).
* C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
* Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
* ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
* Smalltalk (fin des année 1983), début de la programmation objet.
* 1983 : ADA.
* année '80 : Caml (1987), puis CamlLight(1990), puis OCaml(1996), développé
à l'INRIA. (Dernière version en octobre 2012.)
* années '90 : Python (version 1.0 en 1994).
* années '90 : PHP (version 1.0 en 1995).
* années '90 : Java (version 1.0 en 1996).

Je vous conseille d'aller voir le graphique suivant : [http://www.levenez.com/lang/lang.pdf Computer Languages Timeline] (ou [http://www.levenez.com/lang/redirect_lang_a4_pdf.html découpé en pages A4]).

=== Fonctionnel ?? ===

L'adjectif ''fonctionnel'' a au moins deux sens :

# qui fonctionne, en état de marche,
# qui se rapporte aux fonctions.

Les langages fonctionnels sont bien entendus ''fonctionnels'' dans le premier sens, mais c'est surtout le second sens qui nous intéresse. Les langages tels que Pascal, Ada ou C sont qualifié, par opposition, d''''impératifs'''''.

Un des slogans de la programmation fonctionnelle en général est

<blockquote>
''Les fonctions sont des valeurs comme les autres''
</blockquote>

et c'est de là que vient la terminologie... En particulier, il n'y a pas de différence entre les ''instructions'' (qui ont un effet) et les ''expressions'' (qui ont une valeur). Par exemple, en Python,

<pre>
x = x+1
</pre>

ou

<pre>
if delta < 0:
print("Il n'y a pas de solution")
</pre>

sont des ''instructions'' : on ne peut pas les mettre dans une variable.

Comme nous le verront, cela a des conséquences sur l'expressivité du langage et la manière de programmer.

=== Le langage (O)Caml ===

Le langage OCaml est développé par l'INRIA (Institut national de recherche en informatique et automatique). C'est un successeur de CamlLight.

Le nom Caml est formé des initiales de "Categorical Abstract Machine Language", et le langage lui même appartient à la famille de ML ("Meta Language"). C'est un langage fonctionnel ''strict'' (nous verrons ce que cela veut dire), statiquement typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :

* fonctionnel bien sûr,
* mais aussi impératif,
* objet également (c'est le « O » de OCaml).

Dans ce cours, nous utiliserons principalement le style fonctionnel, et un peu le style impératif en fin de semestre.

Voici quelques aspects importants du langages que nous essayeront d'aborder pendant le cours :

* fonctions comme valeurs,
* types de données ''algébriques''
* polymorphisme,
* système d'exceptions,
* support pour des références et des données mutables (programmation « impure »),
* système de modules et de foncteurs,
* ...

La notion de ''récursivité'' sera fondamentale pendant toute la durée du cours...

Un aspect intéressant du langage est que c'est :

* un langage interprété (avec l'interpréteur OCaml),
* soit un langage compilé en bytecode (code binaire indépendant de l'architecture),
* soit un langage compilé optimisé en binaire (dépendant de l'architecture).

=== Autres langages fonctionnels ===

Il existe de nombreux autres langages fonctionnels. Par exemple :

* SML (Standard ML) : [http://en.wikipedia.org/wiki/Standard_ML Wikipedia], autre dialecte de la famille ML.
* LISP, dont les deux dialectes principaux sont :
** Common LISP : [http://en.wikipedia.org/wiki/Common_LISP Wikipedia],
** Scheme : [http://en.wikipedia.org/wiki/Scheme_%28programming_language%29 Wikipedia].
* Haskell : [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Wikipedia] (inspiré en grande partie de [http://en.wikipedia.org/wiki/Miranda_%28programming_language%29 Miranda]).

Plusieurs langages impératifs intègrent maintenant des aspects propres des langages fonctionnels : Python, Scala, ...

=== Applications concrètes ===

Voici quelques exemples de logiciels développés en OCaml :

* [http://ocsigen.org/ Ocsigen], un serveur web,
* [http://www.cis.upenn.edu/~bcpierce/unison/ Unison], un logiciel de synchronisation de fichiers entre ordinateurs,
* [http://mldonkey.sourceforge.net/Main_Page MLDonkey], un logiciel de Peer-to-peer multiréseaux,
* [http://pauillac.inria.fr/advi/ Active DVI] un visualisateur pour le format de fichier DVI,
* analyse de programmes critiques : [http://www.astree.ens.fr/ Astrée],
* informatique financiere : [http://www.janestreet.com Janestreet Capital] et [http://www.lexifi.com Lexifi].

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang ([http://fr.wikipedia.org/wiki/Erlang_%28langage%29 Wikipedia]), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

=== Objectifs du cours ===

# être capable de définir des fonctions récursives, et comprendre ce qu'elles font
# comprendre le typage, les types algébriques et le polymorphisme à la ML
# pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
# être capable de décomposer un problème
# commencer à réfléchir à la complexité de vos programmes

== Premiers pas en Caml ==

Un des slogans de la programmation fonctionnelle est ''tout est une valeur, ou plus précisément,

<blockquote>
''Toute expression a une valeur.''
</blockquote>

Cette idée n'est pas présente en Python où l'on distingue les ''expressions'' ("<tt>3*x+f(2)</tt>" par exemple) et les ''instructions'' ("<tt>if n>22: a=12 else: a=13</tt>" par exemple). En Python, les instructions sont en général séparées par des retours à la ligne et sont ''exécutées'' en séquence. Les expressions sont juste calculées, et ne peuvent pas être séquentialisées.

Dans un langage purement fonctionnel, le "<tt>;</tt>" n'existe pas, et il n'y a que des valeurs...

Les valeurs sont formées en utilisant :

* les fonctions du langage (addition, multiplication, opérateurs logiques),
* des constructions du langage (<tt>if ... then ... else ...</tt> par exemple),
* les relations mathématiques (égalité, plus grand), ... qui sont juste des fonctions renvoyant des booléens,
* les constantes du langage,
* les variables de l'environnement,
* ''les valeurs (en particulier les fonctions) définies par le programmeur''.

Bien entendu, comme Caml est typé, il faut respecter les types.

=== Les types atomiques ===

Caml (et les autres langages fonctionnels typés) possèdent plusieurs types de base tels que :

* les booléens : type <tt>bool</tt> (valeur <tt>true</tt> et <tt>false</tt>) et les opérations <tt>not</tt>, <tt>&&</tt> (et) et <tt>||</tt> (ou).
* Les entiers : type <tt>int</tt> pour les entiers signés compris entre <math>-230</math> et <math>230-1</math>. (Les entiers Caml sont stockés sur 31 bits...) Les opérations associés sont <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, <tt>/</tt> (pour la division entière) et <tt>mod</tt> (pour le modulo).
* Les flottants : type <tt>float</tt> pour les réels en virgule flottante. Les opérations usuelles sont <tt>+.</tt>, <tt>-.</tt>, <tt>*.</tt> et <tt>/.</tt>.
* Les caractères : type <tt>char</tt> (notés entre guillemets simples).
* Le type unité : type <tt>unit</tt>, dont l'unique valeur est <tt>()</tt>. (Nous verrons que ce type a une utilité...)

Même s'il ne s'agit pas vraiment d'un type atomique, nous pouvons également ajouter le type des chaînes de caractères : type <tt>string</tt> (notées entre guillemets doubles).

<source lang="ocaml">
(* exemples ... *)
</source>

'''Remarques :''' les opérations booléennes ("<tt>&&</tt>" pour le « et » et "<tt>||</tt>" pour le « ou ») fonctionnent de à gauche à droite, et l'argument de droite n'est évalué que si c'est nécessaire. Par exemple <tt>true || (0 = 1/0)</tt> donne la valeur <tt>true</tt>, alors que que <tt>false || (0=1/0)</tt> lève l'exception <tt>Division_by_zero</tt>.

=== définitions et environnement ===

Comme tous les langages de programmation, Caml garde en mémoire une liste de définitions. Chacune de ces définitions met en relation un nom ("<tt>x</tt>", "<tt>n</tt>", "<tt>length</tt>", ...) et une valeur ("<tt>3.7</tt>", "<tt>42</tt>", "<tt>fun s -> ...</tt>").

Lorsque l'on lance Caml, l'environnement contient déjà de nombreuse fonctions prédéfinies : <tt>max</tt>, <tt>min</tt>, <tt>mod</tt>, <tt>+</tt>, <tt>float_of_int</tt>, ...

Certaines des variables de l'environnement correspondent à des paramètres de fonction en cours de définition. Ces variables n'ont pas de valeur, mais seulement un type.

==== Environnement ====

* Liste de paires <tt>nom</tt> / <tt>valeur</tt>,
* une nouvelle definition remplace la précédente mais ne l'efface pas, (on ne met pas une valeur à jours)

==== Définitions ====

L'utilisateur peut rajouter des définitions dans l'environnement grâce au mot clé <tt>let</tt>

* <tt>let nom = expr</tt> permet de rajouter une définition simple dans l'environnement. Exemple : <tt>let n = 42</tt>
* <tt>let nom1 = expr1 and nom2 = expr2</tt> permet de rajouter plusieurs définitions simultanément. Exemple : <tt>let a=1 and b=2</tt>
* <tt>let rec nom1 = expr1 and nom2 = expr2</tt> permet de rajouter des définitions mutuellement récursives.

On peut toujours annoter la définition de types de données. Ceci évite à Caml d'avoir à deviner le type que l'on souhaite et permet de préciser la fonction :
<source lang="ocaml">
let n:int = 42
let rec f (n:int) : string = if (n<1) then "" else "*" ^ (f (n-1))
</source>

Si une définition utilise le même nom qu'une définition précédente, la nouvelle définition écrase l'ancienne. Par exemple :
<source lang="ocaml">
# let n=42 ;;
val n : int = 42
# let n=3.1415 ;;
val n : float = 3.1415
# n ;;

* : float = 3.1415
</source>

==== Définitions locales ====

Il est possible de modifier l'environnement de manière temporaire (''locale''). On utilise alors <tt>let nom = expr1 in expr2</tt>. Ceci ajoute la définition <tt>nom = expr1</tt> dans l'environnement, mais seulement pour l'évaluation de l'expression <tt>expr2</tt>.
<source lang="ocaml">
# let x =
let y = 42 in
y/2 ;;
val x : int = 21
# x ;;

* : int = 21
# y ;;
Unbound value y
</source>

=== Les fonctions ===

Caml utilise la notation mathématique pour écrire les types des fonctions. Si <tt>f</tt> est une fonction avec un seul argument de type <tt>string</tt> et dont la valeur de retour est de type <tt>int</tt> (la fonction <tt>length</tt> par exemple), le type de <tt>f</tt> est noté <tt>string -> int</tt>. Dans l'interprète Caml :
<source lang="ocaml">
# String.length ;;

* : string -> int = <fun>
</source>
Nous indique que la fonction <tt>length</tt> est bien de type <tt>string->int</tt>.

Une fonction est définie comme une variable avec un <tt>let</tt> et en utilisant le mot clé <tt>fun</tt> :
<source lang="ocaml">
# let f = fun n -> n+1;;
val f : int -> int = <fun>
# let racine = fun n -> int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
</source>

Une fonction avec plusieurs argument est définie de la même manière avec
<source lang="ocaml">
# let moyenne3 = fun x y z -> (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Le type d'une fonction à plusieurs argument est noté en mettant plusieurs types à gauche de la flèche <tt>-></tt>, comme ci dessus : <tt>type_arg1 -> type_arg2 -> type_arg3 -> type_resultat</tt>.

'''Remarques :'''

* notez l'absence de mot clé <tt>return</tt> et l'absence de virgules pour séparer les différents arguments !
* Le mot clé <tt>fun</tt> permet de définir des fonctions sans leur donner de nom, ce qui n'est pas possible dans les langages comme C ou Java...

On peut également utiliser un raccourci pour définir une fonction sans utiliser le mot clé <tt>fun</tt> : il suffit de mettre les arguments de la fonction avant le signe égal :
<source lang="ocaml">
# let f n = n+1;;
val f : int -> int = <fun>
# let racine n = int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
# let moyenne3 x y z = (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Pour appliquer une fonction à des arguments, on écrit simplement
<source lang="ocaml">
moyenne3 13.5 17.0 -0.333
</source>
Il n'y a ni parenthèse, ni virgule. Les parenthèses peuvent cependant être nécessaires pour différencier
<source lang="ocaml">
moyenne3 13.5 17.0 (-0.333 *. 6.)
</source>
et
<source lang="ocaml">
(moyenne3 13.5 17.0 -0.333) *. 6.
</source>
ou pour que Caml lise correctement
<source lang="ocaml">
moyenne3 13.5 (17.0 -. 12.0) -0.333
</source>

==== Fonctions récursives ====

Si on essaie de définir une fonction récursivement :
<source lang="ocaml">
let f n = if (n<1) then 0 else n + f (n-1)
</source>
Caml répond
<source lang="ocaml">
Error: Unbound value f
</source>
car <tt>f</tt> n'est pas présente dans l'environnement.

Pour rajouter <tt>f</tt> comme variable active (sans valeur) et pouvoir faire une définition récursive, il faut utiliser le mot clé <tt>rec</tt> :
<source lang="ocaml">
# let rec f n = if (n<1) then 0 else n + f (n-1);;
val f : int -> int = <fun>
</source>

Les définitions locales peuvent elles aussi être récursives (<tt>let rec ... in ...</tt>) ou mutuellement récursives (<tt>let rec ... and ... in ...</tt>). Elles acceptent également les annotations de type...

==== fonctions d'ordre supérieur ====

TODO

=== Les listes ===

Le type des listes est fondamental en programmation fonctionnelle. D'une certaine manière, on peut dire qu'ils remplacent les tableaux que l'on utilise constamment en programmation impérative.

Exercice : quels sont les différences importantes (utilisation, complexité, mémoire, ...) entre les tableaux et les listes ?

En Caml, une liste est représentée entre crochets, et les éléments sont séparés par des points-virgules :
<source lang="ocaml">
# let une_liste = [ 1 ; 2 ; 2 ; -1 ; 0 ] ;;
val une_liste : int list = [1; 2; 2; -1; 0]
# let une_autre_liste = [ "coucou" ; "je m'appelle" ; "Bob" ] ;;
val une_autre_liste : string list = ["coucou"; "je m'appelle"; "Bob"]
</source>

Comme vous pouvez le voir dans l'exemple au dessus, le type des listes d'entiers s'appelle "<tt>int list</tt>", le type des listes de flottants s'appelle "<tt>float list</tt>" et le type des listes de listes d'entiers s'appelle ... "<tt>int list list</tt>".

Contrairement au cas des tuples, les éléments d'une liste doivent tous avoir le même type :
<source lang="ocaml">
# let une_non_liste = [ 1 ; "Toto" ; 1.3 ] ;;
This expression has type string but is here used with type int
</source>

Attention : quel est le type de la liste suivante ?
<source lang="ocaml">
# let une_liste_bizarre = [ 1 , 2 , 3 ] ;;
</source>

On peut ajouter un élement devant une liste avec l'opérateur "<tt>::</tt>" et la concaténation des listes s'obtient avec l'opérateur "<tt>@</tt>".
<source lang="ocaml">
# 5::[1;2;3;4] ;;
- : int list = [5; 1; 2; 3; 4]
# [-1;-2;-3;-4] @ [1;2;3;4] ;;
- : int list = [-1; -2; -3; -4; 1; 2; 3; 4]
</source>
Attention : la complexité de l'opération "<tt>::</tt>" ne dépend pas de la taille des listes mises en jeux. Par contre, la complexité de l'opération "<tt>@</tt>" dépend proportionnellement de la taille de son premier argument. Il faut donc toujour privilégier "<tt>::</tt>" par rapport à "<tt>@</tt>". En particulier, il est en général mauvais de rajouter des élément en fin de liste en utilisant "<tt>l @ [e]</tt>".

=== Filtrage, première partie : tuples et listes ===

La notion de ''filtrage'', aussi appelé "pattern-matching" est un outils clé pour la programmation en Caml. L'idée est de décomposer une valeur en "sous-valeurs".

==== Filtrage sur les tuples ====

Comme une paire est de la forme <tt>(x,y)</tt>, on peut décomposer une valeur de type <tt>a*b</tt> en deux sous valeurs. Voici un exemple de syntaxe : le code de la fonction <tt>fst</tt> :
<source lang="ocaml">
let premier p = match p with
(x,y) -> x
</source>

Pour évaluer "<tt>premier e</tt>", Caml regarde le premier argument <tt>e</tt> et essaie de faire coïncider "<tt>(x,y)</tt>". S'il y arrive, alors il renvoie la valeur "<tt>x</tt>". Le typage de Caml inférera automatique que "<tt>p</tt>" doit être une paire, et il n'y a donc pas besoin de prévoir un cas par defaut.

On peut maintenant récupérer la deuxième composante d'un triplet de la manière suivante :
<source lang="ocaml">
let second3 t = match t with
(_, y, _) -> y
</source>
Notez l'utilisation de "<tt>_</tt>" pour donner la position d'une sous-valeur qui ne sert à rien.

Toutes les variables présentes dans le ''motif'' (la partie à gauche de la flèche) se retrouvent dans l'environnement avec pour valeur, la sous-valeur appropriée. Attention, ces variables ne se retrouvent dans l'environnement que dans la partie droite de la flèche.
Ces variables remplacent (temporairement) les variables de même nom qui pouvaient se trouver dans l'environnement. Par exemple, la fonction :
<source lang="ocaml">
let f x = match x with
(x,_) -> x
</source>
est exactement la fonction <tt>fst</tt>.

==== Filtrage sur les listes ====

On peut décomposer une liste en deux sous-valeurs :

* le premier élément de la liste,
* la suite de la liste.

Autrement dit, si la liste <tt>l</tt> n'est pas vide, on peut la décomposer en <tt>e::q</tt>. Comme il est possible que la liste <tt>l</tt> soit vide, il y a en fait deux manière de décomposer <tt>l</tt> :

* soit <tt>[]</tt> (sans aucune sous-valeur),
* soit <tt>e::q</tt> (avec deux sous-valeurs).

Par exemple, voici une manière de tester si une liste est vide :
<source lang="ocaml">
let vide l = match l with
[] -> true
| x::xs -> false
</source>
Les différents cas sont séparés par le symbole "<tt>|</tt>".

On peut également décomposer une liste en 3 sous-valeurs : le premier élément, le second élément et la suite de la liste. Dans ce cas, il a trois cas pour une liste arbitraire :

* elle est vide <tt>[]</tt> (aucune sous-valeur),
* elle ne contient qu'une seul élément <tt>[e]</tt> (une sous-valeur),
* elle contient un premier élément, un deuxième élément, et une suite <tt>a::b::q</tt> (trois sous-valeurs).

On peut par exemple écrire :
<source lang="ocaml">
let deux_elements_ou_plus l = match l with
[] -> false
| [a] -> false
| a::b::q -> true
</source>

Comme on peut toujours décomposer une valeur en une sous-valeur (la valeur elle même), on peut toujours avoir un motif de la forme <tt>x</tt>. Toutes les valeurs pourront être décomposées de cette manière, et il faut donc que ce motif soit le dernier. (Sinon, les motifs suivants ne servent à rien...) On parle de motif ''universel''. (On peut utiliser <tt>_</tt> comme motif universel.) Par exemple, on peut réecrire l'exemple précédent :
<source lang="ocaml">
let deux_elements_ou_plus
_::_::_ -> true
| _ -> false
</source>

==== Compléments ====

# On peut ajouter des constantes dans les motifs. Le motif ne sera utilisé que lorsque la sous-valeur correspondantes a la valeurs correspondante. Par exemple, si on modélise les entiers de Gauss (« entiers complexes ») par des paires d'entiers, on peut définir :
<source lang="ocaml">
let imaginaire_pur c = match c with
(0,0) -> false
| (0,_) -> true
| _ -> false
</source>
# On peut grouper des motifs différents pour faire la même chose. Il faut que les variables qui apparaissent dans les motifs soient les mêmes, et qu'elles aient le même type :
<source lang="ocaml">
let f x = match x with
0::l | 1::_::l | 2::_::_::l -> l (* on groupe 3 motifs en une seule ligne *)
| [] -> []
| x::_ -> [x]
</source>
# on peut « garder » les motifs" par une condition avec le mot clé "<tt>when</tt>"
<source lang="ocaml">
let g x = match x with
x::xs when (List.lenght (f xs) = 1) -> true
| _ -> false
</source>
Attention dans le cas où vous utilisez <tt>when</tt> : il est conseillé de terminer votre filtrage avec un motif universel pour être sûr que vous n'avez pas oublié de cas.
# comme on définit souvent des fonctions par filtrage, Caml autorise la syntaxe
<source lang="ocaml">
function
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
plutôt que
<source lang="ocaml">
fun x -> match x with
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
Remarquez que l'on ne peut faire ça que pour une fonction à une seule variable...
# fonction par filtrage : s'il n'y a qu'un seul motif, on peut alors utiliser le mot clé "<tt>fun</tt>" habituel, ce qui permet la définition d'une fonction à plusieurs arguments. (Mais dans ce cas, les parenthèses autour des tuples sont obligatoires.)
<source lang="ocaml">
# let h = fun (x,y) z (u,v,w) -> x+y+z+v ;;
val h : int * int -> int -> 'a * int * 'b -> int = <fun>
</source>

=== Le polymorphisme ===

=== Transparence référentielle ===

=== Les types algébriques ===

On peut défnir un synomnyme de type avec le mot clef <tt>type</tt>
Exemple :
<source lang="ocaml">type point = float*float</source>

==== Types énumérés ====

On donne tous les éléments du type
Exemple :
<source lang="ocaml">type jours = Lundi | Mardi | Mercredi | ...</source>

Type avec 7 éléments. Les éléments commencent forcément par une majuscule.

On peut comparer des éléments avec "=", "<" et ">" (< et > sont à éviter, il vaut mieux
écrire une fonction pour comparer) On peut aussi faire du filtrage.

Exemple:
<source lang="ocaml">
let week_end j = match j with
Samedi -> true
| Dimanche -> true
| _ -> false
</source>

==== Construction de types paramètres ====

Exemple : type des transformations de l'espace avec :
- Translation
- Rotation
- Symetrie
On aura alors des constructeurs avec des paramètres :

<source lang="ocaml">
type transformation =
Rotation of int*point
| Translation of point
| SymCentrale of point
| Homothetie of float*point
</source>

On n'a pas donné explicitement tous les éléments, mais on les a donné implicitement.
Exemple :
<source lang="ocaml">
let rien = Translation (0.0,0.0)
</source>
Autre exemple :
<source lang="ocaml">
let fait quelquechose t=
match t with
Rotation(a, (x, y)− > a mod360! = 0
|T ranslation(x, y)− > x! = 0.0 && y! = 0.0
|SymCentrale(x, y)− > true
|Homotetie(x, (−, −))− > r! = 1, 0
</source>

==== Les types récursifs ====

En Caml
<source lang="ocaml">
type node = Node of int*node
| Vide
</source>
exemple d'éléments de "node" :
- Vide
- Node(0,Vide)
- Node(1,Node(2,Node(3, Vide)))

Le type "node" est un type récursif. Comme les fonctions récursivent doivent avoir des cas
de base, les types récursifs doivent avoir des constructeurs "de base" (non récursifs). On peut
comparer des éléments avec "=". On peut aussi utiliser le filtrage.

Exemple :
<source lang="ocaml">
let rec taille l = match l with
Vide -> 0
|Node(_,l)->1+taille l
</source>

La fonction taille sur les listes Caml suit le même schéma avec les abréviations Caml.
<source lang="ocaml">
let rec taille l = match l with
[]->0
| a ::l->1+taille
</source>
Ceci explique la différence entre :: (constructeur) et @ (fonction récursive)

Exemple de type récursif, les arbres binaires :
<source lang="ocaml">
type bin = Vide | Noeud of int*bin*bin
</source>
arbre naire :
<source lang="ocaml">
type arbre n_aire =
Vide|Node of int ∗ (arbre_naire list)(bancal)
</source>

== Les structures ==

== La récursivité terminale ==

== Les exceptions ==

== Aspects impératifs dans Caml ==

== Les modules ==

INFO421 : Programmation fonctionnelle

2013-02-12T18:36:50Z

Lachand : /* Les types récursifs */

Ce wiki est un complément de cours pour le cours « info-421 : programmation fonctionnelle ». La participation au wiki est fortement encouragée, et deviendra peut-être obligatoire...

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Je vous conseille d'aller voir [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

== Détails techniques ==

=== Compléments de cours, TD et TP ===

==== Installer Ocaml ====

Si vous voulez installer OCaml sur votre ordinateur :

* Sous Linux : c'est la solution idéale. Il existe probablement des paquets pour votre distribution. Pour Ubuntu, pour avoir un environnement similaire à ce que vous aurez dans les salles informatiques, installez les paquets <tt>ocaml</tt>, <tt>ocaml-core</tt>, <tt>ocaml-mode</tt>, <tt>tuareg-mode</tt> et <tt>emacs</tt>.
* Sous MacOS : il semblerait qu'il y ait des paquets MacPorts pour <tt>ocaml</tt>, <tt>emacs</tt> et <tt>tuareg-mode.el</tt>.
* Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : [http://deptinfo.unice.fr/~roy/CAML/Win/install-win.html Installation de OCaml (sur Windows XP)]. Je n'ai malheureusement (??) pas accès à une machine avec Windows (98/2000/XP/Vista/7), je ne pourrais donc pas beaucoup vous aider.

Contactez moi si vous avez des problèmes.

Pour les exemples simples, vous pouvez aussi utiliser [http://try.ocamlpro.com/ OCaml en ligne]

==== Références supplémentaires ====

* Le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : [http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/ Développement d'applications avec Ocaml]. (Ce livre utilise une vieille version de Ocaml, mais reste pertinent.)
* La documentation de Caml, version 3.09 (utilisé en TP) : [http://caml.inria.fr/pub/docs/manual-ocaml-309/ Documentation and user's manual].
* Le livre de Jason Hickey [http://files.metaprl.org/doc/ocaml-book.pdf Introduction to Objective Caml] (en anglais).

==== Cours ====

==== TD et TP ====

* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/1213/info421/td1.pdf TD1 : premières expressions en Caml (pdf)]

== Introduction ==

Pour paraphraser un collègue dont je ne retrouve pas le nom :

<blockquote>
''Attention :'' il ne s'agit pas d'un cours de programmation fonctionelle
</blockquote>

Il s'agit plutôt d'un cours de programmation '''fonctionnelle'''...

=== Petit historique censuré ===

Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)

D'après [http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm ce site], qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

* années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à ''porter''. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
* FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
* LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
* ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
* Pascal (1975).
* C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
* Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
* ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
* Smalltalk (fin des année 1983), début de la programmation objet.
* 1983 : ADA.
* année '80 : Caml (1987), puis CamlLight(1990), puis OCaml(1996), développé
à l'INRIA. (Dernière version en octobre 2012.)
* années '90 : Python (version 1.0 en 1994).
* années '90 : PHP (version 1.0 en 1995).
* années '90 : Java (version 1.0 en 1996).

Je vous conseille d'aller voir le graphique suivant : [http://www.levenez.com/lang/lang.pdf Computer Languages Timeline] (ou [http://www.levenez.com/lang/redirect_lang_a4_pdf.html découpé en pages A4]).

=== Fonctionnel ?? ===

L'adjectif ''fonctionnel'' a au moins deux sens :

# qui fonctionne, en état de marche,
# qui se rapporte aux fonctions.

Les langages fonctionnels sont bien entendus ''fonctionnels'' dans le premier sens, mais c'est surtout le second sens qui nous intéresse. Les langages tels que Pascal, Ada ou C sont qualifié, par opposition, d''''impératifs'''''.

Un des slogans de la programmation fonctionnelle en général est

<blockquote>
''Les fonctions sont des valeurs comme les autres''
</blockquote>

et c'est de là que vient la terminologie... En particulier, il n'y a pas de différence entre les ''instructions'' (qui ont un effet) et les ''expressions'' (qui ont une valeur). Par exemple, en Python,

<pre>
x = x+1
</pre>

ou

<pre>
if delta < 0:
print("Il n'y a pas de solution")
</pre>

sont des ''instructions'' : on ne peut pas les mettre dans une variable.

Comme nous le verront, cela a des conséquences sur l'expressivité du langage et la manière de programmer.

=== Le langage (O)Caml ===

Le langage OCaml est développé par l'INRIA (Institut national de recherche en informatique et automatique). C'est un successeur de CamlLight.

Le nom Caml est formé des initiales de "Categorical Abstract Machine Language", et le langage lui même appartient à la famille de ML ("Meta Language"). C'est un langage fonctionnel ''strict'' (nous verrons ce que cela veut dire), statiquement typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :

* fonctionnel bien sûr,
* mais aussi impératif,
* objet également (c'est le « O » de OCaml).

Dans ce cours, nous utiliserons principalement le style fonctionnel, et un peu le style impératif en fin de semestre.

Voici quelques aspects importants du langages que nous essayeront d'aborder pendant le cours :

* fonctions comme valeurs,
* types de données ''algébriques''
* polymorphisme,
* système d'exceptions,
* support pour des références et des données mutables (programmation « impure »),
* système de modules et de foncteurs,
* ...

La notion de ''récursivité'' sera fondamentale pendant toute la durée du cours...

Un aspect intéressant du langage est que c'est :

* un langage interprété (avec l'interpréteur OCaml),
* soit un langage compilé en bytecode (code binaire indépendant de l'architecture),
* soit un langage compilé optimisé en binaire (dépendant de l'architecture).

=== Autres langages fonctionnels ===

Il existe de nombreux autres langages fonctionnels. Par exemple :

* SML (Standard ML) : [http://en.wikipedia.org/wiki/Standard_ML Wikipedia], autre dialecte de la famille ML.
* LISP, dont les deux dialectes principaux sont :
** Common LISP : [http://en.wikipedia.org/wiki/Common_LISP Wikipedia],
** Scheme : [http://en.wikipedia.org/wiki/Scheme_%28programming_language%29 Wikipedia].
* Haskell : [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Wikipedia] (inspiré en grande partie de [http://en.wikipedia.org/wiki/Miranda_%28programming_language%29 Miranda]).

Plusieurs langages impératifs intègrent maintenant des aspects propres des langages fonctionnels : Python, Scala, ...

=== Applications concrètes ===

Voici quelques exemples de logiciels développés en OCaml :

* [http://ocsigen.org/ Ocsigen], un serveur web,
* [http://www.cis.upenn.edu/~bcpierce/unison/ Unison], un logiciel de synchronisation de fichiers entre ordinateurs,
* [http://mldonkey.sourceforge.net/Main_Page MLDonkey], un logiciel de Peer-to-peer multiréseaux,
* [http://pauillac.inria.fr/advi/ Active DVI] un visualisateur pour le format de fichier DVI,
* analyse de programmes critiques : [http://www.astree.ens.fr/ Astrée],
* informatique financiere : [http://www.janestreet.com Janestreet Capital] et [http://www.lexifi.com Lexifi].

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang ([http://fr.wikipedia.org/wiki/Erlang_%28langage%29 Wikipedia]), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

=== Objectifs du cours ===

# être capable de définir des fonctions récursives, et comprendre ce qu'elles font
# comprendre le typage, les types algébriques et le polymorphisme à la ML
# pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
# être capable de décomposer un problème
# commencer à réfléchir à la complexité de vos programmes

== Premiers pas en Caml ==

Un des slogans de la programmation fonctionnelle est ''tout est une valeur, ou plus précisément,

<blockquote>
''Toute expression a une valeur.''
</blockquote>

Cette idée n'est pas présente en Python où l'on distingue les ''expressions'' ("<tt>3*x+f(2)</tt>" par exemple) et les ''instructions'' ("<tt>if n>22: a=12 else: a=13</tt>" par exemple). En Python, les instructions sont en général séparées par des retours à la ligne et sont ''exécutées'' en séquence. Les expressions sont juste calculées, et ne peuvent pas être séquentialisées.

Dans un langage purement fonctionnel, le "<tt>;</tt>" n'existe pas, et il n'y a que des valeurs...

Les valeurs sont formées en utilisant :

* les fonctions du langage (addition, multiplication, opérateurs logiques),
* des constructions du langage (<tt>if ... then ... else ...</tt> par exemple),
* les relations mathématiques (égalité, plus grand), ... qui sont juste des fonctions renvoyant des booléens,
* les constantes du langage,
* les variables de l'environnement,
* ''les valeurs (en particulier les fonctions) définies par le programmeur''.

Bien entendu, comme Caml est typé, il faut respecter les types.

=== Les types atomiques ===

Caml (et les autres langages fonctionnels typés) possèdent plusieurs types de base tels que :

* les booléens : type <tt>bool</tt> (valeur <tt>true</tt> et <tt>false</tt>) et les opérations <tt>not</tt>, <tt>&&</tt> (et) et <tt>||</tt> (ou).
* Les entiers : type <tt>int</tt> pour les entiers signés compris entre <math>-230</math> et <math>230-1</math>. (Les entiers Caml sont stockés sur 31 bits...) Les opérations associés sont <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, <tt>/</tt> (pour la division entière) et <tt>mod</tt> (pour le modulo).
* Les flottants : type <tt>float</tt> pour les réels en virgule flottante. Les opérations usuelles sont <tt>+.</tt>, <tt>-.</tt>, <tt>*.</tt> et <tt>/.</tt>.
* Les caractères : type <tt>char</tt> (notés entre guillemets simples).
* Le type unité : type <tt>unit</tt>, dont l'unique valeur est <tt>()</tt>. (Nous verrons que ce type a une utilité...)

Même s'il ne s'agit pas vraiment d'un type atomique, nous pouvons également ajouter le type des chaînes de caractères : type <tt>string</tt> (notées entre guillemets doubles).

<source lang="ocaml">
(* exemples ... *)
</source>

'''Remarques :''' les opérations booléennes ("<tt>&&</tt>" pour le « et » et "<tt>||</tt>" pour le « ou ») fonctionnent de à gauche à droite, et l'argument de droite n'est évalué que si c'est nécessaire. Par exemple <tt>true || (0 = 1/0)</tt> donne la valeur <tt>true</tt>, alors que que <tt>false || (0=1/0)</tt> lève l'exception <tt>Division_by_zero</tt>.

=== définitions et environnement ===

Comme tous les langages de programmation, Caml garde en mémoire une liste de définitions. Chacune de ces définitions met en relation un nom ("<tt>x</tt>", "<tt>n</tt>", "<tt>length</tt>", ...) et une valeur ("<tt>3.7</tt>", "<tt>42</tt>", "<tt>fun s -> ...</tt>").

Lorsque l'on lance Caml, l'environnement contient déjà de nombreuse fonctions prédéfinies : <tt>max</tt>, <tt>min</tt>, <tt>mod</tt>, <tt>+</tt>, <tt>float_of_int</tt>, ...

Certaines des variables de l'environnement correspondent à des paramètres de fonction en cours de définition. Ces variables n'ont pas de valeur, mais seulement un type.

==== Environnement ====

* Liste de paires <tt>nom</tt> / <tt>valeur</tt>,
* une nouvelle definition remplace la précédente mais ne l'efface pas, (on ne met pas une valeur à jours)

==== Définitions ====

L'utilisateur peut rajouter des définitions dans l'environnement grâce au mot clé <tt>let</tt>

* <tt>let nom = expr</tt> permet de rajouter une définition simple dans l'environnement. Exemple : <tt>let n = 42</tt>
* <tt>let nom1 = expr1 and nom2 = expr2</tt> permet de rajouter plusieurs définitions simultanément. Exemple : <tt>let a=1 and b=2</tt>
* <tt>let rec nom1 = expr1 and nom2 = expr2</tt> permet de rajouter des définitions mutuellement récursives.

On peut toujours annoter la définition de types de données. Ceci évite à Caml d'avoir à deviner le type que l'on souhaite et permet de préciser la fonction :
<source lang="ocaml">
let n:int = 42
let rec f (n:int) : string = if (n<1) then "" else "*" ^ (f (n-1))
</source>

Si une définition utilise le même nom qu'une définition précédente, la nouvelle définition écrase l'ancienne. Par exemple :
<source lang="ocaml">
# let n=42 ;;
val n : int = 42
# let n=3.1415 ;;
val n : float = 3.1415
# n ;;

* : float = 3.1415
</source>

==== Définitions locales ====

Il est possible de modifier l'environnement de manière temporaire (''locale''). On utilise alors <tt>let nom = expr1 in expr2</tt>. Ceci ajoute la définition <tt>nom = expr1</tt> dans l'environnement, mais seulement pour l'évaluation de l'expression <tt>expr2</tt>.
<source lang="ocaml">
# let x =
let y = 42 in
y/2 ;;
val x : int = 21
# x ;;

* : int = 21
# y ;;
Unbound value y
</source>

=== Les fonctions ===

Caml utilise la notation mathématique pour écrire les types des fonctions. Si <tt>f</tt> est une fonction avec un seul argument de type <tt>string</tt> et dont la valeur de retour est de type <tt>int</tt> (la fonction <tt>length</tt> par exemple), le type de <tt>f</tt> est noté <tt>string -> int</tt>. Dans l'interprète Caml :
<source lang="ocaml">
# String.length ;;

* : string -> int = <fun>
</source>
Nous indique que la fonction <tt>length</tt> est bien de type <tt>string->int</tt>.

Une fonction est définie comme une variable avec un <tt>let</tt> et en utilisant le mot clé <tt>fun</tt> :
<source lang="ocaml">
# let f = fun n -> n+1;;
val f : int -> int = <fun>
# let racine = fun n -> int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
</source>

Une fonction avec plusieurs argument est définie de la même manière avec
<source lang="ocaml">
# let moyenne3 = fun x y z -> (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Le type d'une fonction à plusieurs argument est noté en mettant plusieurs types à gauche de la flèche <tt>-></tt>, comme ci dessus : <tt>type_arg1 -> type_arg2 -> type_arg3 -> type_resultat</tt>.

'''Remarques :'''

* notez l'absence de mot clé <tt>return</tt> et l'absence de virgules pour séparer les différents arguments !
* Le mot clé <tt>fun</tt> permet de définir des fonctions sans leur donner de nom, ce qui n'est pas possible dans les langages comme C ou Java...

On peut également utiliser un raccourci pour définir une fonction sans utiliser le mot clé <tt>fun</tt> : il suffit de mettre les arguments de la fonction avant le signe égal :
<source lang="ocaml">
# let f n = n+1;;
val f : int -> int = <fun>
# let racine n = int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
# let moyenne3 x y z = (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Pour appliquer une fonction à des arguments, on écrit simplement
<source lang="ocaml">
moyenne3 13.5 17.0 -0.333
</source>
Il n'y a ni parenthèse, ni virgule. Les parenthèses peuvent cependant être nécessaires pour différencier
<source lang="ocaml">
moyenne3 13.5 17.0 (-0.333 *. 6.)
</source>
et
<source lang="ocaml">
(moyenne3 13.5 17.0 -0.333) *. 6.
</source>
ou pour que Caml lise correctement
<source lang="ocaml">
moyenne3 13.5 (17.0 -. 12.0) -0.333
</source>

==== Fonctions récursives ====

Si on essaie de définir une fonction récursivement :
<source lang="ocaml">
let f n = if (n<1) then 0 else n + f (n-1)
</source>
Caml répond
<source lang="ocaml">
Error: Unbound value f
</source>
car <tt>f</tt> n'est pas présente dans l'environnement.

Pour rajouter <tt>f</tt> comme variable active (sans valeur) et pouvoir faire une définition récursive, il faut utiliser le mot clé <tt>rec</tt> :
<source lang="ocaml">
# let rec f n = if (n<1) then 0 else n + f (n-1);;
val f : int -> int = <fun>
</source>

Les définitions locales peuvent elles aussi être récursives (<tt>let rec ... in ...</tt>) ou mutuellement récursives (<tt>let rec ... and ... in ...</tt>). Elles acceptent également les annotations de type...

==== fonctions d'ordre supérieur ====

TODO

=== Les listes ===

Le type des listes est fondamental en programmation fonctionnelle. D'une certaine manière, on peut dire qu'ils remplacent les tableaux que l'on utilise constamment en programmation impérative.

Exercice : quels sont les différences importantes (utilisation, complexité, mémoire, ...) entre les tableaux et les listes ?

En Caml, une liste est représentée entre crochets, et les éléments sont séparés par des points-virgules :
<source lang="ocaml">
# let une_liste = [ 1 ; 2 ; 2 ; -1 ; 0 ] ;;
val une_liste : int list = [1; 2; 2; -1; 0]
# let une_autre_liste = [ "coucou" ; "je m'appelle" ; "Bob" ] ;;
val une_autre_liste : string list = ["coucou"; "je m'appelle"; "Bob"]
</source>

Comme vous pouvez le voir dans l'exemple au dessus, le type des listes d'entiers s'appelle "<tt>int list</tt>", le type des listes de flottants s'appelle "<tt>float list</tt>" et le type des listes de listes d'entiers s'appelle ... "<tt>int list list</tt>".

Contrairement au cas des tuples, les éléments d'une liste doivent tous avoir le même type :
<source lang="ocaml">
# let une_non_liste = [ 1 ; "Toto" ; 1.3 ] ;;
This expression has type string but is here used with type int
</source>

Attention : quel est le type de la liste suivante ?
<source lang="ocaml">
# let une_liste_bizarre = [ 1 , 2 , 3 ] ;;
</source>

On peut ajouter un élement devant une liste avec l'opérateur "<tt>::</tt>" et la concaténation des listes s'obtient avec l'opérateur "<tt>@</tt>".
<source lang="ocaml">
# 5::[1;2;3;4] ;;
- : int list = [5; 1; 2; 3; 4]
# [-1;-2;-3;-4] @ [1;2;3;4] ;;
- : int list = [-1; -2; -3; -4; 1; 2; 3; 4]
</source>
Attention : la complexité de l'opération "<tt>::</tt>" ne dépend pas de la taille des listes mises en jeux. Par contre, la complexité de l'opération "<tt>@</tt>" dépend proportionnellement de la taille de son premier argument. Il faut donc toujour privilégier "<tt>::</tt>" par rapport à "<tt>@</tt>". En particulier, il est en général mauvais de rajouter des élément en fin de liste en utilisant "<tt>l @ [e]</tt>".

=== Filtrage, première partie : tuples et listes ===

La notion de ''filtrage'', aussi appelé "pattern-matching" est un outils clé pour la programmation en Caml. L'idée est de décomposer une valeur en "sous-valeurs".

==== Filtrage sur les tuples ====

Comme une paire est de la forme <tt>(x,y)</tt>, on peut décomposer une valeur de type <tt>a*b</tt> en deux sous valeurs. Voici un exemple de syntaxe : le code de la fonction <tt>fst</tt> :
<source lang="ocaml">
let premier p = match p with
(x,y) -> x
</source>

Pour évaluer "<tt>premier e</tt>", Caml regarde le premier argument <tt>e</tt> et essaie de faire coïncider "<tt>(x,y)</tt>". S'il y arrive, alors il renvoie la valeur "<tt>x</tt>". Le typage de Caml inférera automatique que "<tt>p</tt>" doit être une paire, et il n'y a donc pas besoin de prévoir un cas par defaut.

On peut maintenant récupérer la deuxième composante d'un triplet de la manière suivante :
<source lang="ocaml">
let second3 t = match t with
(_, y, _) -> y
</source>
Notez l'utilisation de "<tt>_</tt>" pour donner la position d'une sous-valeur qui ne sert à rien.

Toutes les variables présentes dans le ''motif'' (la partie à gauche de la flèche) se retrouvent dans l'environnement avec pour valeur, la sous-valeur appropriée. Attention, ces variables ne se retrouvent dans l'environnement que dans la partie droite de la flèche.
Ces variables remplacent (temporairement) les variables de même nom qui pouvaient se trouver dans l'environnement. Par exemple, la fonction :
<source lang="ocaml">
let f x = match x with
(x,_) -> x
</source>
est exactement la fonction <tt>fst</tt>.

==== Filtrage sur les listes ====

On peut décomposer une liste en deux sous-valeurs :

* le premier élément de la liste,
* la suite de la liste.

Autrement dit, si la liste <tt>l</tt> n'est pas vide, on peut la décomposer en <tt>e::q</tt>. Comme il est possible que la liste <tt>l</tt> soit vide, il y a en fait deux manière de décomposer <tt>l</tt> :

* soit <tt>[]</tt> (sans aucune sous-valeur),
* soit <tt>e::q</tt> (avec deux sous-valeurs).

Par exemple, voici une manière de tester si une liste est vide :
<source lang="ocaml">
let vide l = match l with
[] -> true
| x::xs -> false
</source>
Les différents cas sont séparés par le symbole "<tt>|</tt>".

On peut également décomposer une liste en 3 sous-valeurs : le premier élément, le second élément et la suite de la liste. Dans ce cas, il a trois cas pour une liste arbitraire :

* elle est vide <tt>[]</tt> (aucune sous-valeur),
* elle ne contient qu'une seul élément <tt>[e]</tt> (une sous-valeur),
* elle contient un premier élément, un deuxième élément, et une suite <tt>a::b::q</tt> (trois sous-valeurs).

On peut par exemple écrire :
<source lang="ocaml">
let deux_elements_ou_plus l = match l with
[] -> false
| [a] -> false
| a::b::q -> true
</source>

Comme on peut toujours décomposer une valeur en une sous-valeur (la valeur elle même), on peut toujours avoir un motif de la forme <tt>x</tt>. Toutes les valeurs pourront être décomposées de cette manière, et il faut donc que ce motif soit le dernier. (Sinon, les motifs suivants ne servent à rien...) On parle de motif ''universel''. (On peut utiliser <tt>_</tt> comme motif universel.) Par exemple, on peut réecrire l'exemple précédent :
<source lang="ocaml">
let deux_elements_ou_plus
_::_::_ -> true
| _ -> false
</source>

==== Compléments ====

# On peut ajouter des constantes dans les motifs. Le motif ne sera utilisé que lorsque la sous-valeur correspondantes a la valeurs correspondante. Par exemple, si on modélise les entiers de Gauss (« entiers complexes ») par des paires d'entiers, on peut définir :
<source lang="ocaml">
let imaginaire_pur c = match c with
(0,0) -> false
| (0,_) -> true
| _ -> false
</source>
# On peut grouper des motifs différents pour faire la même chose. Il faut que les variables qui apparaissent dans les motifs soient les mêmes, et qu'elles aient le même type :
<source lang="ocaml">
let f x = match x with
0::l | 1::_::l | 2::_::_::l -> l (* on groupe 3 motifs en une seule ligne *)
| [] -> []
| x::_ -> [x]
</source>
# on peut « garder » les motifs" par une condition avec le mot clé "<tt>when</tt>"
<source lang="ocaml">
let g x = match x with
x::xs when (List.lenght (f xs) = 1) -> true
| _ -> false
</source>
Attention dans le cas où vous utilisez <tt>when</tt> : il est conseillé de terminer votre filtrage avec un motif universel pour être sûr que vous n'avez pas oublié de cas.
# comme on définit souvent des fonctions par filtrage, Caml autorise la syntaxe
<source lang="ocaml">
function
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
plutôt que
<source lang="ocaml">
fun x -> match x with
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
Remarquez que l'on ne peut faire ça que pour une fonction à une seule variable...
# fonction par filtrage : s'il n'y a qu'un seul motif, on peut alors utiliser le mot clé "<tt>fun</tt>" habituel, ce qui permet la définition d'une fonction à plusieurs arguments. (Mais dans ce cas, les parenthèses autour des tuples sont obligatoires.)
<source lang="ocaml">
# let h = fun (x,y) z (u,v,w) -> x+y+z+v ;;
val h : int * int -> int -> 'a * int * 'b -> int = <fun>
</source>

=== Le polymorphisme ===

=== Transparence référentielle ===

==== Les types algébriques ====

On peut défnir un synomnyme de type avec le mot clef <tt>type</tt>
Exemple :
<source lang="ocaml">type point = float*float</source>

==== Types énumérés ====

On donne tous les éléments du type
Exemple :
<source lang="ocaml">type jours = Lundi | Mardi | Mercredi | ...</source>

Type avec 7 éléments. Les éléments commencent forcément par une majuscule.

On peut comparer des éléments avec "=", "<" et ">" (< et > sont à éviter, il vaut mieux
écrire une fonction pour comparer) On peut aussi faire du filtrage.

Exemple:
<source lang="ocaml">
let week_end j = match j with
Samedi -> true
| Dimanche -> true
| _ -> false
</source>

==== Construction de types paramètres ====

Exemple : type des transformations de l'espace avec :
- Translation
- Rotation
- Symetrie
On aura alors des constructeurs avec des paramètres :

<source lang="ocaml">
type transformation =
Rotation of int*point
| Translation of point
| SymCentrale of point
| Homothetie of float*point
</source>

On n'a pas donné explicitement tous les éléments, mais on les a donné implicitement.
Exemple :
<source lang="ocaml">
let rien = Translation (0.0,0.0)
</source>
Autre exemple :
<source lang="ocaml">
let fait quelquechose t=
match t with
Rotation(a, (x, y)− > a mod360! = 0
|T ranslation(x, y)− > x! = 0.0 && y! = 0.0
|SymCentrale(x, y)− > true
|Homotetie(x, (−, −))− > r! = 1, 0
</source>

==== Les types récursifs ====

En Caml
<source lang="ocaml">
type node = Node of int*node
| Vide
</source>
exemple d'éléments de "node" :
- Vide
- Node(0,Vide)
- Node(1,Node(2,Node(3, Vide)))

Le type "node" est un type récursif. Comme les fonctions récursivent doivent avoir des cas
de base, les types récursifs doivent avoir des constructeurs "de base" (non récursifs). On peut
comparer des éléments avec "=". On peut aussi utiliser le filtrage.

Exemple :
<source lang="ocaml">
let rec taille l = match l with
Vide -> 0
|Node(_,l)->1+taille l
</source>

La fonction taille sur les listes Caml suit le même schéma avec les abréviations Caml.
<source lang="ocaml">
let rec taille l = match l with
[]->0
| a ::l->1+taille
</source>
Ceci explique la différence entre :: (constructeur) et @ (fonction récursive)

Exemple de type récursif, les arbres binaires :
<source lang="ocaml">
type bin = Vide | Noeud of int*bin*bin
</source>
arbre naire :
<source lang="ocaml">
type arbre n_aire =
Vide|Node of int ∗ (arbre_naire list)(bancal)
</source>

== Les structures ==

== La récursivité terminale ==

== Les exceptions ==

== Aspects impératifs dans Caml ==

== Les modules ==

INFO421 : Programmation fonctionnelle

2013-02-12T18:36:41Z

Lachand : /* Construction de types paramètres */

Ce wiki est un complément de cours pour le cours « info-421 : programmation fonctionnelle ». La participation au wiki est fortement encouragée, et deviendra peut-être obligatoire...

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Je vous conseille d'aller voir [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

== Détails techniques ==

=== Compléments de cours, TD et TP ===

==== Installer Ocaml ====

Si vous voulez installer OCaml sur votre ordinateur :

* Sous Linux : c'est la solution idéale. Il existe probablement des paquets pour votre distribution. Pour Ubuntu, pour avoir un environnement similaire à ce que vous aurez dans les salles informatiques, installez les paquets <tt>ocaml</tt>, <tt>ocaml-core</tt>, <tt>ocaml-mode</tt>, <tt>tuareg-mode</tt> et <tt>emacs</tt>.
* Sous MacOS : il semblerait qu'il y ait des paquets MacPorts pour <tt>ocaml</tt>, <tt>emacs</tt> et <tt>tuareg-mode.el</tt>.
* Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : [http://deptinfo.unice.fr/~roy/CAML/Win/install-win.html Installation de OCaml (sur Windows XP)]. Je n'ai malheureusement (??) pas accès à une machine avec Windows (98/2000/XP/Vista/7), je ne pourrais donc pas beaucoup vous aider.

Contactez moi si vous avez des problèmes.

Pour les exemples simples, vous pouvez aussi utiliser [http://try.ocamlpro.com/ OCaml en ligne]

==== Références supplémentaires ====

* Le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : [http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/ Développement d'applications avec Ocaml]. (Ce livre utilise une vieille version de Ocaml, mais reste pertinent.)
* La documentation de Caml, version 3.09 (utilisé en TP) : [http://caml.inria.fr/pub/docs/manual-ocaml-309/ Documentation and user's manual].
* Le livre de Jason Hickey [http://files.metaprl.org/doc/ocaml-book.pdf Introduction to Objective Caml] (en anglais).

==== Cours ====

==== TD et TP ====

* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/1213/info421/td1.pdf TD1 : premières expressions en Caml (pdf)]

== Introduction ==

Pour paraphraser un collègue dont je ne retrouve pas le nom :

<blockquote>
''Attention :'' il ne s'agit pas d'un cours de programmation fonctionelle
</blockquote>

Il s'agit plutôt d'un cours de programmation '''fonctionnelle'''...

=== Petit historique censuré ===

Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)

D'après [http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm ce site], qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

* années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à ''porter''. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
* FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
* LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
* ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
* Pascal (1975).
* C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
* Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
* ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
* Smalltalk (fin des année 1983), début de la programmation objet.
* 1983 : ADA.
* année '80 : Caml (1987), puis CamlLight(1990), puis OCaml(1996), développé
à l'INRIA. (Dernière version en octobre 2012.)
* années '90 : Python (version 1.0 en 1994).
* années '90 : PHP (version 1.0 en 1995).
* années '90 : Java (version 1.0 en 1996).

Je vous conseille d'aller voir le graphique suivant : [http://www.levenez.com/lang/lang.pdf Computer Languages Timeline] (ou [http://www.levenez.com/lang/redirect_lang_a4_pdf.html découpé en pages A4]).

=== Fonctionnel ?? ===

L'adjectif ''fonctionnel'' a au moins deux sens :

# qui fonctionne, en état de marche,
# qui se rapporte aux fonctions.

Les langages fonctionnels sont bien entendus ''fonctionnels'' dans le premier sens, mais c'est surtout le second sens qui nous intéresse. Les langages tels que Pascal, Ada ou C sont qualifié, par opposition, d''''impératifs'''''.

Un des slogans de la programmation fonctionnelle en général est

<blockquote>
''Les fonctions sont des valeurs comme les autres''
</blockquote>

et c'est de là que vient la terminologie... En particulier, il n'y a pas de différence entre les ''instructions'' (qui ont un effet) et les ''expressions'' (qui ont une valeur). Par exemple, en Python,

<pre>
x = x+1
</pre>

ou

<pre>
if delta < 0:
print("Il n'y a pas de solution")
</pre>

sont des ''instructions'' : on ne peut pas les mettre dans une variable.

Comme nous le verront, cela a des conséquences sur l'expressivité du langage et la manière de programmer.

=== Le langage (O)Caml ===

Le langage OCaml est développé par l'INRIA (Institut national de recherche en informatique et automatique). C'est un successeur de CamlLight.

Le nom Caml est formé des initiales de "Categorical Abstract Machine Language", et le langage lui même appartient à la famille de ML ("Meta Language"). C'est un langage fonctionnel ''strict'' (nous verrons ce que cela veut dire), statiquement typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :

* fonctionnel bien sûr,
* mais aussi impératif,
* objet également (c'est le « O » de OCaml).

Dans ce cours, nous utiliserons principalement le style fonctionnel, et un peu le style impératif en fin de semestre.

Voici quelques aspects importants du langages que nous essayeront d'aborder pendant le cours :

* fonctions comme valeurs,
* types de données ''algébriques''
* polymorphisme,
* système d'exceptions,
* support pour des références et des données mutables (programmation « impure »),
* système de modules et de foncteurs,
* ...

La notion de ''récursivité'' sera fondamentale pendant toute la durée du cours...

Un aspect intéressant du langage est que c'est :

* un langage interprété (avec l'interpréteur OCaml),
* soit un langage compilé en bytecode (code binaire indépendant de l'architecture),
* soit un langage compilé optimisé en binaire (dépendant de l'architecture).

=== Autres langages fonctionnels ===

Il existe de nombreux autres langages fonctionnels. Par exemple :

* SML (Standard ML) : [http://en.wikipedia.org/wiki/Standard_ML Wikipedia], autre dialecte de la famille ML.
* LISP, dont les deux dialectes principaux sont :
** Common LISP : [http://en.wikipedia.org/wiki/Common_LISP Wikipedia],
** Scheme : [http://en.wikipedia.org/wiki/Scheme_%28programming_language%29 Wikipedia].
* Haskell : [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Wikipedia] (inspiré en grande partie de [http://en.wikipedia.org/wiki/Miranda_%28programming_language%29 Miranda]).

Plusieurs langages impératifs intègrent maintenant des aspects propres des langages fonctionnels : Python, Scala, ...

=== Applications concrètes ===

Voici quelques exemples de logiciels développés en OCaml :

* [http://ocsigen.org/ Ocsigen], un serveur web,
* [http://www.cis.upenn.edu/~bcpierce/unison/ Unison], un logiciel de synchronisation de fichiers entre ordinateurs,
* [http://mldonkey.sourceforge.net/Main_Page MLDonkey], un logiciel de Peer-to-peer multiréseaux,
* [http://pauillac.inria.fr/advi/ Active DVI] un visualisateur pour le format de fichier DVI,
* analyse de programmes critiques : [http://www.astree.ens.fr/ Astrée],
* informatique financiere : [http://www.janestreet.com Janestreet Capital] et [http://www.lexifi.com Lexifi].

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang ([http://fr.wikipedia.org/wiki/Erlang_%28langage%29 Wikipedia]), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

=== Objectifs du cours ===

# être capable de définir des fonctions récursives, et comprendre ce qu'elles font
# comprendre le typage, les types algébriques et le polymorphisme à la ML
# pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
# être capable de décomposer un problème
# commencer à réfléchir à la complexité de vos programmes

== Premiers pas en Caml ==

Un des slogans de la programmation fonctionnelle est ''tout est une valeur, ou plus précisément,

<blockquote>
''Toute expression a une valeur.''
</blockquote>

Cette idée n'est pas présente en Python où l'on distingue les ''expressions'' ("<tt>3*x+f(2)</tt>" par exemple) et les ''instructions'' ("<tt>if n>22: a=12 else: a=13</tt>" par exemple). En Python, les instructions sont en général séparées par des retours à la ligne et sont ''exécutées'' en séquence. Les expressions sont juste calculées, et ne peuvent pas être séquentialisées.

Dans un langage purement fonctionnel, le "<tt>;</tt>" n'existe pas, et il n'y a que des valeurs...

Les valeurs sont formées en utilisant :

* les fonctions du langage (addition, multiplication, opérateurs logiques),
* des constructions du langage (<tt>if ... then ... else ...</tt> par exemple),
* les relations mathématiques (égalité, plus grand), ... qui sont juste des fonctions renvoyant des booléens,
* les constantes du langage,
* les variables de l'environnement,
* ''les valeurs (en particulier les fonctions) définies par le programmeur''.

Bien entendu, comme Caml est typé, il faut respecter les types.

=== Les types atomiques ===

Caml (et les autres langages fonctionnels typés) possèdent plusieurs types de base tels que :

* les booléens : type <tt>bool</tt> (valeur <tt>true</tt> et <tt>false</tt>) et les opérations <tt>not</tt>, <tt>&&</tt> (et) et <tt>||</tt> (ou).
* Les entiers : type <tt>int</tt> pour les entiers signés compris entre <math>-230</math> et <math>230-1</math>. (Les entiers Caml sont stockés sur 31 bits...) Les opérations associés sont <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, <tt>/</tt> (pour la division entière) et <tt>mod</tt> (pour le modulo).
* Les flottants : type <tt>float</tt> pour les réels en virgule flottante. Les opérations usuelles sont <tt>+.</tt>, <tt>-.</tt>, <tt>*.</tt> et <tt>/.</tt>.
* Les caractères : type <tt>char</tt> (notés entre guillemets simples).
* Le type unité : type <tt>unit</tt>, dont l'unique valeur est <tt>()</tt>. (Nous verrons que ce type a une utilité...)

Même s'il ne s'agit pas vraiment d'un type atomique, nous pouvons également ajouter le type des chaînes de caractères : type <tt>string</tt> (notées entre guillemets doubles).

<source lang="ocaml">
(* exemples ... *)
</source>

'''Remarques :''' les opérations booléennes ("<tt>&&</tt>" pour le « et » et "<tt>||</tt>" pour le « ou ») fonctionnent de à gauche à droite, et l'argument de droite n'est évalué que si c'est nécessaire. Par exemple <tt>true || (0 = 1/0)</tt> donne la valeur <tt>true</tt>, alors que que <tt>false || (0=1/0)</tt> lève l'exception <tt>Division_by_zero</tt>.

=== définitions et environnement ===

Comme tous les langages de programmation, Caml garde en mémoire une liste de définitions. Chacune de ces définitions met en relation un nom ("<tt>x</tt>", "<tt>n</tt>", "<tt>length</tt>", ...) et une valeur ("<tt>3.7</tt>", "<tt>42</tt>", "<tt>fun s -> ...</tt>").

Lorsque l'on lance Caml, l'environnement contient déjà de nombreuse fonctions prédéfinies : <tt>max</tt>, <tt>min</tt>, <tt>mod</tt>, <tt>+</tt>, <tt>float_of_int</tt>, ...

Certaines des variables de l'environnement correspondent à des paramètres de fonction en cours de définition. Ces variables n'ont pas de valeur, mais seulement un type.

==== Environnement ====

* Liste de paires <tt>nom</tt> / <tt>valeur</tt>,
* une nouvelle definition remplace la précédente mais ne l'efface pas, (on ne met pas une valeur à jours)

==== Définitions ====

L'utilisateur peut rajouter des définitions dans l'environnement grâce au mot clé <tt>let</tt>

* <tt>let nom = expr</tt> permet de rajouter une définition simple dans l'environnement. Exemple : <tt>let n = 42</tt>
* <tt>let nom1 = expr1 and nom2 = expr2</tt> permet de rajouter plusieurs définitions simultanément. Exemple : <tt>let a=1 and b=2</tt>
* <tt>let rec nom1 = expr1 and nom2 = expr2</tt> permet de rajouter des définitions mutuellement récursives.

On peut toujours annoter la définition de types de données. Ceci évite à Caml d'avoir à deviner le type que l'on souhaite et permet de préciser la fonction :
<source lang="ocaml">
let n:int = 42
let rec f (n:int) : string = if (n<1) then "" else "*" ^ (f (n-1))
</source>

Si une définition utilise le même nom qu'une définition précédente, la nouvelle définition écrase l'ancienne. Par exemple :
<source lang="ocaml">
# let n=42 ;;
val n : int = 42
# let n=3.1415 ;;
val n : float = 3.1415
# n ;;

* : float = 3.1415
</source>

==== Définitions locales ====

Il est possible de modifier l'environnement de manière temporaire (''locale''). On utilise alors <tt>let nom = expr1 in expr2</tt>. Ceci ajoute la définition <tt>nom = expr1</tt> dans l'environnement, mais seulement pour l'évaluation de l'expression <tt>expr2</tt>.
<source lang="ocaml">
# let x =
let y = 42 in
y/2 ;;
val x : int = 21
# x ;;

* : int = 21
# y ;;
Unbound value y
</source>

=== Les fonctions ===

Caml utilise la notation mathématique pour écrire les types des fonctions. Si <tt>f</tt> est une fonction avec un seul argument de type <tt>string</tt> et dont la valeur de retour est de type <tt>int</tt> (la fonction <tt>length</tt> par exemple), le type de <tt>f</tt> est noté <tt>string -> int</tt>. Dans l'interprète Caml :
<source lang="ocaml">
# String.length ;;

* : string -> int = <fun>
</source>
Nous indique que la fonction <tt>length</tt> est bien de type <tt>string->int</tt>.

Une fonction est définie comme une variable avec un <tt>let</tt> et en utilisant le mot clé <tt>fun</tt> :
<source lang="ocaml">
# let f = fun n -> n+1;;
val f : int -> int = <fun>
# let racine = fun n -> int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
</source>

Une fonction avec plusieurs argument est définie de la même manière avec
<source lang="ocaml">
# let moyenne3 = fun x y z -> (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Le type d'une fonction à plusieurs argument est noté en mettant plusieurs types à gauche de la flèche <tt>-></tt>, comme ci dessus : <tt>type_arg1 -> type_arg2 -> type_arg3 -> type_resultat</tt>.

'''Remarques :'''

* notez l'absence de mot clé <tt>return</tt> et l'absence de virgules pour séparer les différents arguments !
* Le mot clé <tt>fun</tt> permet de définir des fonctions sans leur donner de nom, ce qui n'est pas possible dans les langages comme C ou Java...

On peut également utiliser un raccourci pour définir une fonction sans utiliser le mot clé <tt>fun</tt> : il suffit de mettre les arguments de la fonction avant le signe égal :
<source lang="ocaml">
# let f n = n+1;;
val f : int -> int = <fun>
# let racine n = int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
# let moyenne3 x y z = (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Pour appliquer une fonction à des arguments, on écrit simplement
<source lang="ocaml">
moyenne3 13.5 17.0 -0.333
</source>
Il n'y a ni parenthèse, ni virgule. Les parenthèses peuvent cependant être nécessaires pour différencier
<source lang="ocaml">
moyenne3 13.5 17.0 (-0.333 *. 6.)
</source>
et
<source lang="ocaml">
(moyenne3 13.5 17.0 -0.333) *. 6.
</source>
ou pour que Caml lise correctement
<source lang="ocaml">
moyenne3 13.5 (17.0 -. 12.0) -0.333
</source>

==== Fonctions récursives ====

Si on essaie de définir une fonction récursivement :
<source lang="ocaml">
let f n = if (n<1) then 0 else n + f (n-1)
</source>
Caml répond
<source lang="ocaml">
Error: Unbound value f
</source>
car <tt>f</tt> n'est pas présente dans l'environnement.

Pour rajouter <tt>f</tt> comme variable active (sans valeur) et pouvoir faire une définition récursive, il faut utiliser le mot clé <tt>rec</tt> :
<source lang="ocaml">
# let rec f n = if (n<1) then 0 else n + f (n-1);;
val f : int -> int = <fun>
</source>

Les définitions locales peuvent elles aussi être récursives (<tt>let rec ... in ...</tt>) ou mutuellement récursives (<tt>let rec ... and ... in ...</tt>). Elles acceptent également les annotations de type...

==== fonctions d'ordre supérieur ====

TODO

=== Les listes ===

Le type des listes est fondamental en programmation fonctionnelle. D'une certaine manière, on peut dire qu'ils remplacent les tableaux que l'on utilise constamment en programmation impérative.

Exercice : quels sont les différences importantes (utilisation, complexité, mémoire, ...) entre les tableaux et les listes ?

En Caml, une liste est représentée entre crochets, et les éléments sont séparés par des points-virgules :
<source lang="ocaml">
# let une_liste = [ 1 ; 2 ; 2 ; -1 ; 0 ] ;;
val une_liste : int list = [1; 2; 2; -1; 0]
# let une_autre_liste = [ "coucou" ; "je m'appelle" ; "Bob" ] ;;
val une_autre_liste : string list = ["coucou"; "je m'appelle"; "Bob"]
</source>

Comme vous pouvez le voir dans l'exemple au dessus, le type des listes d'entiers s'appelle "<tt>int list</tt>", le type des listes de flottants s'appelle "<tt>float list</tt>" et le type des listes de listes d'entiers s'appelle ... "<tt>int list list</tt>".

Contrairement au cas des tuples, les éléments d'une liste doivent tous avoir le même type :
<source lang="ocaml">
# let une_non_liste = [ 1 ; "Toto" ; 1.3 ] ;;
This expression has type string but is here used with type int
</source>

Attention : quel est le type de la liste suivante ?
<source lang="ocaml">
# let une_liste_bizarre = [ 1 , 2 , 3 ] ;;
</source>

On peut ajouter un élement devant une liste avec l'opérateur "<tt>::</tt>" et la concaténation des listes s'obtient avec l'opérateur "<tt>@</tt>".
<source lang="ocaml">
# 5::[1;2;3;4] ;;
- : int list = [5; 1; 2; 3; 4]
# [-1;-2;-3;-4] @ [1;2;3;4] ;;
- : int list = [-1; -2; -3; -4; 1; 2; 3; 4]
</source>
Attention : la complexité de l'opération "<tt>::</tt>" ne dépend pas de la taille des listes mises en jeux. Par contre, la complexité de l'opération "<tt>@</tt>" dépend proportionnellement de la taille de son premier argument. Il faut donc toujour privilégier "<tt>::</tt>" par rapport à "<tt>@</tt>". En particulier, il est en général mauvais de rajouter des élément en fin de liste en utilisant "<tt>l @ [e]</tt>".

=== Filtrage, première partie : tuples et listes ===

La notion de ''filtrage'', aussi appelé "pattern-matching" est un outils clé pour la programmation en Caml. L'idée est de décomposer une valeur en "sous-valeurs".

==== Filtrage sur les tuples ====

Comme une paire est de la forme <tt>(x,y)</tt>, on peut décomposer une valeur de type <tt>a*b</tt> en deux sous valeurs. Voici un exemple de syntaxe : le code de la fonction <tt>fst</tt> :
<source lang="ocaml">
let premier p = match p with
(x,y) -> x
</source>

Pour évaluer "<tt>premier e</tt>", Caml regarde le premier argument <tt>e</tt> et essaie de faire coïncider "<tt>(x,y)</tt>". S'il y arrive, alors il renvoie la valeur "<tt>x</tt>". Le typage de Caml inférera automatique que "<tt>p</tt>" doit être une paire, et il n'y a donc pas besoin de prévoir un cas par defaut.

On peut maintenant récupérer la deuxième composante d'un triplet de la manière suivante :
<source lang="ocaml">
let second3 t = match t with
(_, y, _) -> y
</source>
Notez l'utilisation de "<tt>_</tt>" pour donner la position d'une sous-valeur qui ne sert à rien.

Toutes les variables présentes dans le ''motif'' (la partie à gauche de la flèche) se retrouvent dans l'environnement avec pour valeur, la sous-valeur appropriée. Attention, ces variables ne se retrouvent dans l'environnement que dans la partie droite de la flèche.
Ces variables remplacent (temporairement) les variables de même nom qui pouvaient se trouver dans l'environnement. Par exemple, la fonction :
<source lang="ocaml">
let f x = match x with
(x,_) -> x
</source>
est exactement la fonction <tt>fst</tt>.

==== Filtrage sur les listes ====

On peut décomposer une liste en deux sous-valeurs :

* le premier élément de la liste,
* la suite de la liste.

Autrement dit, si la liste <tt>l</tt> n'est pas vide, on peut la décomposer en <tt>e::q</tt>. Comme il est possible que la liste <tt>l</tt> soit vide, il y a en fait deux manière de décomposer <tt>l</tt> :

* soit <tt>[]</tt> (sans aucune sous-valeur),
* soit <tt>e::q</tt> (avec deux sous-valeurs).

Par exemple, voici une manière de tester si une liste est vide :
<source lang="ocaml">
let vide l = match l with
[] -> true
| x::xs -> false
</source>
Les différents cas sont séparés par le symbole "<tt>|</tt>".

On peut également décomposer une liste en 3 sous-valeurs : le premier élément, le second élément et la suite de la liste. Dans ce cas, il a trois cas pour une liste arbitraire :

* elle est vide <tt>[]</tt> (aucune sous-valeur),
* elle ne contient qu'une seul élément <tt>[e]</tt> (une sous-valeur),
* elle contient un premier élément, un deuxième élément, et une suite <tt>a::b::q</tt> (trois sous-valeurs).

On peut par exemple écrire :
<source lang="ocaml">
let deux_elements_ou_plus l = match l with
[] -> false
| [a] -> false
| a::b::q -> true
</source>

Comme on peut toujours décomposer une valeur en une sous-valeur (la valeur elle même), on peut toujours avoir un motif de la forme <tt>x</tt>. Toutes les valeurs pourront être décomposées de cette manière, et il faut donc que ce motif soit le dernier. (Sinon, les motifs suivants ne servent à rien...) On parle de motif ''universel''. (On peut utiliser <tt>_</tt> comme motif universel.) Par exemple, on peut réecrire l'exemple précédent :
<source lang="ocaml">
let deux_elements_ou_plus
_::_::_ -> true
| _ -> false
</source>

==== Compléments ====

# On peut ajouter des constantes dans les motifs. Le motif ne sera utilisé que lorsque la sous-valeur correspondantes a la valeurs correspondante. Par exemple, si on modélise les entiers de Gauss (« entiers complexes ») par des paires d'entiers, on peut définir :
<source lang="ocaml">
let imaginaire_pur c = match c with
(0,0) -> false
| (0,_) -> true
| _ -> false
</source>
# On peut grouper des motifs différents pour faire la même chose. Il faut que les variables qui apparaissent dans les motifs soient les mêmes, et qu'elles aient le même type :
<source lang="ocaml">
let f x = match x with
0::l | 1::_::l | 2::_::_::l -> l (* on groupe 3 motifs en une seule ligne *)
| [] -> []
| x::_ -> [x]
</source>
# on peut « garder » les motifs" par une condition avec le mot clé "<tt>when</tt>"
<source lang="ocaml">
let g x = match x with
x::xs when (List.lenght (f xs) = 1) -> true
| _ -> false
</source>
Attention dans le cas où vous utilisez <tt>when</tt> : il est conseillé de terminer votre filtrage avec un motif universel pour être sûr que vous n'avez pas oublié de cas.
# comme on définit souvent des fonctions par filtrage, Caml autorise la syntaxe
<source lang="ocaml">
function
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
plutôt que
<source lang="ocaml">
fun x -> match x with
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
Remarquez que l'on ne peut faire ça que pour une fonction à une seule variable...
# fonction par filtrage : s'il n'y a qu'un seul motif, on peut alors utiliser le mot clé "<tt>fun</tt>" habituel, ce qui permet la définition d'une fonction à plusieurs arguments. (Mais dans ce cas, les parenthèses autour des tuples sont obligatoires.)
<source lang="ocaml">
# let h = fun (x,y) z (u,v,w) -> x+y+z+v ;;
val h : int * int -> int -> 'a * int * 'b -> int = <fun>
</source>

=== Le polymorphisme ===

=== Transparence référentielle ===

==== Les types algébriques ====

On peut défnir un synomnyme de type avec le mot clef <tt>type</tt>
Exemple :
<source lang="ocaml">type point = float*float</source>

==== Types énumérés ====

On donne tous les éléments du type
Exemple :
<source lang="ocaml">type jours = Lundi | Mardi | Mercredi | ...</source>

Type avec 7 éléments. Les éléments commencent forcément par une majuscule.

On peut comparer des éléments avec "=", "<" et ">" (< et > sont à éviter, il vaut mieux
écrire une fonction pour comparer) On peut aussi faire du filtrage.

Exemple:
<source lang="ocaml">
let week_end j = match j with
Samedi -> true
| Dimanche -> true
| _ -> false
</source>

==== Construction de types paramètres ====

Exemple : type des transformations de l'espace avec :
- Translation
- Rotation
- Symetrie
On aura alors des constructeurs avec des paramètres :

<source lang="ocaml">
type transformation =
Rotation of int*point
| Translation of point
| SymCentrale of point
| Homothetie of float*point
</source>

On n'a pas donné explicitement tous les éléments, mais on les a donné implicitement.
Exemple :
<source lang="ocaml">
let rien = Translation (0.0,0.0)
</source>
Autre exemple :
<source lang="ocaml">
let fait quelquechose t=
match t with
Rotation(a, (x, y)− > a mod360! = 0
|T ranslation(x, y)− > x! = 0.0 && y! = 0.0
|SymCentrale(x, y)− > true
|Homotetie(x, (−, −))− > r! = 1, 0
</source>

=== Les types récursifs ===

En Caml
<source lang="ocaml">
type node = Node of int*node
| Vide
</source>
exemple d'éléments de "node" :
- Vide
- Node(0,Vide)
- Node(1,Node(2,Node(3, Vide)))

Le type "node" est un type récursif. Comme les fonctions récursivent doivent avoir des cas
de base, les types récursifs doivent avoir des constructeurs "de base" (non récursifs). On peut
comparer des éléments avec "=". On peut aussi utiliser le filtrage.

Exemple :
<source lang="ocaml">
let rec taille l = match l with
Vide -> 0
|Node(_,l)->1+taille l
</source>

La fonction taille sur les listes Caml suit le même schéma avec les abréviations Caml.
<source lang="ocaml">
let rec taille l = match l with
[]->0
| a ::l->1+taille
</source>
Ceci explique la différence entre :: (constructeur) et @ (fonction récursive)

Exemple de type récursif, les arbres binaires :
<source lang="ocaml">
type bin = Vide | Noeud of int*bin*bin
</source>
arbre naire :
<source lang="ocaml">
type arbre n_aire =
Vide|Node of int ∗ (arbre_naire list)(bancal)
</source>

== Les structures ==

== La récursivité terminale ==

== Les exceptions ==

== Aspects impératifs dans Caml ==

== Les modules ==

INFO421 : Programmation fonctionnelle

2013-02-12T18:36:26Z

Lachand : /* Types énumérés */

Ce wiki est un complément de cours pour le cours « info-421 : programmation fonctionnelle ». La participation au wiki est fortement encouragée, et deviendra peut-être obligatoire...

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Je vous conseille d'aller voir [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

== Détails techniques ==

=== Compléments de cours, TD et TP ===

==== Installer Ocaml ====

Si vous voulez installer OCaml sur votre ordinateur :

* Sous Linux : c'est la solution idéale. Il existe probablement des paquets pour votre distribution. Pour Ubuntu, pour avoir un environnement similaire à ce que vous aurez dans les salles informatiques, installez les paquets <tt>ocaml</tt>, <tt>ocaml-core</tt>, <tt>ocaml-mode</tt>, <tt>tuareg-mode</tt> et <tt>emacs</tt>.
* Sous MacOS : il semblerait qu'il y ait des paquets MacPorts pour <tt>ocaml</tt>, <tt>emacs</tt> et <tt>tuareg-mode.el</tt>.
* Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : [http://deptinfo.unice.fr/~roy/CAML/Win/install-win.html Installation de OCaml (sur Windows XP)]. Je n'ai malheureusement (??) pas accès à une machine avec Windows (98/2000/XP/Vista/7), je ne pourrais donc pas beaucoup vous aider.

Contactez moi si vous avez des problèmes.

Pour les exemples simples, vous pouvez aussi utiliser [http://try.ocamlpro.com/ OCaml en ligne]

==== Références supplémentaires ====

* Le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : [http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/ Développement d'applications avec Ocaml]. (Ce livre utilise une vieille version de Ocaml, mais reste pertinent.)
* La documentation de Caml, version 3.09 (utilisé en TP) : [http://caml.inria.fr/pub/docs/manual-ocaml-309/ Documentation and user's manual].
* Le livre de Jason Hickey [http://files.metaprl.org/doc/ocaml-book.pdf Introduction to Objective Caml] (en anglais).

==== Cours ====

==== TD et TP ====

* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/1213/info421/td1.pdf TD1 : premières expressions en Caml (pdf)]

== Introduction ==

Pour paraphraser un collègue dont je ne retrouve pas le nom :

<blockquote>
''Attention :'' il ne s'agit pas d'un cours de programmation fonctionelle
</blockquote>

Il s'agit plutôt d'un cours de programmation '''fonctionnelle'''...

=== Petit historique censuré ===

Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)

D'après [http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm ce site], qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

* années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à ''porter''. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
* FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
* LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
* ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
* Pascal (1975).
* C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
* Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
* ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
* Smalltalk (fin des année 1983), début de la programmation objet.
* 1983 : ADA.
* année '80 : Caml (1987), puis CamlLight(1990), puis OCaml(1996), développé
à l'INRIA. (Dernière version en octobre 2012.)
* années '90 : Python (version 1.0 en 1994).
* années '90 : PHP (version 1.0 en 1995).
* années '90 : Java (version 1.0 en 1996).

Je vous conseille d'aller voir le graphique suivant : [http://www.levenez.com/lang/lang.pdf Computer Languages Timeline] (ou [http://www.levenez.com/lang/redirect_lang_a4_pdf.html découpé en pages A4]).

=== Fonctionnel ?? ===

L'adjectif ''fonctionnel'' a au moins deux sens :

# qui fonctionne, en état de marche,
# qui se rapporte aux fonctions.

Les langages fonctionnels sont bien entendus ''fonctionnels'' dans le premier sens, mais c'est surtout le second sens qui nous intéresse. Les langages tels que Pascal, Ada ou C sont qualifié, par opposition, d''''impératifs'''''.

Un des slogans de la programmation fonctionnelle en général est

<blockquote>
''Les fonctions sont des valeurs comme les autres''
</blockquote>

et c'est de là que vient la terminologie... En particulier, il n'y a pas de différence entre les ''instructions'' (qui ont un effet) et les ''expressions'' (qui ont une valeur). Par exemple, en Python,

<pre>
x = x+1
</pre>

ou

<pre>
if delta < 0:
print("Il n'y a pas de solution")
</pre>

sont des ''instructions'' : on ne peut pas les mettre dans une variable.

Comme nous le verront, cela a des conséquences sur l'expressivité du langage et la manière de programmer.

=== Le langage (O)Caml ===

Le langage OCaml est développé par l'INRIA (Institut national de recherche en informatique et automatique). C'est un successeur de CamlLight.

Le nom Caml est formé des initiales de "Categorical Abstract Machine Language", et le langage lui même appartient à la famille de ML ("Meta Language"). C'est un langage fonctionnel ''strict'' (nous verrons ce que cela veut dire), statiquement typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :

* fonctionnel bien sûr,
* mais aussi impératif,
* objet également (c'est le « O » de OCaml).

Dans ce cours, nous utiliserons principalement le style fonctionnel, et un peu le style impératif en fin de semestre.

Voici quelques aspects importants du langages que nous essayeront d'aborder pendant le cours :

* fonctions comme valeurs,
* types de données ''algébriques''
* polymorphisme,
* système d'exceptions,
* support pour des références et des données mutables (programmation « impure »),
* système de modules et de foncteurs,
* ...

La notion de ''récursivité'' sera fondamentale pendant toute la durée du cours...

Un aspect intéressant du langage est que c'est :

* un langage interprété (avec l'interpréteur OCaml),
* soit un langage compilé en bytecode (code binaire indépendant de l'architecture),
* soit un langage compilé optimisé en binaire (dépendant de l'architecture).

=== Autres langages fonctionnels ===

Il existe de nombreux autres langages fonctionnels. Par exemple :

* SML (Standard ML) : [http://en.wikipedia.org/wiki/Standard_ML Wikipedia], autre dialecte de la famille ML.
* LISP, dont les deux dialectes principaux sont :
** Common LISP : [http://en.wikipedia.org/wiki/Common_LISP Wikipedia],
** Scheme : [http://en.wikipedia.org/wiki/Scheme_%28programming_language%29 Wikipedia].
* Haskell : [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Wikipedia] (inspiré en grande partie de [http://en.wikipedia.org/wiki/Miranda_%28programming_language%29 Miranda]).

Plusieurs langages impératifs intègrent maintenant des aspects propres des langages fonctionnels : Python, Scala, ...

=== Applications concrètes ===

Voici quelques exemples de logiciels développés en OCaml :

* [http://ocsigen.org/ Ocsigen], un serveur web,
* [http://www.cis.upenn.edu/~bcpierce/unison/ Unison], un logiciel de synchronisation de fichiers entre ordinateurs,
* [http://mldonkey.sourceforge.net/Main_Page MLDonkey], un logiciel de Peer-to-peer multiréseaux,
* [http://pauillac.inria.fr/advi/ Active DVI] un visualisateur pour le format de fichier DVI,
* analyse de programmes critiques : [http://www.astree.ens.fr/ Astrée],
* informatique financiere : [http://www.janestreet.com Janestreet Capital] et [http://www.lexifi.com Lexifi].

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang ([http://fr.wikipedia.org/wiki/Erlang_%28langage%29 Wikipedia]), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

=== Objectifs du cours ===

# être capable de définir des fonctions récursives, et comprendre ce qu'elles font
# comprendre le typage, les types algébriques et le polymorphisme à la ML
# pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
# être capable de décomposer un problème
# commencer à réfléchir à la complexité de vos programmes

== Premiers pas en Caml ==

Un des slogans de la programmation fonctionnelle est ''tout est une valeur, ou plus précisément,

<blockquote>
''Toute expression a une valeur.''
</blockquote>

Cette idée n'est pas présente en Python où l'on distingue les ''expressions'' ("<tt>3*x+f(2)</tt>" par exemple) et les ''instructions'' ("<tt>if n>22: a=12 else: a=13</tt>" par exemple). En Python, les instructions sont en général séparées par des retours à la ligne et sont ''exécutées'' en séquence. Les expressions sont juste calculées, et ne peuvent pas être séquentialisées.

Dans un langage purement fonctionnel, le "<tt>;</tt>" n'existe pas, et il n'y a que des valeurs...

Les valeurs sont formées en utilisant :

* les fonctions du langage (addition, multiplication, opérateurs logiques),
* des constructions du langage (<tt>if ... then ... else ...</tt> par exemple),
* les relations mathématiques (égalité, plus grand), ... qui sont juste des fonctions renvoyant des booléens,
* les constantes du langage,
* les variables de l'environnement,
* ''les valeurs (en particulier les fonctions) définies par le programmeur''.

Bien entendu, comme Caml est typé, il faut respecter les types.

=== Les types atomiques ===

Caml (et les autres langages fonctionnels typés) possèdent plusieurs types de base tels que :

* les booléens : type <tt>bool</tt> (valeur <tt>true</tt> et <tt>false</tt>) et les opérations <tt>not</tt>, <tt>&&</tt> (et) et <tt>||</tt> (ou).
* Les entiers : type <tt>int</tt> pour les entiers signés compris entre <math>-230</math> et <math>230-1</math>. (Les entiers Caml sont stockés sur 31 bits...) Les opérations associés sont <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, <tt>/</tt> (pour la division entière) et <tt>mod</tt> (pour le modulo).
* Les flottants : type <tt>float</tt> pour les réels en virgule flottante. Les opérations usuelles sont <tt>+.</tt>, <tt>-.</tt>, <tt>*.</tt> et <tt>/.</tt>.
* Les caractères : type <tt>char</tt> (notés entre guillemets simples).
* Le type unité : type <tt>unit</tt>, dont l'unique valeur est <tt>()</tt>. (Nous verrons que ce type a une utilité...)

Même s'il ne s'agit pas vraiment d'un type atomique, nous pouvons également ajouter le type des chaînes de caractères : type <tt>string</tt> (notées entre guillemets doubles).

<source lang="ocaml">
(* exemples ... *)
</source>

'''Remarques :''' les opérations booléennes ("<tt>&&</tt>" pour le « et » et "<tt>||</tt>" pour le « ou ») fonctionnent de à gauche à droite, et l'argument de droite n'est évalué que si c'est nécessaire. Par exemple <tt>true || (0 = 1/0)</tt> donne la valeur <tt>true</tt>, alors que que <tt>false || (0=1/0)</tt> lève l'exception <tt>Division_by_zero</tt>.

=== définitions et environnement ===

Comme tous les langages de programmation, Caml garde en mémoire une liste de définitions. Chacune de ces définitions met en relation un nom ("<tt>x</tt>", "<tt>n</tt>", "<tt>length</tt>", ...) et une valeur ("<tt>3.7</tt>", "<tt>42</tt>", "<tt>fun s -> ...</tt>").

Lorsque l'on lance Caml, l'environnement contient déjà de nombreuse fonctions prédéfinies : <tt>max</tt>, <tt>min</tt>, <tt>mod</tt>, <tt>+</tt>, <tt>float_of_int</tt>, ...

Certaines des variables de l'environnement correspondent à des paramètres de fonction en cours de définition. Ces variables n'ont pas de valeur, mais seulement un type.

==== Environnement ====

* Liste de paires <tt>nom</tt> / <tt>valeur</tt>,
* une nouvelle definition remplace la précédente mais ne l'efface pas, (on ne met pas une valeur à jours)

==== Définitions ====

L'utilisateur peut rajouter des définitions dans l'environnement grâce au mot clé <tt>let</tt>

* <tt>let nom = expr</tt> permet de rajouter une définition simple dans l'environnement. Exemple : <tt>let n = 42</tt>
* <tt>let nom1 = expr1 and nom2 = expr2</tt> permet de rajouter plusieurs définitions simultanément. Exemple : <tt>let a=1 and b=2</tt>
* <tt>let rec nom1 = expr1 and nom2 = expr2</tt> permet de rajouter des définitions mutuellement récursives.

On peut toujours annoter la définition de types de données. Ceci évite à Caml d'avoir à deviner le type que l'on souhaite et permet de préciser la fonction :
<source lang="ocaml">
let n:int = 42
let rec f (n:int) : string = if (n<1) then "" else "*" ^ (f (n-1))
</source>

Si une définition utilise le même nom qu'une définition précédente, la nouvelle définition écrase l'ancienne. Par exemple :
<source lang="ocaml">
# let n=42 ;;
val n : int = 42
# let n=3.1415 ;;
val n : float = 3.1415
# n ;;

* : float = 3.1415
</source>

==== Définitions locales ====

Il est possible de modifier l'environnement de manière temporaire (''locale''). On utilise alors <tt>let nom = expr1 in expr2</tt>. Ceci ajoute la définition <tt>nom = expr1</tt> dans l'environnement, mais seulement pour l'évaluation de l'expression <tt>expr2</tt>.
<source lang="ocaml">
# let x =
let y = 42 in
y/2 ;;
val x : int = 21
# x ;;

* : int = 21
# y ;;
Unbound value y
</source>

=== Les fonctions ===

Caml utilise la notation mathématique pour écrire les types des fonctions. Si <tt>f</tt> est une fonction avec un seul argument de type <tt>string</tt> et dont la valeur de retour est de type <tt>int</tt> (la fonction <tt>length</tt> par exemple), le type de <tt>f</tt> est noté <tt>string -> int</tt>. Dans l'interprète Caml :
<source lang="ocaml">
# String.length ;;

* : string -> int = <fun>
</source>
Nous indique que la fonction <tt>length</tt> est bien de type <tt>string->int</tt>.

Une fonction est définie comme une variable avec un <tt>let</tt> et en utilisant le mot clé <tt>fun</tt> :
<source lang="ocaml">
# let f = fun n -> n+1;;
val f : int -> int = <fun>
# let racine = fun n -> int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
</source>

Une fonction avec plusieurs argument est définie de la même manière avec
<source lang="ocaml">
# let moyenne3 = fun x y z -> (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Le type d'une fonction à plusieurs argument est noté en mettant plusieurs types à gauche de la flèche <tt>-></tt>, comme ci dessus : <tt>type_arg1 -> type_arg2 -> type_arg3 -> type_resultat</tt>.

'''Remarques :'''

* notez l'absence de mot clé <tt>return</tt> et l'absence de virgules pour séparer les différents arguments !
* Le mot clé <tt>fun</tt> permet de définir des fonctions sans leur donner de nom, ce qui n'est pas possible dans les langages comme C ou Java...

On peut également utiliser un raccourci pour définir une fonction sans utiliser le mot clé <tt>fun</tt> : il suffit de mettre les arguments de la fonction avant le signe égal :
<source lang="ocaml">
# let f n = n+1;;
val f : int -> int = <fun>
# let racine n = int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
# let moyenne3 x y z = (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Pour appliquer une fonction à des arguments, on écrit simplement
<source lang="ocaml">
moyenne3 13.5 17.0 -0.333
</source>
Il n'y a ni parenthèse, ni virgule. Les parenthèses peuvent cependant être nécessaires pour différencier
<source lang="ocaml">
moyenne3 13.5 17.0 (-0.333 *. 6.)
</source>
et
<source lang="ocaml">
(moyenne3 13.5 17.0 -0.333) *. 6.
</source>
ou pour que Caml lise correctement
<source lang="ocaml">
moyenne3 13.5 (17.0 -. 12.0) -0.333
</source>

==== Fonctions récursives ====

Si on essaie de définir une fonction récursivement :
<source lang="ocaml">
let f n = if (n<1) then 0 else n + f (n-1)
</source>
Caml répond
<source lang="ocaml">
Error: Unbound value f
</source>
car <tt>f</tt> n'est pas présente dans l'environnement.

Pour rajouter <tt>f</tt> comme variable active (sans valeur) et pouvoir faire une définition récursive, il faut utiliser le mot clé <tt>rec</tt> :
<source lang="ocaml">
# let rec f n = if (n<1) then 0 else n + f (n-1);;
val f : int -> int = <fun>
</source>

Les définitions locales peuvent elles aussi être récursives (<tt>let rec ... in ...</tt>) ou mutuellement récursives (<tt>let rec ... and ... in ...</tt>). Elles acceptent également les annotations de type...

==== fonctions d'ordre supérieur ====

TODO

=== Les listes ===

Le type des listes est fondamental en programmation fonctionnelle. D'une certaine manière, on peut dire qu'ils remplacent les tableaux que l'on utilise constamment en programmation impérative.

Exercice : quels sont les différences importantes (utilisation, complexité, mémoire, ...) entre les tableaux et les listes ?

En Caml, une liste est représentée entre crochets, et les éléments sont séparés par des points-virgules :
<source lang="ocaml">
# let une_liste = [ 1 ; 2 ; 2 ; -1 ; 0 ] ;;
val une_liste : int list = [1; 2; 2; -1; 0]
# let une_autre_liste = [ "coucou" ; "je m'appelle" ; "Bob" ] ;;
val une_autre_liste : string list = ["coucou"; "je m'appelle"; "Bob"]
</source>

Comme vous pouvez le voir dans l'exemple au dessus, le type des listes d'entiers s'appelle "<tt>int list</tt>", le type des listes de flottants s'appelle "<tt>float list</tt>" et le type des listes de listes d'entiers s'appelle ... "<tt>int list list</tt>".

Contrairement au cas des tuples, les éléments d'une liste doivent tous avoir le même type :
<source lang="ocaml">
# let une_non_liste = [ 1 ; "Toto" ; 1.3 ] ;;
This expression has type string but is here used with type int
</source>

Attention : quel est le type de la liste suivante ?
<source lang="ocaml">
# let une_liste_bizarre = [ 1 , 2 , 3 ] ;;
</source>

On peut ajouter un élement devant une liste avec l'opérateur "<tt>::</tt>" et la concaténation des listes s'obtient avec l'opérateur "<tt>@</tt>".
<source lang="ocaml">
# 5::[1;2;3;4] ;;
- : int list = [5; 1; 2; 3; 4]
# [-1;-2;-3;-4] @ [1;2;3;4] ;;
- : int list = [-1; -2; -3; -4; 1; 2; 3; 4]
</source>
Attention : la complexité de l'opération "<tt>::</tt>" ne dépend pas de la taille des listes mises en jeux. Par contre, la complexité de l'opération "<tt>@</tt>" dépend proportionnellement de la taille de son premier argument. Il faut donc toujour privilégier "<tt>::</tt>" par rapport à "<tt>@</tt>". En particulier, il est en général mauvais de rajouter des élément en fin de liste en utilisant "<tt>l @ [e]</tt>".

=== Filtrage, première partie : tuples et listes ===

La notion de ''filtrage'', aussi appelé "pattern-matching" est un outils clé pour la programmation en Caml. L'idée est de décomposer une valeur en "sous-valeurs".

==== Filtrage sur les tuples ====

Comme une paire est de la forme <tt>(x,y)</tt>, on peut décomposer une valeur de type <tt>a*b</tt> en deux sous valeurs. Voici un exemple de syntaxe : le code de la fonction <tt>fst</tt> :
<source lang="ocaml">
let premier p = match p with
(x,y) -> x
</source>

Pour évaluer "<tt>premier e</tt>", Caml regarde le premier argument <tt>e</tt> et essaie de faire coïncider "<tt>(x,y)</tt>". S'il y arrive, alors il renvoie la valeur "<tt>x</tt>". Le typage de Caml inférera automatique que "<tt>p</tt>" doit être une paire, et il n'y a donc pas besoin de prévoir un cas par defaut.

On peut maintenant récupérer la deuxième composante d'un triplet de la manière suivante :
<source lang="ocaml">
let second3 t = match t with
(_, y, _) -> y
</source>
Notez l'utilisation de "<tt>_</tt>" pour donner la position d'une sous-valeur qui ne sert à rien.

Toutes les variables présentes dans le ''motif'' (la partie à gauche de la flèche) se retrouvent dans l'environnement avec pour valeur, la sous-valeur appropriée. Attention, ces variables ne se retrouvent dans l'environnement que dans la partie droite de la flèche.
Ces variables remplacent (temporairement) les variables de même nom qui pouvaient se trouver dans l'environnement. Par exemple, la fonction :
<source lang="ocaml">
let f x = match x with
(x,_) -> x
</source>
est exactement la fonction <tt>fst</tt>.

==== Filtrage sur les listes ====

On peut décomposer une liste en deux sous-valeurs :

* le premier élément de la liste,
* la suite de la liste.

Autrement dit, si la liste <tt>l</tt> n'est pas vide, on peut la décomposer en <tt>e::q</tt>. Comme il est possible que la liste <tt>l</tt> soit vide, il y a en fait deux manière de décomposer <tt>l</tt> :

* soit <tt>[]</tt> (sans aucune sous-valeur),
* soit <tt>e::q</tt> (avec deux sous-valeurs).

Par exemple, voici une manière de tester si une liste est vide :
<source lang="ocaml">
let vide l = match l with
[] -> true
| x::xs -> false
</source>
Les différents cas sont séparés par le symbole "<tt>|</tt>".

On peut également décomposer une liste en 3 sous-valeurs : le premier élément, le second élément et la suite de la liste. Dans ce cas, il a trois cas pour une liste arbitraire :

* elle est vide <tt>[]</tt> (aucune sous-valeur),
* elle ne contient qu'une seul élément <tt>[e]</tt> (une sous-valeur),
* elle contient un premier élément, un deuxième élément, et une suite <tt>a::b::q</tt> (trois sous-valeurs).

On peut par exemple écrire :
<source lang="ocaml">
let deux_elements_ou_plus l = match l with
[] -> false
| [a] -> false
| a::b::q -> true
</source>

Comme on peut toujours décomposer une valeur en une sous-valeur (la valeur elle même), on peut toujours avoir un motif de la forme <tt>x</tt>. Toutes les valeurs pourront être décomposées de cette manière, et il faut donc que ce motif soit le dernier. (Sinon, les motifs suivants ne servent à rien...) On parle de motif ''universel''. (On peut utiliser <tt>_</tt> comme motif universel.) Par exemple, on peut réecrire l'exemple précédent :
<source lang="ocaml">
let deux_elements_ou_plus
_::_::_ -> true
| _ -> false
</source>

==== Compléments ====

# On peut ajouter des constantes dans les motifs. Le motif ne sera utilisé que lorsque la sous-valeur correspondantes a la valeurs correspondante. Par exemple, si on modélise les entiers de Gauss (« entiers complexes ») par des paires d'entiers, on peut définir :
<source lang="ocaml">
let imaginaire_pur c = match c with
(0,0) -> false
| (0,_) -> true
| _ -> false
</source>
# On peut grouper des motifs différents pour faire la même chose. Il faut que les variables qui apparaissent dans les motifs soient les mêmes, et qu'elles aient le même type :
<source lang="ocaml">
let f x = match x with
0::l | 1::_::l | 2::_::_::l -> l (* on groupe 3 motifs en une seule ligne *)
| [] -> []
| x::_ -> [x]
</source>
# on peut « garder » les motifs" par une condition avec le mot clé "<tt>when</tt>"
<source lang="ocaml">
let g x = match x with
x::xs when (List.lenght (f xs) = 1) -> true
| _ -> false
</source>
Attention dans le cas où vous utilisez <tt>when</tt> : il est conseillé de terminer votre filtrage avec un motif universel pour être sûr que vous n'avez pas oublié de cas.
# comme on définit souvent des fonctions par filtrage, Caml autorise la syntaxe
<source lang="ocaml">
function
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
plutôt que
<source lang="ocaml">
fun x -> match x with
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
Remarquez que l'on ne peut faire ça que pour une fonction à une seule variable...
# fonction par filtrage : s'il n'y a qu'un seul motif, on peut alors utiliser le mot clé "<tt>fun</tt>" habituel, ce qui permet la définition d'une fonction à plusieurs arguments. (Mais dans ce cas, les parenthèses autour des tuples sont obligatoires.)
<source lang="ocaml">
# let h = fun (x,y) z (u,v,w) -> x+y+z+v ;;
val h : int * int -> int -> 'a * int * 'b -> int = <fun>
</source>

=== Le polymorphisme ===

=== Transparence référentielle ===

==== Les types algébriques ====

On peut défnir un synomnyme de type avec le mot clef <tt>type</tt>
Exemple :
<source lang="ocaml">type point = float*float</source>

==== Types énumérés ====

On donne tous les éléments du type
Exemple :
<source lang="ocaml">type jours = Lundi | Mardi | Mercredi | ...</source>

Type avec 7 éléments. Les éléments commencent forcément par une majuscule.

On peut comparer des éléments avec "=", "<" et ">" (< et > sont à éviter, il vaut mieux
écrire une fonction pour comparer) On peut aussi faire du filtrage.

Exemple:
<source lang="ocaml">
let week_end j = match j with
Samedi -> true
| Dimanche -> true
| _ -> false
</source>

=== Construction de types paramètres ===

Exemple : type des transformations de l'espace avec :
- Translation
- Rotation
- Symetrie
On aura alors des constructeurs avec des paramètres :

<source lang="ocaml">
type transformation =
Rotation of int*point
| Translation of point
| SymCentrale of point
| Homothetie of float*point
</source>

On n'a pas donné explicitement tous les éléments, mais on les a donné implicitement.
Exemple :
<source lang="ocaml">
let rien = Translation (0.0,0.0)
</source>
Autre exemple :
<source lang="ocaml">
let fait quelquechose t=
match t with
Rotation(a, (x, y)− > a mod360! = 0
|T ranslation(x, y)− > x! = 0.0 && y! = 0.0
|SymCentrale(x, y)− > true
|Homotetie(x, (−, −))− > r! = 1, 0
</source>

=== Les types récursifs ===

En Caml
<source lang="ocaml">
type node = Node of int*node
| Vide
</source>
exemple d'éléments de "node" :
- Vide
- Node(0,Vide)
- Node(1,Node(2,Node(3, Vide)))

Le type "node" est un type récursif. Comme les fonctions récursivent doivent avoir des cas
de base, les types récursifs doivent avoir des constructeurs "de base" (non récursifs). On peut
comparer des éléments avec "=". On peut aussi utiliser le filtrage.

Exemple :
<source lang="ocaml">
let rec taille l = match l with
Vide -> 0
|Node(_,l)->1+taille l
</source>

La fonction taille sur les listes Caml suit le même schéma avec les abréviations Caml.
<source lang="ocaml">
let rec taille l = match l with
[]->0
| a ::l->1+taille
</source>
Ceci explique la différence entre :: (constructeur) et @ (fonction récursive)

Exemple de type récursif, les arbres binaires :
<source lang="ocaml">
type bin = Vide | Noeud of int*bin*bin
</source>
arbre naire :
<source lang="ocaml">
type arbre n_aire =
Vide|Node of int ∗ (arbre_naire list)(bancal)
</source>

== Les structures ==

== La récursivité terminale ==

== Les exceptions ==

== Aspects impératifs dans Caml ==

== Les modules ==

INFO421 : Programmation fonctionnelle

2013-02-12T18:36:12Z

Lachand : /* Les types algébriques */

Ce wiki est un complément de cours pour le cours « info-421 : programmation fonctionnelle ». La participation au wiki est fortement encouragée, et deviendra peut-être obligatoire...

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Je vous conseille d'aller voir [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

== Détails techniques ==

=== Compléments de cours, TD et TP ===

==== Installer Ocaml ====

Si vous voulez installer OCaml sur votre ordinateur :

* Sous Linux : c'est la solution idéale. Il existe probablement des paquets pour votre distribution. Pour Ubuntu, pour avoir un environnement similaire à ce que vous aurez dans les salles informatiques, installez les paquets <tt>ocaml</tt>, <tt>ocaml-core</tt>, <tt>ocaml-mode</tt>, <tt>tuareg-mode</tt> et <tt>emacs</tt>.
* Sous MacOS : il semblerait qu'il y ait des paquets MacPorts pour <tt>ocaml</tt>, <tt>emacs</tt> et <tt>tuareg-mode.el</tt>.
* Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : [http://deptinfo.unice.fr/~roy/CAML/Win/install-win.html Installation de OCaml (sur Windows XP)]. Je n'ai malheureusement (??) pas accès à une machine avec Windows (98/2000/XP/Vista/7), je ne pourrais donc pas beaucoup vous aider.

Contactez moi si vous avez des problèmes.

Pour les exemples simples, vous pouvez aussi utiliser [http://try.ocamlpro.com/ OCaml en ligne]

==== Références supplémentaires ====

* Le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : [http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/ Développement d'applications avec Ocaml]. (Ce livre utilise une vieille version de Ocaml, mais reste pertinent.)
* La documentation de Caml, version 3.09 (utilisé en TP) : [http://caml.inria.fr/pub/docs/manual-ocaml-309/ Documentation and user's manual].
* Le livre de Jason Hickey [http://files.metaprl.org/doc/ocaml-book.pdf Introduction to Objective Caml] (en anglais).

==== Cours ====

==== TD et TP ====

* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/1213/info421/td1.pdf TD1 : premières expressions en Caml (pdf)]

== Introduction ==

Pour paraphraser un collègue dont je ne retrouve pas le nom :

<blockquote>
''Attention :'' il ne s'agit pas d'un cours de programmation fonctionelle
</blockquote>

Il s'agit plutôt d'un cours de programmation '''fonctionnelle'''...

=== Petit historique censuré ===

Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)

D'après [http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm ce site], qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

* années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à ''porter''. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
* FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
* LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
* ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
* Pascal (1975).
* C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
* Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
* ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
* Smalltalk (fin des année 1983), début de la programmation objet.
* 1983 : ADA.
* année '80 : Caml (1987), puis CamlLight(1990), puis OCaml(1996), développé
à l'INRIA. (Dernière version en octobre 2012.)
* années '90 : Python (version 1.0 en 1994).
* années '90 : PHP (version 1.0 en 1995).
* années '90 : Java (version 1.0 en 1996).

Je vous conseille d'aller voir le graphique suivant : [http://www.levenez.com/lang/lang.pdf Computer Languages Timeline] (ou [http://www.levenez.com/lang/redirect_lang_a4_pdf.html découpé en pages A4]).

=== Fonctionnel ?? ===

L'adjectif ''fonctionnel'' a au moins deux sens :

# qui fonctionne, en état de marche,
# qui se rapporte aux fonctions.

Les langages fonctionnels sont bien entendus ''fonctionnels'' dans le premier sens, mais c'est surtout le second sens qui nous intéresse. Les langages tels que Pascal, Ada ou C sont qualifié, par opposition, d''''impératifs'''''.

Un des slogans de la programmation fonctionnelle en général est

<blockquote>
''Les fonctions sont des valeurs comme les autres''
</blockquote>

et c'est de là que vient la terminologie... En particulier, il n'y a pas de différence entre les ''instructions'' (qui ont un effet) et les ''expressions'' (qui ont une valeur). Par exemple, en Python,

<pre>
x = x+1
</pre>

ou

<pre>
if delta < 0:
print("Il n'y a pas de solution")
</pre>

sont des ''instructions'' : on ne peut pas les mettre dans une variable.

Comme nous le verront, cela a des conséquences sur l'expressivité du langage et la manière de programmer.

=== Le langage (O)Caml ===

Le langage OCaml est développé par l'INRIA (Institut national de recherche en informatique et automatique). C'est un successeur de CamlLight.

Le nom Caml est formé des initiales de "Categorical Abstract Machine Language", et le langage lui même appartient à la famille de ML ("Meta Language"). C'est un langage fonctionnel ''strict'' (nous verrons ce que cela veut dire), statiquement typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :

* fonctionnel bien sûr,
* mais aussi impératif,
* objet également (c'est le « O » de OCaml).

Dans ce cours, nous utiliserons principalement le style fonctionnel, et un peu le style impératif en fin de semestre.

Voici quelques aspects importants du langages que nous essayeront d'aborder pendant le cours :

* fonctions comme valeurs,
* types de données ''algébriques''
* polymorphisme,
* système d'exceptions,
* support pour des références et des données mutables (programmation « impure »),
* système de modules et de foncteurs,
* ...

La notion de ''récursivité'' sera fondamentale pendant toute la durée du cours...

Un aspect intéressant du langage est que c'est :

* un langage interprété (avec l'interpréteur OCaml),
* soit un langage compilé en bytecode (code binaire indépendant de l'architecture),
* soit un langage compilé optimisé en binaire (dépendant de l'architecture).

=== Autres langages fonctionnels ===

Il existe de nombreux autres langages fonctionnels. Par exemple :

* SML (Standard ML) : [http://en.wikipedia.org/wiki/Standard_ML Wikipedia], autre dialecte de la famille ML.
* LISP, dont les deux dialectes principaux sont :
** Common LISP : [http://en.wikipedia.org/wiki/Common_LISP Wikipedia],
** Scheme : [http://en.wikipedia.org/wiki/Scheme_%28programming_language%29 Wikipedia].
* Haskell : [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Wikipedia] (inspiré en grande partie de [http://en.wikipedia.org/wiki/Miranda_%28programming_language%29 Miranda]).

Plusieurs langages impératifs intègrent maintenant des aspects propres des langages fonctionnels : Python, Scala, ...

=== Applications concrètes ===

Voici quelques exemples de logiciels développés en OCaml :

* [http://ocsigen.org/ Ocsigen], un serveur web,
* [http://www.cis.upenn.edu/~bcpierce/unison/ Unison], un logiciel de synchronisation de fichiers entre ordinateurs,
* [http://mldonkey.sourceforge.net/Main_Page MLDonkey], un logiciel de Peer-to-peer multiréseaux,
* [http://pauillac.inria.fr/advi/ Active DVI] un visualisateur pour le format de fichier DVI,
* analyse de programmes critiques : [http://www.astree.ens.fr/ Astrée],
* informatique financiere : [http://www.janestreet.com Janestreet Capital] et [http://www.lexifi.com Lexifi].

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang ([http://fr.wikipedia.org/wiki/Erlang_%28langage%29 Wikipedia]), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

=== Objectifs du cours ===

# être capable de définir des fonctions récursives, et comprendre ce qu'elles font
# comprendre le typage, les types algébriques et le polymorphisme à la ML
# pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
# être capable de décomposer un problème
# commencer à réfléchir à la complexité de vos programmes

== Premiers pas en Caml ==

Un des slogans de la programmation fonctionnelle est ''tout est une valeur, ou plus précisément,

<blockquote>
''Toute expression a une valeur.''
</blockquote>

Cette idée n'est pas présente en Python où l'on distingue les ''expressions'' ("<tt>3*x+f(2)</tt>" par exemple) et les ''instructions'' ("<tt>if n>22: a=12 else: a=13</tt>" par exemple). En Python, les instructions sont en général séparées par des retours à la ligne et sont ''exécutées'' en séquence. Les expressions sont juste calculées, et ne peuvent pas être séquentialisées.

Dans un langage purement fonctionnel, le "<tt>;</tt>" n'existe pas, et il n'y a que des valeurs...

Les valeurs sont formées en utilisant :

* les fonctions du langage (addition, multiplication, opérateurs logiques),
* des constructions du langage (<tt>if ... then ... else ...</tt> par exemple),
* les relations mathématiques (égalité, plus grand), ... qui sont juste des fonctions renvoyant des booléens,
* les constantes du langage,
* les variables de l'environnement,
* ''les valeurs (en particulier les fonctions) définies par le programmeur''.

Bien entendu, comme Caml est typé, il faut respecter les types.

=== Les types atomiques ===

Caml (et les autres langages fonctionnels typés) possèdent plusieurs types de base tels que :

* les booléens : type <tt>bool</tt> (valeur <tt>true</tt> et <tt>false</tt>) et les opérations <tt>not</tt>, <tt>&&</tt> (et) et <tt>||</tt> (ou).
* Les entiers : type <tt>int</tt> pour les entiers signés compris entre <math>-230</math> et <math>230-1</math>. (Les entiers Caml sont stockés sur 31 bits...) Les opérations associés sont <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, <tt>/</tt> (pour la division entière) et <tt>mod</tt> (pour le modulo).
* Les flottants : type <tt>float</tt> pour les réels en virgule flottante. Les opérations usuelles sont <tt>+.</tt>, <tt>-.</tt>, <tt>*.</tt> et <tt>/.</tt>.
* Les caractères : type <tt>char</tt> (notés entre guillemets simples).
* Le type unité : type <tt>unit</tt>, dont l'unique valeur est <tt>()</tt>. (Nous verrons que ce type a une utilité...)

Même s'il ne s'agit pas vraiment d'un type atomique, nous pouvons également ajouter le type des chaînes de caractères : type <tt>string</tt> (notées entre guillemets doubles).

<source lang="ocaml">
(* exemples ... *)
</source>

'''Remarques :''' les opérations booléennes ("<tt>&&</tt>" pour le « et » et "<tt>||</tt>" pour le « ou ») fonctionnent de à gauche à droite, et l'argument de droite n'est évalué que si c'est nécessaire. Par exemple <tt>true || (0 = 1/0)</tt> donne la valeur <tt>true</tt>, alors que que <tt>false || (0=1/0)</tt> lève l'exception <tt>Division_by_zero</tt>.

=== définitions et environnement ===

Comme tous les langages de programmation, Caml garde en mémoire une liste de définitions. Chacune de ces définitions met en relation un nom ("<tt>x</tt>", "<tt>n</tt>", "<tt>length</tt>", ...) et une valeur ("<tt>3.7</tt>", "<tt>42</tt>", "<tt>fun s -> ...</tt>").

Lorsque l'on lance Caml, l'environnement contient déjà de nombreuse fonctions prédéfinies : <tt>max</tt>, <tt>min</tt>, <tt>mod</tt>, <tt>+</tt>, <tt>float_of_int</tt>, ...

Certaines des variables de l'environnement correspondent à des paramètres de fonction en cours de définition. Ces variables n'ont pas de valeur, mais seulement un type.

==== Environnement ====

* Liste de paires <tt>nom</tt> / <tt>valeur</tt>,
* une nouvelle definition remplace la précédente mais ne l'efface pas, (on ne met pas une valeur à jours)

==== Définitions ====

L'utilisateur peut rajouter des définitions dans l'environnement grâce au mot clé <tt>let</tt>

* <tt>let nom = expr</tt> permet de rajouter une définition simple dans l'environnement. Exemple : <tt>let n = 42</tt>
* <tt>let nom1 = expr1 and nom2 = expr2</tt> permet de rajouter plusieurs définitions simultanément. Exemple : <tt>let a=1 and b=2</tt>
* <tt>let rec nom1 = expr1 and nom2 = expr2</tt> permet de rajouter des définitions mutuellement récursives.

On peut toujours annoter la définition de types de données. Ceci évite à Caml d'avoir à deviner le type que l'on souhaite et permet de préciser la fonction :
<source lang="ocaml">
let n:int = 42
let rec f (n:int) : string = if (n<1) then "" else "*" ^ (f (n-1))
</source>

Si une définition utilise le même nom qu'une définition précédente, la nouvelle définition écrase l'ancienne. Par exemple :
<source lang="ocaml">
# let n=42 ;;
val n : int = 42
# let n=3.1415 ;;
val n : float = 3.1415
# n ;;

* : float = 3.1415
</source>

==== Définitions locales ====

Il est possible de modifier l'environnement de manière temporaire (''locale''). On utilise alors <tt>let nom = expr1 in expr2</tt>. Ceci ajoute la définition <tt>nom = expr1</tt> dans l'environnement, mais seulement pour l'évaluation de l'expression <tt>expr2</tt>.
<source lang="ocaml">
# let x =
let y = 42 in
y/2 ;;
val x : int = 21
# x ;;

* : int = 21
# y ;;
Unbound value y
</source>

=== Les fonctions ===

Caml utilise la notation mathématique pour écrire les types des fonctions. Si <tt>f</tt> est une fonction avec un seul argument de type <tt>string</tt> et dont la valeur de retour est de type <tt>int</tt> (la fonction <tt>length</tt> par exemple), le type de <tt>f</tt> est noté <tt>string -> int</tt>. Dans l'interprète Caml :
<source lang="ocaml">
# String.length ;;

* : string -> int = <fun>
</source>
Nous indique que la fonction <tt>length</tt> est bien de type <tt>string->int</tt>.

Une fonction est définie comme une variable avec un <tt>let</tt> et en utilisant le mot clé <tt>fun</tt> :
<source lang="ocaml">
# let f = fun n -> n+1;;
val f : int -> int = <fun>
# let racine = fun n -> int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
</source>

Une fonction avec plusieurs argument est définie de la même manière avec
<source lang="ocaml">
# let moyenne3 = fun x y z -> (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Le type d'une fonction à plusieurs argument est noté en mettant plusieurs types à gauche de la flèche <tt>-></tt>, comme ci dessus : <tt>type_arg1 -> type_arg2 -> type_arg3 -> type_resultat</tt>.

'''Remarques :'''

* notez l'absence de mot clé <tt>return</tt> et l'absence de virgules pour séparer les différents arguments !
* Le mot clé <tt>fun</tt> permet de définir des fonctions sans leur donner de nom, ce qui n'est pas possible dans les langages comme C ou Java...

On peut également utiliser un raccourci pour définir une fonction sans utiliser le mot clé <tt>fun</tt> : il suffit de mettre les arguments de la fonction avant le signe égal :
<source lang="ocaml">
# let f n = n+1;;
val f : int -> int = <fun>
# let racine n = int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
# let moyenne3 x y z = (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Pour appliquer une fonction à des arguments, on écrit simplement
<source lang="ocaml">
moyenne3 13.5 17.0 -0.333
</source>
Il n'y a ni parenthèse, ni virgule. Les parenthèses peuvent cependant être nécessaires pour différencier
<source lang="ocaml">
moyenne3 13.5 17.0 (-0.333 *. 6.)
</source>
et
<source lang="ocaml">
(moyenne3 13.5 17.0 -0.333) *. 6.
</source>
ou pour que Caml lise correctement
<source lang="ocaml">
moyenne3 13.5 (17.0 -. 12.0) -0.333
</source>

==== Fonctions récursives ====

Si on essaie de définir une fonction récursivement :
<source lang="ocaml">
let f n = if (n<1) then 0 else n + f (n-1)
</source>
Caml répond
<source lang="ocaml">
Error: Unbound value f
</source>
car <tt>f</tt> n'est pas présente dans l'environnement.

Pour rajouter <tt>f</tt> comme variable active (sans valeur) et pouvoir faire une définition récursive, il faut utiliser le mot clé <tt>rec</tt> :
<source lang="ocaml">
# let rec f n = if (n<1) then 0 else n + f (n-1);;
val f : int -> int = <fun>
</source>

Les définitions locales peuvent elles aussi être récursives (<tt>let rec ... in ...</tt>) ou mutuellement récursives (<tt>let rec ... and ... in ...</tt>). Elles acceptent également les annotations de type...

==== fonctions d'ordre supérieur ====

TODO

=== Les listes ===

Le type des listes est fondamental en programmation fonctionnelle. D'une certaine manière, on peut dire qu'ils remplacent les tableaux que l'on utilise constamment en programmation impérative.

Exercice : quels sont les différences importantes (utilisation, complexité, mémoire, ...) entre les tableaux et les listes ?

En Caml, une liste est représentée entre crochets, et les éléments sont séparés par des points-virgules :
<source lang="ocaml">
# let une_liste = [ 1 ; 2 ; 2 ; -1 ; 0 ] ;;
val une_liste : int list = [1; 2; 2; -1; 0]
# let une_autre_liste = [ "coucou" ; "je m'appelle" ; "Bob" ] ;;
val une_autre_liste : string list = ["coucou"; "je m'appelle"; "Bob"]
</source>

Comme vous pouvez le voir dans l'exemple au dessus, le type des listes d'entiers s'appelle "<tt>int list</tt>", le type des listes de flottants s'appelle "<tt>float list</tt>" et le type des listes de listes d'entiers s'appelle ... "<tt>int list list</tt>".

Contrairement au cas des tuples, les éléments d'une liste doivent tous avoir le même type :
<source lang="ocaml">
# let une_non_liste = [ 1 ; "Toto" ; 1.3 ] ;;
This expression has type string but is here used with type int
</source>

Attention : quel est le type de la liste suivante ?
<source lang="ocaml">
# let une_liste_bizarre = [ 1 , 2 , 3 ] ;;
</source>

On peut ajouter un élement devant une liste avec l'opérateur "<tt>::</tt>" et la concaténation des listes s'obtient avec l'opérateur "<tt>@</tt>".
<source lang="ocaml">
# 5::[1;2;3;4] ;;
- : int list = [5; 1; 2; 3; 4]
# [-1;-2;-3;-4] @ [1;2;3;4] ;;
- : int list = [-1; -2; -3; -4; 1; 2; 3; 4]
</source>
Attention : la complexité de l'opération "<tt>::</tt>" ne dépend pas de la taille des listes mises en jeux. Par contre, la complexité de l'opération "<tt>@</tt>" dépend proportionnellement de la taille de son premier argument. Il faut donc toujour privilégier "<tt>::</tt>" par rapport à "<tt>@</tt>". En particulier, il est en général mauvais de rajouter des élément en fin de liste en utilisant "<tt>l @ [e]</tt>".

=== Filtrage, première partie : tuples et listes ===

La notion de ''filtrage'', aussi appelé "pattern-matching" est un outils clé pour la programmation en Caml. L'idée est de décomposer une valeur en "sous-valeurs".

==== Filtrage sur les tuples ====

Comme une paire est de la forme <tt>(x,y)</tt>, on peut décomposer une valeur de type <tt>a*b</tt> en deux sous valeurs. Voici un exemple de syntaxe : le code de la fonction <tt>fst</tt> :
<source lang="ocaml">
let premier p = match p with
(x,y) -> x
</source>

Pour évaluer "<tt>premier e</tt>", Caml regarde le premier argument <tt>e</tt> et essaie de faire coïncider "<tt>(x,y)</tt>". S'il y arrive, alors il renvoie la valeur "<tt>x</tt>". Le typage de Caml inférera automatique que "<tt>p</tt>" doit être une paire, et il n'y a donc pas besoin de prévoir un cas par defaut.

On peut maintenant récupérer la deuxième composante d'un triplet de la manière suivante :
<source lang="ocaml">
let second3 t = match t with
(_, y, _) -> y
</source>
Notez l'utilisation de "<tt>_</tt>" pour donner la position d'une sous-valeur qui ne sert à rien.

Toutes les variables présentes dans le ''motif'' (la partie à gauche de la flèche) se retrouvent dans l'environnement avec pour valeur, la sous-valeur appropriée. Attention, ces variables ne se retrouvent dans l'environnement que dans la partie droite de la flèche.
Ces variables remplacent (temporairement) les variables de même nom qui pouvaient se trouver dans l'environnement. Par exemple, la fonction :
<source lang="ocaml">
let f x = match x with
(x,_) -> x
</source>
est exactement la fonction <tt>fst</tt>.

==== Filtrage sur les listes ====

On peut décomposer une liste en deux sous-valeurs :

* le premier élément de la liste,
* la suite de la liste.

Autrement dit, si la liste <tt>l</tt> n'est pas vide, on peut la décomposer en <tt>e::q</tt>. Comme il est possible que la liste <tt>l</tt> soit vide, il y a en fait deux manière de décomposer <tt>l</tt> :

* soit <tt>[]</tt> (sans aucune sous-valeur),
* soit <tt>e::q</tt> (avec deux sous-valeurs).

Par exemple, voici une manière de tester si une liste est vide :
<source lang="ocaml">
let vide l = match l with
[] -> true
| x::xs -> false
</source>
Les différents cas sont séparés par le symbole "<tt>|</tt>".

On peut également décomposer une liste en 3 sous-valeurs : le premier élément, le second élément et la suite de la liste. Dans ce cas, il a trois cas pour une liste arbitraire :

* elle est vide <tt>[]</tt> (aucune sous-valeur),
* elle ne contient qu'une seul élément <tt>[e]</tt> (une sous-valeur),
* elle contient un premier élément, un deuxième élément, et une suite <tt>a::b::q</tt> (trois sous-valeurs).

On peut par exemple écrire :
<source lang="ocaml">
let deux_elements_ou_plus l = match l with
[] -> false
| [a] -> false
| a::b::q -> true
</source>

Comme on peut toujours décomposer une valeur en une sous-valeur (la valeur elle même), on peut toujours avoir un motif de la forme <tt>x</tt>. Toutes les valeurs pourront être décomposées de cette manière, et il faut donc que ce motif soit le dernier. (Sinon, les motifs suivants ne servent à rien...) On parle de motif ''universel''. (On peut utiliser <tt>_</tt> comme motif universel.) Par exemple, on peut réecrire l'exemple précédent :
<source lang="ocaml">
let deux_elements_ou_plus
_::_::_ -> true
| _ -> false
</source>

==== Compléments ====

# On peut ajouter des constantes dans les motifs. Le motif ne sera utilisé que lorsque la sous-valeur correspondantes a la valeurs correspondante. Par exemple, si on modélise les entiers de Gauss (« entiers complexes ») par des paires d'entiers, on peut définir :
<source lang="ocaml">
let imaginaire_pur c = match c with
(0,0) -> false
| (0,_) -> true
| _ -> false
</source>
# On peut grouper des motifs différents pour faire la même chose. Il faut que les variables qui apparaissent dans les motifs soient les mêmes, et qu'elles aient le même type :
<source lang="ocaml">
let f x = match x with
0::l | 1::_::l | 2::_::_::l -> l (* on groupe 3 motifs en une seule ligne *)
| [] -> []
| x::_ -> [x]
</source>
# on peut « garder » les motifs" par une condition avec le mot clé "<tt>when</tt>"
<source lang="ocaml">
let g x = match x with
x::xs when (List.lenght (f xs) = 1) -> true
| _ -> false
</source>
Attention dans le cas où vous utilisez <tt>when</tt> : il est conseillé de terminer votre filtrage avec un motif universel pour être sûr que vous n'avez pas oublié de cas.
# comme on définit souvent des fonctions par filtrage, Caml autorise la syntaxe
<source lang="ocaml">
function
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
plutôt que
<source lang="ocaml">
fun x -> match x with
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
Remarquez que l'on ne peut faire ça que pour une fonction à une seule variable...
# fonction par filtrage : s'il n'y a qu'un seul motif, on peut alors utiliser le mot clé "<tt>fun</tt>" habituel, ce qui permet la définition d'une fonction à plusieurs arguments. (Mais dans ce cas, les parenthèses autour des tuples sont obligatoires.)
<source lang="ocaml">
# let h = fun (x,y) z (u,v,w) -> x+y+z+v ;;
val h : int * int -> int -> 'a * int * 'b -> int = <fun>
</source>

=== Le polymorphisme ===

=== Transparence référentielle ===

==== Les types algébriques ====

On peut défnir un synomnyme de type avec le mot clef <tt>type</tt>
Exemple :
<source lang="ocaml">type point = float*float</source>

=== Types énumérés ===

On donne tous les éléments du type
Exemple :
<source lang="ocaml">type jours = Lundi | Mardi | Mercredi | ...</source>

Type avec 7 éléments. Les éléments commencent forcément par une majuscule.

On peut comparer des éléments avec "=", "<" et ">" (< et > sont à éviter, il vaut mieux
écrire une fonction pour comparer) On peut aussi faire du filtrage.

Exemple:
<source lang="ocaml">
let week_end j = match j with
Samedi -> true
| Dimanche -> true
| _ -> false
</source>
=== Construction de types paramètres ===

Exemple : type des transformations de l'espace avec :
- Translation
- Rotation
- Symetrie
On aura alors des constructeurs avec des paramètres :

<source lang="ocaml">
type transformation =
Rotation of int*point
| Translation of point
| SymCentrale of point
| Homothetie of float*point
</source>

On n'a pas donné explicitement tous les éléments, mais on les a donné implicitement.
Exemple :
<source lang="ocaml">
let rien = Translation (0.0,0.0)
</source>
Autre exemple :
<source lang="ocaml">
let fait quelquechose t=
match t with
Rotation(a, (x, y)− > a mod360! = 0
|T ranslation(x, y)− > x! = 0.0 && y! = 0.0
|SymCentrale(x, y)− > true
|Homotetie(x, (−, −))− > r! = 1, 0
</source>

=== Les types récursifs ===

En Caml
<source lang="ocaml">
type node = Node of int*node
| Vide
</source>
exemple d'éléments de "node" :
- Vide
- Node(0,Vide)
- Node(1,Node(2,Node(3, Vide)))

Le type "node" est un type récursif. Comme les fonctions récursivent doivent avoir des cas
de base, les types récursifs doivent avoir des constructeurs "de base" (non récursifs). On peut
comparer des éléments avec "=". On peut aussi utiliser le filtrage.

Exemple :
<source lang="ocaml">
let rec taille l = match l with
Vide -> 0
|Node(_,l)->1+taille l
</source>

La fonction taille sur les listes Caml suit le même schéma avec les abréviations Caml.
<source lang="ocaml">
let rec taille l = match l with
[]->0
| a ::l->1+taille
</source>
Ceci explique la différence entre :: (constructeur) et @ (fonction récursive)

Exemple de type récursif, les arbres binaires :
<source lang="ocaml">
type bin = Vide | Noeud of int*bin*bin
</source>
arbre naire :
<source lang="ocaml">
type arbre n_aire =
Vide|Node of int ∗ (arbre_naire list)(bancal)
</source>

== Les structures ==

== La récursivité terminale ==

== Les exceptions ==

== Aspects impératifs dans Caml ==

== Les modules ==

INFO421 : Programmation fonctionnelle

2013-02-12T18:35:20Z

Lachand : /* Les types algébriques */

Ce wiki est un complément de cours pour le cours « info-421 : programmation fonctionnelle ». La participation au wiki est fortement encouragée, et deviendra peut-être obligatoire...

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Je vous conseille d'aller voir [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

== Détails techniques ==

=== Compléments de cours, TD et TP ===

==== Installer Ocaml ====

Si vous voulez installer OCaml sur votre ordinateur :

* Sous Linux : c'est la solution idéale. Il existe probablement des paquets pour votre distribution. Pour Ubuntu, pour avoir un environnement similaire à ce que vous aurez dans les salles informatiques, installez les paquets <tt>ocaml</tt>, <tt>ocaml-core</tt>, <tt>ocaml-mode</tt>, <tt>tuareg-mode</tt> et <tt>emacs</tt>.
* Sous MacOS : il semblerait qu'il y ait des paquets MacPorts pour <tt>ocaml</tt>, <tt>emacs</tt> et <tt>tuareg-mode.el</tt>.
* Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : [http://deptinfo.unice.fr/~roy/CAML/Win/install-win.html Installation de OCaml (sur Windows XP)]. Je n'ai malheureusement (??) pas accès à une machine avec Windows (98/2000/XP/Vista/7), je ne pourrais donc pas beaucoup vous aider.

Contactez moi si vous avez des problèmes.

Pour les exemples simples, vous pouvez aussi utiliser [http://try.ocamlpro.com/ OCaml en ligne]

==== Références supplémentaires ====

* Le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : [http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/ Développement d'applications avec Ocaml]. (Ce livre utilise une vieille version de Ocaml, mais reste pertinent.)
* La documentation de Caml, version 3.09 (utilisé en TP) : [http://caml.inria.fr/pub/docs/manual-ocaml-309/ Documentation and user's manual].
* Le livre de Jason Hickey [http://files.metaprl.org/doc/ocaml-book.pdf Introduction to Objective Caml] (en anglais).

==== Cours ====

==== TD et TP ====

* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/1213/info421/td1.pdf TD1 : premières expressions en Caml (pdf)]

== Introduction ==

Pour paraphraser un collègue dont je ne retrouve pas le nom :

<blockquote>
''Attention :'' il ne s'agit pas d'un cours de programmation fonctionelle
</blockquote>

Il s'agit plutôt d'un cours de programmation '''fonctionnelle'''...

=== Petit historique censuré ===

Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)

D'après [http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm ce site], qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

* années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à ''porter''. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
* FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
* LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
* ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
* Pascal (1975).
* C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
* Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
* ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
* Smalltalk (fin des année 1983), début de la programmation objet.
* 1983 : ADA.
* année '80 : Caml (1987), puis CamlLight(1990), puis OCaml(1996), développé
à l'INRIA. (Dernière version en octobre 2012.)
* années '90 : Python (version 1.0 en 1994).
* années '90 : PHP (version 1.0 en 1995).
* années '90 : Java (version 1.0 en 1996).

Je vous conseille d'aller voir le graphique suivant : [http://www.levenez.com/lang/lang.pdf Computer Languages Timeline] (ou [http://www.levenez.com/lang/redirect_lang_a4_pdf.html découpé en pages A4]).

=== Fonctionnel ?? ===

L'adjectif ''fonctionnel'' a au moins deux sens :

# qui fonctionne, en état de marche,
# qui se rapporte aux fonctions.

Les langages fonctionnels sont bien entendus ''fonctionnels'' dans le premier sens, mais c'est surtout le second sens qui nous intéresse. Les langages tels que Pascal, Ada ou C sont qualifié, par opposition, d''''impératifs'''''.

Un des slogans de la programmation fonctionnelle en général est

<blockquote>
''Les fonctions sont des valeurs comme les autres''
</blockquote>

et c'est de là que vient la terminologie... En particulier, il n'y a pas de différence entre les ''instructions'' (qui ont un effet) et les ''expressions'' (qui ont une valeur). Par exemple, en Python,

<pre>
x = x+1
</pre>

ou

<pre>
if delta < 0:
print("Il n'y a pas de solution")
</pre>

sont des ''instructions'' : on ne peut pas les mettre dans une variable.

Comme nous le verront, cela a des conséquences sur l'expressivité du langage et la manière de programmer.

=== Le langage (O)Caml ===

Le langage OCaml est développé par l'INRIA (Institut national de recherche en informatique et automatique). C'est un successeur de CamlLight.

Le nom Caml est formé des initiales de "Categorical Abstract Machine Language", et le langage lui même appartient à la famille de ML ("Meta Language"). C'est un langage fonctionnel ''strict'' (nous verrons ce que cela veut dire), statiquement typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :

* fonctionnel bien sûr,
* mais aussi impératif,
* objet également (c'est le « O » de OCaml).

Dans ce cours, nous utiliserons principalement le style fonctionnel, et un peu le style impératif en fin de semestre.

Voici quelques aspects importants du langages que nous essayeront d'aborder pendant le cours :

* fonctions comme valeurs,
* types de données ''algébriques''
* polymorphisme,
* système d'exceptions,
* support pour des références et des données mutables (programmation « impure »),
* système de modules et de foncteurs,
* ...

La notion de ''récursivité'' sera fondamentale pendant toute la durée du cours...

Un aspect intéressant du langage est que c'est :

* un langage interprété (avec l'interpréteur OCaml),
* soit un langage compilé en bytecode (code binaire indépendant de l'architecture),
* soit un langage compilé optimisé en binaire (dépendant de l'architecture).

=== Autres langages fonctionnels ===

Il existe de nombreux autres langages fonctionnels. Par exemple :

* SML (Standard ML) : [http://en.wikipedia.org/wiki/Standard_ML Wikipedia], autre dialecte de la famille ML.
* LISP, dont les deux dialectes principaux sont :
** Common LISP : [http://en.wikipedia.org/wiki/Common_LISP Wikipedia],
** Scheme : [http://en.wikipedia.org/wiki/Scheme_%28programming_language%29 Wikipedia].
* Haskell : [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Wikipedia] (inspiré en grande partie de [http://en.wikipedia.org/wiki/Miranda_%28programming_language%29 Miranda]).

Plusieurs langages impératifs intègrent maintenant des aspects propres des langages fonctionnels : Python, Scala, ...

=== Applications concrètes ===

Voici quelques exemples de logiciels développés en OCaml :

* [http://ocsigen.org/ Ocsigen], un serveur web,
* [http://www.cis.upenn.edu/~bcpierce/unison/ Unison], un logiciel de synchronisation de fichiers entre ordinateurs,
* [http://mldonkey.sourceforge.net/Main_Page MLDonkey], un logiciel de Peer-to-peer multiréseaux,
* [http://pauillac.inria.fr/advi/ Active DVI] un visualisateur pour le format de fichier DVI,
* analyse de programmes critiques : [http://www.astree.ens.fr/ Astrée],
* informatique financiere : [http://www.janestreet.com Janestreet Capital] et [http://www.lexifi.com Lexifi].

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang ([http://fr.wikipedia.org/wiki/Erlang_%28langage%29 Wikipedia]), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

=== Objectifs du cours ===

# être capable de définir des fonctions récursives, et comprendre ce qu'elles font
# comprendre le typage, les types algébriques et le polymorphisme à la ML
# pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
# être capable de décomposer un problème
# commencer à réfléchir à la complexité de vos programmes

== Premiers pas en Caml ==

Un des slogans de la programmation fonctionnelle est ''tout est une valeur, ou plus précisément,

<blockquote>
''Toute expression a une valeur.''
</blockquote>

Cette idée n'est pas présente en Python où l'on distingue les ''expressions'' ("<tt>3*x+f(2)</tt>" par exemple) et les ''instructions'' ("<tt>if n>22: a=12 else: a=13</tt>" par exemple). En Python, les instructions sont en général séparées par des retours à la ligne et sont ''exécutées'' en séquence. Les expressions sont juste calculées, et ne peuvent pas être séquentialisées.

Dans un langage purement fonctionnel, le "<tt>;</tt>" n'existe pas, et il n'y a que des valeurs...

Les valeurs sont formées en utilisant :

* les fonctions du langage (addition, multiplication, opérateurs logiques),
* des constructions du langage (<tt>if ... then ... else ...</tt> par exemple),
* les relations mathématiques (égalité, plus grand), ... qui sont juste des fonctions renvoyant des booléens,
* les constantes du langage,
* les variables de l'environnement,
* ''les valeurs (en particulier les fonctions) définies par le programmeur''.

Bien entendu, comme Caml est typé, il faut respecter les types.

=== Les types atomiques ===

Caml (et les autres langages fonctionnels typés) possèdent plusieurs types de base tels que :

* les booléens : type <tt>bool</tt> (valeur <tt>true</tt> et <tt>false</tt>) et les opérations <tt>not</tt>, <tt>&&</tt> (et) et <tt>||</tt> (ou).
* Les entiers : type <tt>int</tt> pour les entiers signés compris entre <math>-230</math> et <math>230-1</math>. (Les entiers Caml sont stockés sur 31 bits...) Les opérations associés sont <tt>+</tt>, <tt>-</tt>, <tt>*</tt>, <tt>/</tt> (pour la division entière) et <tt>mod</tt> (pour le modulo).
* Les flottants : type <tt>float</tt> pour les réels en virgule flottante. Les opérations usuelles sont <tt>+.</tt>, <tt>-.</tt>, <tt>*.</tt> et <tt>/.</tt>.
* Les caractères : type <tt>char</tt> (notés entre guillemets simples).
* Le type unité : type <tt>unit</tt>, dont l'unique valeur est <tt>()</tt>. (Nous verrons que ce type a une utilité...)

Même s'il ne s'agit pas vraiment d'un type atomique, nous pouvons également ajouter le type des chaînes de caractères : type <tt>string</tt> (notées entre guillemets doubles).

<source lang="ocaml">
(* exemples ... *)
</source>

'''Remarques :''' les opérations booléennes ("<tt>&&</tt>" pour le « et » et "<tt>||</tt>" pour le « ou ») fonctionnent de à gauche à droite, et l'argument de droite n'est évalué que si c'est nécessaire. Par exemple <tt>true || (0 = 1/0)</tt> donne la valeur <tt>true</tt>, alors que que <tt>false || (0=1/0)</tt> lève l'exception <tt>Division_by_zero</tt>.

=== définitions et environnement ===

Comme tous les langages de programmation, Caml garde en mémoire une liste de définitions. Chacune de ces définitions met en relation un nom ("<tt>x</tt>", "<tt>n</tt>", "<tt>length</tt>", ...) et une valeur ("<tt>3.7</tt>", "<tt>42</tt>", "<tt>fun s -> ...</tt>").

Lorsque l'on lance Caml, l'environnement contient déjà de nombreuse fonctions prédéfinies : <tt>max</tt>, <tt>min</tt>, <tt>mod</tt>, <tt>+</tt>, <tt>float_of_int</tt>, ...

Certaines des variables de l'environnement correspondent à des paramètres de fonction en cours de définition. Ces variables n'ont pas de valeur, mais seulement un type.

==== Environnement ====

* Liste de paires <tt>nom</tt> / <tt>valeur</tt>,
* une nouvelle definition remplace la précédente mais ne l'efface pas, (on ne met pas une valeur à jours)

==== Définitions ====

L'utilisateur peut rajouter des définitions dans l'environnement grâce au mot clé <tt>let</tt>

* <tt>let nom = expr</tt> permet de rajouter une définition simple dans l'environnement. Exemple : <tt>let n = 42</tt>
* <tt>let nom1 = expr1 and nom2 = expr2</tt> permet de rajouter plusieurs définitions simultanément. Exemple : <tt>let a=1 and b=2</tt>
* <tt>let rec nom1 = expr1 and nom2 = expr2</tt> permet de rajouter des définitions mutuellement récursives.

On peut toujours annoter la définition de types de données. Ceci évite à Caml d'avoir à deviner le type que l'on souhaite et permet de préciser la fonction :
<source lang="ocaml">
let n:int = 42
let rec f (n:int) : string = if (n<1) then "" else "*" ^ (f (n-1))
</source>

Si une définition utilise le même nom qu'une définition précédente, la nouvelle définition écrase l'ancienne. Par exemple :
<source lang="ocaml">
# let n=42 ;;
val n : int = 42
# let n=3.1415 ;;
val n : float = 3.1415
# n ;;

* : float = 3.1415
</source>

==== Définitions locales ====

Il est possible de modifier l'environnement de manière temporaire (''locale''). On utilise alors <tt>let nom = expr1 in expr2</tt>. Ceci ajoute la définition <tt>nom = expr1</tt> dans l'environnement, mais seulement pour l'évaluation de l'expression <tt>expr2</tt>.
<source lang="ocaml">
# let x =
let y = 42 in
y/2 ;;
val x : int = 21
# x ;;

* : int = 21
# y ;;
Unbound value y
</source>

=== Les fonctions ===

Caml utilise la notation mathématique pour écrire les types des fonctions. Si <tt>f</tt> est une fonction avec un seul argument de type <tt>string</tt> et dont la valeur de retour est de type <tt>int</tt> (la fonction <tt>length</tt> par exemple), le type de <tt>f</tt> est noté <tt>string -> int</tt>. Dans l'interprète Caml :
<source lang="ocaml">
# String.length ;;

* : string -> int = <fun>
</source>
Nous indique que la fonction <tt>length</tt> est bien de type <tt>string->int</tt>.

Une fonction est définie comme une variable avec un <tt>let</tt> et en utilisant le mot clé <tt>fun</tt> :
<source lang="ocaml">
# let f = fun n -> n+1;;
val f : int -> int = <fun>
# let racine = fun n -> int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
</source>

Une fonction avec plusieurs argument est définie de la même manière avec
<source lang="ocaml">
# let moyenne3 = fun x y z -> (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Le type d'une fonction à plusieurs argument est noté en mettant plusieurs types à gauche de la flèche <tt>-></tt>, comme ci dessus : <tt>type_arg1 -> type_arg2 -> type_arg3 -> type_resultat</tt>.

'''Remarques :'''

* notez l'absence de mot clé <tt>return</tt> et l'absence de virgules pour séparer les différents arguments !
* Le mot clé <tt>fun</tt> permet de définir des fonctions sans leur donner de nom, ce qui n'est pas possible dans les langages comme C ou Java...

On peut également utiliser un raccourci pour définir une fonction sans utiliser le mot clé <tt>fun</tt> : il suffit de mettre les arguments de la fonction avant le signe égal :
<source lang="ocaml">
# let f n = n+1;;
val f : int -> int = <fun>
# let racine n = int_of_float (sqrt (float_of_int n));;
val racine : int -> int = <fun>
# let moyenne3 x y z = (x +. y +. z) /. 3. ;;
val moyenne3 : float -> float -> float -> float = <fun>
</source>

Pour appliquer une fonction à des arguments, on écrit simplement
<source lang="ocaml">
moyenne3 13.5 17.0 -0.333
</source>
Il n'y a ni parenthèse, ni virgule. Les parenthèses peuvent cependant être nécessaires pour différencier
<source lang="ocaml">
moyenne3 13.5 17.0 (-0.333 *. 6.)
</source>
et
<source lang="ocaml">
(moyenne3 13.5 17.0 -0.333) *. 6.
</source>
ou pour que Caml lise correctement
<source lang="ocaml">
moyenne3 13.5 (17.0 -. 12.0) -0.333
</source>

==== Fonctions récursives ====

Si on essaie de définir une fonction récursivement :
<source lang="ocaml">
let f n = if (n<1) then 0 else n + f (n-1)
</source>
Caml répond
<source lang="ocaml">
Error: Unbound value f
</source>
car <tt>f</tt> n'est pas présente dans l'environnement.

Pour rajouter <tt>f</tt> comme variable active (sans valeur) et pouvoir faire une définition récursive, il faut utiliser le mot clé <tt>rec</tt> :
<source lang="ocaml">
# let rec f n = if (n<1) then 0 else n + f (n-1);;
val f : int -> int = <fun>
</source>

Les définitions locales peuvent elles aussi être récursives (<tt>let rec ... in ...</tt>) ou mutuellement récursives (<tt>let rec ... and ... in ...</tt>). Elles acceptent également les annotations de type...

==== fonctions d'ordre supérieur ====

TODO

=== Les listes ===

Le type des listes est fondamental en programmation fonctionnelle. D'une certaine manière, on peut dire qu'ils remplacent les tableaux que l'on utilise constamment en programmation impérative.

Exercice : quels sont les différences importantes (utilisation, complexité, mémoire, ...) entre les tableaux et les listes ?

En Caml, une liste est représentée entre crochets, et les éléments sont séparés par des points-virgules :
<source lang="ocaml">
# let une_liste = [ 1 ; 2 ; 2 ; -1 ; 0 ] ;;
val une_liste : int list = [1; 2; 2; -1; 0]
# let une_autre_liste = [ "coucou" ; "je m'appelle" ; "Bob" ] ;;
val une_autre_liste : string list = ["coucou"; "je m'appelle"; "Bob"]
</source>

Comme vous pouvez le voir dans l'exemple au dessus, le type des listes d'entiers s'appelle "<tt>int list</tt>", le type des listes de flottants s'appelle "<tt>float list</tt>" et le type des listes de listes d'entiers s'appelle ... "<tt>int list list</tt>".

Contrairement au cas des tuples, les éléments d'une liste doivent tous avoir le même type :
<source lang="ocaml">
# let une_non_liste = [ 1 ; "Toto" ; 1.3 ] ;;
This expression has type string but is here used with type int
</source>

Attention : quel est le type de la liste suivante ?
<source lang="ocaml">
# let une_liste_bizarre = [ 1 , 2 , 3 ] ;;
</source>

On peut ajouter un élement devant une liste avec l'opérateur "<tt>::</tt>" et la concaténation des listes s'obtient avec l'opérateur "<tt>@</tt>".
<source lang="ocaml">
# 5::[1;2;3;4] ;;
- : int list = [5; 1; 2; 3; 4]
# [-1;-2;-3;-4] @ [1;2;3;4] ;;
- : int list = [-1; -2; -3; -4; 1; 2; 3; 4]
</source>
Attention : la complexité de l'opération "<tt>::</tt>" ne dépend pas de la taille des listes mises en jeux. Par contre, la complexité de l'opération "<tt>@</tt>" dépend proportionnellement de la taille de son premier argument. Il faut donc toujour privilégier "<tt>::</tt>" par rapport à "<tt>@</tt>". En particulier, il est en général mauvais de rajouter des élément en fin de liste en utilisant "<tt>l @ [e]</tt>".

=== Filtrage, première partie : tuples et listes ===

La notion de ''filtrage'', aussi appelé "pattern-matching" est un outils clé pour la programmation en Caml. L'idée est de décomposer une valeur en "sous-valeurs".

==== Filtrage sur les tuples ====

Comme une paire est de la forme <tt>(x,y)</tt>, on peut décomposer une valeur de type <tt>a*b</tt> en deux sous valeurs. Voici un exemple de syntaxe : le code de la fonction <tt>fst</tt> :
<source lang="ocaml">
let premier p = match p with
(x,y) -> x
</source>

Pour évaluer "<tt>premier e</tt>", Caml regarde le premier argument <tt>e</tt> et essaie de faire coïncider "<tt>(x,y)</tt>". S'il y arrive, alors il renvoie la valeur "<tt>x</tt>". Le typage de Caml inférera automatique que "<tt>p</tt>" doit être une paire, et il n'y a donc pas besoin de prévoir un cas par defaut.

On peut maintenant récupérer la deuxième composante d'un triplet de la manière suivante :
<source lang="ocaml">
let second3 t = match t with
(_, y, _) -> y
</source>
Notez l'utilisation de "<tt>_</tt>" pour donner la position d'une sous-valeur qui ne sert à rien.

Toutes les variables présentes dans le ''motif'' (la partie à gauche de la flèche) se retrouvent dans l'environnement avec pour valeur, la sous-valeur appropriée. Attention, ces variables ne se retrouvent dans l'environnement que dans la partie droite de la flèche.
Ces variables remplacent (temporairement) les variables de même nom qui pouvaient se trouver dans l'environnement. Par exemple, la fonction :
<source lang="ocaml">
let f x = match x with
(x,_) -> x
</source>
est exactement la fonction <tt>fst</tt>.

==== Filtrage sur les listes ====

On peut décomposer une liste en deux sous-valeurs :

* le premier élément de la liste,
* la suite de la liste.

Autrement dit, si la liste <tt>l</tt> n'est pas vide, on peut la décomposer en <tt>e::q</tt>. Comme il est possible que la liste <tt>l</tt> soit vide, il y a en fait deux manière de décomposer <tt>l</tt> :

* soit <tt>[]</tt> (sans aucune sous-valeur),
* soit <tt>e::q</tt> (avec deux sous-valeurs).

Par exemple, voici une manière de tester si une liste est vide :
<source lang="ocaml">
let vide l = match l with
[] -> true
| x::xs -> false
</source>
Les différents cas sont séparés par le symbole "<tt>|</tt>".

On peut également décomposer une liste en 3 sous-valeurs : le premier élément, le second élément et la suite de la liste. Dans ce cas, il a trois cas pour une liste arbitraire :

* elle est vide <tt>[]</tt> (aucune sous-valeur),
* elle ne contient qu'une seul élément <tt>[e]</tt> (une sous-valeur),
* elle contient un premier élément, un deuxième élément, et une suite <tt>a::b::q</tt> (trois sous-valeurs).

On peut par exemple écrire :
<source lang="ocaml">
let deux_elements_ou_plus l = match l with
[] -> false
| [a] -> false
| a::b::q -> true
</source>

Comme on peut toujours décomposer une valeur en une sous-valeur (la valeur elle même), on peut toujours avoir un motif de la forme <tt>x</tt>. Toutes les valeurs pourront être décomposées de cette manière, et il faut donc que ce motif soit le dernier. (Sinon, les motifs suivants ne servent à rien...) On parle de motif ''universel''. (On peut utiliser <tt>_</tt> comme motif universel.) Par exemple, on peut réecrire l'exemple précédent :
<source lang="ocaml">
let deux_elements_ou_plus
_::_::_ -> true
| _ -> false
</source>

==== Compléments ====

# On peut ajouter des constantes dans les motifs. Le motif ne sera utilisé que lorsque la sous-valeur correspondantes a la valeurs correspondante. Par exemple, si on modélise les entiers de Gauss (« entiers complexes ») par des paires d'entiers, on peut définir :
<source lang="ocaml">
let imaginaire_pur c = match c with
(0,0) -> false
| (0,_) -> true
| _ -> false
</source>
# On peut grouper des motifs différents pour faire la même chose. Il faut que les variables qui apparaissent dans les motifs soient les mêmes, et qu'elles aient le même type :
<source lang="ocaml">
let f x = match x with
0::l | 1::_::l | 2::_::_::l -> l (* on groupe 3 motifs en une seule ligne *)
| [] -> []
| x::_ -> [x]
</source>
# on peut « garder » les motifs" par une condition avec le mot clé "<tt>when</tt>"
<source lang="ocaml">
let g x = match x with
x::xs when (List.lenght (f xs) = 1) -> true
| _ -> false
</source>
Attention dans le cas où vous utilisez <tt>when</tt> : il est conseillé de terminer votre filtrage avec un motif universel pour être sûr que vous n'avez pas oublié de cas.
# comme on définit souvent des fonctions par filtrage, Caml autorise la syntaxe
<source lang="ocaml">
function
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
plutôt que
<source lang="ocaml">
fun x -> match x with
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
Remarquez que l'on ne peut faire ça que pour une fonction à une seule variable...
# fonction par filtrage : s'il n'y a qu'un seul motif, on peut alors utiliser le mot clé "<tt>fun</tt>" habituel, ce qui permet la définition d'une fonction à plusieurs arguments. (Mais dans ce cas, les parenthèses autour des tuples sont obligatoires.)
<source lang="ocaml">
# let h = fun (x,y) z (u,v,w) -> x+y+z+v ;;
val h : int * int -> int -> 'a * int * 'b -> int = <fun>
</source>

=== Le polymorphisme ===

=== Transparence référentielle ===

=== Les types algébriques ===

On peut défnir un synomnyme de type avec le mot clef <tt>type</tt>
Exemple :
<source lang="ocaml">type point = float*float</source>

=== Types énumérés ===

On donne tous les éléments du type
Exemple :
<source lang="ocaml">type jours = Lundi | Mardi | Mercredi | ...</source>

Type avec 7 éléments. Les éléments commencent forcément par une majuscule.

On peut comparer des éléments avec "=", "<" et ">" (< et > sont à éviter, il vaut mieux
écrire une fonction pour comparer) On peut aussi faire du filtrage.

Exemple:
<source lang="ocaml">
let week_end j = match j with
Samedi -> true
| Dimanche -> true
| _ -> false
</source>
=== Construction de types paramètres ===

Exemple : type des transformations de l'espace avec :
- Translation
- Rotation
- Symetrie
On aura alors des constructeurs avec des paramètres :

<source lang="ocaml">
type transformation =
Rotation of int*point
| Translation of point
| SymCentrale of point
| Homothetie of float*point
</source>

On n'a pas donné explicitement tous les éléments, mais on les a donné implicitement.
Exemple :
<source lang="ocaml">
let rien = Translation (0.0,0.0)
</source>
Autre exemple :
<source lang="ocaml">
let fait quelquechose t=
match t with
Rotation(a, (x, y)− > a mod360! = 0
|T ranslation(x, y)− > x! = 0.0 && y! = 0.0
|SymCentrale(x, y)− > true
|Homotetie(x, (−, −))− > r! = 1, 0
</source>

=== Les types récursifs ===

En Caml
<source lang="ocaml">
type node = Node of int*node
| Vide
</source>
exemple d'éléments de "node" :
- Vide
- Node(0,Vide)
- Node(1,Node(2,Node(3, Vide)))

Le type "node" est un type récursif. Comme les fonctions récursivent doivent avoir des cas
de base, les types récursifs doivent avoir des constructeurs "de base" (non récursifs). On peut
comparer des éléments avec "=". On peut aussi utiliser le filtrage.

Exemple :
<source lang="ocaml">
let rec taille l = match l with
Vide -> 0
|Node(_,l)->1+taille l
</source>

La fonction taille sur les listes Caml suit le même schéma avec les abréviations Caml.
<source lang="ocaml">
let rec taille l = match l with
[]->0
| a ::l->1+taille
</source>
Ceci explique la différence entre :: (constructeur) et @ (fonction récursive)

Exemple de type récursif, les arbres binaires :
<source lang="ocaml">
type bin = Vide | Noeud of int*bin*bin
</source>
arbre naire :
<source lang="ocaml">
type arbre n_aire =
Vide|Node of int ∗ (arbre_naire list)(bancal)
</source>

== Les structures ==

== La récursivité terminale ==

== Les exceptions ==

== Aspects impératifs dans Caml ==

== Les modules ==