Synthèse de programmes : principes et liens avec l’AGI

La synthèse de programmes consiste à construire automatiquement un programme qui respecte une spécification : propriétés logiques, exemples d’entrées et de sorties, ou combinaison de contraintes. Elle peut associer recherche symbolique et apprentissage profond pour proposer, exécuter et sélectionner des solutions. C’est une piste vers des systèmes capables d’acquérir de nouvelles compétences, mais produire un programme correct dans un domaine limité ne démontre pas une intelligence générale.

Le principe : chercher une règle exécutable

En programmation classique, vous décrivez les étapes à exécuter. En synthèse, vous décrivez surtout le résultat attendu, puis un système cherche une procédure compatible avec cette demande. La différence porte sur ce qui reste à découvrir : une transformation, une condition, une composition d’opérations ou une fonction entière.

Une tâche de synthèse comprend généralement trois éléments :

une spécification, qui décrit les comportements acceptables ;
un espace de programmes, défini par un langage et des opérations autorisées ;
une procédure de recherche et de contrôle, qui propose des candidats et évalue leur conformité.

Le programme obtenu peut être du code courant, une expression mathématique ou une séquence d’opérations dans un langage spécialisé. Il doit posséder une sémantique définie : on sait comment l’exécuter et ce que signifient ses instructions.

Cette distinction sépare la synthèse d’une simple explication en langage naturel. Une réponse peut décrire correctement une méthode sans fournir une procédure exécutable ; inversement, un petit programme peut résoudre une tâche sans produire de justification pédagogique.

La généralisation intervient dès que le programme doit fonctionner sur des entrées absentes des exemples. Retrouver les réponses fournies ne suffit donc pas : il faut découvrir une règle qui se transfère aux cas pertinents.

Un exemple : déduire une transformation de texte

Imaginons un exercice pédagogique. Vous fournissez les transformations suivantes :

Entrée : facture_rouge.pdf
Sortie : rouge

Entrée : facture_bleue.pdf
Sortie : bleue

Plusieurs procédures conviennent : retirer un préfixe et une extension fixes, extraire le texte après le premier séparateur, ou sélectionner une portion selon sa position. Elles donnent ici les mêmes réponses, mais divergent sur d’autres noms de fichiers.

Ajoutons une entrée :

Entrée : archive_facture_verte.pdf
Sortie attendue : verte

Ce cas élimine certaines hypothèses. Il ne dit pourtant pas encore comment traiter une extension différente, un séparateur absent ou un nom composé. Ces décisions appartiennent à la spécification, même si l’interface les laisse implicites.

Le synthétiseur doit donc gérer une ambiguïté d’intention. Il peut classer les solutions selon leur simplicité, demander un exemple discriminant ou présenter plusieurs interprétations. Aucun algorithme ne peut déduire avec certitude une intention que les données disponibles ne permettent pas de distinguer.

Cette logique apparaît dans les travaux de Sumit Gulwani sur les transformations de chaînes, publiés en janvier 2011. La publication originale sur la programmation par exemples décrit un langage spécialisé et une recherche de programmes compatibles avec les exemples. L’enjeu dépasse la génération de texte : il s’agit de construire une transformation réutilisable et de résoudre ses ambiguïtés.

Une histoire antérieure aux modèles de langage

La synthèse ne naît pas avec les assistants de code. Une de ses traditions historiques vient de la logique : si l’on peut démontrer constructivement qu’une sortie satisfaisant certaines conditions existe, la démonstration peut fournir la méthode pour la calculer.

Zohar Manna et Richard Waldinger ont développé cette approche déductive. Leur présentation des fondements de la synthèse déductive, publiée en 1992, explique comment extraire une procédure d’une preuve suffisamment constructive. La garantie recherchée concerne alors une spécification explicite, plutôt qu’une ressemblance avec des programmes connus.

Une autre tradition part d’exemples et cherche une règle qui les explique. Elle rend la demande plus accessible, au prix d’une information généralement moins complète. La programmation par exemples illustre ce compromis : donner une transformation attendue peut être facile, préciser toutes ses exceptions l’est moins.

Le sketching propose une voie intermédiaire. Le développeur fournit une ébauche de programme et laisse certains choix à résoudre automatiquement. Il conserve une partie de la stratégie, tandis que le synthétiseur explore les détails manquants.

Ces traditions coexistent. L’histoire du domaine n’est donc pas un remplacement simple de la logique par les réseaux de neurones. Elle correspond à plusieurs réponses à une même difficulté : exprimer suffisamment le besoin et explorer efficacement les implémentations possibles.

Les grandes familles de méthodes

