L'implémentation Caml que l'on utilisera dans ces TD/TP est Objective Caml, développé à l'INRIA (Institut National de Recherche en Informatique et Automatique) depuis 1984. Il s'appuie sur une expérience de conception de langage de la famille des langages fonctionnels ML ... c'est un lointain descendant du LISP. Il se veut universel en permettant 3 approches :
Il est basé sur un typage fort et intégre un système d'inférences de types : le programmeur n'a pas besoin de donner des informations de type, ceux-ci sont obtenus automatiquement par le compilateur.
Des références et liens sont donnés sur la page d'accueil de ce cours de programmation fonctionnelle. On notera notamment :
Dans ce sujet de TD/TP, on donne quelques compléments et rappels de cours qui ne prétendent pas être exhaustifs. Si plus d'informations sont nécessaires, vous pouvez consultez les références précédentes adaptées au niveau de précisions voulu (détail technique ou compréhension général d'un concept). Il est conseillé de reprendre et tester les exemples donnés, de les modifier ou d'en faire des variantes pour vous assurer de la bonne assimilation des notions introduites puis de faire les exercices proposés.
Objective Caml peut s'utiliser en 2 modes, interactif ou compilé. Le deuxième mode d'utilisation fera l'objet de travaux qui seront étudiés ultérieurement. On s'intéressera donc pendant un certain temps au premier mode. Il s'active en lançant dans une fenêtre "xterm", la commande ocaml. On se trouve alors face à une "boucle" d'interaction, similaire dans son principe à celle proposée par clisp.
L'option -I catalogue permet d'indiquer un chemin dans lequel se fera la recherche de fichiers sources ou compilés.
On dispose de plusieurs directives qui modifient le comportement de la boucle d'interaction. Ces directives commencent par # et se terminent par ;;. En voici quelques unes :
#quit;; permet de sortir de la boucle d'interaction
#directory catalogue;; permet d'ajouter un chemin de recherche
#use "fichier_source";; permet de charger des fichiers( en général d'extension .ml)
#trace fonction;; permet de lancer une trace des appels des fonctions
#untrace fonction;; ou #untrace all;; enlève la trace de la fonction ou toutes les traces.
Les types de base en Caml sont :
int représente des entiers relatifs munis des opérations classiques : +, -, *, / (division entière), mod (reste de la division entière) et les comparaisons (<, >, <=, >=).
float réprésente des réels munis des opérations standards désignées comme ci-dessus mais suivies d'un point : +. désigne l'addition réelle, par exemple.
char représente des caractères désignés entre quotes, 'a' par exemple, ou par leur code ascii précédé d'un \, '\065' par exemple, ou encore au moyen d'un symbole spécial précédé d'un \, '\n' désigne un saut de ligne par exemple.
bool représente des valeurs booléennes : true ou false. les opérateurs prédéfinis sont la négation not, la conjonction && et la disjonction ||.
string représente les chaînes de caractères désignées entre guillemets, "exemple de chaine". L'opérateur de concaténation est noté ^.
Une déclaration globale correspond à la liaison d'un symbole avec une valeur, comme en lisp. L'ensemble des liaisons constitue l'environnement. La forme d'une déclaration globale est la suivante :
#let an=2004;;
val an:int=2004
#let an2=an+1;;
val an2:int=2005
Attention : avec Objective Caml, les noms de variables et de fonctions doivent commencer par une minuscule (les noms commençant par une majuscule sont réservés pour désigner des constructeurs).
Les déclarations locales permettent de changer temporairement l'environnement, en introduisant des liaisons temporaires.
#let a=1 and b=2 in a*b;;
- : int = 2
Exercice 1 :
Prédire le résultat de la construction suivante. Le vérifier et expliquer l'évaluation.
#let a=1
in let a=2 and b=a
in a+b;;
Il s'agit d'une construction classique "if ... then ... else" qui doit renvoyer un résultat de même type pour chacune des deux clauses : celle qui suit le then et celle qui suit le else.
#if 2>3 then "etrange"
else 0;;
This expression has type int but is here used with type string
#if 2<3 then "etrange"
else "ok";;
- : string = "etrange"
failwith
L'utilisation de failwith provoque l'arrêt de l'évaluation en déclanchant une exception.
Exemple :
#let a=55 and x=0 in a/x;;
Uncaught exception: Division_by_zero.
#let a=55 and x=0 in
if x=0 then failwith "division par zero"
else a/x;;
Uncaught exception: Failure "division par zero"
==, teste si les valeurs occupent les mêmes zones mémoires.
==, test si les valeurs sont identiques en explorant les structures.
Exemple :
#"caml"="caml";;
- : bool = true
#"caml"=="caml";;
- : bool = false
Caml accepte plusieurs syntaxes de définition de fonction, telles qu'illustrées dans l'exemple suivant.
#let double = function x -> 2*x;;
val double : int -> int = <fun>
#let double x = 2*x;;
val double : int -> int = <fun>
#let double (x) = 2*x;;
val double : int -> int = <fun>
Le procédé d'inférence de type opère dans l'évaluation du type des paramètres de la fonction. Il peut conduire à désigner une indétermination du typage des paramètres et les déclarer de manière abstraite : on utilise pour cela un pseudo-type générique désigné par 'a ou par 'b, 'c, ... suivant le nombre de typages indéterminés que contient l'expression.
Exercice 2 :
Prédire le typage de la construction suivante. Le vérifier.
#let ident = function x -> x;;
Ce type de construction permet le polymorphisme : c'est à dire l'adaptation du programme (ou de la fonction) à des données de types différents qui se détermineront progressivement au cours de leur utilisation.
Une fonction à plusieurs variables s'écrit comme une fonction de fonction :
#let max = function n ->
function p ->
if n>p then n else p;;
val max : int -> int -> int = <fun>
Le typage renvoyé est une simplification de int -> (int -> int) .
On peut simplifier la construction précédente par :
#let max n p = if n>p then n else p;;
val max : int -> int -> int = <fun>
Une construction alternative consiste à définir une fonction sur un couple ou plus généralement sur un n-uplet.
#let max (n,p) = if n>p then n else p;;
val max : int * int -> int = <fun>
Exercice 3 : curryfication et décurryfication
Ecrire une fonction appelée curry qui transforme une fonction à 1 argument de type produit cartésien de 2 variables en une fonction à 2 arguments. Cette fonction doit pouvoir être utilisée comme suit :
#let modul (a,b) = a*a+b*b;;
#let modul2 = curry modul;;
#modul2 3 4;;
- : int =25
#let modul3 = uncurry modul2;;
#modul3 (3,4);;
- : int =25
Une fonction récursive doit être déclarée avec la construction "let rec ...". Ci-après, une nouvelle version de la fonction factorielle.
#let rec fact = function n ->
if n=0 then 1
else n*fact(n-1);;
Caml permet l'utilisation de paramètres fonctionnels de façon totalement abstraite. Ils sont utilisés directement, le système d'inférence de type se charge de les reconnaître.
Exemple : Calcul de la somme pour n allant de 1 à p de f(p) :
#let rec sigma (f,p) =
if p=1 then f(1)
else f(p)+sigma(f,p-1);;
val sigma (int -> int)*int -> int = <fun>
La forme élémentaire suivante évalue une expression par un jeu de "filtres". Les filtres sont appliqués dans l'ordre où ils apparaissent. L'évaluation correspond alors à la valeur associée au premier filtre applicable.
match exp with
p1 -> exp1
| p2 -> exp2
...
| pn -> expn;;
On utilise généralement cette construction dans des définitions de fonctions. Ci-après, le retour de la fonction factorielle ...
#let rec fact n = match n with
0 -> 1
| n -> n*fact(n-1);;
Dans le cas de la définition d'une fonction, on peut alors simplifier l'expression sous la forme suivante :
#let rec fact = function
0 -> 1
| n -> n*fact(n-1);;
Le filtrage conduit donc à une énumération de cas. Lorsque tous les cas restants doivent conduire au même résultat, on peut alors utiliser la construction :
| _ -> expression_commune;;
Exemple : Voici une encodage de l'implication logique.
#let implique = function
(true, false) -> false
| _ -> true;;
Exercice 4 :
Ecrire une fonction qui compose les 2 fonctions passées en argument. Appliquer cette fonction aux fonctions double et carre qui retournent respectivement le double et le carré de leur argument.
Exercice 5 :
Ecrire une fonction qui calcule la suite de Fibonacci : u(0)=u(1)=1 et u(n)=u(n-1)+u(n-2). On utilisera une consctruction à base de filtrage.
Exercice 6 :
Ecrire une fonction f qui, à son argument x, renvoie la fonction qui multiplie son propre paramètre par x. Voici après une exemple d'utilisation et du résultat retourné :
#(f(3))(4);;
- : int = 12
Exercice 7 :
Ecrire la fonction deriv qui renvoie le taux d'accroissement d'une fonction f en un point x, pour un accroissement dx. f, x et dx sont donnés en argument.
Exercice 8 :
Ecrire une fonction qui calcule le nombre minimum de pièces contenues dans une somme donnée, en n'utilisant que des pièces de 10, 5 ou 1 euros. Exemple : pour une somme de 87 euros, la fonction renverra 11 (8 pièces de 10 euros, 1 pièce de 5 euros et 2 pièces de 1 euro).
Exercice 9 :
Rechercher les informations sur le module String à partir du manuel de référence de Ocaml de X. Leroy (dont les références sont indiqués ci-dessus) de façon à trouver les fonctions qui permettent de connaître la longueur d'une chaîne de caractère ainsi que l'extraction d'une sous-chaîne. Par ailleurs, l'opérateur de concaténation est le symbole ^.
1. Ecrire une fonction qui inverse un mot. Exemple "CAML" sera transformé en "LMAC"
2. Ecrire une fonction qui reconnaît les palindrommes, comme "bob" ou "eluparcettecrapule".