DatAlog — Extensions

1. Introduction

Le cours 8 a fusionné Table, DOM et Prolog en une application cohérente : DatAlog. Mais dans sa section 8, intitulée sobrement « Extensions possibles », on a listé tout ce qu'on pourrait ajouter. Ce cours 9 est la réponse à cette question !

On va enrichir chaque module avec des fonctionnalités qui le rapprochent d'un vrai langage de programmation logique :

• Table — CSV avec champs entre guillemets (pour gérer les noms comme « Iris, Marie »)
• Prolog — Arithmétique (is/2, >/2), négation (\+/1), listes ([a,b,c]), findall/3, member/2, agrégations natives
• Demo — Démonstration complète exploitant toutes ces extensions
• Main — Mode interactif amélioré, support multi-tables

L'objectif est de montrer comment un petit moteur Prolog peut être étendu progressivement sans exploser en complexité. Chaque extension est orthogonale : on peut les ajouter une par une, sans casser les autres.

2. CSV robuste

La version de base de Table (cours 5) découpait chaque ligne avec String.split_on_char ','. Problème : qu'en est-il d'un champ comme "Iris, Marie" ? La virgule interne est interprétée comme un séparateur, et le champ est coupé en deux. Catastrophe.

La solution : un parseur CSV respectant les guillemets qui ne découpe que les virgules hors guillemets.

(* Découpage intelligent : ignore les virgules entre guillemets *)
let split_csv_line line =
  let len = String.length line in
  let rec aux i in_quotes start acc =
    if i >= len then
      let part = String.sub line start (len - start) in
      List.rev (part :: acc)
    else match line.[i] with
      '\"' -> aux (i + 1) (not in_quotes) start acc
      ',' when not in_quotes ->
          let part = String.sub line start (i - start) in
          aux (i + 1) false (i + 1) (part :: acc)
      _ -> aux (i + 1) in_quotes start acc
  in
  aux 0 false 0 []

(* Nettoyage : enlever les guillemets, gérer les "" échappés *)
let clean_field s =
  let s = String.trim s in
  (* Si la chaîne est entre guillemets, on les enlève *)
  (* et on remplace les double-guillemets "" par un simple ") *)
  ...

Avec cette extension, le champ "Iris, Marie" est correctement parsé comme un seul champ contenant Iris, Marie, et non comme deux champs "Iris et Marie".

3. Arithmétique

Le Prolog classique (cours 7) ne savait pas compter. Les prédicats gt(N, 10) utilisaient une comparaison symbolique limitée. Le cours 9 apporte la totale : évaluation arithmétique avec is/2 et des comparateurs dignes de ce nom (>, <, >=, =<).

3.1 is/2 — Évaluation d'expressions

Le prédicat is/2 évalue une expression arithmétique et unifie le résultat avec une variable. C'est le pont entre le monde logique et le monde numérique.

(* Évaluation arithmétique récursive *)
let rec eval_arith s t =
  let t = apply s t in
  match t with
  | Atom n ->
      float_of_string n
  | Struct ("+", [a; b]) ->
      eval_arith s a +. eval_arith s b
  | Struct ("*", [a; b]) ->
      eval_arith s a *. eval_arith s b
  | Struct ("-", [a; b]) ->  (* soustraction *)
      eval_arith s a -. eval_arith s b
  | Struct ("mod", [a; b]) -> (* modulo *)
      ...
  | Struct ("abs", [a]) -> (* valeur absolue *)
      abs_float (eval_arith s a)
  | Var x ->
      raise (ArithError ("variable non liée : " ^ x))

Quelques exemples de règles utilisant is/2 :

% Panier moyen par achat
panier_moyen(X, Moy) :-
  cell(X, montant, M),
  cell(X, nbachats, N),
  N > 0,
  Moy is M / N.

% Montant après remise de 15%
apres_remise(X, M_remise) :-
  cell(X, montant, Montant),
  M_remise is Montant * 0.85.

% Âge dans 10 ans
age_dans_10_ans(X, Age2) :-
  cell(X, age, A),
  Age2 is A + 10.

3.2 Comparateurs arithmétiques

Fini les gt(N, 10) à l'ancienne ! On utilise maintenant les vrais opérateurs Prolog : N > 10, A >= 60. Le moteur évalue les deux côtés numériquement avant de comparer.

(* Comparateurs arithmétiques dans eval_simple_builtin *)
let try_arith_cmp op a b =
  let va = eval_arith s a in
  let vb = eval_arith s b in
  match op with
  | ">"  -> va > vb
  | "<"  -> va < vb
  | ">=" -> va >= vb
  | "=<" -> va <= vb
  | "=:=" -> va = vb   (* égalité arithmétique *)
  | "=\\=" -> va <> vb  (* inégalité arithmétique *)

Les règles du cours 8 qui utilisaient gt/2 fonctionnent toujours, mais on peut maintenant écrire la même chose de façon plus naturelle :

% Avant (Cours 8) :
fidele(X) :- cell(X, nbachats, N), gt(N, 10).

% Après (Cours 9) :
fidele(X) :- cell(X, nbachats, N), N > 10.

4. Négation par échec

Un des prédicats les plus demandés en Prolog est la négation. Comment exprimer « X n'est pas premium » ? En Prolog, on utilise la négation par échec (Negation as Failure, NaF) notée \+/1.

L'idée est simple : \+ but réussit si but échoue, et échoue si but réussit. C'est la négation du point de vue du moteur d'inférence, pas de la logique classique. C'est subtil mais puissant.

※ Négation par échec dans le moteur de preuve *)
  if is_neg_goal g then
    match g with
    | Struct ("\\+", [neg_goal]) ->
        let results = prove s [neg_goal] kb in
        if results = [] then prove s gs kb
        else []
    | _ -> []