Les méthodes diffèrent par la manière de représenter les candidats, de les chercher et de les contrôler. Une même architecture peut en combiner plusieurs.

Méthode	Principe de recherche	Information nécessaire	Limite caractéristique
Énumération	Construire et essayer des programmes autorisés	Grammaire, exemples ou propriétés	Multiplication des combinaisons
Résolution de contraintes	Encoder les choix dans un problème logique	Sémantique et contraintes formalisables	Difficulté et taille de l’encodage
Déduction constructive	Extraire une procédure d’une preuve	Spécification logique adaptée	Formalisation et recherche de preuve
Recherche guidée par apprentissage	Prioriser les candidats jugés prometteurs	Données d’apprentissage et contrôle des résultats	Biais du guide et coût d’exploration

L’énumération n’implique pas nécessairement d’essayer aveuglément toutes les chaînes de caractères. Les types éliminent les compositions incompatibles ; la sémantique permet de regrouper des expressions équivalentes ; des résultats intermédiaires peuvent être réutilisés.

Les solveurs de contraintes procèdent autrement : ils cherchent une affectation des choix qui rende les conditions satisfaisables. Leur efficacité dépend fortement de la formulation du problème. Transformer une tâche en contraintes ne la rend pas automatiquement facile.

L’apprentissage apporte une priorité de recherche. Il peut suggérer une opération, une structure de programme ou une décomposition probable. Cette suggestion réduit parfois l’exploration nécessaire, mais sa plausibilité ne constitue pas une garantie de correction.

La question pratique reste identique : quel mécanisme décide qu’un candidat peut être accepté, et sur quel domaine cette décision est-elle valable ?

Les contre-exemples transforment la recherche

Une architecture centrale alterne construction et réfutation. Le synthétiseur propose un programme compatible avec les cas connus ; un vérificateur cherche ensuite une entrée sur laquelle ce programme viole la spécification. S’il en trouve une, elle devient une contrainte supplémentaire.

Cette boucle porte le nom de CEGIS, pour counterexample-guided inductive synthesis. Armando Solar-Lezama en décrit l’utilisation dans le travail sur le program sketching, diffusé en 2012 puis publié en revue en 2013.

Le contre-exemple apporte davantage qu’un simple verdict négatif. Il exclut aussi les autres candidats qui commettraient la même erreur. La recherche accumule ainsi des informations sur les comportements à éviter.

La portée du contrôle doit cependant rester explicite. Un test constate le résultat sur des entrées particulières. Une vérification bornée explore un domaine limité ; une preuve peut établir une propriété générale sous des hypothèses données. Ces niveaux ne sont pas interchangeables.

De plus, une spécification peut être cohérente et insuffisante. Un programme respectant toutes les contraintes peut encore manquer le besoin réel si une règle métier a été oubliée.

Pour juger un résultat, demandez donc quelle propriété a été contrôlée, avec quelles hypothèses et quelles bornes. Le mot « vérifié » devient informatif seulement lorsque ces éléments sont précisés.

Ce que l’apprentissage profond apporte

L’obstacle principal est souvent combinatoire : chaque instruction supplémentaire ouvre de nouvelles compositions. Un réseau peut apprendre quelles opérations semblent utiles à partir des exemples, puis orienter un moteur de recherche vers ces régions de l’espace.

DeepCoder, présenté à ICLR en 2017, illustre cette division du travail. Le réseau prédit des propriétés du programme recherché, notamment les fonctions susceptibles d’y apparaître ; ces prédictions orientent des techniques de recherche. Le modèle appris aide à trouver le programme, tandis que son comportement reste évalué par exécution ou résolution.

Une autre possibilité consiste à générer directement des candidats, puis à les tester et à les corriger. L’intérêt est d’exploiter des régularités apprises sur du code et des descriptions de tâches. Le risque est de privilégier une solution familière qui ne correspond pas aux contraintes présentes.

Il faut aussi distinguer synthèse neuronale et exécution neuronale. Dans la première, un réseau contribue à produire un programme ensuite exécuté selon des règles explicites. Dans la seconde, le réseau réalise lui-même une transformation, sans nécessairement fournir de procédure symbolique inspectable.

Ces approches peuvent être complémentaires. Une perception apprise peut identifier des objets dans une image ; une recherche de programme peut ensuite déterminer comment les déplacer. L’interface entre les deux devient toutefois un point critique : une mauvaise représentation initiale peut rendre la bonne règle inaccessible.

Apprendre des abstractions avec DreamCoder

Un langage spécialisé facilite la recherche, mais ses opérations sont souvent choisies à la main. Si elles correspondent mal aux tâches, les solutions deviennent longues ou impossibles à exprimer. D’où une question supplémentaire : le système peut-il enrichir lui-même son vocabulaire de programmes ?

