« INFO421 : Programmation fonctionnelle » : différence entre les versions

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche
mAucun résumé des modifications
m (mise à jours, début du cours 2013)
Ligne 12 : Ligne 12 :




== Détails techniques ==


=== Compléments de cours, TD et TP ===
==Détails techniques==


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


Si vous voulez installer OCaml sur votre ordinateur :
====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 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.
* 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.
Contactez moi si vous avez des problèmes.


Pour les exemples simples, vous pouvez aussi utiliser [http://try.ocamlpro.com/ OCaml en ligne]
J'ai créé une petite [http://www.lama.univ-savoie.fr/wiki/index.php?title=INFO401_:_utilisation_Caml page dédiée pour la syntaxe de Caml et son utilisation].


====Références supplémentaires====
==== 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.)
* 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 ====
* La documentation de Caml, version 3.09 (utilisé en TP) : [http://caml.inria.fr/pub/docs/manual-ocaml-309/ Documentation and user's manual].

==== TD et TP ====


----
==Introduction==

== Introduction ==


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


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


Il s'agit plutôt d'un cours de programmation '''fonctio<u>nn</u>elle'''...
Il s'agit plutôt d'un cours de programmation '''fonctio<u>nn</u>elle'''...


=== Petit historique censuré ===

===Petit historique censuré===


Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)
Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)
Ligne 60 : Ligne 66 :
* Smalltalk (fin des année 1983), début de la programmation objet.
* Smalltalk (fin des année 1983), début de la programmation objet.
* 1983 : ADA.
* 1983 : ADA.
* année '80 : Caml (1987), puis CamlLight(1990), puis OCaml(1996), développé
* 1983 : Miranda un langage fonctionnel « pur ».
à l'INRIA. (Dernière version en octobre 2012.)
* 1985 : Caml, développé à l'INRIA.
* 1990 : Haskell, inspiré de Miranda,
* années '90 : Python (version 1.0 en 1994).
* 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]).
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 ??===
=== Fonctionnel ?? ===


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

# qui fonctionne, en état de marche,
# qui fonctionne, en état de marche,
# qui se rapporte aux fonctions.
# 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''.
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>
''<u>Les fonctions sont des valeurs comme les autres</u>''
</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,
Un des slogans de la programmation fonctionnelle en général est
<center>''<u>Les fonctions sont des valeurs comme les autres</u>''</center>
et c'est de là que vient la terminologie...


<pre>
Comme nous le verront, cela a de nombreuses conséquences sur l'expressivité du langage et la manière de programmer.
x = x+1
</pre>


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

