Cognition : un nouveau langage d’antisyntaxe qui redéfinit la méta-programmation

Introduction au langage de programmation Cognition

Problématique

• Les programmeurs Lisp affirment qu’avec le code S-expressions et un système de macros fonctionnel, la méta-programmation et la création de systèmes généralisés sont possibles
• Mais Lisp a un problème fondamental
  • La méta-programmation et la programmation ne coïncident pas, donc Lisp impose toujours une syntaxe stricte (parenthèses ou caractères dédiés au look-ahead)
  • La parenthèse ouvrante indique à Lisp qu’il doit continuer à lire jusqu’à rencontrer la parenthèse fermante
  • Cela rend les parenthèses gauche et droite immuables dans le langage (pas au sens conceptuel, mais impossible dans certaines implémentations)
  • Plus important, modifier plus tard l’ordre de distinction de ces tokens est impossible sans manipulation de chaîne de caractères
• D’autres langages ont aussi des mécanismes différents pour déterminer ce qu’il faut lire ensuite en regardant certains tokens
  • Ce processus est ce que l’on appelle la syntaxe
• Cognition adopte une antisyntaxe basée sur une notation postfixe complète pour faire autrement
  • Elle se rapproche des langages de programmation concaténatifs, mais ces derniers ont aussi deux problèmes majeurs
    1. l’introduction de caractères de crochets gauche/droit (en réalité une notation préfixe)
    2. les caractères de quote pour les chaînes
  • Cela n’est pas adapté pour un langage général
  • Le même problème apparaît dans l’implémentation Lisp en syntaxe C (abondance de caractères d’échappement, nécessité d’espaces pour distinguer le début et la fin d’un token)
• Racket possède un système de macros, mais il n’est pas dynamique à l’exécution et s’appuie sur un préprocesseur

Présentation de Cognition

• Un projet sur lequel j’ai travaillé avec Matthew Hinton pendant plusieurs mois
• L’objectif est de créer l’un des systèmes de syntaxe les plus généralisés avec une notation postfixe complète
• Une connaissance de la syntaxe, de la tokenization et du parsing peut être nécessaire, mais j’essaie d’expliquer de manière accessible
• Dépôt : https://github.com/metacrank/cognition

Cognition bare-metal

• Baremetal Cognition est proche de Brainfuck, mais rend possible une méta-programmation poussée
• Exemple de code de bootstrap :

ldfgldftgldfdtgldf dfiff1 crank f

• Les espaces et les retours à la ligne comptent
  • La 2e ligne a un espace après df
  • La 3e ligne contient un espace
• C’est ce qui permet d’introduire deux nouveaux concepts : délimiteur (delimiter) et ignoré (ignore)

Tokenization

• Le délimiteur permet au tokenizer de séparer le début et la fin d’un token
• La liste de tokenizer mono-caractère est publique, et elle peut être lue et modifiée depuis Cognition
• Un caractère ignoré est totalement ignoré par le tokenizer dès la première étape de la boucle read-eval-print
  • C’est-à-dire qu’au début de la collecte des tokens, l’ensemble des caractères ignorés configurés est sauté
• Par défaut, tous les caractères sont des délimiteurs et aucun caractère n’est ignoré
• Il est possible d’activer un basculement blacklist/whitelist pour les listes de délimiteurs et de caractères ignorés (ce qui apporte concision et praticité)

Falias

• Un Falias est une liste de mots qui s’exécutent lorsqu’elle est placée sur la pile
• Chaque Falias exécute le sommet de la pile (équivalent à eval dans Stem)
• f est le Falias par défaut : au lieu d’être placé sur la pile, il exécute le sommet de pile d
• d remplace la liste des délimiteurs par la valeur chaîne du mot (c’est-à-dire en retirant l de la liste des délimiteurs)
• Dans l’environnement par défaut, aucun mot ne s’exécute, à part les Falias spéciaux

Remarque sur les délimiteurs

• Les délimiteurs obéissent à une règle intéressante
  • Si, dans la boucle de tokenization, un caractère n’est pas ignoré, le caractère délimiteur est inclus dans le token courant et la boucle continue
  • C’est le contraire d’un singlet (qui inclut lui-même puis saute pour terminer la collecte du token)
• Le mode blacklist/whitelist peut aussi être configuré
  • Les listes de délimiteurs, de singlets et de caractères ignorés peuvent être blacklister/whitelister
  • Par défaut, il n’existe ni délimiteur blacklisté, ni singlet whiteliste, ni caractère ignoré whitelisté
• Tous les autres caractères sont collectés comme partie du token courant, et l’on continue d’ajouter de nouveaux caractères tant que la boucle n’est pas arrêtée par les règles des délimiteurs ou des singlets

Suite du code de bootstrap

ldf

• Cela rend l non délimiteur

gldftgldfdtgldf  dfiff1 crank f

• d étant un délimiteur, gl est placé sur la pile, puis le Falias f est appelé pour rendre gl non délimiteur
• tgl est placé sur la pile et devient non délimiteur via df
• dtgl est placé sur la pile et devient non délimiteur via \ndf; ici \n est le seul caractère non délimiteur (la fin de ligne \n est incluse dans le code réel)
• Selon les règles des délimiteurs, le caractère espace et \n sont placés sur la pile (la 3e ligne contient un espace)
• Un autre mot \ \n est tokenisé
• La pile est actuellement la suivante (du bas vers le haut) : 3. dtgl 2. [caractère espace]\n
  1. [caractère espace]\n
