83
Introduction aux fonctionnalités de base du langage Ocaml M.V. Aponte Année 2007/2008

Introduction aux fonctionnalités de base du langage Ocaml

  • Upload
    others

  • View
    3

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Introduction aux fonctionnalités de base du langage Ocaml

Introduction aux fonctionnalités de base

du langage Ocaml

M.V. Aponte

Année 2007/2008

Page 2: Introduction aux fonctionnalités de base du langage Ocaml

Pourquoi Ocaml?

• C’est un langage complet, concis et puissant:• traits fonctionnels, et impératifs,• système de modules génériques,• Programmation objet sophistiquée,• nombreuses librairies

• C’est un langage sûr et facile à employer:typage fort et inférence des types.

Documentation, distribution et plus de détails:http://caml.inria.fr/ocaml.

Page 3: Introduction aux fonctionnalités de base du langage Ocaml

Le mode compilé

Éditer le source

hello.mlprint_string "Hello World!\n";;

Compiler, lier et exécuter (sous le Shell d’Unix):

ocamlc -o hello hello.ml./helloHello World!

Page 4: Introduction aux fonctionnalités de base du langage Ocaml

Le mode intéractif

Dans ce mode, Ocaml analyse et répond à chaque phraseentrée par l’utilisateur.

Pour lancer Ocaml en mode intéractif tapez la commandeocaml. Vous aurez la réponse:

% ocamlOb jec t i ve Caml vers ion 3.06

#

Le caractère # invite l’utilisateur à entrer une phrase qui doitterminer par ;; et un retour chariot.

Page 5: Introduction aux fonctionnalités de base du langage Ocaml

Le mode intéractif(suite)

• Ocaml analyse chaque phrase:• calcule son type (inférence des types),• la traduit en langage exécutable (compilation)• et enfin l’exécute afin de fournir la réponse demandée.

• La réponse donnée en mode intéractif contient:• Le nom de la variable déclarée s’il y en a.• Le type trouvé pendant le typage.• La valeur calculée après exécution.

Page 6: Introduction aux fonctionnalités de base du langage Ocaml

Exemple

# let x = 4+2;;val x : int = 6

La réponse d’Ocaml :• l’identificateur x est déclaré (val x),• avec le type des entiers (:int),• et la valeur 6 (=6).

L’identificateur x est lié à la valeur 6 de type int:

# x;;val x : int = 6

# x * 3;;- : int = 18

Page 7: Introduction aux fonctionnalités de base du langage Ocaml

Les types de base

Type Constantes Primitivesunit () pas d’opération!bool true false && || notchar ’a’ ’\n’ ’\097’ code, chrint 1 2 3 + - * / max_intfloat 1.0 2. 3.14 +. -. *. /. cosstring "a\tb\010c\n" ^ s.[i] s.[i] <- c

Comparaison (pour tous les types) =, > , < , >=, <=,<>.

Page 8: Introduction aux fonctionnalités de base du langage Ocaml

Exemples

# 1+ 2;;- : int = 3

# 1.5 +. 2.3;;- : float = 3.8

# let x = "cou" in x^x;;- : string = "coucou"

# 2 > 7;;- : bool = false

# "bonjour" > "bon";;- : bool = true

Page 9: Introduction aux fonctionnalités de base du langage Ocaml

Les programmes

Un programme est une suite de phrases:définition de valeur let x = edéfinition de fonction let f x1 ... xn = edéfinition de fonctions let [ rec ] f1 x1 ... = e1 ...( mutuellement récursives) [ and fn xn ... = en ]définition de type(s) type q1 = t1... [and qn = tn ]expression e

Les phrases se terminent par ;; optionnel entre desdéclarations, mais obligatoires sinon.

Page 10: Introduction aux fonctionnalités de base du langage Ocaml

Exemples de programmes

# let baguette = 4.20;; (* declaration valeur *)val baguette : float = 4.2

# let euro x = x /. 6.55957;; (* declaration fonction *)val euro : float -> float = <fun>

# euro baguette;; (* expression *)- : float = 0.640285872397123645

Page 11: Introduction aux fonctionnalités de base du langage Ocaml

Remarques

• Il n’y a ni intructions, ni procédures.• Tout sous-programme est une fonction.• Toute expression retourne une valeur.• En dehors des déclarations (des valeurs, des classes, des

modules, des types), toute phrase Ocaml est uneexpression et dénote ainsi une valeur résultat.

• Les fonctions sont des valeurs comme les autres.

Page 12: Introduction aux fonctionnalités de base du langage Ocaml

Les valeurs en Ocaml

• objets,• valeurs de base (de type int, bool, string, . . . ),• fonctions,• valeurs de types construits (tuples, enregistrements, listes,

variants, . . . ).

Page 13: Introduction aux fonctionnalités de base du langage Ocaml

Déclarations globales

