init-prog-ocaml-correction.md 17.9 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
 Introduction à la Programmation Fonctionnelle en OCaml
======================================================

**M2 LMFI**

## Démarrage

Le plus simple pour une première découverte : http://try.ocamlpro.com

Sinon vous pouvez directement lancer l'interpréteur `ocaml` dans une console.

Mieux encore, Lancez l'interpréteur OCaml sous l'éditeur `emacs` :

  - ouvrez un nouveau fichier `exo.ml` (l'extension `.ml` est nécessaire),
  - dans le menu `Tuareg`, dans le sous-menu `Interactive Mode`, choisir `Run OCaml Toplevel`
  - confirmez le lancement de `ocaml` par un retour-chariot.

Chaque expression entrée dans la fenêtre de `exo.ml` peut être évaluée en se plaçant sur un caractère quelconque de l'expression, puis en utilisant le raccourci `ctrl-c,ctrl-e`, qui correspond à `Evaluate phrase` dans le sous-menu `Interactive Mode` du menu `Tuareg` d'emacs.

**Nota Bene** : dans emacs, on peut maintenant se passer de l'ancien terminateur `;;`. En contrepartie, *toutes* les phrases doivent commencer par `let`, même les tests. Au lieu de `1+2;;`, on écrira donc maintenant `let _ = 1+2`.

## Coeur fonctionnel d'OCaml

Présentation du lambda-calcul, avec ses trois constructions de base :

 - variables
 - abstraction de fonction : `λx.t` (correspondant à `fun x -> t` en OCaml)
 - application de fonction : `t u` (idem en OCaml)

Règle de calcul : la β-réduction où `(λx.t) u` donne `t{x:=u}` (la définition de la substitution est laissée en exercice).

Exemple de propriété théorique de la réduction du lamda-calcul : la confluence.

Exemple de terme dont la réduction est infinie : `ΔΔ` valant `(λx.(x x))(λx.(x x))`.
Pas d'équivalent direct en OCaml pour des raisons de typage.

Typage simple du lambda-calcul : 

 - On type les variables en regardant dans un environnement de typage Γ
 - Si `Γ+x:τ ⊢ t:σ` alors `Γ ⊢ (λx.t):(τ→σ)`
 - Si `Γ ⊢ t:(τ→σ)` et `Γ ⊢ u:τ` alors `Γ ⊢ (t u) : σ`

Lien avec la logique minimale (gérant uniquement l'implication) : il suffit de ne garder que les types dans les règles précédentes.
C'est (le début de) l'isomorphisme de Curry-Howard.

Le typage d'OCaml est une évolution de ces règles de départ, avec en plus une notion de variables de type (`'a` dans la syntaxe OCaml).

Propriétés essentielles du lambda-calcul simplement typé :

 - Préservation du typage lors de la réduction
 - Normalisation forte : un terme bien typé ne peut avoir de réduction infinie.
   Ceci combiné à la confluence signifie que la réduction d'un terme `t` finit toujours sur une unique forme normale `t₀` de `t`.

OCaml satisfait la première propriété (préservation du typage lors du calcul), ce qui est essentiel pour garantir toute une famille de plantage lors du calcul (cf. les "segfaults"). Par contre un système sans calcul infini est très restrictif, OCaml incorpore une notion de récursion générale, cf plus bas.

## Premières extensions OCaml

le `let` (global) et le `let ... in`.

Exemples:

```ocaml
let identity = fun x -> x
(* ou de maniere equivalente: *)
let identity x = x
(* projections, pouvant servir de pseudo-booléens *)
let proj1 x y = x
let proj2 x y = y
let pseudoif b x y = b x y
```

#### Exercice : Mécanisme de liaison en OCaml

Prévoir le résultat fourni par l'interpréteur OCaml après chacune des commandes suivantes :

```ocaml
let x = 2
```

```ocaml
let x = 3 in
let y = x + 1 in
x + y
```

```ocaml
let x = 3
and y = x + 1 in
x + y
```

Pourquoi la deuxième et la troisième commande ne fournissent-elles pas le même résultat ?

Réponses: le `let...in` de la deuxième phrase est une liaison *locale*, donnant 7 comme résultat de la phrase, tandis que après cette phrase `x` est de nouveau la définition globale valant 2. Quant à la phrase avec `let...and...in`, il s'agit d'une variante où les calculs sont fait en premiers, et les liaisons (locales) en second. Donc le `x+1` réfère au `x` global, avant qu'on ne crée un `x` et un `y` locaux valant tous les deux 3. Réponse finale 6.


Considérons maintenant les phrases suivantes :

```ocaml
let x = 3
let f y = y + x
let _ = f 2
let x = 0
let _ = f 2
```

Quels sont les résultats des appels de fonctions successifs `f 2` ?

Réponse: 5 dans les deux cas, en effet cacher la première définition globale de `x` par une nouvelle définition globale ne change rien pour la fonction `f` qui continue à utiliser le `x` visible au moment de la définition de `f`.

#### Exercice : Placement des parenthèses

Ajouter les parenthèses nécessaires pour que le code ci-dessous compile:

```ocaml
let somme x y = x + y
let _ = somme somme somme 2 3 4 somme 2 somme 3 4
```

Réponse: `somme (somme (somme 2 3) 4) (somme 2 (somme 3 4))`.


## Premiers types de données : Booléens et Entiers

OCaml fournit le type `bool` et ses constantes `true` et `false`.
On dispose d'une construction `if ... then ... else ...`.
Quelques opérations booléennes :

  - la negation : `not`
  - le "et" logique : `&&`
  - le "ou" logique : `||`

Remarque : l'évaluation d'un `&&` ou d'un `||` suit des règles particulières (dites *paresseuses*), alors que le reste d'OCaml utilise normalement une évaluation *stricte* : calcul de tous les arguments d'une fonction avant de déclencher cet appel de fonction.

On peut obtenir des résultats booléens lors d'un test d'égalité `x = y` ou de différence `x <> y` ou d'ordre `x < y` ou `x <= y`, etc.

OCaml fournit un type `int` des entiers "machines" (donc à capacité bornée, attention aux débordements).
Il existe un type d'entiers non bornés si besoin.
Quelques opérations sur les entiers : addition `+`, multiplication `*`, division entière `/`, modulo `x mod y`.


#### Exercice : Fonctions booléennes

  - Écrire une fonction `checktauto : (bool->bool)->bool` qui teste si une fonction booléenne à un argument répond toujours `true`.

  - Même chose avec `checktauto2` et `checktauto3` pour des fonctions booléennes à 2 puis 3 arguments. On peut faire ça en énumerant à la main tous les cas, mais il y a évidemment plus malin, par exemple réutiliser `checktauto`.

  - En utilisant des conditionnelles, écrivez une fonction `g` qui se comporte comme la fonction `f` ci-dessous. Vérifier ensuite à l'aide de `checktauto3` que `f` et `g` produisent bien toujours le même résultat.

```ocaml
let f x y z = match x, y, z with
  | _ , false , true -> 1
  | false , true , _ -> 2
  | _ , _ , false -> 3
  | _ , _ , true -> 4
```

Réponses:

```ocaml
let checktauto f = f true && f false

let checktauto2 f = f true true && f true false && f false true && f false false 
(* ou mieux: *)
let checktauto2 f = checktauto (f true) && checktauto (f false)
(* ou encore mieux: *)
let checktauto2 f = checktauto (fun b -> checktauto (f b))

let checktauto3 f = checktauto2 (f true) && checktauto2 (f false)
(* ou *)
let checktauto3 f = checktauto (fun b -> checktauto2 (f b))

let g x y z =
 if not y && z then 1
 else if not x && y then 2
 else if not z then 3
 else 4
 
let _ = checktauto3 (fun x y z -> f x y z = g x y z)
```


## Recursivité 

Le `let rec` permet de réutiliser la fonction qu'on est en train d'écrire !

Attention à ne pas boucler ! Il faut donc prévoir un cas d'arrêt (p.ex. `x=0`) et faire des appels récursifs sur des valeurs décroissantes.

#### Exercice : écrire quelques fonctions récursives classiques

Factorielle


```ocaml
let rec factorial n =
  if n = 0 then 1
  else n * factorial (n-1)
```

Nombres de Fibonacci

```ocaml
let rec fib n =
  if n <= 1 then 1
  else fib (n-1) + fib (n-2)
```

Attention, la fonction précédente va avoir un comportement exponentiel (pourquoi?).
Voici un exemple de version efficace.

```ocaml
let rec fib_loop n a b =
 if n=0 then a
 else fib_loop (n-1) b (a+b)

let fib n = fib_loop n 1 1
```

Pgcd:

```ocaml
let rec pgcd a b =
 if b = 0 then a
 else pgcd b (a mod b)
```

Puissance

```ocaml
let rec puissance a n =
 if n = 0 then 1
 else a * puissance a (n-1)
```

On peut également profiter de la structure binaire des nombres pour faire moins de multiplications:

```ocaml
let rec puissance a n =
 if n = 0 then 1
 else if n mod 2 = 0 then
   let b = puissance a (n/2) in
   b*b
 else
   let b = puissance a (n/2) in
   a*b*b
```
 

## Fonctions de première classse et application partielle

Des fonctions en argument ou en réponse ...
Des arguments qui manquent ...

Exemple : la composition de fonction

```ocaml
let compose f g = fun x -> f (g (x))
```

Ou de manière équivalente:

```ocaml
let compose f g x = f (g (x))
```

Pierre Letouzey's avatar
Pierre Letouzey committed
266
Bien noter (et comprendre!) le type inféré par OCaml: `('a->'b)->('c->'a)->'c->'b`
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357


Autre exemple : sommation d'une fonction `f` entre les entiers `a` et `b`

```ocaml
let rec sum f a b =
  if b < a then 0
  else f a + sum f (a+1) b
```

Dernier exemple : un itérateur général de fonctions :

```ocaml
let rec iter f n x =
 if n = 0 then x
 else iter f (n-1) (f x)
```

Type inféré par OCaml : `('a->'a)->int->'a->'a`.

Exemple d'utilisation, pour retrouver la puissance:

```ocaml
let puissance a n = iter (fun x -> a*x) n 1
```


## Type de données : les paires

Une paire regroupe deux éléments `(a,b)` qui ne sont pas forcément du même type.
Le type de cette paire s'écrit alors `τ * σ` si les types de `a` et `b` sont respectivement `τ` et `σ`.

Il y a également des triplets, quadruplets, n-uplets bâtis sur le même principe, par exemple `(1,2,true)` est un `int * int * bool`.

Pour utiliser une paire, soit on la projette (via les fonctions prédéfinies `fst` et `snd`),
soit on la déconstruit (via une syntaxe telle que `let (x,y) = ... in ...`.

Exemple : nombres de fibonacci successifs

```ocaml
let fibs n =
 if n = 0 then (1,1)
 else
    let (a,b) = fibs (n-1) in
    (b, a+b)
    
let fib n = fst (fibs n)
```

Fonctions curryfiées ou décurrifiées.

Si une fonction OCaml a plusieurs arguments, l'usage est plutôt de mettre ces arguments les uns après les autres, ce qui donne un type de la forme `typ_arg1 -> typ_arg2 -> ... -> typ_res`. On parle de style *à la Curry*, ou *curryfié*.

Mais il est aussi possible de regrouper tous ces arguments dans un nuplet, ce qui donne un type de la forme `typ_arg1 * typ_arg2 * ... * typ_argn -> typ_res`. C'est le style *décurryfié*. Dans cette version, pas d'application partielle possible aisément. Par contre cela peut parfois être commode de traiter tout un groupe d'arguments comme un seul.

Passage d'une fonction binaire curryfiée en décurryfiée :

```ocaml
let uncurry f (x,y) = f x y
(* typage : ('a -> 'b -> 'c) -> 'a * 'b -> 'c *)
```

Passage d'une fonction binaire décurryfiée en curryfié :

```ocaml
let curry f x y = f (x,y)
(* typage : ('a * 'b -> 'c) -> 'a -> 'b -> 'c *)
```


## Type de données : les listes

Une liste OCaml est un groupement ordonné d'éléments de même type, en nombre non prédéfini.
Exemple: `[1;2;3;4]` est une `int list`.
Les opérations élémentaires de construction de liste sont la liste vide `[]` et le prolongement
`x::l` d'une liste existante `l` par un nouvel élément `x` à gauche.
Notez que la syntaxe `[1;2;3;4]` n'est qu'un raccourci pour `1::(2::(3::(4::[])))`.

Pour analyser une liste, on peut utiliser des fonctions prédéfinies `List.hd` et `List.tl`, mais il est souvent plus élégant et à peine plus long d'utiliser une opération `match...with` (cf exemples ci-dessous).

Les listes (tout comme les paires auparavant, et les arbres ci-dessous) sont des structures *immutables* : une fois une liste constituée, on ne change plus son contenu. Par contre on peut former de nouvelles listes en réutilisant tout ou partie d'anciennes listes.

La tête de la liste (sa gauche) s'accède ou se ralonge en temps constant. Par contre le fond de la liste (sa droite) ne peut s'atteindre qu'en visitant toute la liste, donc en un temps linéaire (proportionnel à la taille de la liste).

Voici quelques exemples classiques

```ocaml
(* longueur d'une liste, déjà fourni par OCaml sous le nom List.length *)
let rec length l =
  match l with
  | [] -> 0
Pierre Letouzey's avatar
Pierre Letouzey committed
358
  | _ :: q -> 1 + length q
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503

(* concaténation de deux listes, déjà fourni par OCaml via la syntaxe @ *)
let rec append l1 l2 =
 match l1 with
 | [] -> l2
 | x1::q1 -> x1 :: (append q1 l2)
 
(* concaténation retournant la première liste, cf. List.rev_append *)
let rec rev_append l1 l2 =
 match l1 with
 | [] -> l2
 | x1::q1 -> rev_append q1 (x1::l2)
 
(* miroir d'une liste, cf List.rev *)
let rec rev l = rev_append l []

(* miroir d'une liste, version directe, mais en temps quadratique en la taille de l *)
let rec slow_rev l =
 match l with
 | [] -> []
 | x::q -> (slow_rev q) @ [x]

(* filtre d'une liste selon un test booléen, cf List.filter *)
let rec filter f l =
 match l with
 | [] -> []
 | x::q -> if f x then x :: filter f q else filter f q

(* action d'une fonction sur tous les éléments, cf List.map : ('a -> 'b) -> 'a list -> 'b list *)
let rec map f l =
 match l with
 | [] -> []
 | x::q -> f x :: map f q
```

A régarder également dans la documentation : les itérateurs `fold_left` et `fold_right`.

Attention à l'usage sur de grosses listes (plus de 30000 éléments), certaines fonctions peuvent échouer avec l'erreur `Stack overflow`. Pour éviter cela, on peut utiliser le style *récursif terminal* (cf p.ex. `rev_append` ci-dessus) ... ou bien utiliser autre chose que des listes (arbres ou tableaux).

## Type de données : les arbres

Pas de type des arbres prédéfinis en OCaml, il y aurait trop de variantes selon les usages voulus. Heureusement, OCaml nous permet d'ajouter facilement nos propres *types algébriques* au système.

Par exemple, avec des éléments de type `'a` comme décoration à chaque noeud binaire:

```ocaml
type 'a arbre =
 | Noeud of 'a * 'a arbre * 'a arbre
 | Feuille

let monarbre = Noeud (1,Noeud (2,Feuille,Feuille), Feuille)
```

Pour l'analyse, on utilise la construction `match...with` de manière similaire aux listes
(ou le raccourci `function`, qui correspond à un `fun` suivi d'un `match`). 

```ocaml
let rec taille a =
 match a with
 | Feuille -> 0
 | Noeud (_,g,d) -> 1 + taille g + taille d
 
let rec profondeur = function
 | Feuille -> 0
 | Noeud (_,g,d) -> 1 + max (profondeur g) (profondeur d)
 
(* parcours infixe et conversion en liste *)
let rec tolist = function
 | Feuille -> []
 | Noeud (x,g,d) -> tolist g @ [x] @ tolist d
```

L'intérêt de ce genre d'arbre vient par exemple quand les données sont rangées par ordre croissant lors d'un parcours infixe, on parle alors d'arbre binaire de recherche (ABR).

```ocaml
(* fonction auxiliaire testant f sur tous les éléments d'un arbre *)
let rec pourtout f a = match a with
 | Feuille -> true
 | Noeud (x,g,d) -> f x && pourtout f g && pourtout f d

(* vérification de la propriété ABR *)
let rec estabr = function
 | Feuille -> true
 | Noeud (x,g,d) ->
    pourtout (fun y -> y<x) g && pourtout (fun y -> y>x) d && estabr g && estabr d
```

Note: cette version de la fonction `estabr` a une mauvaise complexité. Exercice : en écrire une version linéaire.

On peut alors faire de la recherche dichotomique pour savoir si un élément est dans l'arbre ou non:
```ocaml
let rec search x a =
 match a with
 | Feuille -> false
 | Noeud (y,g,_) when x < y -> search x g
 | Noeud (y,_,d) when x > y -> search x d
 | Noeud _ -> true (* dernier cas possible : le noeud contient x *)
```

Si l'arbre est bien plat (c'est à dire complet ou presque), cette recherche est alors en temps
logarithmique en la taille de l'arbre. Il est possible de s'assurer que les arbres restent plats
même lorsqu'on les fait grossir, voir par exemple les arbres Rouges-Noirs ou les arbres AVL.

OCaml fournit par défaut une bibliothèque de fonctions ensemblistes rapides basées sur des arbres, voir le module `Set`.

## Types algébriques d'OCaml : faites vos propres types

Au delà des arbres, on peut continuer à concevoir des types algébriques correspondant à nos besoins. Par exemple, pour un petit langage de calcul formel:

```ocaml
type unop = Sin | Cos
type binop = Plus | Mult

type expr =
 | Cst of int
 | Var of string (* nom de la variable *)
 | Unop of unop * expr
 | Binop of binop * expr * expr

(* codage de 3x+sin(y) *)
let exemple = Binop(Plus,Binop(Mult,Cst 3,Var "x"),Unop(Sin,Var "y"))
```

Notez que le passage d'une chaine de caractère comme `"3x+sin(y)"` à la forme arborescente ci-dessus (de type `expr`) peut se faire automatiquement, mais ce n'est pas évident. Il s'agit d'une analyse lexicale et grammaticale, pour laquelle il existe des outils dédiés (cf `ocamllex` et `ocamlyacc`).

On peut alors écrire un simplificateur d'expression, essayant de se débarasser des constantes.
Ceci n'est qu'un début, à perfectionner.

```ocaml
let rec simpl e = match e with
| Binop (o,e1,e2) ->
  (match o, simpl e1, simpl e2 with
   | Plus, Cst n1, Cst n2 -> Cst (n1+n2)
   | Mult, Cst n1, Cst n2 -> Cst (n1*n2)
   | Plus, Cst 0, e2' -> e2'
   | Plus, e1', Cst 0 -> e1'
   | Mult, Cst 0, _ -> Cst 0
   | Mult, _, Cst 0 -> Cst 0
   | Mult, Cst 1, e2' -> e2'
   | Mult, e1', Cst 1 -> e1'
   | o, e1',e2' -> Binop(o,e1',e2'))
| Unop (u,e) -> Unop(u, simpl e)  (* TODO : simplifications liées aux fonctions unaires *)
| _ -> e (* pas de simplification pour une constante seule ou une variable seule *)
```

Pierre Letouzey's avatar
typos    
Pierre Letouzey committed
504
Enfin, voici un dérivateur formel. Le premier argument est le nom de la variable par laquelle on dérive.
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528

```ocaml
let rec derive x e = match e with
| Cst n -> Cst 0
| Var y -> if x = y then Cst 1 else Cst 0
| Unop(Sin,e) -> Binop(Mult,Unop(Cos,e),derive x e)
| Unop(Cos,e) -> Binop(Mult,Binop(Mult,Cst (-1),Unop(Sin,e)),derive x e)
| Binop(Plus,e1,e2) -> Binop(Plus,derive x e1, derive x e2)
| Binop(Mult,e1,e2) -> Binop(Plus,Binop(Mult,e1,derive x e2),Binop(Mult,derive x e1,e2))
```
 


## OCaml c'est aussi ...

OCaml est un langage généraliste, donc on y trouve bien d'autres choses
que les éléments présentés lors de ce rapide survol:

  - de la programmation impérative (`for`, `while`, références, tableau, ...)
  - des primitives d'interaction avec le reste du monde (I/O, fichiers, système, réseau, ...)
  - des exceptions (programmables)
  - un système de modules
  - de la programmation objet
  - ...