• df définit \ \n comme non délimiteur
• if définit \ \n comme caractère ignoré (ignoré au début de la tokenization)
• f exécute dtgl, qui active le basculement dflag de la liste noire/blanche des délimiteurs
• Désormais, tous les caractères non délimiteurs deviennent des délimiteurs, et tous les délimiteurs deviennent des caractères non délimiteurs
• Enfin, l’espace et la fin de ligne deviennent les délimiteurs de token, et sont ignorés au démarrage de la tokenization
• Puis 1 est tokenisé et placé sur la pile, puis le mot crank est tokenisé et exécuté par f (1 est traité comme un nombre dans ce cas, mais dans Cognition, tout est un mot)
• Séquence de bootstrap terminée. Le rôle de crank sera expliqué dans la section suivante

Résumé du bootstrap

• Cognition permet de modifier dynamiquement la tokenization par programmation
  • ce qui est impossible dans les autres langages
  • on peut programmer un tokenizer pour des langages externes dans Cognition et tokeniser selon ce que l’on veut
• C’est possible grâce à la notation postfixe et à l’absence de look-ahead
  • aucune analyse de plus d’un token n’est nécessaire avant d’évaluer une expression
• Les Falias permettent d’exécuter des mots sans mot préfixe ni mot système

Crank

• Le système metacrank permet de définir la méthode par défaut d’exécution d’un token placé sur la pile
• Le mot crank prend un nombre en argument et exécute le sommet de la pile à chaque fois que n mots sont placés sur celle-ci
• Exemple de code (crank 1 en configuration) :

5 crank 2
crank 2 crank 
1 crank unglue swap quote prepose def

• En environnement crank 1, on peut arrêter d’utiliser f
  • chaque token tokenisé est évalué un par un
  • comme la syntaxe est programmée autour des espaces et retours à la ligne, le code reste intuitivement lisible
• Le code commence par tenter d’évaluer 5 (ce n’est pas un builtin, il s’auto-évalue)
• crank est configuré pour s’exécuter dès que 5 tokens sont placés sur la pile
• 2crank, 2, crank et 1 sont tous placés sur la pile (crank est un builtin avec crank 5, donc il n’est pas exécuté) : 4. 2crank 3. 2 2. crank
  1. 1
• crank est le 5e mot, donc il s’exécute (crank 1 en configuration)
• unglue est un builtin qui récupère la valeur du mot du sommet de pile utilisée par 1
  • c’est-à-dire le pointeur de fonction associé au builtin crank
• La pile devient : 3. 2crank 2. 2
  1. [CLIB]
  • CLIB pointe vers le pointeur de fonction du builtin crank
• Exécution de swap : 3. 2crank 2. [CLIB]
  1. 2
• Exécution de quote (builtin citant le sommet de pile) : 3. 2crank 2. [CLIB]
  1. [2]
• Exécution de prepose (similaire à compose dans Stem, mais placé en tête, nommé VMACRO) : 2. 2crank
  1. ([2] [CLIB])
• Appel de def
  • définit le mot 2crank en plaçant 2 et en appelant le pointeur de fonction qui référence le builtin crank
• Il reste à expliquer ce qu’est un VMACRO, ainsi que la différence entre la pile Cognition et la pile Stem

Différences avec Stem

• Dans la pile Stem, on peut déposer directement un mot sur la pile
• Dans Cognition, un mot est mis dans un conteneur et déposé sur la pile sans être évalué
  • Dans Stem, un mot comme compose agit sur un mot (ou un conteneur avec un seul mot) et un autre conteneur
  • Cela rend l’API de Cognition plus cohérente
• Le mot cd s’appuie aussi sur ce concept

Macros

• Autre différence entre la citation Stem et le conteneur Cognition
• Lorsqu’une macro est évaluée, tout ce qui se trouve dans la macro est évalué et crank est ignoré
• Lorsqu’il est lié à un mot, lors de l’évaluation de ce mot,

[GN⁺]

Commentaires Hacker News

Voici un résumé de quelques remarques principales :

• L’explication du projet Cognition lui-même apparaît trop tard dans l’introduction du document. Il vaudrait mieux présenter d’abord les éléments les plus importants pour gagner du temps au lecteur.
• Comme avec la configuration de la couche reader de Racket, il existe déjà d’autres approches permettant d’étendre la syntaxe tout en préservant l’interopérabilité. On peut se demander si l’approche de Cognition est vraiment « meilleure ».
• Même Common Lisp permet de modifier librement la syntaxe via les reader macros, les macros et les compiler macros. La méta-programmation consiste avant tout à traiter la sémantique plutôt que la syntaxe.
• La capacité de Cognition à définir, redéfinir et sortir/revenir de structures syntaxiques au runtime est belle et intéressante. Cela ouvre la possibilité de créer de vraies machines capables de « penser ».
• La syntaxe servant à fournir une structure, la supprimer serait contradictoire. Une syntaxe trop concise peut nuire à la lisibilité et à la compréhension.
• La manière de présenter le document est un peu verbeuse et semble parfois satirique, ce qui le rend difficile à lire. Mais le sujet est traité en profondeur.