Le langage fonctionnel Caml

Caml manipule des valeurs qui sont classées par types. Un type représente un ensemble de valeurs. Toute valeur appartient à un et un seul type. Il faut faire une distinction entre l'expression d'un type et son extension. L' expression d ' un type exprime la façon dont il est construit à partir d'autres types. L' extension d ' un type est l'ensemble des valeurs de ce type. Si t est une expression de type nous noterons ext ( t ) l'extension de t .

Les types constructibles en Caml seront étudiés pas à pas tout au long de ce cours. Pour débuter nous considérerons un sous-ensemble des types de Caml, que nous appellerons types de base . Ce sont les suivants :

• le type bool dont l'extension est constitué des valeurs true et false ( ext (bool) = {true, false}) ;
• le type int dont l'extension est l'ensemble des entiers appartenant à un intervalle dépendant de l'implémentation ([-2 ³⁰ , 2 ³⁰ -1] en général) ;
• le type float dont l'extension est l'ensemble des flottants appartenant à un intervalle dépendant de l'implémentation (si possible des flottants double précision à la norme IEEE) ;
• le type char dont l'extension est l'ensemble des caractères dont le code numérique est compris entre 0 et 255. Les caractères dont le code est compris entre 0 et 127 sont du standard ASCII et ceux dont le code est compris entre 128 et 255 dépendent de l'implémentation ;
• le type string dont l'extension est l'ensemble des chaînes de 0 à n caractères où n dépend de l'implémentation (65535 au minimum) ;
• le type unit dont l'extension ne contient qu'une seule valeur notée () et qui signifie « rien ».

Une valeur peut être nommée. Un nom de valeur est :

• soit un identificateur différent des mots-clés réservés. Par exemple :

Figure 1.1 : Les expressions de base

lon lar prénom1

• soit un symbole d'opérateur précédé du mot-clé prefix. Par exemple :

prefix + prefix >=

Les noms de valeurs sont aussi appelés variables . Ils doivent être différent des mots-clés réservés de Caml comme cela est classique dans la plupart des langages de programmation.

Une liaison est une association entre un nom et une valeur. Une liaison entre un nom n et une valeur v de type t sera notée :

n : t = v

Par exemple :

lon : int = 15

Un environnement est un ensemble de liaisons. Par exemple :

{lon : int = 15, lar : int = 5}

Au début d'une session Caml il existe un environnement initial qui contient des liaisons prédéfinies, nous l'appellerons Env _ init .

Un environnement peut être étendu par un autre environnement. L'extension d'un environnement Env ₁ par un environnement Env ₂ , que nous noterons Env ₁  Env ₂ , est obtenue en ajoutant les liaisons de Env ₂ aux liaisons de Env ₁ dont le nom n'est pas présent dans Env ₂ . On a :

Env1  Env2 = {n : t = v | n  Env1 et n  Env2 }  Env2

On constate que cette opération à pour effet de ne garder que les liaisons les plus récentes de chaque nom. Par exemple :

{lon : int = 10}  {lon : int = 15, lar : int = 5} = {lon : int = 15, lar : int = 5}

Une expression est une construction Caml destinée à être évaluée. Toute expression a un type et une valeur. Le type d'une expression est déterminé (on dit aussi synthétisé) par Caml avant son évaluation.

Le type et la valeur d'une expression Caml dépendent de l'environnement dans lequel elle est évaluée. Si e est une expression et Env un environnement nous noterons :

type(e, Env)

et :

val(e, Env)

le type et la valeur de e dans Env . Par la suite nous dirons qu'une expression e est valide dans un environnement Env , si type ( e , Env ) est calculable.

Les types et les expressions valides en Caml seront étudiés pas à pas tout au long de ce cours. Pour débuter nous considérerons un sous-ensemble d'expressions (voir Figure 1.1), que nous appellerons de base, qui sont construites à partir des valeurs, des noms de valeur, et d'opérateurs sur les entiers, les flottants et les chaînes de caractères.

Considérons, par exemple, l'environnement :

Env = {lon : int = 15, lar : int = 5}

On a :

type(2, Env) = int
type(lon, Env) = int
type(lar, Env) = int
type(lon + lar, Env) = int
type(2 * (lon + lar), Env) = int

et :

val(2 * (lon + lar), Env)
= val(2, Env) * val((lon + lar), Env)
= 2 * val(lon + lar, Env)
= 2 * (val(lon, Env) + val(lar, Env))
= 2 * (15 + 5)
= 40

Il est souvent nécessaire d'effectuer des calculs qui dépendent d'une condition. Pour cela Caml dispose d'une construction particulière : l' alternative . Une expression alternative a la forme suivante :

if e1 then e2 else e3

où e 1 est une expression de type bool et e 2 et e 3 sont des expressions de même type. Par exemple :

#if 10 > 5 then "Evidemment !" else "Bizarre !";;
- : string = "Evidemment !"

Les règles de typage et d'évaluation d'une alternative sont les suivantes :

On constate que selon la valeur de la condition, soit e ₂ , soit e ₃ sont évaluées mais pas les deux.

Il est possible d'omettre la partie else. On a :

if e1 then e2  if e1 then e2 else ()

ce qui implique que l'expression e ₂ soit elle-même de type unit.

Les expressions suivantes sont équivalentes à l'alternative :

e1 & e2  if e1 then e2 else false,
e1 or e2  if e1 then true else e2

Par exemple :

#(true or false) & true;;
- : bool = true

II-E-1. Définitions globales▲

let n1 = e1 and … and nk = ek;;

#let deux_fois_pi = 2. *. 3.14;;
deux_fois_pi : float = 6.28
#let lon = 15 and lar = 5;;
lon : int = 15
lar : int = 5

Env_courant  Env_def(let n1 = e1 and … and nk = ek, Env_courant).

Env_init  {rayon : float = 10., pi : float = 3.14}

let surface = 2. *. pi *. rayon;;

Env_init  {rayon : float = 10., pi : float = 3.14, surface : float = 62.8}

#let annee_courante = 1998;;
annee_courante : int = 1998
#2000 - annee_courante;;
- : int = 2
#let age = annee_courante - 1981;;
age : int = 17
#let annee_courante = 1999;;
annee_courante : int = 1999
#2000 - annee_courante;;
- : int = 1
#age;;
- : int = 17

#let lon = 5 and lon = 10;;
> Toplevel input:
>let lon = 5 and lon = 10;;
> ^^^
> Variable lon is bound twice in this pattern.

#let cote = 10 and périmètre = 4 * cote;;
> Toplevel input:
>let cote = 10 and périmètre = 4 * cote;;
> ^^^^
> Variable cote is unbound.

#let cote = 10;;
cote : int = 10
#let périmètre = 4 * cote;;
périmètre : int = 40

II-E-2. Définitions locales▲

let n1 = e1 and … and nk = ek in e

#8 * (let lon = 15 and lar = 5 in 2 * (lon + lar));;
- : int = 320

let lon = 15 and lar = 5 and hauteur = 30 in
let surface = lon * lar in surface * hauteur;;
- : int = 2250

La figure 1.2 schématise l'interaction entre le programmeur et l'interprète Caml au cours d'une session interactive.