Un identificateur est déclaré globalement par le mot clef let:

# let x = 7;;val x : int = 7

# x+2;;- : int = 9

⇒ Les identificateurs déclarées globalement ont une portéeglobale.

Page 14: Introduction aux fonctionnalités de base du langage Ocaml

Déclarations locales

Un identificateur est déclaré localement par la constructionlet ... in:

#let y = 5 in 3 *y;- : int =15

#y;;Unbound value y

⇒ Une déclaration locale est visible seulement dansl’expression qui suit le in.

Page 15: Introduction aux fonctionnalités de base du langage Ocaml

Déclarations globales et locales

Remarque: Il y a une différence de taille entre ces deuxconstructions :

• la première est une déclaration et ne retourne pas devaleur.

• la deuxième est une expression et retourne donc unevaleur.

# 2 + (let y = 5 in 3 *y);;- : int = 17

# 2 + (let y = 15);;Syntax error

Page 16: Introduction aux fonctionnalités de base du langage Ocaml

Valeurs constantes

Les identificateur déclarés jusqu’ici sont constants:

• La déclaration let x =v ne permet la modification de lavaleur v associée à x

• On pourra introduire une nouvelle liaison pour x,let x = v1 qui masque la première dans la suite duprogramme, mais si “l’ancien” x est utilisé ailleurs, savaleur v est toujours d’actualité.

Page 17: Introduction aux fonctionnalités de base du langage Ocaml

Expression conditionnelle

Expression dont le résultat dépend de la valeur de la condition(boléenne).

Une conditionelle a toujours deux branches: les expressionsdans ces branches doivent être de même type.

# if true then "vrai" else "faux";;- : string = "vrai"

# let x = 7 in if x>2 then 1 else true;;Characters 32-36:

let x = 7 in if x>2 then 1 else true;;^^^^

This expression has type bool but is here usedwith type int

Page 18: Introduction aux fonctionnalités de base du langage Ocaml

Les fonctions

Un identificateur de fonction est déclaré comme tout autre, àl’aide d’un let.

# let double y = y*2;;val double : int -> int = < fun >

Une syntaxe alternative pour la même fonction:

# let double (y) = y*2;;val double : int -> int = < fun >

La première est la syntaxe la plus utilisée en Ocaml.

Page 19: Introduction aux fonctionnalités de base du langage Ocaml

Le type des fonctions (avec un argument)

# let double y = y*2;;val double : int -> int = < fun >

• Le type d’une fonction est noté t -> q, où t est le typede l’argument, et q celui du résultats de la fonction.

• Ici, l’argument et le résultat sont de type int.

L’identificateur double est lié à une valeur fonctionnelle:

# double;;val double : int -> int = < fun >

Page 20: Introduction aux fonctionnalités de base du langage Ocaml

Application de fonctions

On applique une fonction en la faisant suivre de son argument(éventuellement entre parenthèses). Elle retourne un résultat:

# double 9;;- : int = 18

# double(9);;- : int = 18

L’application peut également se faire avec deux syntaxes: avecou sans parenthèeses.

Page 21: Introduction aux fonctionnalités de base du langage Ocaml

Fonctions à plusieurs arguments

Une fonction peut prendre plusieurs arguments:

# let moyenne x y = (x+.y)/. 2.0;;val moyenne : float -> float -> float = <fun>

Le type de moyenne:

• cette fonction prend deux arguments de type float:float→ float− >

• elle renvoie un résultat de ce même type: float.

Page 22: Introduction aux fonctionnalités de base du langage Ocaml

Type des fonctions à plusieurs arguments

La fonction:

let f x1 x2 . . . xn = corps

possède n arguments x1, x2, . . . xn et un résultat calculé parcorps. Son type est de la forme:

t1 → t2 . . . → tn → tres

où ti est le type de l’argument xi , et tres est le type du résultatcalculé par corps.

Page 23: Introduction aux fonctionnalités de base du langage Ocaml

Appliquer une fonction à plusieurs arguments

Pour appliquer une fonction à plusieurs arguments, on les luipasse, les uns après les autres:

# mot_compose "mot" "cle";;- : string = "mot-cle"

# let somme x y = x + y;;val somme : int -> int -> int = <fun>

# somme 3 4;;- : int = 7

Page 24: Introduction aux fonctionnalités de base du langage Ocaml

N-uplets

Un n-uplet est un “paquet” de n valeurs v1, v2, . . . vn separéespar des virgules.

Exemples: (1,true) est un 2-uplet; ("bonjour", 5, ’c’) est untriplet.

# let a = (1, true);;val a : int * bool = (1, true)

# let livre = ("Paroles", "Prevert, Jacques", 1932);;val livre : string * string * int =("Paroles", "Prevert, Jacques", 1932)

Page 25: Introduction aux fonctionnalités de base du langage Ocaml

N-uplets (suite)