DreamCoder, décrit dans une publication déposée en juin 2020, associe recherche de programmes, apprentissage d’une bibliothèque de composants et apprentissage d’un guide neuronal. Des structures récurrentes dans les solutions peuvent devenir des abstractions réutilisables.

L’intérêt est cumulatif. Une composition utile, auparavant reconstruite à chaque problème, devient une opération disponible pour les suivants. La bibliothèque modifie donc l’espace de recherche, tandis que le guide apprend à mieux l’explorer.

Il faut distinguer ce mécanisme d’un simple stockage de réponses. Réutiliser une abstraction signifie appliquer une structure à de nouvelles entrées ou l’intégrer dans une autre composition. La valeur de cette abstraction se mesure à ce qu’elle permet de résoudre ensuite.

Cette idée n’élimine pas les choix initiaux. Le système conserve un langage de départ, des règles d’exécution et une procédure d’apprentissage définis par ses concepteurs. Une bibliothèque apprise peut également devenir encombrante ou trop spécialisée.

DreamCoder fournit ainsi un exemple de mécanisme d’acquisition d’abstractions, pas une démonstration d’autonomie intellectuelle générale. Le transfert vers des domaines éloignés reste une question distincte du progrès à l’intérieur des domaines étudiés.

Pourquoi cette piste intéresse la recherche sur l’AGI

Un programme peut représenter une règle compacte et l’appliquer à des situations nouvelles. Cette propriété rend la synthèse intéressante pour étudier la composition de connaissances, l’adaptation et l’apprentissage à partir de peu d’exemples.

Dans On the Measure of Intelligence, publié en novembre 2019, François Chollet distingue la compétence obtenue de l’efficacité avec laquelle un système acquiert de nouvelles compétences. Son cadre demande de tenir compte des connaissances préalables, de l’expérience et de la difficulté de généralisation.

Cette position invite à examiner comment une solution est acquise, plutôt que son seul résultat. La page sur la généralisation développe cette distinction. La synthèse offre un terrain pour l’étudier, parce que les hypothèses peuvent prendre la forme de procédures exécutables.

Les tâches de transformation de grilles, abordées dans la page de référence ARC-AGI, permettent notamment de raisonner en termes d’objets, de relations et d’opérations. Trouver une procédure compatible avec les démonstrations constitue une manière possible de les traiter.

Mais une réussite ne permet pas, à elle seule, d’identifier le mécanisme utilisé. Elle peut provenir d’une recherche structurée, d’une reconnaissance de motifs déjà appris ou d’une combinaison. Il faut des expériences supplémentaires pour départager ces explications.

Cette page expose les principes durables ; l’article voisin sur la synthèse de programmes et la piste de Ndea traite l’angle du projet de recherche.

Les désaccords portent aussi sur les connaissances initiales

Les chercheurs ne s’accordent pas sur la quantité de structure qu’il convient de fournir à un système. Des objets, des relations spatiales et des opérations prédéfinies peuvent faciliter l’apprentissage. Ils peuvent aussi orienter les résultats vers les catégories anticipées par les concepteurs.

Richard Sutton défend une autre priorité dans The Bitter Lesson, publié en mars 2019 : privilégier les méthodes générales de recherche et d’apprentissage capables de bénéficier de davantage de calcul, plutôt que d’accumuler des connaissances humaines spécifiques.

Cette position ne réfute pas la synthèse de programmes. Une recherche dans un espace de programmes peut elle-même être générale et guidée par apprentissage. La tension apparaît surtout lorsque la réussite dépend d’un langage très spécialisé, ajusté aux problèmes évalués.

Il faut donc séparer plusieurs questions : les primitives sont-elles écrites à la main ? Le guide est-il appris ? Le système peut-il inventer des abstractions ? Peut-il changer de représentation lorsque son langage actuel ne suffit plus ?

Présenter ce débat comme une opposition entre symboles et neurones masquerait les architectures hybrides. La divergence concerne aussi la manière d’obtenir la structure utile et les conditions de son transfert.

La position prudente consiste à comparer les mécanismes sur des tâches nouvelles, avec des ressources documentées. Ni une préférence théorique ni un résultat isolé ne tranche la question de l’architecture nécessaire à l’AGI.

Les limites : représentation, coût et intention

La synthèse suppose que la solution soit accessible dans l’espace exploré. Si le langage ne permet pas d’exprimer une opération indispensable, prolonger la recherche ne résout rien. Élargir le langage apporte de l’expressivité, mais augmente les possibilités à examiner.