Exemples d'utilisation en pratique :

% Clients non premium
non_premium(X) :- row(X), \+ premium(X).

% Clients non parisiens
non_parisien(X) :- row(X), \+ parisien(X).

% Premium non senior (recommandation)
reco_autre(X) :- premium(X), \+ senior(X).

% Jeune non premium (marketing ciblé)
jeune_non_premium(X) :-
  cell(X, age, A), A < 30, \+ premium(X).

Notez l'utilisation de row(X) : c'est un fait généré automatiquement pour chaque ligne de la table (row(0), row(1), ...). Il permet d'itérer sur tous les identifiants de la table.

5. Listes

5.1 Syntaxe listes

Le Prolog utilise une notation très élégante pour les listes : [a, b, c] est du sucre syntaxique pour .(a, .(b, .(c, []))). La barre verticale permet le pattern matching : [H | T] décompose une liste en tête et queue.

Notre parseur supporte les deux notations :

※ Parser de listes *)
and parse_list_body s =
  let s = String.trim s in
  (* Chercher une barre verticale hors parenthèses *)
  match find_bar 0 0 with
  | Some pos ->
      (* [H | T] *)
      Struct (".", [parse_term h; parse_term t])
  | None ->
      (* [a, b, c] : construire la liste chaînée *)
      let terms = split_top_comma s in
      let rec build = function
        | [] -> Atom "[]"
        | h :: t -> Struct (".", [parse_term h; build t])
      in build terms

L'affichage utilise la même logique en sens inverse : une Struct(".", ...) est affichée sous forme [a, b, c] plutôt que .(a, .(b, .(c, []))). C'est plus lisible, et c'est tout l'intérêt du sucre syntaxique.

5.2 member/2 et append/3

Deux prédicats classiques sur les listes sont fournis comme natifs :

• member(E, L) — réussit si E est un élément de la liste L
• append(A, B, C) — réussit si C est la concaténation de A et B

※ member/2 : énumérer les éléments d'une liste *)
and prove_list_goal s g gs kb = match g with
  | Struct ("member", [e; lst]) ->
      let rec elements t = match t with
        | Atom "[]" -> []
        | Struct (".", [h; t']) ->
            h :: elements t'
      in
      items |> List.filter_map (fun item ->
        try Some (prove (unify e item s) gs kb)
        with UnifyError -> None)
      |> List.flatten
  | _ -> []

En pratique, member/2 permet de filtrer les éléments d'une liste :

% Lister tous les premiums
liste_premiums(L) :- findall(X, premium(X), L).

% Vérifier si un client est dans la liste des premiums
client_premium(X) :-
  liste_premiums(L), member(X, L).

6. findall/3

Le prédicat findall/3 est l'un des plus utiles de Prolog : il collecte toutes les solutions d'un but dans une liste. C'est le pont entre le backtracking (qui énumère une solution à la fois) et le traitement par lots (toutes les solutions d'un coup).

※ findall/3 : collecter toutes les solutions *)
and prove_findall_goal s g gs kb = match g with
  | Struct ("findall", [template; goal; list_ret]) ->
      let results = prove s [goal] kb in
      let items = List.map (fun s' ->
        apply s' template
      ) results in
      ※ Convertir la liste en terme Prolog *)
      let list_term = to_prolog_list items in
      ※ Unifier le résultat avec list_ret *)
      prove (unify list_ret list_term s) gs kb