Un n-uplet permet de mettre dans un “paquet” autant devaleurs que l’on veut. Cela est pratique, si une fonction doitrenvoyer “plusieurs” résultats:

# let f x y = (x+y, x*y);;val f : int -> int -> int * int = <fun>

# f 2 3;;- : int * int = (5, 6)

# let division_euclidienne x y = (x/y, x mod y);;val division_euclidienne : int -> int -> int * int = <fun>

# division_euclidienne 5 2;;- : int * int = (2, 1)

Page 26: Introduction aux fonctionnalités de base du langage Ocaml

Type des n-uplets

Le type d’un n-uplet (v1, v2, . . . , vn)est t1 ∗ t2 . . . ∗ tn,où ti est le type de la composante vi .

Exemples: (1,true) est de type int * bool et ("bonjour", 5,’c’) est de type string * int * char.

# let a = (1, true);;val a : int * bool = (1, true)

# let b = ("bonjour", 5, ’c’);;val b : string * int * char = ("bonjour", 5, ’c’)

Page 27: Introduction aux fonctionnalités de base du langage Ocaml

Fonctions avec n-uplet d’arguments

Une autre manière de définir une fonction à plusieursarguments est de les mettre tous dans un n-uplet.

# let somme (x,y) = x+y;;val somme : int * int -> int = <fun>

Attention: cette fonction ne possède qu’un seul argument, quiest ici une paire. Parmi les appels suivants, le premier estcorrect, alors que le deuxième ne l’est pas:

# somme (2,3);;- : int = 5

# somme 2 3;;This function is applied to too many arguments

Page 28: Introduction aux fonctionnalités de base du langage Ocaml

Type de fonctions avec n-uplet d’arguments

La fonction:

let f(x1, x2, . . . , xn) = corps

possède 1 argument, qui est un n-uplet de valeurs(x1, x2, . . . xn) et un résultat calculé par corps.

Le type du n-uplet (x1, x2, . . . , xn) est t1 ∗ t2 . . . ∗ tn,où ti est le type de chaque xi . Donc, le type de f est:

t1 ∗ t2 . . . ∗ tn → tcorps

où tcorps est le type du résultat calculé par corps.

Page 29: Introduction aux fonctionnalités de base du langage Ocaml

Fonctions avec arguments “un par un”

Les fonctions qui prennent leurs arguments un à un, telle:

let f x1 x2 . . . xn = corps

et celles qui les prennent dans un n-uplet, telle:

let f (x1, x2, . . . , xn) = corps

ne sont pas équivalentes: leurs types d’arguments sontdifférents.

Page 30: Introduction aux fonctionnalités de base du langage Ocaml

Fonctions avec arguments “un par un” (suite)

Le type de l’argument d’une fonction renseigne sur la naturedes arguments qu’on doit lui passer:

• dans le premier cas, on doit passer n arguments les unsaprès les autres. Son type est:

t1 → t2 . . . → tn → tres

• dans le deuxième, on passe un seul argument n-uplet.Son type est:

t1 ∗ t2 . . . ∗ tn → tres

Page 31: Introduction aux fonctionnalités de base du langage Ocaml

Fonctions récursives

Le mot-clé rec sert à introduire les définitions récursives:

# let rec factorielle n =if n<2 then 1 else n*factorielle (n-1);;

val factorielle : int -> int = <fun>

# factorielle 5;;- : int = 120

Page 32: Introduction aux fonctionnalités de base du langage Ocaml

Fonctions récursives(suite)

Pour s’arrêter jour, une fonction récursive doit possèder aumoins un cas d’arrêt. On parle de:

• cas de base, où la fonction s’arrête pour retourner unesolution “simple”,

• et de cas récursifs, où la fonction construit son résultat pardes appels récursifs.

Schéma récursif: sur les entiers, les fonctions récursives ontsouvent la forme

let rec f n =if n <= 0 then “solution sans récursion”else . . .f(n-1) . . .

Page 33: Introduction aux fonctionnalités de base du langage Ocaml

Déroulement d’un appel récursif

# let rec factorielle n =if n<2 then 1 else n*factorielle (n-1);;

val factorielle : int -> int = <fun>

# factorielle 3;;- : int = 6

Appel de factorielle 3:

