Principe de catlang

catlang est un petit langage de programmation dont le compilateur produit un seul SELECT exécuté sur PostgreSQL. Le programme count : Int -> Int présenté dans l’article illustre ce principe : il prend un entier x, boucle tant que n-100 est négatif, incrémente n et renvoie finalement 100. La boucle est exprimée à l’aide d’une construction loop qui renvoie soit inr (continuer) soit inl (terminer). Cette sémantique purement fonctionnelle est ensuite traduite en un graphe d’opérateurs catégoriques.

Langage intermédiaire basé sur la théorie des catégories

Après désugaring, le code devient une expression d’un intermediate language (IL) composé de symboles tels que id △ id, ⨟ (composition), ▽ (co‑choice) et prj₁/prj₂ (projections). Chaque opérateur possède une sémantique algébrique simple : A ⨟ B signifie « exécuter A puis transmettre le résultat à B ». Cette granularité permet de mapper l’IL vers différents back‑ends ; dans le cas présent, le mapping cible PostgreSQL. Le texte montre explicitement la forme de l’IL, par exemple : 

id △ id
⨟ cochoice
    ( undist
    ⨟   ( (prj₁ ⨟ id ▽ id) △ id
          ⨟   ( prj₁ △ 100
              ⨟ (-)
              ⨟ abs
              )
            △ id
          ⨟ prj₁ △ id
          ⨟ dist … )
    )
⨟ prj₁
Cette représentation montre comment les opérations arithmétiques (-, +), les tests de signe (abs) et les contrôles de boucle (inl/inr) sont découpés en primitives composables.

Transformation en SQL et exemple généré

Le processus de compilation consiste à remplacer chaque primitive de l’IL par une sous‑requête SQL. Le résultat est un WITH RECURSIVE qui reproduit la logique de la boucle, suivi de multiples CTE (t0, t1, …) qui implémentent les opérateurs dist, undist et les projections. Le fragment fourni débute ainsi :

SELECT
f0 AS f0
FROM
(SELECT
 f0 AS f0, f1 AS f1
 FROM
 (SELECT *
  FROM
  (WITH t0 AS
   (SELECT *
    FROM
    (WITH RECURSIVE recursion AS
     (SELECT
      clock_timestamp() as step
      , *
      FROM
      (WITH t1 AS …
Le WITH RECURSIVE assure l’itération jusqu’à ce que la condition n-100 >= 0 soit satisfaite, reproduisant exactement le comportement du programme catlang. Chaque étape du graphe catégorique se traduit en une jointure ou une projection SQL, ce qui explique la profondeur et la verbosité du code final.

Analyse des limites et perspectives

Le principal inconvénient réside dans la taille du SQL généré : même pour un programme trivial, le compilateur produit plusieurs dizaines de CTE imbriquées. Cette surcharge peut pénaliser le planificateur de PostgreSQL, augmenter le temps de parsing et rendre le debugging pratiquement impossible. De plus, l’approche repose sur des constructions SQL standard ; aucune optimisation spécifique (index, parallélisme) n’est introduite par le compilateur, ce qui laisse la performance dépendre entièrement du moteur sous‑jacent. Enfin, l’article ne fournit pas de métriques de temps d’exécution ni de comparaison avec une implémentation native, ce qui limite l’évaluation empirique du modèle. Malgré ces contraintes, le projet démontre que la catégorisation d’un langage de haut niveau peut être systématiquement traduite en requêtes relationnelles, ouvrant la voie à d’autres cibles (graphes, flux) si le mapping IL est redéfini.