On peut représenter les files par des tableaux circulaires, ie où les indices de début de file first et de fin de file next - 1 sont données dans une arithmétique modulo la taille du tableau. Dans cette méthode il faut réserver une place maximale pour la file (la taille du tableau).
type 'a queue =
{ mutable first : int;
mutable next : int;
mutable full: bool;
mutable empty: bool;
content : 'a vect };;
let make_Q len x =
{first = 0; next = 0;
full = false; empty = true;
content = make_vect len x};;
let reset_Q f =
begin f.first <- 0; f.next <- 0;
f.full <- false; f.empty <- true;
end;;
let is_emptyQ f = f.empty;;
let is_fullQ f = f.full;;
let enQ x f = begin
if f.full then failwith "File pleine."
else begin
f.content.(f.next) <- x;
f.next <- (f.next + 1) mod vect_length(f.content);
end;
if f.empty then f.empty <- false;
f.full <- f.next = f.first;
end;;
let deQ f = begin
if f.empty then failwith "File vide"
else
let val = f.content.(f.first) in begin
f.first <- (f.first + 1) mod vect_length(f.content);
if f.full then f.full <- false;
f.empty <- f.next = f.first;
val
end
end;;
Une autre représentation est une liste modifiable, dont on
repère le dernier élément last. Cette
représentation, plus dynamique, ne fait aucun hypothèse
de taille maximale sauf sur l'espace du tas ( heap) global de
toutes les variables disponibles.
La représentation d'une file (avec un tableau ou une liste) n'est pas importante. Seule l'interface exportée compte pour utiliser les listes. Comme pour les interfaces prédéfinis de Caml (graphique, fichiers, vecteurs, etc.) Cette propriété d'abstraction des structures de données est fondamentale. Elle permet la construction modulaire des programmes. Pour transformer nos files en module exportable, on utlise les modules de Caml. (Remarquons que la structure du type des files est non exporté. )
type 'a queue;; value enQ : 'a -> 'a queue -> unit;; (* enQ x q entre x dans la queue q *) value deQ : 'a queue -> 'a;; (* [deQ q] enlève le premier de la file [q]. Sa valeur est le résultat. *) value reset_Q : 'a queue -> unit;; (* remise à zéro de la file *) value is_emptyQ : 'a queue -> bool;; (* [true] ssi la file est vide *) value is_fullQ : 'a queue -> bool;; (* [true] ssi la file est pleine *) value make_Q: 'a -> 'a queue;; (* [make_Q len x] crée une file de taille [len] initialisée par [x] *)Pour rentrer un tel fichier d'interface, il faut utiliser le compilateur par Compile sur Mac ou PC, ou
camlc -c sur Unix.
Il y a 2 types de noms d'identificateur:
nommage absolu: graphics__moveto, graphics__lineto,
etc
nommage relatif: moveto, lineto
après avoir fait #open "graphics"
Le top-level interactif est dans un module top implicite.
Pour charger un module, on fait load "x.ml", ou
load_object "x.zo", open "x.mli".
Les interfaces de module doivent être compilés (format
.zi). L'interface d'un module est implicitement
importé par le nommage absolu (contenant le nom du module) ou
par la directive \#open.
Les suffixes .zo désignent des fichiers
compilés d'implémentation.
La compilation génère des fichiers .zo ou
.zi à partir de .ml ou
.mli. Si pas de .mli, un .zi
est automatiquement généré en faisant un
interface standard. La compilation de .mli, puis de
.ml permet de vérifier l'adéquation de
l'interface par rapport à l'implémentation.
Un module peut être fabriqué à partir d'autres modules plus élémentaires. C'est ce qu'on appelle la construction modulaire des programmes. Il existe des mécanisme de mises à jour automatique d'un ensemble de modules (cf. Makefiles d'Unix).
C'est une très belle structure représentée par un tas (cf le ch 4 du poly). On peut représenter les files de priorité par un arbre binaire presque parfait, stocké dans un tableau.
type 'a tas =
{ mutable cardinal : int;
tas : 'a vect };;
let nTas = ref 0;;
let ajouter v a =
incr nTas;
let i = ref (!nTas - 1) in
while !i > 0 && a.((!i - 1) / 2) <= v do
a.(!i) <- a.((!i - 1) / 2);
i := (!i - 1) / 2
done;
a.(!i) <- v;;
let maximum t = t.tas.(0);;
let supprimer t =
t.cardinal <- t.cardinal - 1;
let a = t.tas in
let nTas = t.cardinal in
a.(0) <- a.(nTas);
let i = ref 0
and v = a.(0)
and j = ref 0 in
begin
try
while 2 * !i + 1 < nTas do
j := 2 * !i + 1;
if !j + 1 < nTas && a.(!j + 1) > a.(!j)
then j := !j + 1;
if v >= a.(!j) then raise Exit;
a.(!i) <- a.(!j);
i := !j
done
with Exit -> ()
end;
a.(!i) <- v;;
Heapsort est un tri dérivé en O(N log N), mais
seulement amusant dans le principe.
Une autre structure (moins utilisée) est la pile, LIFO last in, last out. On peut évaluer les termes avec une pile, en rendant itératif le programme récursif vu à la PC 7. C'est un mécanisme général: récursion = itération + pile, qui est à l'origine de la compilation des langages évolués (FORTRAN, ALGOL) en programmes itératifs (assembleur). Dans notre cours, nous préférons l'écriture récursive qui nous semble plus naturelle.
Pour isoler les instructions des commentaires, pour distinguer les identificateurs, les chaînes de caractères, etc, on fait en général une 1ère passe sur un flot de caractères tapés sur l'entrée standard: c'est l'analyse lexicale qui consiste à supprimer les espaces, tabulations, retour à la ligne.
let cur_char = ref ` `
and advance() = cur_char := input_char(stdin);;
let is_letter (c) =
(`A` <= c && c <= `Z`) ||
(`a` <= c && c <= `z`);;
let is_digit (c) =
(`0` <= c && c <= `9`) ;;
let is_blank (c) =
c = ` ` || c = `\t` || c = `\r` || c = `\n` ;;
let skip_blanks () =
while is_blank (!cur_char) do
advance()
done;;
let next_ident() =
let buf = make_string 100 ` `
and i = ref 0 in begin
while is_letter (!cur_char) do
buf.[!i] <- !cur_char;
incr i;
advance()
done;
sub_string buf 0 !i
end;;
let next_number() =
let res = ref 0 in
begin
while is_digit (!cur_char) do
res := !res*10 + int_of_char (!cur_char)
- int_of_char (`0`);
advance()
done;
!res
end;;
On ne garde plus qu'une suite de lexems, encore appelés
tokens. On écrit une fonction next_lexem
qui saute les espaces et retourne le prochain lexem dans la variable
globale cur_item.
let erreur (s) = failwith ("Erreur: " ^ s) ;;
type lexem =
L_Ident of string (* identificateur *)
| L_Nb of int (* nombre *)
| L_Plus (* + *)
| L_Moins (* - *)
| L_Mult (* * *)
| L_Div (* / *)
| L_Opar (* ( *)
| L_Fpar (* ) *)
| L_Assign1 (* := *)
| L_Assign2 (* <- *)
| L_EOF (* end of file *)
;;
let cur_lexem = ref L_EOF
and next_lexem () =
cur_lexem :=
try
skip_blanks ();
match !cur_char with
`a`.. `z` | `A`..`Z` -> L_Ident(next_ident ())
|`0`..`9` -> L_Nb(next_number ())
|`+` -> begin advance(); L_Plus end
|`-` -> begin advance(); L_Moins end
|`*` -> begin advance(); L_Mult end
|`/` -> begin advance(); L_Div end
|`:` -> begin advance();
if !cur_char <> `=` then L_Div
else begin advance(); L_Assign1 end
end
|`(` -> begin advance(); L_Opar end
|`)` -> begin advance(); L_Fpar end
| _ -> erreur "forbidden char"
with
End_of_file -> L_EOF;;
Il existe des outils pour générer automatiquement les
analyseurs lexicaux: lex de Lesk ou camllex.
La théorie se fait avec les automates finis (ou expressions
régulières et langages réguliers).
let rec expression () =
let a = terme () in
match !cur_lexem with
L_Plus -> begin next_lexem(); Add (a, expression ()) end
| L_Moins -> begin next_lexem(); Soust (a, expression ()) end
| _ -> a
and terme () =
let a = facteur () in
match !cur_lexem with
L_Mult -> begin next_lexem(); Mult (a, expression ()) end
| L_Div -> begin next_lexem(); Div (a, expression ()) end
| _ -> a
and facteur () =
match !cur_lexem with
L_Opar -> begin next_lexem();
let a = expression () in
if !cur_lexem = L_Fpar then begin
next_lexem();
a end
else erreur "missing parenthesis" end
| L_Ident(s) -> begin next_lexem(); Var (s) end
| L_Nb (x) -> begin next_lexem(); Const (x) end
| _ -> erreur "forbidden character";;
Remarque: les opérateurs sont associatifs à droite avec
cette méthode. Comment la changer pour rendre des expressions
avec les opérateurs de même précédence
associatifs à gauche?
Il existe des outils pour générer automatiquement les
analyseurs syntaxique: yacc de Johnson ou
camlyacc. La théorie se fait avec les automates
à pile (ou langages context-free, aussi appelés
algébriques).
On peut imprimer en inversant l'analyseur syntaxique (avec le bon nombre de parenthèses)
let rec print_expression (e) =
match e with
Add (e1, e2) -> begin
print_terme (e1); printf " + ";
print_expression (e2) end
| Sub (e1, e2) -> begin
print_terme (e1); printf " - ";
print_expression (e2) end
| _ -> print_terme e
and print_terme (e) =
Mult (e1, e2) -> begin
print_terme (e1); printf " * ";
print_expression (e2) end
| Div (e1, e2) -> begin
print_terme (e1); printf " / ";
print_expression (e2) end
| _ -> print_facteur e
and print_facteur (e) =
match e with
Var (s) -> printf "%s" s
| Const (x) -> printf "%d" x
| _ -> begin
printf "("; print_expression (e);
printf ")" end ;;
Pour faire de beaux tapis, tartans, broderies ou couettes, on prend le langage Quilt (cf livre de Ravi Sethi).
exp ::= C (* constantes *)
| ident (* variables *)
| turn (exp)
| sew (exp, exp)
| (exp)
| pile (exp, exp)
| let déclarations in exp
déclarations ::=
val ident = exp
| fun ident (arg1, arg2, ... argn) = exp
arg ::= ident
où ident est un identificateur quelconque.
Une expression est un rectangle caractérisé par sa boîte enveloppante et son contenu dessiné. Les opérations sont:
turn (e) est la rotation de 90 degrés
sew(exp1,exp2) est la concaténation horizontale
pile (exp1, exp2) est la concaténation verticale
let val ou let fun définissent des variables ou des
fonctions.
Comment exécuter une expression de Quilt? Par exemple,
let fun unturn (x) = turn(turn(turn(x))) in unturn (sew(a,b))tournera la boite AB de 90 degré vers la gauche. Et on peut continuer en faisant des motifs
let fun unturn (x) = turn(turn(turn(x))) in let val x = unturn (sew(a,b)) in let val y = pile (a, b) in sew (x, y)etc... On arrive très rapidement à faire de beaux motifs. On peut corser l'analyse syntaxique en mettant certaines opérations infixes, par exemple
a;b pour
sew(a,b), ou +e pour turn(e).