factorielle 3⇒if 3<2 then 1 else 3*factorielle (3-1)⇒3 * (factorielle(2))⇒3 * (if 2<2 then 1 else 2*factorielle (2-1))⇒3 * (2*factorielle (1))⇒3 * (2* (if 1<2 then 1 else ...) ⇒3 * 2 * 1⇒6

Page 34: Introduction aux fonctionnalités de base du langage Ocaml

Inférence de types

En Ocaml, il n’est pas nécessaire de déclarer les types desidentificateurs ou des arguments d’une fonction, intervenantdans une définition.

Le typeur infère leur type d’après leur contexte.

Page 35: Introduction aux fonctionnalités de base du langage Ocaml

Exemple d’inférence de types

let f(x) = x + 1

Sachant que + est définit uniquement sur les entiers, et dont le typeest +: int ∗ int→ int, le typeur déduit les contraintes:

• le type de f est de la forme:

f : tx → tcorps

où tx est le type de x argument de la fonction, et tcorps est le typedu corps.

• pour que x+1 soit bien typé, x doit être de type int⇒tx = int ,

• si ces contraintes sont respectées, alors le corps x+1 est detype int⇒ tcorps = int .

Conclusion: tx = int et tcorps = int, donc

f : int→ int

Page 36: Introduction aux fonctionnalités de base du langage Ocaml

Polymorphisme

Certaines définitions n’imposent aucune contrainte (oupresque) sur les types des objets manipulés. Dans ce cas, leurtype peut-être quelconque. On parle alors de polymorphismeparamétrique.

Exemple:

let premier (x,y) = x

• premier : tx ∗ ty → tcorps, où tx , ty et tcorps sont les typesde x, de y et du corps de la fonction.

• La seule contrainte imposée par le corps, est que son typesoit le même que celui de la première composante de lapaire argument, i.e: tcorps = tx ,

Page 37: Introduction aux fonctionnalités de base du langage Ocaml

Polymorphisme(suite)

Aucune autre contrainte ne se dégage de l’examen du code ici.D’après les hypothèses de départ, on obtient:

premier : tx ∗ ty → tx

tx , ty ne sont pas de véritables types mais des variables detype.

Page 38: Introduction aux fonctionnalités de base du langage Ocaml

Polymorphisme (suite)

Puisqu’aucune contrainte ne pèse sur tx , ty , on pourrait lesremplacer par n’importe quel type eton obtiendrait un typage cohérent.

Par exemple, on peut choisir parmi les typages:

premier :

int ∗ bool→ int(int→ int) ∗ string→ (int→ int)couleur ∗ int→ couleur...

Page 39: Introduction aux fonctionnalités de base du langage Ocaml

Polymorphisme (suite)

Plutôt que de choisir pour tx et ty , des types arbitraires, Ocamlintroduit les notions de

• variables de types, notées ’a, ’b, . . . et lues α, β, . . .,

• et de type polymorphe paramétrique : c’est un typeparamètré par des variables de types.

Page 40: Introduction aux fonctionnalités de base du langage Ocaml

Polymorphisme paramétrique

Ainsi, le type donné à premier contient des variables de typepour tx et ty , notées ’a et ’b:

premier : ’a * ’b -> ’a

Il signifie:

pour deux types quelconques, que nous nommons ’a et ’b,premier renvoie ’a*’b dans ’a.

Page 41: Introduction aux fonctionnalités de base du langage Ocaml

Polymorphisme

Un type polymorphe n’est pas un type “passe-partout”. Parexemple, les utilisations suivantes de premier sont maltypées:

# let premier (x,y) = x;;val premier : ’a * ’b -> ’a = <fun>

# premier 1;;This expression has type int but is here usedwith type ’a * ’b

# (premier(true,2)) + 3;;This expression has type bool butis here used with type int

# premier (1,2,3);;This expression has type int * int * int butis here used with type ’a * ’b

Page 42: Introduction aux fonctionnalités de base du langage Ocaml

Exemples de constructions polymorphes prédéfinies

#fst;;- : ’a * ’b -> ’a = <fun>

# (=);;- : ’a -> ’a -> bool = <fun>

# (>);;- : ’a -> ’a -> bool = <fun>

Page 43: Introduction aux fonctionnalités de base du langage Ocaml

Filtrage

Permet de programmer pas cas. On examine la structure d’unevaleur et l’on choisit les actions à effectuer selon chaque cas.La structure de chaque cas est décrite à l’aide d’un filtre oumotif.

Syntaxe:

match exprwith filtre_1 -> action_1| filtre_2 -> action_2| ....| _ -> action_tous_autres_cas

Page 44: Introduction aux fonctionnalités de base du langage Ocaml

Filtrage(suite)

A gauche de chaque flèche: un motif (en anglais, pattern), quidécrit une forme possible de la valeur à comparer.

A droite de chaque flèche: l’action à éffectuer dans ce cas.

Le symbole _ est un motif lu “dans tous les autres cas”.

La valeur filtrée est comparée succésivement à chacun desfiltres selon l’ordre de leur défintion.

Page 45: Introduction aux fonctionnalités de base du langage Ocaml

Exemple de filtrage

La fonction suivante filtre ses arguments (une paire) pour faireleur addition en tenant compte du cas où l’un d’entre eux estzéro:

# let somme x y = match (x,y)with (0,n) -> n| (n,0) -> n| (a,b) -> a+b;;

val somme : int -> int -> int = < fun >

# somme 0 3;;- : int = 3# somme 2 4;;- : int = 6

Page 46: Introduction aux fonctionnalités de base du langage Ocaml

Un type predéfini polymorphe: les listes

Elles permettent de modéliser les suites d’éléments de mêmetype, accéssibles séquentiellement.C’est un type des données polymorphe:

’a list

désigne les listes de type ’a.

On peut spécialiser ’a et obtenir des listes:• d’entiers: int list,• de paires: bool*int list,• de dates: date list, etc...

Page 47: Introduction aux fonctionnalités de base du langage Ocaml

Les listes (suite)

Constantes:

• [] est la liste vide.• Deux notations pour les listes non vides:

• [a; b; c] c’est la notation courante.• a::l, c’est la notation pour le filtrage.

Opérateurs: @ de concaténation de deux listes.

Fonctions pre-définies: dans le module List.

Page 48: Introduction aux fonctionnalités de base du langage Ocaml

Exemples

Une liste d’entiers:

# [1;2;3];;- : int list = [1; 2; 3]

Concaténation de deux listes:

# ["a";"bc"] @ ["bonjour"];;- : string list = ["a"; "bc"; "bonjour"]

La liste vide est polymorphe:

# [];;- : ’a list = []

# [1]@[];;- : int list = [1]

# ["ab";"cd"]@[];;- : string list = ["ab"; "cd"]

Page 49: Introduction aux fonctionnalités de base du langage Ocaml

Exemples(suite)

Appel de la fonction length du module List:

# List.length [1;2;3];;- : int = 3

Liste de paires:

# [(1,’a’); (23, ’c’)];;- : (int * char) list = [(1, ’a’); (23, ’c’)]

Liste de listes:

# [[1;2];[3]];;- : int list list = [[1; 2]; [3]]

Erreurs:

# [(1,2);3];;This expression has type int but is here used with type int * int

# [2]@[’a’];;This expression has type char but is here used with type int

# [[1;2];3];;This expression has type int but is here used with type int list

Page 50: Introduction aux fonctionnalités de base du langage Ocaml

Construire une liste par la notation a::l

Il s’agit d’une liste construite à partir

• d’un élément a, qui sera le premier élément de la listea::l,

• et une liste l , qui sera la suite de la liste a::l.

# 1::[];;- : int list = [1]

# 1::[3;5];;- : int list = [1; 3; 5]

# 1::(2::(3::[]));;- : int list = [1; 2; 3]

Ce constructeur est surtout employé pour définir les fonctionssur les listes.

Page 51: Introduction aux fonctionnalités de base du langage Ocaml

Fonctions sur les listes

Souvent on définit les fonctions sur les listes par “filtrage”. Ondoit traiter au moins deux cas:

• la liste est vide ⇒ elle correspond au motif ou “filtre” []

• la liste contient au moins un élément ⇒ elle correspond aumotif a::l, où a est son premier élément, et l est le reste.

Exceptions (failwith): la construction predéfinie failwith,lève l’exception Failure suivie du nom de la fonction qui aéchoué. Cela arrête l’ exécution du programme.

Page 52: Introduction aux fonctionnalités de base du langage Ocaml

Exemple

La fonction qui extrait le premier élément d’une liste, compareson argument avec les deux cas possibles:

• Si elle est vide, la fonction échoue.

• Si elle n’est pas vide, elle est nécessairement de la formee:: reste, où e est le premier élément de la liste.

Page 53: Introduction aux fonctionnalités de base du langage Ocaml

Exemple (suite)

# let premier l =match lwith [] -> failwith "premier"

| e::reste -> e;;val premier : ’a list -> ’a = <fun>

# premier [3;4];;- : int = 3

# premier [’a’;’g’];;- : char = ’a’

# premier [];;Exception: Failure "premier".

Page 54: Introduction aux fonctionnalités de base du langage Ocaml

Appels pour premier

# let premier l =match lwith [] -> failwith "premier"

| e::reste -> e;;val premier : ’a list -> ’a = <fun>

# premier [3;4;5];;- : int = 3

# premier [];;Exception: Failure "premier".

premier [3;4;5]⇒premier 3::[4;5]⇒ 3

premier [3]⇒premier 3::[]⇒ 3

Page 55: Introduction aux fonctionnalités de base du langage Ocaml

Fonctions sur les listes(suite)

La fonction qui teste si une liste est vide:

# let vide l =match lwith [] -> true

| _ -> false;;val vide : ’a list -> bool = <fun>

# vide [1;2];;- : bool = false

# vide [];;- : bool = true

Page 56: Introduction aux fonctionnalités de base du langage Ocaml

Fonctions récursives sur les listes

Les fonctions qui examinent “en profondeur” les listes sont leplus souvent récursives et définies par filtrage.

Exemple: Compter le nombre d’éléments d’une liste:

# let rec longueur l =match lwith [] -> 0

| _::reste -> 1 + longueur reste;;val longueur : ’a list -> int = <fun>

# longueur [];;- : int = 0

# longueur ["a"; "salut"];;- : int = 2

Cette fonction est pre-définie sous le nom de List.lenght.

Page 57: Introduction aux fonctionnalités de base du langage Ocaml

Fonctions récursives sur les listes (suite)

# let rec longueur l =match lwith [] -> 0

| _::reste -> 1 + longueur reste;;val longueur : ’a list -> int = <fun>

longueur [1;5;2]⇒ longueur 1::[5;2]⇒ 1 + (longueur [5;2])⇒ 1 + (longueur 5::[2])⇒ 1 + 1 + (longueur [2])⇒ 1 + 1 + (longueur 2::[])⇒ 1 + 1 + 1 + longueur []⇒ 1 + 1 + 1 + 0

Page 58: Introduction aux fonctionnalités de base du langage Ocaml

Les fonctions de la librairie

Il existe des nombreuses fonctions dans la librairie Ocaml.Elles sont organisées en modules, et sont accessibles avec lanotation pointée.

Exemple: le module List contient des utilitaires sur les lites.Pour utiliser la fonction length qui calcule la longueur d’uneliste, on écrira:

# List.length ["ab"; "bonjour"];;- : int = 2

Page 59: Introduction aux fonctionnalités de base du langage Ocaml

Quelques modules de la librairie

• Module Arg: parsing of command line arguments

• Module Array: array operations

• Module Buffer: extensible string buffers

• Module Callback: registering Caml values with the C runtime

• Module Char: character operations

• Module Complex: Complex numbers

• Module Format: pretty printing

• Module Gc: memory management control and statistics

• Module Genlex: a generic lexical analyzer

• Module Hashtbl: hash tables and hash functions

• Module Int32: 32-bit integers

• Module Int64: 64-bit integers

• Module List: list operations

• Module Map: association tables over ordered types

• Module Printf: formatting printing functions

• Module Queue: first-in first-out queues

• Module Random: pseudo-random number generator (PRNG)

• Module Set: sets over ordered types

• Module Sort: sorting and merging lists

• Module Stack: last-in first-out stacks

• Module Stream: streams and parsers

• Module String: string operations

• Module Sys: system interface

Page 60: Introduction aux fonctionnalités de base du langage Ocaml

Quelques fonctions du module List

• val length : ’a list -> intReturn the length (number of elements) of the given list.

• val hd : ’a list -> ’aReturn the first element of the given list. Raise Failure "hd" if the list is empty.

• val tl : ’a list -> ’a listReturn the given list without its first element. Raise Failure "tl" if the list is empty.

• val nth : ’a list -> int -> ’aReturn the n-th element of the given list. The first element (head of the list) is at position 0. Raise Failure"nth" if the list is too short.

• val rev : ’a list -> ’a listList reversal.

Page 61: Introduction aux fonctionnalités de base du langage Ocaml

Types déclarés

En Ocaml, il est possible de créer des nouveaux typesconstruits.Syntaxe:

type q = typexpr

• typexpr est une expression de type décrivant la lastructure du nouveau type.

• q est l’identificateur qui désigne le nouveau type.

Page 62: Introduction aux fonctionnalités de base du langage Ocaml

Types somme

Le type somme permet de définir des données au moyen d’uneliste de cas décrivant leur structure.

Il permet également de regrouper plusieurs types dans unmême type, par exemple, des entiers et des réels.

On sépare les cas par le symbole |, prononcé “ou”.

Chaque cas est discriminé à l’aide d’un constructeur. Il s’agitd’un identificateur qui commence par une majuscule.

Page 63: Introduction aux fonctionnalités de base du langage Ocaml

Syntaxe des types somme

type nom_type ::= Constr1 type1| Constr2...| Constrn typen

Dans ce schéma, le type est décrit par n cas et autant deconstructeurs (Constr1, Constr2, . . . Constrn).

Chaque constructeur est soit tout seul, soit accompagné d’untype: Constr2 est seul, Constr1 est accompagné du type type1.

Page 64: Introduction aux fonctionnalités de base du langage Ocaml

Type carte

# type carte = As of couleur| Roi of couleur| Dame of couleur| Valet of couleur| Simple of couleur * int| Joker

and couleur = Pique | Coeur | Carreau | Trefle

# let roi_pique = Roi (Pique);;roi_pique : carte = Roi Pique

# let sept_coeur = Simple(Coeur,7);;sept_coeur : carte = Simple (Coeur, 7)

# Joker;;- : carte = Joker

Page 65: Introduction aux fonctionnalités de base du langage Ocaml

Valeur à la belote

# let valeur_belote (atout, carte) =match cartewith As _ -> 11

| Roi _ -> 4| Dame _ -> 3| Valet c -> if c = atout then 20 else 2| Simple (_,10) -> 10| Simple (c,9) -> if c = atout then 14 else 0| _ -> 0;;

val valeur_belote : couleur * carte -> int = <fun>

Page 66: Introduction aux fonctionnalités de base du langage Ocaml

Types paramétrés

Il est possible de déclarer des types avec des paramètres. Lesparamètres sont des variables de type, et le type déclaré est dece fait polymorphe.

Exemple: Le type des cellules polymorphes:

type ’a celulle = {contenu: ’a};;

Selon les valeurs qu’on stocke dans une cellule, le typecellule sera spécialisé à un type particulier:

# let cint = {contenu = 3};;val cint : int celulle = {contenu = 3}

# let ccouleur = {contenu = Rouge};;val ccouleur : peinture celulle = {contenu = Rouge}

Page 67: Introduction aux fonctionnalités de base du langage Ocaml

Arbres binaires polymorphes

On peut employer les paramètres de type pour décrire lesarbres binaires polymorphes:

# type ’a arbre = Vide| Noeud of ’a arbre * ’a * ’a arbre;;

Un arbre d’entiers et un arbre de chaînes de caractères:

# let un = Noeud(Vide, 1, Vide);;val un : int arbre = Noeud (Vide, 1, Vide)

# let bonjour = Noeud(Vide,"bonjour" , Vide);;val bonjour : string arbre = Noeud (Vide, "bonjour", Vide)

Page 68: Introduction aux fonctionnalités de base du langage Ocaml

Types récursifs: arbres binaires d’entiers

Vide Noeud(’a)/ \

/ \’a arbre ’a arrbre

# let un = Noeud(Vide, 1, Vide);;val un : ’a arbre = Noeud (Vide, 1, Vide)

un = Noeud(1)/ \

/ \Vide Vide

Page 69: Introduction aux fonctionnalités de base du langage Ocaml

Types récursifs: arbres binaires d’entiers

La fonction qui additionne les éléments d’un arbre d’entiers.

# let rec somme_arbre arb =match arbwith Vide -> 0| Noeud (a,n,b) ->

somme_arbre a + n + somme_arbre b;;val somme_arbre : int arbre -> int = < fun >

Page 70: Introduction aux fonctionnalités de base du langage Ocaml

Traits impératifs

Ocaml possède plusieurs constructions de la programmationimpérative:

• variables et structures des donneées modifiables(tableaux, enregistrements, références, flux),

• affectation,• instructions d’entrée/sortie,

• boucles itératives et

• exceptions.

Page 71: Introduction aux fonctionnalités de base du langage Ocaml

Calculs avec expressions

La manière de calculer en programmation fonctionnelle estbasée sur l’utilisation d’expressions, qui calculent des valeursrésultats:

# let x = 3 in x + 4;;

# let f (x) = x + 1 in f(2);;

Cette formulation est très proche des mathématiques, leurexécution aboutit à une valeur rendue en résultat.

Page 72: Introduction aux fonctionnalités de base du langage Ocaml

Calculs avec effets

Une autre manière de calculer, dite impérative consiste à:

exécuter des instructions d’entrées/sorties, d’affectation ou demodification de la mémoire. Ces intructions ne rendent pas derésultat, mais changent l’état de la machine: à savoir, de lamémoire ou des entrées/sorties.

Ces actions sont appélés effets.

Page 73: Introduction aux fonctionnalités de base du langage Ocaml

Effets: actions sans résultat

Dans un langage impératif, on calcule avec des suitesd’instructions, qui ne rendent pas de résultat:

int x = System.in.read();int valAbs;if (x<=0) {valAbs = -x} else {valAbs = x} System.out.write(valAbs);

Ce programme change l’état de la mémoire (par affectation desvariables x et valAbs) et des entrées/sorties.

En Ocaml on pourrait écrire:

let valAbs =let x = read_int() inif x<=0 then -x else x

in print_int(valAbs);;

Page 74: Introduction aux fonctionnalités de base du langage Ocaml

Le type vide en Ocaml

Les instructions d’entrée/sorties d’Ocaml, sont des effets:

# print_string"Bonjour";;Bonjour- : unit = ()

Examinons cette réponse:

• Bonjour est l’effet produit par l’exécution.• - : unit = () est la réponse habituelle donnée par le

compilateur intéractif Ocaml: elle contient le nom del’identificateur éventuellement déclaré, son type et savaleur.

Page 75: Introduction aux fonctionnalités de base du langage Ocaml

Le type vide en Ocaml: unit

À la différence d’autres langages, en Ocaml, même un effet,doit rendre un résultat:⇒ Ici, c’est () de type unit.

Le résultat d’un effet en Ocaml est:

• “vide”, noté (),• du type “vide”, noté unit.

⇒ Le type vide est l’équivalent du type void de Java.

Page 76: Introduction aux fonctionnalités de base du langage Ocaml

Les séquences d’instructions

En Ocaml, les suites d’instruction séparées par despoint-virgules sont appelées séquences d’instructions:

• Une séquence d’instruction a pour résultat celui de ladernière instruction de la séquence,

• Une instruction intermédiaire qui renvoie un résultat autreque () est signalée par le compilateur.

# print_string"Bonjour"; print_string" Adieu";;Bonjour Adieu- : unit = ()

# 3+4; print_string" Adieu";;Warning S: this expression should have type unit.Adieu- : unit = ()

Page 77: Introduction aux fonctionnalités de base du langage Ocaml

Entrées/sorties en Ocaml

read_line: unit→ stringread_int: unit→ intprint_string: string→ unitprint_int: int→ unitprint_newline: unit→ unit

Page 78: Introduction aux fonctionnalités de base du langage Ocaml

Exemples

Une fonction pour afficher un arbre d’entiers:

#let rec affiche_int_arbre= functionVide -> print_string "()"

| Noeud (Vide, y, Vide) -> print_int y| Noeud (g, y, d) ->

print_string "("; (affiche_int_arbre g);print_string ","; print_int y; print_string ",";(affiche_int_arbre d); print_string ")";;

val affiche_int_arbre : int arbre -> unit = <fun>

# affiche_int_arbreNoeud (Noeud (Noeud (Vide, 1, Vide), 3, Noeud (Vide, 5, Vide)), 7,Noeud (Noeud (Vide, 1, Vide), 3, Vide))

((1,3,5),7,(1,3,()))- : unit = ()

Page 79: Introduction aux fonctionnalités de base du langage Ocaml

Un programme intéractif

Calcul de note d’un examen: il demande une note d’écrit etd’oral et calcule le résultat final en leur appliquant la fonction f:#let calcule_note f =

print_string"Note d’ecrit: ";let n = float_of_string(read_line()) inprint_string"Note d’oral: ";let m = float_of_string(read_line()) inf(n,m);;

val calcule_note : (float * float -> ’a) -> ’a = <fun>

#let moyenne () =let calc (x,y) =

let m = (x+.y)/.2.0 inprint_string (if m> 10.0 then "RECU(E)" else "AJOURNE(E)");print_newline()

in calcule_note calc;;val moyenne : unit -> unit = <fun>

# moyenne();;Note d’ecrit: 14.3Note d’oral: 11.5RECU(E)- : unit = ()

# let autre_note () =calcule_note (fun (x,y) -> (0.6*. x) +. (0.4 *. y));;

val autre_note : unit -> float = <fun>

Page 80: Introduction aux fonctionnalités de base du langage Ocaml

Les tableaux

Les tableaux sont des structures des données mutables avectype polymorphe.

• un tableau avec éléments de type t est de type t array.

• un exemple de tableau [| 0; 1; 3|]

• L’affectation d’une cellule se fait via la flèche inversée <-.

• Les indices sont des entiers, dont le premier est zéro.

Page 81: Introduction aux fonctionnalités de base du langage Ocaml

Les tableaux

# let a = [| 0; 1; 3|] ;;val a : int array = [|0; 1; 3|]

# a.(0)<-7;;- : unit = ()

# a;;- : int array = [|7; 1; 3|]

Les opérations prédéfinies (dans le module Array) sur lestableaux:

• Array.lenght,• Array.create long init, crée un tableau de taillelong initialisé à init partout.

Page 82: Introduction aux fonctionnalités de base du langage Ocaml

Les boucles

Boucle For:La boucle for permet de rpéter une série d’instructions unnombre de fois fixé à l’avance.# let digits = Array.create 10 0;;val digits : int array = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]

# for i = 0 to 9 dodigits.(i) <- digits.(i) + i done;;

- : unit = ()

#for i = 0 to 10 do print_int i done;;012345678910- : unit = ()

# for i = 10 downto 0 do print_int i done;;109876543210- : unit = ()

# let fact (n) =let accu = ref 1 infor i = 1 to n do accu := i * !accu done;!accu;;

val fact : int -> int = <fun>

# fact(2);;- : int = 2

# fact(3);;- : int = 6

Page 83: Introduction aux fonctionnalités de base du langage Ocaml

Boucle While:#let j =ref 10 in while (!j)> 0

do begin print_int !j; j := !j-1; end done;;10987654321- : unit = ()

# j;;Characters 0-1:Unbound value j

Notez que j est une variable locale à l’expresion suivant le in,et de ce fait, elle est n’est plus definie en dehors de celle-ci.

#let insertion_sort a =for i = 1 to Array.length a - 1 do

let val_i = a.(i) inlet j = ref i inwhile !j > 0 && val_i < a.(!j - 1) do

a.(!j) <- a.(!j - 1);j := !j - 1

done;a.(!j) <- val_i

done;;val insertion_sort : ’a array -> unit = <fun>