<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 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), typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :
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,
* fonctionnel bien sûr,
* mais aussi impératif,
* mais aussi impératif,
* objet également (c'est le « O » de OCaml).
* objet également (c'est le « O » de OCaml).


Dans ce cours, nous utiliserons seulement le style fonctionnel.
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 verrons peut-être pendant le cours :
Voici quelques aspects importants du langages que nous essayeront d'aborder pendant le cours :

* fonctions comme valeurs valeurs,
* fonctions comme valeurs,
* types de données ''algébriques''
* polymorphisme,
* polymorphisme,
* système d'exceptions,
* système d'exceptions,
* système de modules et de foncteurs,
* support pour des références et des données mutables (programmation « impure »),
* 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 aspect intéressant du langage est que c'est soit :
* un langage interprété (avec l'interpréteur OCaml),
* 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é en bytecode (code binaire indépendant de l'architecture),
* soit un langage compilé optimisé en binaire (dépendant de l'architecture).
* soit un langage compilé optimisé en binaire (dépendant de l'architecture).


=== Autres langages fonctionnels ===
On peut donc choisir ce que l'on veut pour ces applications.


===Autres langages fonctionnels===
Il existe de nombreux autres langages fonctionnels. Par exemple :


Il existe de nombreux autres langages fonctionnels. Je vous montrerais peut-être des exemples en cours. Voici quelques exemples importants :
* SML (Standard ML) : [http://en.wikipedia.org/wiki/Standard_ML Wikipedia], autre dialecte de la famille ML.
* SML (Standard ML) : [http://en.wikipedia.org/wiki/Standard_ML Wikipedia], autre dialecte de la famille ML.
* LISP, dont les deux dialectes principaux sont :
* LISP, dont les deux dialectes principaux sont :
** Common LISP : [http://en.wikipedia.org/wiki/Common_LISP Wikipedia],
** Common LISP : [http://en.wikipedia.org/wiki/Common_LISP Wikipedia],
** Scheme : [http://en.wikipedia.org/wiki/Scheme_(programming_language) Wikipedia].
** Scheme : [http://en.wikipedia.org/wiki/Scheme_%28programming_language%29 Wikipedia].
* Haskell : [http://en.wikipedia.org/wiki/Haskell_(programming_language) Wikipedia] (inspiré en grande partie de [http://en.wikipedia.org/wiki/Miranda_(programming_language) Miranda]).
* 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===
=== Applications concrètes ===


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

* [http://ocsigen.org/ Ocsigen], un serveur web,
* [http://ocsigen.org/ Ocsigen], un serveur web,
* [http://www.cis.upenn.edu/~bcpierce/unison/ Unison], un logiciel de synchronisation de fichiers entre ordinateurs,
* [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://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.
* [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_(langage) Wikipedia]), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.
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 ===
D'autre part, l'efficacité des langages fonctionnels peut être constatée sur le [http://shootout.alioth.debian.org/ The Computer Language Benchmarks Game], où différents langages de programmation sont comparés (temps d'exécution, taille du code source et utilisation de la mémoire) sur des taches différentes. Les langages fonctionnels sont toujours bien représentés...

===Objectifs du cours===


# être capable de définir des fonctions récursives, et comprendre ce qu'elles font
# être capable de définir des fonctions récursives, et comprendre ce qu'elles font
# comprendre le typage et le polymorphisme à la ML
# 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
# pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
# être capable de décomposer un problème
# être capable de décomposer un problème
# comprendre et utiliser la notion de type récursif
# commencer à réfléchir à la complexité de vos programmes
# commencer à réfléchir à la complexité de vos programmes
=


==Premiers pas en Caml==
== Premiers pas en Caml ==

===Les valeurs===

Un des slogans de la programmation fonctionnelle est ''tout est une valeur, ou plus précisément,
<center>''Tout programme <u>a</u> une valeur.''</center>

Cette idée n'est pas présente en C, et encore moins en Pascal, où l'on distingue les ''expressions'' ("<tt>3*x+f(2)</tt>" par exemple) et les ''instructions'' ("<tt>if (n>22) then a:=12 else a:=13</tt>" par exemple). En Pascal, les instructions sont en général séparées par des "<tt>;</tt>" 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)
* les opérateurs logiques (qui sont juste des fonctions des booléens vers les booléens),
* les relations mathématiques (égalité, plus grand, ... qui sont juste des fonctions dont le type de retour est le type des booléens),
* les constantes,
* les variables,
* des constructions du langage (<tt>if ... then ... else ...</tt>) par exemple).

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


====Les valeurs de type atomique====

Voici quelques exemples d'expressions bien formées : on suppose que <tt>n</tt> est de type entier, <tt>x</tt> est de type flottant et <tt>s</tt> de type chaîne de caractères.
<source lang="ocaml">
17
</source>

<source lang="ocaml">
n
</source>

<source lang="ocaml">
n+(3*2)
</source>

<source lang="ocaml">
(n+3)*2
</source>

<source lang="ocaml">
n+3*2 (* --> même valeur que n+(3*2) *)
</source>

<source lang="ocaml">
length ("Bonjour") (* --> valeur 7 *)
</source>

<source lang="ocaml">
length "Bonjour" (* --> valeur 7 *)
</source>

<source lang="ocaml">
if (x>0) then n
else (n+1) (* --> suivant la valeur de x, c'est soit la valeur de n, soit la valeur de n+1 *)
</source>

<source lang="ocaml">
(if (x>0) then n
else n) + 1 (* --> (presque) la même chose que n+1 *)
</source>

Voici des exemples de valeurs mal formées :
<source lang="ocaml">
x+1 (* --> x et 1 n'ont pas le meme type *)
</source>

<source lang="ocaml">
x+1.0 (* --> le "+" ne fonctionne que sur des entiers (Pour les flottants, il faut utiliser "+." "*.", ...) *)
</source>

<source lang="ocaml">
length x (* --> length a un argument de type chaine, mais x est de type flottant *)
</source>

<source lang="ocaml">
if (x=0) then x
else n (* --> le type d'une valeur doit etre connu, mais x et n n'ont pas le meme type *)
</source>

<source lang="ocaml">
if (true) then x
else n (* --> idem (meme si dans ce cas, on peut ignorer le "else") ()
</source>


Caml donne des messages d'erreur explicites dans ces cas là. Par exemple, si on rentre l'expression
<source lang="ocaml">
let x = 1.5 in x+1
</source>
Caml répond :
# let x = 1.5 in <u>x</u>+1 ;;
This expression has type float but is here used with type int
(Remarquez le <tt>x</tt> souligné pour nous dire d'où vient l'erreur...)

::'''Remarque :''' en Caml, on peut déclarer une variable locale à une expression avec la syntaxe "<tt>let x= expr in expr</tt>".

====Les valeurs fonctionnelles====

Les exemples du paragraphe précédent ne devraient pas trop vous surprendre. La vraie nouveauté est que même les fonctions sont des valeurs.
<source lang="ocaml">
length (* valeur de type "fonction des chaînes vers les entiers" *)
</source>

Une valeur de type fonctionnel peut être définie de la manière suivante :
<source lang="ocaml">
fun x y -> 2*(x+y)
</source>
Ceci ressemble à une définition mathématique usuelle :
<center> La fonction qui à <math>x</math> et <math>y</math> associe <math>2\times(x+y)</math>, que l'on note habituellement <math>x,y\mapsto 2\times(x+y)</math></center>

Remarquez que cette fonction n'a pas de nom. Les langages impératifs tels que C, ou Pascal ne permettent pas de définir une fonction sans lui donner de nom.


Une telle fonction avec 2 arguments pourra être appliquée pour obtenir une nouvelle valeur. Dans l'exemple précédent, la fonction avaient deux arguments entiers et donnait un résultat de type entier. Si on donne le nom <tt>f</tt> à cette fonction :
<source lang="ocaml">
let f = fun x y -> 2*(x+y)
</source>
on pourra obtenir de nouvelles valeurs telles que :
<source lang="ocaml">
f 1 2
</source>

::'''Notez bien''' que pour appliquer une fonction à ses arguments, les parenthèses ne sont en général pas nécessaires, et qu'on n'utilise pas de "<tt>,</tt>" pour séparer les arguments.

====Notion d'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>, ... Une occurrence d'un nom de variable de l'environnement qui est en position de ''variable libre'' sera remplacé par la valeur correspondante.


=====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 ''nom'' = ''expr''</tt> permet de rajouter une définition récursive dans l'environnement. Exemple : <tt>let rec f n = if (n<1) then 0 else n+ f (n-1)</tt>
* <tt>let rec ''nom1'' = ''expr1'' and ''nom2'' = ''expr2''</tt> permet de rajouter des définitions mutuellement récursives.

Dans chacun des cas précédents, on peut 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 définitions locales peuvent elles aussi être multiples (<tt>let ... and ... in</tt>), récursives (<tt>let rec ... in</tt>), mutuellement récursives (<tt>let rec ... and ... in</tt>). Elles acceptent également les annotations de type...

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

Une des idées importantes en programmation fonctionnelle est la notion de « transparence référentielle » : grosso-modo, cela veut dire que l'on a toujours le droit de remplacer une expression par sa valeur sans changer le sens du programme. Bien que ceci semble évident, ce n'est pas vrai dans un langage tels que le langage C...

Pour comprendre pourquoi ceci n'est pas vrai dans un programme Pascal, considérez la fonction suivante
<source lang="pascal">
function f (x:integer) : integer ;
begin
writeln('Salut...');
y:=0; { y est une variable globale }
f:=x+1;
end;
</source>
La valeur de <tt>f(3)</tt> est <tt>4</tt>, mais on ne peut pas remplacer <tt>f(3)</tt> par <tt>4</tt> sans changer le comportement du programme...

C'est cette propriété qui facilite grandement la formalisation des langages fonctionnels, car on peut appliquer le principe mathématique
<center> si <math>x=y</math> alors <math>f(x)=f(y)</math>.</center>

===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>),
* les entiers : type <tt>int</tt> pour les entiers signés compris entre <math>-2^{30}</math> et <math>2^{30}-1</math>. (Les entiers Caml sont stockés sur 31 bits...)
* les flottants : type <tt>float</tt> pour les réels en virgule flottante,
* 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).

Caml définit de nombreuse fonctions sur ces types de données :
* opérations arithmétiques
* fonctions mathématiques usuelles (logarithme, sinus, ...)
* ...

::'''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écessaires. 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>.

====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 d
ont 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'in
terprète Caml :
<source lang="ocaml">
# length ;;
- : string -> int = <fun>
</source>
Nous indique que la fonction <tt>length</tt> est bien de type <tt>string->int</tt>.

Une nouveauté des langages fonctionnels par rapports à Pascal est que <tt>string->int</tt> est un type comme les autre, et on peut donc créer une fonction d
e type <tt>string -> (string -> int)</tt>. Prenons par exemple la fonction suivante :
<source lang="ocaml">
let f:string->int = fun s ->
let t = "prefix-" in
length (t ^ s) (* "^" est l'opérateur de concaténation des chaînes. *)
</source>
Cette fonction va calculer la longueur de son argument, auquel on a rajouter le préfixe <tt>"prefix-"</tt>.

Si on veut pouvoir changer le préfixe que l'on rajoute devant <tt>s</tt>, on peut faire la fonction suivante :
<source lang="ocaml">
let g:string -> ( string -> int) =
fun prefix ->
fun s -> length (t^s)
</source>
La fonction <tt>f</tt> précédente aurait pu être obtenue grâce à "<tt>g "prefix-"</tt>".

::'''Remarque :''' Caml n'utilise pas les parenthèses dans ce cas là : il notera "<tt>string -> string -> int</tt>".


Nous verrons un peu plus tard que les fonctions peuvent avoir des arguments qui sont eux mêmes des fonctions.

::<u>Exercice :</u> essayez de trouver une fonction de type <tt>(int->int) -> int</tt>.


====Les paires====

Un autre type intéressant est celui des paires de valeur. Par exemple, le type "<tt>int * string</tt>" est compose de valeur "<tt>(3,"toto")</tt>". On peut accéder au premier élément d'une paire avec la fonction "<tt>fst</tt>" et au second élément avec la fonction "<tt>snd</tt>".
<source lang="ocaml">
let paire = ("Bonjour !" , 42*42) in (snd paire)
</source>
donnera la valeur 1764.

Ce type correspond exactement à la notion de ''produit cartésien'' utilisée en mathématiques :
<center><math> A \times B \quad=\quad \{ (a,b) \ |\ a\in A \,,\,b\in B\} </math></center>

Les fonctions <tt>fst</tt> et <tt>snd</tt> sont généralement appelées ''projections'' :
<center><math> \pi_1 : A\times B \to A \qquad (a,b) \mapsto a</math></center>
(et pareillement pour la projection sur l'élément de droite...)


Ce type de données particulièrement utile lorsque l'on veut écrire une fonction qui renvoie 2 ou 3 valeurs. On verra par la suite qu'il existe d'autre types plus appropriés si l'on veut avoir de nombreux champs, et s'il l'on veut leur donner un nom. (Dans une paire, la première composante et la seconde composante n'ont pas de nom propre...)

Notez également que les fonctions a plusieurs arguments n'utilisent en général pas de produit cartésien. Pour Caml :
* une fonction de type <tt>(A*B) -> C</tt> est une fonction à un seul argument, mais son argument est une paire,
* une fonction de type <tt>A -> B -> C</tt> est une fonction à deux arguments séparés. (Plus précisément, c'est une fonction à un argument qui renvoie une fonction à un argument.)


:<u>Exercice : </u> cherchez une manière de passer d'une fonction de type <tt>A*B -> C</tt> à une fonction de type <tt>A -> B -> C</tt>, et vice-versa. Ces transformations s'appellent la ''curryfication'' et la ''decurryfication''.

:Écrivez les fonctions <tt>curry :: ('a*'b -> 'c) -> ('a -> 'b -> 'c)</tt> et <tt>un curry : ('a -> 'b -> 'c) -> ('a*'b -> 'c)</tt> en Caml.


:'''Remarque :''' dans de nombreux cas, les parenthèses autour d'un tuple ne sont pas nécessaires :
<source lang="ocaml">
# let x = 42 , "Toto" and y = (42 , "Toto") in
x=y ;;
- : bool = true
</source>
:Dans le doute, mettez des parenthèses pour éviter des bugs.

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

:<u>Exercice : </u> 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 du produit cartésien de types, 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>


La concaténation des listes s'obtient avec l'opérateur "<tt>@</tt>" et pour rajouter un element devant une liste existante on utilise "<tt>::</tt>".
<source lang="ocaml">
# 0::[1;2;3;4] ;;
- : int list = [0; 1; 2; 3; 4]
# [-1;-2;-3;-4] @ [1;2;3;4] ;;
- : int list = [-1; -2; -3; -4; 1; 2; 3; 4]
</source>
Il existe en plus (dans la bibliothèque "<tt>List</tt>" les fonctions suivantes
* <tt>length</tt>,
* <tt>hd</tt> pour récupérer le premier élément d'une liste,
* <tt>tl</tt> pour récupérer la ''queue'' d'une liste (toute la liste, sans son premier élément).


:'''Remarque :''' Caml possède plusieurs fonctions <tt>length</tt> : notamment une pour les listes et une pour les chaînes de caractères. Pour accéder à ces fonctions (qui ne sont pas dans la bibliothèque standard), il faut utiliser :
:* <tt>List.length</tt> pour la longueur des listes,
:* <tt>String.length</tt> pour la longueur des chaînes.
:Vous pouvez aussi ''ouvrir'' toute la bibliothèque correspondante en utilisant la ligne "<tt>open List</tt>" au début de votre programme pour avoir accès à toutes les fonctions de la bibliothèque sur les listes...


La manière usuelle de définir des fonctions récursives sur les listes d'utilisez plutôt le ''filtrage'' (''"pattern matching"'') décrit plus loin, ou les fonctions prédéfinies comme <tt>List.fold_left</tt> ou <tt>List.fold_right</tt> (qui seront vues en TD et TP).

--- examples et explication de fold ?

====Filtrage, première partie====

La notion de ''filtrage'', aussi appelé ''"pattern-matching"'' est un outils clé pour la programmation en Caml. L'idée est d'essayer de faire correspondre une valeur avec un certain nombre de ''motifs''. Le "<tt>case .. of</tt>" de Pascal en est une version ultra pauvre et simplifiée.

En Caml, la syntaxe du pattern matching est la suivante :
match ''expr'' with
''pattern1'' -> ''expr1''
| ''pattern2'' -> ''expr2''
| ''pattern3'' -> ''expr3''
| ''pattern4'' -> ''expr4''
L'évaluation d'une telle expression se fait de la manière suivante : Caml évalue l'expression "''<tt>expr</tt>''", et essaie de la faire coïncider au motif "<tt>pattern1</tt>" (on dit que Caml essaie d'<i>unifier</i> l'expression "''<tt>expr</tt>''" avec le motif "''<tt>pattern1</tt>''"). Si il y parvient, il évalue l'expression "''<tt>expr1</tt>''" et renvoie la valeur correspondante. Caml regarde tous les motif dans l'ordre.

Par exemple,
<source lang="ocaml">
match (2+2) with
1 -> "Problème."
| 3 -> "Problème."
| 4 -> "Ouf"
| _ -> "problème."
</source>
s'évaluera en la valeur <tt>"Ouf"</tt>.


Le motif "<tt>_</tt>" est un motif ''universel'', et permet de faire ce que l'on ferait avec un "<tt>else</tt>" en Pascal. Le véritable avantage de filtrage de Caml se voit dans le filtrage sur les types ''"composés"'' comme les tuples, les listes ou les types sommes. Le filtrage permet de "déconstruire" une valeur en ces différents constituants. Par exemple, voici comment on pourrait programmer 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 essaie de faire coïncider la valeur de "<tt>e</tt>" avec un truc de la forme "<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 écrire des motifs plus intéressants comme
<source lang="ocaml">
let imaginaire_pur x = match x with
(0,_) -> true
| _ -> false
</source>
qui permettra de tester si la première coordonnée (partie réelle d'une nombre complexe) est nulle ou pas. On aura pu écrire de manière équivalente :
<source lang="ocaml">
let imaginaire_pur x = if (fst x = 0) then true else false
</source>

::<u> Question :</u> à votre avis, que fait la fonction suivante :
<source lang="ocaml">
let une_fonction x = match x with
(1,(y,z)) -> y-z
| (0,(y,z) -> y+z
| (-1,(y,z) -> z-y
| (_,(y,_) -> y
</source>


:'''Attention :''' les variables qui apparaissent dans les motifs « écrasent » les variables de même nom qui peuvent apparaître avant dans l'expression :
<source lang="ocaml">
let f x = match x with
(x,_) -> x
</source>
:calcule la fonction "<tt>fst</tt>". De plus, les motifs ne sont pas évalués : dans
<source lang="ocaml">
let un = 1
let g x = match x with
un -> 1
| 2 -> 2
| _ -> 3
</source>
:la fonction "<tt>g</tt>" prendra toujours la valeur <tt>1</tt> car le "<tt>un</tt>" est considéré comme un nom de variable...


Pour filtrer sur une liste, on utilise "<tt>[]</tt>" et "<tt>::</tt>". 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>
On peut écrire des fonctions comme
<source lang="ocaml">
let un_element l = match l with
[x] -> true
| _ -> false
let deux_elements l = match l with
x::y::[] -> true
| _ -> false
let trois_element_ou_plus l = match l with
_::_::_::_ -> true
| _ -> false
</source>



--- complément sur l'unification, un peu plus de détails ?
--- un motif qui contient juste une variable est universel


:'''Compléments syntaxiques :''' Caml définit les sucres syntaxiques suivants
:* "or pattern" : on peut grouper plusieurs motifs qui définissent les mêmes variables et donnent la même expression
<source lang="ocaml">
let f x = match x with
0::l | 1::l | 1::l -> l (* on groupe 3 motifs en une seule ligne *)
| [] -> []
| x::_ -> [x]
</source>
:* "garde pour les motifs" : 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>
:* fonction par filtrage : 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====

Nous avons vu que Caml était un langage fortement typé : toutes les expressions ont un type, et on ne peut appliquer des fonctions que lorsqu'elles ont ses arguments ont le bon type.

Quel est le type de la fonction "<tt>fst</tt>" ?
<source lang="ocaml">
let fst = function (x,_) -> x
</source>
Cette fonction est à la fois de type "<tt>int * int -> int</tt>", "<tt>int * float -> int</tt>", ... Pour Caml, cette fonction est de type "<tt>t1 * t2 -> t1</tt>" pour n'importe quels types "<tt>t1</tt>" et "<tt>t2</tt>". Caml dénote un tel type avec de guillemets simples de la manière suivante :
<source lang="ocaml">
# let fst = function (x,_) -> x ;;
val fst : 'a * 'b -> 'a = <fun>
</source>


:''Complément : '' même si cela ne vous arrivera probablement pas dans un premier temps, sachez que seuls les valeurs ''évaluées'' peuvent être polymorphes. Par exemple, dans
<source lang="ocaml">
# let i x = x
let j = i i ;;
val i : 'a -> 'a = <fun>
val j : '_a -> '_a = <fun>
</source>
:l'expression "<tt>j</tt>" n'est pas vraiment polymorphe. (C'est le sens du "<tt>_</tt>" devant le "<tt>a</tt>".) Le "<tt>'_a</tt>" veut dire : « ''la fonction "<tt>j</tt>" a pour type "<tt>t -> t</tt>", mais je ne connais pas encore ce type "<tt>t</tt>".)'' »
:Dés que l'on applique "<tt>j</tt>" à quelque chose, Caml pourra savoir quel est le type de "<tt>j</tt>" :
<source lang="ocaml">
# j 42 ;;
- : int = 42
# j ;;
- : int -> int = <fun>
</source>


:'''Remarque :''' polymorphisme « ad-hoc »...
--- à faire

==Les types avec constructeurs (types ''sommes'')==

Nous avons vu en TP qu'il était possible de définir un ''synonyme de type'' avec le mot clé <tt>type</tt> : par exemple
<code lang="ocaml">
type point = float * float
</code>
permet de définir un nouveau type appelé "<tt>point</tt>". Les valeurs de ce type sont exactement les même que celle de type "<tt>float*float</tt>". C'est bien, mais ça ne permet de définir de ''nouveaux'' types.


===Déclaration des types sommes===

La notion de ''type avec constructeur'' est centrale dans les langage fonctionnelle de la famille ML ou Miranda. Ces types vont pouvoir par exemple servir à définir des types finis :
<source lang="ocaml">
type jours = Lundi | Mardi | Mercredi | Jeudi | Vendredi | Samedi | Dimanche
</source>

Pour déclarer un type avec constructeur, on utilise "<tt>type ''nom_type'' = ''Constr_1'' | ... | ''Constr_n''</tt>" où :
* <tt>''nom_type''</tt> est le nom du type que l'on définit. Ce nom doit forcement commencer par une minuscule. (Comme les types prédéfinis : <tt>int</tt>, <tt>float</tt>, ...)
* <tt>''Constr_1''</tt> et suivants sont les ''constructeurs'' du type. Les constructeurs commencent forcément par une majuscule.


Les types avec constructeurs deviennent plus intéressant lorsque l'on rajoute des ''arguments'' à certains constructeurs. Par exemple, supposons que l'on écrive un programme qui manipule des opérations géométriques dans le plan. On pourra définir le type suivant :
<source lang="ocaml">
type op = Symetrie_centrale | Rotation of float | ...
</source>
Un élément de ce type est soit :
* une symétrie centrale (pas besoin d'argument),
* une rotation autour de l'origine, avec un argument de type <tt>float</tt> : l'angle de la rotation. Voici quelques exemples de valeurs de type "<tt>op</tt>": "<tt>Symetrie_centrale</tt>", "<tt>Rotation (45.0)</tt>", "<tt>Rotation (0.0)</tt>" ou "<tt>Rotation (-360.0)</tt>".


:'''Attention :''' on pourrait penser que "<tt>Rotation</tt>" est une fonction qui prend un argument. Ça n'est pas le cas. "<tt>Rotation</tt>" est un ''constructeur'' qui doit nécessairement s'utiliser avec exactement un argument. (Les parenthèses sont facultatives, mais conseillées.



Comme on a le droit d'utiliser n'importe quel type comme argument d'un constructeur, voici ce qu'on pourrait mettre dans le type "<tt>op</tt>":
<source lang="ocaml">
type op = Symetrie_centrale | Rotation of float | Translation of float*float | Homothetie of float
</source>
De cette manière, on a également les translation selon un vecteur (donné par deux coordonnées flottantes) ou une homothétie de facteur flottant. Voici des nouvelles valeurs dans le type "<tt>op</tt>" : "<tt>Translation (0.0 , 1.0)</tt>", "<tt>Translation (1.3 , 3.5)</tt>" ou "<tt>Homothetie (2.0)</tt>".


:'''Remarque :''' les types avec constructeurs sont aussi appelés ''types sommes''. La raison est que le type des paires (<tt>''type_1'' * ''type_2''</tt>) est appelé ''type produit'' pour une raison évidente : il correspond au produit cartésien. De manière un peu similaire, les type avec constructeurs permettent de faire l'opération ''d'union disjointe'' sur les types. Par exemple, le type "<tt>C1 of ''type_1'' | C2 of ''type_2''</tt>" représente exactement la réunion disjointe des types <tt>''type_1''</tt> et <tt>''type_2''</tt>.


Bien entendu, un constructeur de type somme peut avoir des arguments dont le type est lui même un type somme...



Voici deux examples de types sommes definis par Caml : le premier est simplement le type <tt>bool</tt> :
<source lang="ocaml">
type bool = true | false
</source>
Ce type, comme le type des listes est en fait défini à un niveau plus bas ; et c'est pourquoi ses constructeurs peuvent commencer par une minuscule.

Le second type interessant est le type <tt>'a option</tt> :
<source lang="ocaml">
type 'a option = None | Some of 'a
</source>
La première remarque est que ce type est ''paramétré'' par un autre type : "<tt>'a</tt>". Autrement dit, on peut parler du type "<tt>int option</tt>", ou du type "<tt>(float -> bool) option</tt>".

Le type <tt>int option</tt> contient tous les entiers (sous la forme <tt>Some ''n''</tt>), mais également une valeur speciale <tt>None</tt>. On s'en sert en particulier pour modeliser les programmes non totaux. (Ceux qui ne donnent pas toujours une valeurs.) La valeur <tt>None</tt> joue un peu le role du pointeur <tt>NULL</tt> ou de l'entier <tt>-1</tt>.

===Filtrage===

On peut examiner une valeur d'un type somme grâce à l'égalité, mais cela ne permet pas d'accéder aux arguments d'un constructeur :
<source lang="ocaml">
let weekend (j:jours) = if (j=Samedi) || (j=Dimanche)
then true
else false
</source>

Par exemple, si on veut tester si une opération géométrique (type <tt>op</tt>) est une rotation, comment faire ?


On utilise le filtrage...

Le filtrage sur un type somme permet de faire comme un <tt>case of</tt> de Pascal, mais permet en plus de récupérer les valeur des arguments des constructeurs dans des variables.
<source lang="ocaml">
let rotation (o:op) =
match o with
Symmetrie_centrale -> false
| Rotation (a) -> true
| Translation (x,y) -> false
| Homothetie (z) -> false
</source>
Dans le filtrage précèdent, les variables <tt>a</tt>, <tt>x</tt>, <tt>y</tt> et <tt>z</tt> servent à récupérer les valeurs des arguments des constructeurs.

Comme lors du filtrage sur les listes ou les tuples, on peut décider d'ignorer certaines valeurs avec des motifs universels. Voila une seconde version de la fonction précédente :
<source lang="ocaml">
let rotation (o:op) =
match o with
Rotation (_) -> true
| _ -> false
</source>

===Types récursifs===

La véritable puissance des types sommes est dans l'utilisation des types sommes récursifs. Nous avons écrit des fonctions récursive, mais il existe également des types récursifs. Par exemple, en Pascal, le type des liste simplement chaînées s'écrit
<source lang="pascal">
type
liste = ^cellule;
cellule = record
valeur: integer ;
suivant: liste;
end;
</source>
C'est un type récursif : une liste, c'est un pointeur vers une cellule, càd vers un entier et une liste.

En Caml, le type des listes simplement chaînées s'obtient plus simplement avec :
<source lang="ocaml">
type liste = Cons int*liste
</source>
Autrement dit, une liste est donnée par un entier et une liste.

Comme le pointeur vide n'existe pas en Caml, et que de toute façon, une liste n'est pas vraiment un pointeur, il faut en fait rajouter la possibilité d'avoir la liste vide :
<source lang="ocaml">
type liste = Vide | Cons int*liste
</source>

:'''Remarque :''' alors que pour définir une fonction récursive, en doit utiliser le mot clé "<tt>rec</tt>", pour définir un type, il n'y a pas de mot clé spécial.


Finalement, comme les type ont le droit d'avoir des paramètres, on peut donner le type des listes contenant un type arbitraire avec :
<source lang="ocaml">
type 'a liste = Vide | Cons of 'a*'a liste
</source>
'''Attention :'''
# les paramètres d'un types sont précédés d'un guillemet simple,
# on doit mettre les paramètres avant le nom du type,
# il ne faut pas oublier de remettre les paramètres lors des appels récursifs au type.


La définition du type <tt>liste</tt> est équivalente à la définition du type <tt>list</tt> de Caml. Une des différences est que Caml utilise "<tt>[]</tt>" comme constructeur de liste vide, et "<tt>::</tt>" plutôt que "<tt>Cons</tt>". (Ce ne sont pas des constructeurs valides pour les types définis par l'utilisateur.)


On peut utiliser le filtrage comme pour un type somme non récursif. Voici par exemple la fonction qui convertit une liste à nous en une liste de Caml :
<source lang="ocaml">
let rec liste2list : 'a liste -> 'a list = function
Vide -> []
| Cons (a,l) -> a::(liste2list l)
</source>
(Remarquez l'utilisation du mot clé "<tt>function</tt>" à la place de "<tt>fun l -> match l with</tt>".)


De nombreux types de données sont facilement définissables par un type inductif correspondant. Les seuls types qui posent problème sont les types impératifs (tableaux par exemple) ou les types cycliques (listes doublements chaînées).

Nous verrons plus tard par quoi remplacer ces types, ou comment les utiliser...

==Les structures==

===Définition du type===

Caml permet de définir des ''structures'' : ce sont des tuples, mais où les éléments ont un nom. Il faut commencer par définir le type :
<source lang="ocaml">
type etat_tortue= {
coord_x : int ;
coord_y : int ;
angle : float ;
penup : bool
}
</source>

Notez l'utilisation du mot clé <tt>type</tt> pour faire une définition de type. Chaque ''champs'' de la structure est déclaré par "<tt>''id'' : ''type''</tt>", où <tt>''id''</tt> est le nom du champs (commençant forcement par une minuscule) et <tt>''type''</tt> est le type du champs.

Il n'y a pas de mot clé particulier pour dire que l'on définit une structure : ce sont les accolades "<tt>{</tt>" et "<tt>}</tt>" qui disent à Caml ce qu'il faut faire.


:'''Attention :''' les noms des champs des structures doivent être unique (au moins à l'intérieur de chaque fichier). Vous ne pouvez donc pas avoir un type "<tt>triangle</tt>" avec des champs "<tt>coord_x</tt>" ou "<tt>angle</tt>" dans le même fichier.


===Définition des valeurs===

Pour définir une valeur d'un tels type, on utilise une syntaxe similaire à la définition du type :
<source lang="ocaml">
let tortue_initiale : etat_tortue = {
coord_x = 0 ;
coord_y = 0 ;
angle = 0.0 ;
penup = false
}
</source>

Notez une fois encore l'utilisation des accolades, et l'utilisation du symbole "<tt>=</tt>" pour définir les valeurs des champs de la structure.

Comme d'habitude, le type est facultatif :
<source lang="ocaml">
let tortue_initiale : etat_tortue = {
coord_x = 0 ;
coord_y = 0 ;
angle = 0.0 ;
penup = false
}
</source>
est une définition valide.


===Projections===

Pour accéder à un champs dans une structure, on utilise le point "<tt>.</tt>" suivi du nom du champs :
<source lang="ocaml">
let distance_carree_origine (t:etat_tortue) : int = t.coord_x * t.coord_x + t.coord_y * t.coord_y
</source>


===Filtrage===

On peut utiliser le filtrage sur une structure. Quand on fait ceci, on n'est pas obligé de préciser tous les champs :
<source lang="ocaml">
... match t with
{ coord_x = x ; coord_y = y } -> ... x ... y ... (* x et y contiennent les coordonnées de la tortue *)
</source>

==Les exceptions==

Les exceptions de Caml sont un mécanisme assez polyvalent permettant surtout :
* de gérer des erreurs lors de l'évaluation d'une valeur,
* de gérer le flot de contrôle des programmes.

A plusieurs point de vue, les exception de Caml sont similaires aux exception de Java ou de Pascal. Une des différences cependant, c'est que ''les exceptions en Caml ne sont pas exceptionnelles''.



===Exceptions comme erreurs===


====Exemples====

Bien que typées correctement, certaines expressions provoquent des erreurs lors de leur évaluation : par exemple,
<source lang="ocaml">
let pb1 = 1 / 0
</source>
et
<source lang="ocaml">
let pb2 = List.hd []
</source>
provoquent respectivement les messages suivant de la part de Caml :
<source lang="ocaml">
Exception: Division_by_zero.
</source>
et
<source lang="ocaml">
Exception: Failure "hd".
</source>

Le message d'erreur doit être interprété comme : ''"J'ai rencontré un truc bizarre, alors je m'arrête, et je donne le nom du truc bizarre que j'ai rencontré"'' :
* <tt>Division_by_zero</tt> pour indiquer ... une division par 0,
* <tt>Failure "hd"</tt> pour indiquer une erreur lors de l'évaluation de la fonction <tt>hd</tt> sur un argument.

L'intérêt d'utiliser une exception plutôt que d'utiliser le type <tt>option</tt>, c'est que dans les cas d'utilisation normale, on manipule le résultat comme d'habitude. C'est seulement dans le cas exceptionnel que l'erreur est automatiquement propagée.


====Provoquer des erreurs====

Caml possède un type <tt>exn</tt> contenant les exceptions. Ce type est un peu comme un type somme, et <tt>Division_by_zero</tt> est un constructeur de ce type :
<source lang="ocaml">
Division_by_zero ;;
- : exn = Division_by_zero
</source>
Autrement dit, <tt>Division_by_zero</tt> est une valeur comme les autres. ''Ça n'est pas une erreur !''.


Il est possible de ''provoquer'' soit même des erreurs quand on veut. On dit que l'on ''lève une exception''. Le mot clé correspondant est <tt>raise</tt>. Lever l'exception <tt>Division_by_zero</tt> n'a pas beaucoup d'utilité, mais l'exception <tt>Invalid_argument</tt> peut être utile :
<source lang="ocaml">
let rec fib n =
if n<0 then raise (Invalid_argument "fib : indice negatif")
else if n<2 then n
else fib (n-1) + fib (n-2)
</source>
L'expression <tt>raise (Invalid_argument "fib : indice negatif")</tt> permet de provoquer l'erreur <tt>Invalid_argument</tt> avec l'argument <tt>"fib : indice negatif"</tt>...

L'évaluation de <tt>fib</tt> sur des entiers positifs marche normalement, mais appeler <tt>fib (-1)</tt> provoquera la chose suivante :
<source lang="ocaml">
Exception: Invalid_argument "fib : indice negatif".
</source>


:'''Remarque :''' moralement, le constructeur <tt>Invalid_argument</tt> a été déclaré avec <tt>Invalid_argument of string</tt>.



Il est important de constater que lorsque Caml rencontre une telle exception, l'évaluation s'arrête : par exemple dans
<source lang="ocaml">
let v =
let pb = fib (-1) in
(* gros calcul qui n'utilise pas la variable pb *)
...
</source>
Caml ne fait pas le gros calcul en question, mais s'arrête dés qu'il a rencontré l'exception. On se sert donc parfois des exceptions pour stopper l'exécution d'un programme où on veut...


====Déclarer une nouvelle exception====

Caml utilise certains types d'erreurs génériques. Les plus courants sont
* <tt>Not_found</tt> pour dire que quelque chose n'a pas été trouvé,
* <tt>Failure of string</tt> pour signaler une erreur lors que l'exécution d'un programme,
* <tt>Invalid_argument of string</tt> pour signaler un argument invalide,
* <tt>Match_Failure of string*int*int</tt> pour signaler un problème lors d'un filtrage.

Si on veut déclarer un nouveau type d'erreur, on utilise la syntaxe
<source lang="ocaml">
exception Mon_erreur of string*int
</source>
Les arguments du constructeur d'exception servent en général à donner des information sur l'erreur :
<source lang="ocaml">
let rec fib n =
if n<0 then raise (Mon_erreur ("Indice negatif pour fib",n))
else if n<2 then n
else fib (n-1) + fib (n-2)
</source>
permet de donner la valeur de l'indice qui a provoqué l'erreur de <tt>fib</tt>


Le mot clé <tt>exception</tt> précise que l'on déclare une exception, et on utilise ensuite la même syntaxe que pour les constructeurs.


:'''Remarque :''' la différence entre le type des exceptions et les types sommes, c'est que pour les exceptions, on peut rajouter des constructeurs au fur et à mesure... (Il existe une variante des types avec constructeurs qui permet de faire ça, mais on n'en parlera pas en cours.)


En général, on utilise les exceptions prédéfinies de Caml quand elles correspondent à l'erreur en question :
* <tt>Not_found</tt> pour une fonction comme <tt>cherche_cle</tt> du TD4 par exemple,
* <tt>Invalid_argument</tt> pour préciser qu'un argument n'est pas correct, càd qu'une fonction n'est pas utilisée correctement,
* <tt>Failure</tt> pour indiquer que la fonction ne c'est pas terminée correctement, par exemple dans la fonction <tt>supprime_cle</tt> du TD4, pour préciser que la clé qu'on essaie de supprimer n'existe pas.


:'''Remarque :''' il n'est pas toujours facile de décider si l'on veut utiliser <tt>Failure</tt> ou <tt>Invalid_argument</tt>. Ça n'est pas très grave...


====Gestion des erreurs====

Provoquer des erreurs, c'est bien, mais si on ne peut rien en faire, ça ne sert à rien... Pour gérer les exceptions, on utilise ... un ''gestionnaire d'exceptions'', aussi appelé ''exception handler'' en anglais.

Moralement, on explique à Caml : ''"fait ce truc là, mais si tu rencontre cette exception, fait ce truc là à la place"''. Sauf qu'on écrit
<pre>
try ce_truc_là
with cette_exception -> ce_truc_là_à_place
</pre>

Par exemple, vous voulez utiliser le premier élément d'une liste, mais si cette liste est vide, vous voulez utiliser 0 à la place. Pour faire ça en utilisant la fonction <tt>List.hd</tt> et les exceptions, on peut écrire :
<source lang="ocaml">
...
let element =
try List.hd l
with Failure "hd" -> 0
</source>

Tout comme pour le filtrage, on peut mettre plusieurs motifs pour le gestionnaire d'exception :
<source lang="ocaml">
try expr
with
Division_by_zero -> -1
| Failure _ -> -2
| Invalid_argument "hd" -> -3
| Invalid_argument _ -> -4
| _ -> raise Probleme_inconnu
</source>

Tout comme un <tt>let x = val in expr</tt> est une unique expression, un <tt>try expr with ...</tt> est une unique expression. Un <tt>try expr with ...</tt> a donc une valeur ; et cette valeur est calculée comme suit :
# Caml évalue l'expression <tt>expr</tt> : si l'évaluation se termine correctement, alors en renvoie la valeur trouvée
# si l'évaluation provoque une exception, alors on regarde si l'exception est prise en compte par le gestionnaire : si oui, on utilise le gestionnaire pour calculer une nouvelle valeur,
# si l'erreur n'est pas prise en compte, on la laisse, et l'évaluation se termine donc par une erreur.


:'''Remarque :''' un gestionnaire d'erreur peut lui même provoquer des erreurs. Dans ce cas, l'erreur est propagée, sauf si le gestionnaire d'erreur contient lui-même un gestionnaire d'erreurs !


===Exception et flot d'exécution===

Même si elles ne sont pas nécessaires, les exceptions permettent parfois (souvent) d'écrire du code un peu plus lisible (plus simple) et plus efficace. Elle permettent au programmeur de modifier le flot d'exécution de son programme...


====Les instructions <tt>break</tt> et <tt>continue</tt> des langages impératifs====

En C, Java ou Pascal, on peut (mais c'est mal) utiliser des instructions comme <tt>break</tt> (sortie d'une boucle), <tt>continue</tt> (passage direct à l'itération suivante), ou le <tt>goto</tt> démoniaque (sauter directement à un endroit arbitraire dans le programme).

Ce qu'ont en communs ces constructions, c'est de modifier l'ordre habituelle d'exécution du programme. C'est ce qui les rends difficile à utiliser, car on ne n'est jamais très sur de ce qui va se passer. (C'est en particulier vrai pour le <tt>goto</tt>.)

Les exceptions de Caml permettent de faire des choses similaires (modifier l'exécution du programme), mais de manière propre.


====gestion du flot en Caml====



====Exemples et points importants====


Attention pour les fonctions récursives


==La récursivité terminale==

Contrairement à la programmation impérative (C, Pascal ou même Java), la structure de base pour « itérer » un programme en programmation fonctionnelle est la récursion. Le problème de cette méthode de programmation est que lors de chaque appel récursif, le compilateur / interpréteur doit sauvegarder tout l'environnement (valeur de toutes les variables nécessaires à l'évaluation) pour pouvoir les retrouver après l'appel récursif. Par exemple, dans
<source lang="ocaml">
let rec fact n =
if n<1
then 1
else n*(fact (n-1))
</source>
l'interprète doit sauvegarder la valeur de <tt>t</tt> pour pouvoir, une fois la valeur de <tt>fact (n-1)</tt> calculer le résultat final (à savoir, <tt>n*(fact (n-1))</tt>. Chaque appel récursif consomme donc de la mémoire car toutes les valeurs successive sont ''empilées'', pour être ensuite ''dépilées'' lors du calcul final. Plus on fait d'appel récursif, et plus l'environnement est gros (par exemple s'il contient des listes de grande taille) et plus on court le risque que l'interprète Caml nous rende la fameuse phrase <tt>stack overflow</tt>. C'est-à-dire que le calcul prend trop de place mémoire : la pile (''stack'' en anglais) est pleine.

Dans certain cas, la sauvegarde du contexte ne sert à rien car il n'y a plus de calcul après l'appel récursif. Par exemple pour le calcul du dernier élément d'une liste :
<source lang="ocaml">
let rec dernier l = match l with
[] -> raise (Invalid_argument "dernier")
| [a] -> a
| _::l -> dernier l
</source>
l'environnement ne sert à rien, car une fois que l'appel récursif <tt>dernier l</tt> est évalué, il ne reste plus rien à faire...

On parle dans ce cas d'appel '''récursif terminal''', et l'interprète Caml les détecte et ne sauvegarde pas l'environnement.

Il est parfois (souvent ?) possible de transformer une fonction récursive en une fonction récursive où tous les appels sont récursifs terminaux. Pour la fonction factorielle on peut créer une fonction auxiliaire avec un argument supplémentaire :
<source lang="ocaml">
let fact n =
let rec fact_aux n acc =
if n<1
then acc
else fact_aux (n-1) (acc*n)
in fact_aux n 1
</source>


Un autre exemple :
<source lang="ocaml">
let longueur l =
let rec aux l acc = match l with
[] -> acc
| a::l -> aux l acc+1
in aux l 0
</source>


<u>Remarque :</u> si on veut être précis, les résultats emmagasinés par l'accumulateur se font dans l'ordre inverse du calcul récursif. Pour la fonction factorielle récursive, la première multiplication a lieu lors de l'appel à <tt>fact 2</tt> qui devient <tt>2*(fact 1)</tt>, càd <tt>2*1</tt>. Cette valeur est ensuite redonné à <tt>fact 3</tt> etc. Dans la fonction auxiliaire récursive terminale, la première multiplication est <tt>n*acc</tt>, càd <tt>n*1</tt> : les multiplication se font dans l'ordre opposé.

Ceci est particulièrement important pour les fonctions récursives renvoyant des listes, où les fonctions récursives terminales (comme <tt>List.fold_left</tt>) ont souvent tendance à rendre une liste renversé. Dans ce cas, il suffit de renverser la liste tout à la fin du calcul. (Et il ne faut surtout pas construire les liste en insérant à la fin de l'accumulateur !)

==Les modules==

La notion de ''modules'' et de ''foncteur'' (ou module paramétré) est une manière d'encapsuler en ensemble de définitions (types, exceptions, fonctions, ...) dans une unité. Certaine librairies sont offertes par l'intermédiaire de modules (les librairies <tt>Map</tt> et <tt>Set</tt> par exemple). Certaines autres librairies (comme <tt>List</tt>) ne contiennent pas de module explicite, mais comme un fichier est plus ou moins considéré comme un gros module, la différence n'est pas énorme.


===Exemple simple : les piles===

Imaginons que nous voulons créer un type de données pour les ''piles''. Nous devons définir un type de données, une fonction <tt>push</tt> et une fonction <tt>pop</tt> :
<source lang="ocaml">
type 'a pile = 'a list (* on représente une pile par une liste *)
let push : 'a -> 'a pile -> 'a pile = fun a l -> a::l
let pop : 'a pile -> 'a * 'a pile = function a::l -> (a,l)
</source>

Nous pouvons déclarer et créer un module <tt>Pile</tt> contenant toutes ces définitions avec
<source lang="ocaml">
module Pile = struct
type 'a pile = 'a list (* on représente une pile par une liste *)
let push : 'a -> 'a pile -> 'a pile = fun a l -> a::l
let pop : 'a pile -> 'a * 'a pile = function a::l -> (a,l)
end
</source>
Lorsqu'on interprété le module, Caml répond en nous donnant ''l'interface'' du module :
<source lang="ocaml">
module Pile :
sig
type 'a pile = 'a list
val push : 'a -> 'a pile -> 'a pile
val pop : 'a pile -> 'a * 'a pile
end
</source>

Un module est un peu comme une structure avec des champs : on accède au contenu avec la notation <tt>nom_module.champ</tt> :
<source lang="ocaml">
let vide : int Pile.pile = []
let p = Pile.push 0 vide
</source>


De manière générale, on essaie de fournir une interface complète pour utiliser les données :
<source lang="ocaml">
module Pile = struct
type 'a pile = 'a list (* on représente une pile par une liste *)
exception Pile_Vide
let vide : 'a pile = []
let est_vide : 'a pile -> bool = function
[] -> true
| _ -> false
let push : 'a -> 'a pile -> 'a pile = fun a l -> a::l
let pop : 'a pile -> 'a * 'a pile = function
a::l -> (a,l)
| [] -> raise Pile_Vide
end
</source>


===Cacher certains champs, types abstraits===

Il est parfois intéressant de fournir un type de données avec des fonctions, sans pour autant expliquer comment le type est vraiment définit. On demande à l'utilisateur de n'utiliser que les fonctions fournies pour manipuler le type. Cette approche présente des intérêts dans des cas comme les arbres équilibrés, où les fonctions fournies garantisse l'équilibre, alors que le type (arbres binaires) ne le garantit pas. Ainsi, si l'utilisateur n'utilise que les fonctions fournies, tout se passera bien.

Pour éviter que l'utilisateur ne construise lui même des arbres à la main, il est possible de ''cacher'' la définition d'un type en donnant un type au module. Par exemple :
<source lang="ocaml">
module type Pile_Type = sig
type 'a pile (* je ne met pas la définition du type *)
exception Pile_Vide
val vide : 'a pile
val est_vide : 'a pile -> bool
val push : 'a -> 'a pile -> 'a pile
(* je ne déclare pas la fonction pop *)
end

module Pile : Pile_Type = struct
type 'a pile = 'a list (* on représente une pile par une liste *)
exception Pile_Vide
let vide : 'a pile = []
let est_vide : 'a pile -> bool = function
[] -> true
| _ -> false
let push : 'a -> 'a pile -> 'a pile = fun a l -> a::l
let pop : 'a pile -> 'a * 'a pile = function
a::l -> (a,l)
| [] -> raise Pile_Vide
end
</source>
Le fait de donner explicitement l'interface du module (sa ''signature'') permet de cacher certaines fonctions :
<source lang="ocaml">
# Pile.push ;;
- : 'a -> 'a Pile.pile -> 'a Pile.pile = <fun>
# Pile.pop ;;
Unbound value Pile.pop
# Pile.vide ;;
- : 'a Pile.pile = <abstr>
</source>

<tt>push</tt> existe normalement, mais <tt>pop</tt>, comme elle n'a pas été déclarée dans la signature, n'est pas utilisable à l'extérieur du module. (C'est une fonction locale au module.) De plus, la ''définition'' du type <tt>'a pile</tt> n'est pas non plus utilisable à l'extérieur du module. La valeur de <tt>vide</tt> est donc une valeur ''abstraite''.




===Les foncteurs===
== Les types algébrique ==


Les ''foncteurs'' sont simplement des modules paramétrés par d'autres modules. Par exemple, si on a un module <tt>TypeOrdonne</tt> :
<source lang="ocaml">
module type Type_Ordonne = sig
type element
val plus_petit : element -> element -> bool
end
</source>
on peut vouloir définir le type des ''ensembles'' d'éléments, avec la signature suivante : On peut donc déclarer :
<source lang="ocaml">
module type ENSEMBLE = sig
type element
type ensemble
val vide : ensemble
val egal : ensemble -> ensemble -> bool
val appartient : element -> ensemble -> bool
val ajoute : element -> ensemble -> ensemble
val supprime : element -> ensemble -> ensemble
val union : ensemble -> ensemble -> ensemble
val intersection : ensemble -> ensemble -> ensemble
val difference : ensemble -> ensemble -> ensemble
...
end
</source>


== Les structures ==
Pour faire ça, le plus simple (mais pas le plus efficace) est de modéliser un ensemble d'éléments par une liste triée sans doublons. Pour pouvoir trier la liste, il faut donc avoir une fonction de comparaison. On définit donc un ''foncteur'' qui va transformer un <tt>Type_Ordonne</tt> en <tt>ENSEMBLE</tt> :
<source lang="ocaml">
module FaireEnsemble (O : Type_Ordonne) : ENSEMBLE with type element = O.element =
struct
type element = O.element
type ensemble = O.element list
let vide = []
let egal e1 e2 = (e1=e2)
let rec appartient a e = match e with
[] -> false
| b::e -> a=b || appartient a e
let rec ajoute a e = match e with
[] -> [a]
| b::e when (O.plus_petit a b) && (O.plus_petit b a) -> a::b::e
| b::e when (O.plus_petit a b) -> a::b::e
| b::e -> b::(ajoute a e)
...
end
</source>


:<u>exercice :</u> finissez l'implantation du foncteur <tt>FaireEnsemble</tt>.


== La récursivité terminale ==
Une fois ce module terminé, vous pouvez définir le type des <tt>ENSEMBLES</tt> sur n'importe quel type avec une comparaison :
<source lang="ocaml">
module Int_Ordonne : Type_Ordonne = struct
type element = int
let plus_petit n m = n-m <= 0
end
module Ensemble_Int = FaireEnsemble(Int_Ordonne)
</source>




== Les exceptions ==
:'''Remarque :''' les librairies Caml contiennent une implémentation efficace pour les ensembles finis (ou pour les dictionnaires) basée sur les arbres binaires de recherche bien équilibrés. Je vous conseille d'aller voir le fichier <tt>/usr/lib/ocaml/3.???/set.mli</tt> pour voir comment cela fonctionne.


==Aspects impératifs dans Caml==


== Aspects impératifs dans Caml ==
===Les références===


===Exemples===


===Les tableaux===
== Les modules ==

Version du 16 janvier 2013 à 12:10

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 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 ocaml, ocaml-core, ocaml-mode, tuareg-mode et emacs.
  • Sous MacOS : il semblerait qu'il y ait des paquets MacPorts pour ocaml, emacs et tuareg-mode.el.
  • Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : 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 OCaml en ligne

Références supplémentaires

Cours

TD et TP

Introduction

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

Attention : il ne s'agit pas d'un cours de programmation fonctionelle

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 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 : Computer Languages Timeline (ou découpé en pages A4).

Fonctionnel ??

L'adjectif fonctionnel a au moins deux sens :

  1. qui fonctionne, en état de marche,
  2. 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

Les fonctions sont des valeurs comme les autres

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, 

x = x+1

ou 

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

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) : Wikipedia, autre dialecte de la famille ML.
  • LISP, dont les deux dialectes principaux sont :
  • Haskell : Wikipedia (inspiré en grande partie de 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 :

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang (Wikipedia), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

Objectifs du cours

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

=

Premiers pas en Caml

Les types algébrique

Les structures

La récursivité terminale

Les exceptions

Aspects impératifs dans Caml

Les modules

Récupérée de « http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=INFO421_:_Programmation_fonctionnelle&oldid=5888 »