Avec notre jeu de données :

% Collecter tous les premiums
?- liste_premiums(L).
% L = [2, 4, 5, 7, 8]
% (les identifiants des clients premium)

% findall/3 permet aussi de collecter d'autres choses :
?- findall(M, cell(X, montant, M), Montants).
% Montants = [1500, 800, 2500, 300, 4200, 950, 1800, 5000, 3200, 650]

7. Agrégations

Le cours 5 offrait des fonctions statistiques sur les colonnes (sum, avg, count, min, max). Le cours 9 les rend disponibles depuis les règles Prolog via des prédicats d'agrégation natifs.

※ Agrégation : sum_col/2, avg_col/2, count_col/2, min_col/2, max_col/2 *)
and prove_aggregate_goal s g gs kb = match g with
  | Struct (agg, [col_name; result]) ->
      ※ Collecter toutes les valeurs numériques de la colonne *)
      let values = kb |> List.filter_map (fun cl ->
        match cl.head with
        | Struct ("cell", [_; Atom c; Atom v])
            when c = col_str ->
            float_of_string v (* try ... *)
      ) in
      let v = match agg with
        | "sum_col" -> List.fold_left (+.) 0. values
        | "avg_col" -> ...
        | "count_col" -> ...
        | "min_col" -> ...
        | "max_col" -> ...
      in
      prove (unify result (atom_of_float v) s) gs kb

Ces prédicats s'utilisent simplement dans les règles :

% Total des ventes
total_ventes(S) :- sum_col(montant, S).

% Nombre de clients
nb_clients(N) :- count_col(client, N).

% Âge moyen
moyenne_age(M) :- avg_col(age, M).

% Montant minimum et maximum
montant_min(Mn) :- min_col(montant, Mn).
montant_max(Mx) :- max_col(montant, Mx).

8. Variables anonymes

En Prolog, on utilise souvent des variables qu'on n'utilise jamais. Par exemple, pour savoir si quelqu'un a un montant, on pourrait écrire cell(X, montant, _). Le _ (underscore) est la variable anonyme : elle s'unifie avec n'importe quoi, mais sa valeur ne nous intéresse pas.

Dans notre moteur, chaque occurrence de _ est remplacée par une variable fraîche (unique) avant la résolution :

※ Remplacer _ par des variables fraîches *)
let rec anon_to_fresh t = match t with
  | Atom _ -> t
  | Var "_" -> Var (fresh_name "anon")
  | Var x -> Var x
  | Struct (f, args) ->
      Struct (f, List.map anon_to_fresh args)

Les variables fraîches sont générées avec un compteur global : _gen_anon_1, _gen_anon_2, etc. Cela évite les collisions entre plusieurs occurrences de _ dans une même requête.

9. Multi-tables

Le cours 8 proposait les jointures comme extension. Dans le cours 9, le mode interactif supporte le chargement de deux fichiers CSV avec la commande /load2. Les tables sont fusionnées horizontalement (concaténation des colonnes, ligne à ligne).

※ Fusion de deux tables (jointure par position) *)
let combined = {
  headers = t1.headers @ t2.headers;
  rows = List.map2 (fun r1 r2 ->
    r1 @ r2
  ) t1.rows t2.rows
}

Cette fusion permet d'écrire des règles qui croisent les données des deux tables :

% Si on charge ventes.csv + produits.csv :
% les colonnes sont Client,Ville,Montant,NbAchats,Age,Categorie,Produit,Categorie,Prix,Stock