Le choix de la représentation est tout aussi déterminant. Une image décrite comme une liste de pixels n’offre pas les mêmes raccourcis qu’une image décrite comme un ensemble d’objets. Construire la bonne représentation peut demander autant de travail que découvrir la transformation.

La simplicité d’un programme dépend elle-même du langage disponible. Une règle paraît courte lorsqu’une primitive réalise déjà l’essentiel du travail. Comparer des longueurs de programmes exige donc d’examiner aussi la bibliothèque et les connaissances qu’elle contient.

Le coût ne se réduit pas au nombre d’appels à un modèle. Il comprend les candidats explorés, leur exécution, la vérification, la mémoire et les éventuelles adaptations. Un résultat obtenu avec davantage de recherche doit être présenté avec ce budget.

Enfin, un programme explicite n’est pas automatiquement sûr. Ses effets peuvent dépasser la transformation attendue s’il accède à des fichiers ou à un réseau. Lorsqu’on exécute des candidats inconnus, un bac à sable et des limites de ressources servent à contenir ces effets pendant l’évaluation.

Évaluer une démonstration et reconnaître les usages utiles

Une évaluation convaincante doit distinguer les exemples utilisés pour chercher des solutions des cas conservés pour les mesurer. Elle doit également préciser les interventions humaines : choix des primitives, corrections de la spécification et sélection finale des candidats.

Pour lire une publication ou examiner un prototype, vérifiez :

La demande : exemples seuls, description libre ou propriétés formelles.
L’espace exploré : langage, bibliothèque et restrictions.
Le contrôle : tests, recherche de contre-exemples ou preuve.
Les ressources : calcul, temps, mémoire et intervention humaine.
Le transfert : variantes proches ou changements de structure.

Le guide pour évaluer un agent IA fournit une méthode complémentaire lorsque la synthèse s’insère dans une boucle d’outils. Une amélioration peut provenir du modèle, du moteur de recherche ou d’un meilleur vérificateur : les expériences doivent permettre de les distinguer.

Les assistants de développement tels que Codex, Claude Code et OpenHands constituent un contexte voisin. Leur présence dans une tâche de programmation ne suffit cependant pas à établir une synthèse formellement vérifiée : il faut examiner les contraintes et les contrôles effectivement employés.

Les usages les plus faciles à cadrer présentent une sortie exécutable, un domaine délimité et des critères de réussite observables. Plus l’objectif dépend d’une intention tacite ou d’effets difficiles à simuler, plus la spécification et la validation deviennent centrales.

À retenir

La synthèse construit une procédure à partir de contraintes ; sa fiabilité dépend de la spécification et du contrôle.
L’apprentissage profond peut guider la recherche, proposer des candidats et contribuer à l’acquisition d’abstractions.
Réussir les exemples ne prouve ni la correction générale ni le transfert vers d’autres domaines.
La synthèse fournit des mécanismes pertinents pour étudier l’intelligence, sans établir à elle seule une voie suffisante vers l’AGI.

Le dossier AGI et recherche replace ces mécanismes parmi les autres approches de l’apprentissage, du raisonnement et de l’évaluation.

Pages liées

Questions fréquentes

Quelle différence entre synthèse de programmes et compilation ?

Un compilateur traduit généralement un programme déjà défini vers une autre représentation, en préservant son comportement. Un synthétiseur doit déterminer une implémentation à partir d’une description qui laisse des choix ouverts. Certains outils combinent ces fonctions.

La synthèse de programmes exige-t-elle un modèle de langage ?

Non. Elle peut utiliser une énumération de programmes, des solveurs de contraintes ou une démonstration logique. Un modèle appris peut aider à explorer les possibilités, mais il ne constitue pas une condition nécessaire.

Un programme synthétisé est-il toujours lisible ?

Non. Sa lisibilité dépend du langage utilisé, des abstractions disponibles et des critères de sélection. Un programme compact peut rester difficile à comprendre si ses opérations sont opaques ou si ses noms ne décrivent pas leur rôle.

La synthèse de programmes peut-elle remplacer les développeurs ?

Elle automatise certaines recherches d’implémentation, mais laisse ouvertes la définition du besoin, la conception du système et l’évaluation des conséquences. Son utilité dépend de la précision des contraintes et de la possibilité de contrôler le résultat.

Peut-on reconnaître une AGI à sa capacité à écrire du code ?

Cette capacité constitue un élément d’évaluation, pas un critère suffisant. Il faut aussi examiner l’acquisition de compétences nouvelles, le transfert entre domaines et les ressources nécessaires. Une performance en programmation ne répond pas seule à ces questions.