% Clients qui achètent un produit Informatique
client_informatique(X) :-
  cell(X, categorie, "Premium"),
  cell(X, categorie, "Informatique").

Notez que la jointure est par position (ligne i de la table 1 avec ligne i de la table 2). Une vraie jointure SQL (JOIN ... ON ...) nécessiterait un mécanisme plus avancé, mais c'est déjà un bon début.

10. Mode interactif amélioré

Le mode interactif du cours 9 s'enrichit de nouvelles commandes pour exploiter toutes les extensions :

Les nouvelles commandes :

11. Extensions encore possibles

Le cours 9 implémente la plupart des extensions suggérées dans le cours 8. Mais il reste de la place pour aller plus loin. Voici des pistes pour un éventuel cours 10 (ou pour vos projets personnels) :

11.1 Interface web (Dream / Eliom)

Imaginez DatAlog accessible depuis un navigateur : chargez vos CSV par drag & drop, écrivez vos règles dans un éditeur, visualisez les résultats en temps réel. Dream est un framework web léger pour OCaml qui permettrait de faire ça en quelques centaines de lignes.

let () =
  Dream.run ~port:8080
  (fun request ->
    match Dream.method_ request, Dream.path request with
    | `GET, [] ->
        (* Afficher la page d'accueil *)
        Dream.html index_html
    | `POST, ["query"] ->
        (* Exécuter une requête Prolog *)
        ...)

11.2 Export PDF

Le rapport HTML peut être converti en PDF avec des outils comme wkhtmltopdf ou WeasyPrint. Il suffit d'ajouter un fichier CSS dédié à l'impression (déjà partiellement présent dans le style).

11.3 Cache de déduction

Actuellement, chaque requête re-parcourt toute la base de connaissances. On pourrait mémoïser les résultats des prédicats les plus utilisés (comme le fait un vrai Datalog avec l'évaluation « bottom-up »).

※ Cache de déduction : idée *)
module Cache = struct
  type key = string  (* nom du prédicat *)
  type value = subst list

  let table = Hashtbl.create 16

  let memoize kb goal =
    match Hashtbl.find_opt table key with
    | Some cached -> cached
    | None ->
        let res = query kb goal in
        Hashtbl.add table key res;
        res
end

11.4 Jointure par clé

La fusion par position est limitée. Une vraie jointure par clé nécessiterait un prédicat join/4 ou une syntaxe spéciale :

% Idée : jointure entre deux tables
jointure(Client, Ville, Produit) :-
  table("ventes", Client, Ville, _),
  table("produits", Client, Produit, _).

11.5 Cut (!)

Le cut (!) est un prédicat Prolog qui permet de contrôler le backtracking : une fois qu'un cut est traversé, Prolog ne revient pas en arrière pour essayer d'autres clauses. C'est utile pour l'efficacité et pour implémenter le « if-then-else ». Mais c'est aussi controversé car ça casse la sémantique déclarative.

11.6 DCG (Definite Clause Grammars)

Les DCG sont un sucre syntaxique pour écrire des grammaires en Prolog. Elles sont utilisées pour le parsing de langages naturels et formels. Notre parseur CSV pourrait être réécrit en DCG !

12. Conclusion

Ce cours 9 a montré comment étendre un petit moteur Prolog sans le casser. Chaque extension a été ajoutée de manière orthogonale :

• L'arithmétique (is/2, comparateurs) ajoute une couche d'évaluation en plus de l'unification
• La négation (\+/1) s'appuie sur le moteur de preuve existant
• Les listes et findall/3 exploitent le typage algébrique d'OCaml
• Les agrégations pontent le monde tabulaire et le monde logique
• Le CSV robuste rend l'outil utilisable sur des données réelles

La leçon plus générale : quand on conçoit un logiciel de manière modulaire (chapitre 4, cours 4 sur les foncteurs), on peut l'étendre indéfiniment sans réécrire le passé. C'est ça, la compositionnalité.

Pour tester toutes ces extensions :

# Lancer la démonstration complète (toutes les extensions)
cd cours9
make demo

# Lancer le mode interactif avec les nouvelles commandes
make run

# Analyse rapide d'un fichier CSV
./datalog data/ventes.csv

# Analyse avec règles personnalisées (extensions incluses)
./datalog data/ventes.csv data/regles.pl