Kim Yu

Rescaled Weibull tail-distributions

published or not. The documents may come

Theorem. Let X be a random variable from a Weibull-tail model [START_REF] Asimit | Pitfalls in using Weibull tailed distributions[END_REF]. Let Y = λX with λ > 0. Then, Y follows a Weibull tail-distribution with associated Weibull tail-coefficient θ.

Proof. Let us consider

P (Y ≤ y) = P (λX ≤ y) = P (X ≤ y/λ) = F (y/λ) = 1 -exp -y 1/θ l(y) ,
with l(y) = λ -1/θ ℓ(y/λ). The conclusion follows.

On the basis of this result, the estimation of θ can be achieved by applying classical Weibull-tail index estimators to X or λX. Berred [START_REF] Berred | Record values and the estimation of the Weibull tail-coefficient[END_REF] uses record values while most of estimators are based on the largest observations of the sample: Asimit et al. [START_REF] Asimit | Pitfalls in using Weibull tailed distributions[END_REF], Beirlant et al. [START_REF] Beirlant | Semiparametric lower bounds for tail index estimation[END_REF][START_REF] Beirlant | The mean residual life function at great age: applications to tail estimation[END_REF][START_REF] Beirlant | Practical analysis of extreme values[END_REF], Broniatowski [6], Diebolt et al. [START_REF] Diebolt | Bias-reduced estimators of the Weibull tail-coefficient[END_REF][START_REF] Diebolt | Bias-reduced extreme quantiles estimators of Weibull tail-distributions[END_REF], Dierckx et al. [START_REF] Dierckx | A new estimation method for Weibull-type tails based on the mean excess function[END_REF], Gardes et al. [START_REF] Gardes | Estimating extreme quantiles of Weibull taildistributions[END_REF][START_REF] Gardes | Comparison of Weibull tail-coefficient estimators[END_REF][START_REF] Gardes | Estimation of the Weibull tail-coefficient with linear combination of upper order statistics[END_REF][START_REF] Gardes | Weibull tail-distributions revisited: a new look at some tail estimators[END_REF][START_REF] Methni | Estimation of extreme quantiles from heavy and light tailed distributions[END_REF], Girard [START_REF] Girard | A Hill type estimate of the Weibull tail-coefficient[END_REF], Goegebeur et al. [START_REF] Goegebeur | Generalized kernel estimators for the Weibull-tail coefficient[END_REF][START_REF] Goegebeur | Goodness-of-fit testing for Weibull-type behavior[END_REF] and Mercadier et al. [START_REF] Mercadier | Optimal rates of convergence in the Weibull model based on kernel-type estimators[END_REF].


Théophile Gautier, historien du théâtre ?

Olivier BARA En 1929, a paru chez Payot une édition choisie des feuilletons de Théophile Gautier intitulée Les Maîtres du théâtre français de Rotrou à Dumas fils. L'auteur de cette édition, Amédée Britsch, bibliothécaire en chef de l'université de Paris, donne sens à ses choix de textes et précise en préface ses ambitions, notamment celle-ci : « Ainsi rassemblés dans l'ordre historique, [les feuilletons de Gautier] nous laissent regretter la belle et vivante histoire du théâtre français que le critique eût pu écrire, lui qui l'apercevait pardelà les frontières de l'espace et du temps, en conjonction avec les théâtres grec et latin, anglais et allemand, avec Euripide, Plaute, Shakespeare et Goethe qu'il goûtait également 1 ». Le projet et la tentation de l'éditeur de ce recueil sont clairs : il s'agit d'une part de corriger la myopie supposée du feuilletoniste en révélant la hauteur et la longueur de perception de son regard, sa capacité à embrasser l'histoire du théâtre en deçà et au-delà de l'hic et nunc des affiches parisiennes de son temps ; d'autre part, face au fatras des feuilletons accumulés pendant près de quarante ans au gré des circonstances, l'ambition d'Amédée Britsch consiste à construire artificiellement une « histoire du théâtre français » selon Gautier, à suggérer à travers le choix des feuilletons et leur montage chronologique une vision gautiériste de l'histoire du théâtre. Cette vision est construite de façon conjecturale par l'édition de 1929 selon un double processus de sélection d'une majorité de feuilletons portant sur des reprises de pièces anciennes, des XVII e et XVIII e siècles, et de mise en série des dramaturges analysés par Gautier, « de Rotrou à Dumas fils », selon le titre du recueil. Le choix est évidemment arbitraire : sont éliminés du volume les multiples vaudevillistes contemporains dont les oeuvres sont commentées à longueur de colonnes par Gautier qui, il est vrai, ne les considérait pas comme des « maîtres » ; sont passés sous silence les comptes rendus de spectacles para ou infra-littéraires, équestres, pantomimiques ou féeriques, que le feuilletoniste se plaît à intégrer dans ses comptes rendus 2 comme dans sa pensée du théâtre, saisi dans ses développements anciens et modernes ; sont imposés, enfin, sous l'appellation de « maîtres du théâtre français », deux noms constituant des bornes artificielles de l'empan historique embrassé par Gautier. Certes, le choix de Rotrou fait sens chez Gautier, tourné vers le théâtre dit préclassique de l'époque Louis XIII, passionné par la redécouverte, due à l'acteur et directeur de l'Odéon Bocage, du Véritable Saint Genest, « drame shakespearien avec changement de scène » et « double théâtre [START_REF] Gautier | Signe du soutien actif apporté à cette redécouverte de la pièce de Rotrou, Gautier a composé un « Prologue d'ouverture de l'Odéon[END_REF] annoncée se réduit de façon drastique aux vingt-cinq années, vingt-quatre plus exactement, qui séparent l'entrée en critique de Gautier en 1835 6 de la publication de ce recueil en 1858. L'« avertissement des éditeurs », en tête de volume, tente de justifier un tel titre, qui voit le feuilletoniste élevé au rang d'historien, ou l'historien du théâtre ramené au statut de chroniqueur de la vie théâtrale de son temps : Le théâtre comme le journal, dans l'ère moderne, se trouvent placés sous le signe de la mutabilité, de la variation rapide des goûts comme de l'accélération du temps ; un feuilletoniste solidement installé durant plus de deux décennies dans son rez-de-chaussée, chroniqueur régulier du passage des époques et des modes, aurait de fait voix d'historien, d'historien du théâtre en l'occurrence -du moins si l'on considère qu'au XIX e siècle il n'est d'historien des temps que le chroniqueur de l'éphémère. Paradoxalement, c'est au régime du passage, du passager et de l'évanescent, qu'il s'agit d'arracher le feuilletoniste, transfiguré en historien par la grâce d'une mise en recueil de ses feuilletons -feuilletons eux-mêmes arrachés à leur temporalité propre comme à leur support médiatique et à leur mode de consommation, pour accéder à un nouveau régime temporel dans le monument du Livre. Gautier n'est bien sûr pas le seul feuilletoniste à voir son oeuvre hebdomadaire, circonstancielle, transformée en témoignage pour l'histoire autant qu'en livre d'histoire : Jules Janin, Francisque Sarcey ou Jules Lemaître, pour ne citer que les plus illustres critiques de théâtre, virent aussi leurs feuilletons séparés du journal pour se fixer dans le recueil, et accéder ainsi après-coup à la fonction historiographique [START_REF] Voir | Histoire de la littérature dramatique[END_REF] La contre-histoire du théâtre, attentive à réintégrer dans la connaissance des temps passés les simples « talents » oubliés, à les arracher à la poussière du temps, tend surtout à résister (nouvel héritage romantique) à la prégnance du modèle classique néo-aristotélicien dans l'histoire du théâtre en voie de fixation [START_REF]Voir le vigoureux et revigorant ouvrage de Florence DUPONT, Aristote ou le vampire du théâtre occidental[END_REF] . La désinvolture et l'ironie sont les instruments chargés de saper la promotion des règles dites classiques, considérée comme tournant de l'histoire du théâtre français, arrachement au chaos et élévation vers la lumière. À propos du Véritable Saint-Genest redécouvert à l'Odéon en 1845, le feuilletoniste Gautier remarque : « La fougue cavalière de Rotrou accepte difficilement ces règles terribles des trois unités, contre lesquelles Corneille se débat dans ses préfaces avec cette humilité que le génie seul est capable d'avoir visà-vis de la sottise et de la pédanterie [START_REF] Gautier | Les Maîtres du théâtre français de Rotrou à Dumas fils[END_REF] ». Dans Les Grotesques, l'invention des fameuses unités est moins due à un processus historique de réinterprétation de la Poétique d'Aristote entamée depuis la Renaissance par un Jean de La Taille, ou d'accompagnement culturel de la politique centralisatrice de Richelieu et Louis XIII, qu'aux contingences de la petite histoire de la courtisanerie des poètes et des faiblesses de Richelieu : Ici éclaterait le triple paradoxe de Gautier, écrivain de l'histoire.

Tel serait le premier paradoxe de Gautier historien du théâtre malgré lui : il est l'historien d'un théâtre finalement sans histoire. S'affirme régulièrement sous sa plume le principe de rémanence dans le temps, qui fait de l'actuel un simple avatar de l'éternel. Ainsi, un genre nouveau au XIX e siècle, le mélodrame, identifié au nouveau régime industriel du théâtre comme à la massification de son public, apparaît bientôt aux yeux du feuilletoniste revenu de tous les étonnements premiers comme une simple perpétuation de l'antique par la résistance dans l'histoire d'un théâtre de types fixes :

Le vieux mélodrame se rapprochait de la tragédie ou de la comédie antiques par ses personnages passés à l'état de types, et qui auraient pu se jouer avec des masques. Chaque rôle avait sa physionomie traditionnelle, et dont on ne s'écartait jamais, pas plus qu'à Naples on ne change le nez noir de Pulcinella et aux Funambules le visage blafard de Pierrot [START_REF] Gautier | feuilleton du Moniteur universel[END_REF] .

Cette vision proprement conservatrice d'un théâtre dont le devenir masque une profonde permanence se constitue grâce à la distance temporelle : ce feuilleton du Moniteur universel date du 14 mai 1855 et revisite le « bon gros mélodrame » des origines, le mélo de Pixerécourt et de Ducange, à la lumière moderne du drame de Dupeuty et Bourget, Les Carrières de Montmartre, drame où se révèle toute l'efficacité des « ingrédients du genre ». L'intérêt de Gautier pour les minores du théâtre présent ou ancien serait en partie lié à cette quête, angoissée peut-être, d'une perpétuation essentielle, perceptible en deçà des trop apparentes évolutions de la scène. Le mélodrame classique, dans le même article, ramène à une « ère naïve de l'art », à la « simplicité magnifique et patriarcale 24 » à laquelle il est donné au feuilletoniste de rêversonge régressif et protecteur : l'originel retrouvé au théâtre est une petite victoire sur le régime historique de la perte. Dans d'autres domaines dramatiques, la Phèdre de Racine apparaît « complètement païenne » : « c'est de l'Euripide presque pur, mélangé çà et là d'un peu de Sénèque 25 ». Plus surprenant encore, le Marivaux du Jeu de l'amour et du hasard communique avec Shakespeare : « Cette veine romanesque de Shakespeare, si Marivaux n'y a pas puisé, il l'aura sans doute rencontrée dans la littérature italienne, comme le grand Williams [sic]. Ces concetti si brillants, ces ingéniosités si fines, que le goût n'a pas le courage de les blâmer, ont une source pareille [START_REF] Gautier | [END_REF] ». Même chez un auteur comme Beaumarchais conçu, nous le verrons plus loin, comme fondateur d'une nouvelle ère du théâtre, se constatent l'éternité et l'ubiquité de la comédie. À propos du Barbier de Séville, Gautier note : « Il y a un fonds éternel dans cette pièce si neuve d'allures, le fonds que cent-mille pantomimes n'ont pas épuisé en remplaçant Rosine par Colombine, Bartholo par Cassandre, Almaviva par le beau Léandre, Figaro par Arlequin, Basile débarbouillé dans sa noirceur jésuitique par Pierrot 27 […] ». Et Gautier de rêver, dans le célèbre article « Shakespeare aux Funambules » de la Revue de Paris en 1842, à « ce grand poète », « cet être collectif », auteur sans attache temporelle ni spatiale des « parades » et autres canevas de la pantomime [START_REF] Gautier | Shakespeare aux Funambules[END_REF] . Le goût de Gautier pour la comédie, son attachement à la permanence des types, révèlent combien le plaisir du théâtre peut être lié chez lui à la sortie hors de l'histoire, au dégagement temporel offert par l'articulation ludique des mêmes types et des mêmes situations comiques. Le temps comique, fondamentalement anhistorique, est celui du retour permanent du même, au même.

Cette compression des temps par quoi s'annule toute idée de possible progrès dans l'art dramatique trouve aussi une explication dans la conception romantique du génie nourrie par Gautier. Le génie dramatique concentre par avance tous les développements possibles de son art, entraînant après lui une constante involution du temps -les successeurs de talent ne font que revenir aux formes engendrées par l'artiste génial. Tel est le deuxième paradoxe, lié à l'imaginaire gautiériste d'une aurore contenant, plus qu'à l'état de simple promesse, tous les rayonnements d'un nouveau devenir. Corneille est cette aurore par où commence et déjà s'achève, faute de développements possibles, tout un pan de l'histoire du théâtre.

Tout est déjà là :

Le style de Nicomède n'est autre chose que le style du drame trouvé avant le drame, comme le style du Menteur est le style de la comédie trouvé avant la comédie, comme le style du Cid est le style de la tragédie trouvé avant la tragédie. Corneille, dès l'aurore du théâtre, a créé la triple lyre et l'a livrée avec toutes ses cordes aux poètes de l'avenir. -On en a retranché, mais on n'en a pas ajouté [START_REF] Gautier | Les beautés choquantes" : Corneille dans la critique dramatique de Gautier », dans Corneille des Romantiques, textes réunis et présentés[END_REF] .

Éternel retour du même dans l'éternité du scénario comique comme des types ; simples avatars de formes dramatiques faisant l'histoire du théâtre ; éclats de génie concentrant d'un coup tous les développements possibles de la scène : cette triple négation de l'histoire conçue comme processus coexiste pourtant chez Gautier avec la perception d'une évolution fondée sur une rupture -troisième paradoxe : celui de la réintroduction de la coupure historique dans une vision étale du passé théâtral. La rupture est notamment celle de Beaumarchais ; elle met un terme, selon Gautier, à « l'influence latine », à la « comédie à masques » recouvrant les visages humains ; elle inaugure « la modernité de la comédie » ou la « comédie romantique », ou encore « la comédie sociale à intentions révolutionnaires dans le fond comme dans la forme ». Pourtant, dans ce rare moment où le feuilletoniste pense l'histoire du théâtre en termes de basculement, lié aux bouleversements sociaux et politiques de la Révolution, une hésitation se perçoit, comme un léger tremblement de la plume ; le feuilletoniste confie : « nous aimons assez ces masques derrière lesquels le poète est à son aise pour faire défiler l'humanité avec une sorte d'abstraction philosophique des temps et des lieux. Ce n'est ni un blâme ni une préférence que nous prétendons exprimer ici, mais une simple constatation [START_REF] Gautier | [END_REF] . » La préférence de Gautier s'exprime plus franchement dans son oeuvre romanesque et théâtrale, occupée à ressusciter les types de la comédie dans Le Capitaine Fracasse comme dans Pierrot posthume ou Le Tricorne enchanté. De même, tout en prenant acte des réformes de Goldoni, qui mettent fin à la comédie improvisée et aux masques italiens, Gautier avoue avoir une préférence pour le théâtre merveilleux et fou de Carlo Gozzi [START_REF] Voir | Gautier et le théâtre du XVIII e siècle[END_REF] .

Ne s'agit-il pas de réaffirmer ici comme ailleurs, dans cette nostalgie du masque et du type rattachés à une anthropologie classique, à une conception fixiste de l'humanité, l'impérieuse nécessité de préserver au théâtre un processus allégorique, seul moyen de sauver l'idée de sa disparition totale dans la pure présence matérielle des corps et des objets en scène ? On touche ici à l'une des affirmations les plus puissantes de Gautier, qui tend à assimiler le théâtre au dernier stade de l'évolution artistique d'une civilisation condamnée à la chute. Telle est l'affirmation posée très tôt, dans l'article consacré à Théophile de Viau et intégré en 1844 dans l'édition des Grotesques :

Le théâtre exclut absolument la fantaisie. -Les idées bizarres y sont trop en relief, et les quinquets jettent un tour trop vif sur les frêles créatures de l'imagination. Les pages d'un livre sont plus complaisantes, le fantôme impalpable de l'idée se dresse silencieusement devant le lecteur, qui ne le voit que des yeux de l'âme. Au théâtre, l'idée est matérielle, on la touche du doigt dans la personne de l'acteur ; l'idée met du plâtre et du rouge, elle porte une perruque, elle se passe un bouchon brûlé sur les sourcils pour se les rendre plus noirs, elle est là sur ses talons, près du trou du souffleur, tendant l'oreille et faisant la grosse voix. […] L'ode est le commencement de tout, c'est l'idée ; le théâtre est la fin de tout, c'est l'action ; l'un est l'esprit, l'autre est la matière. […] Ce n'est que dans leur vieillesse que les sociétés ont un théâtre ; dans leur décrépitude, quand elles ne peuvent plus supporter le peu d'idéalité que le théâtre contient, elles ont la ressource du cirque [START_REF] Gautier | Théophile de Viau[END_REF] .

Par l'opposition entre le genre primitif, originel, de l'ode et la forme moderne du théâtre, ces phrases font écho aux théories hugoliennes exposées dans la préface de Cromwell. Manque toutefois la perspective dialectique qui, chez Hugo, articule l'ode, l'épopée et le drame -lequel drame n'est d'ailleurs pas réductible au théâtre. Cette réécriture binaire de la dialectique historique correspond finalement à la vision antiprogressiste de l'histoire propre à Gautier. Si histoire du théâtre il y a, ou pensée historique du devenir du théâtre, elle est hantée par la perspective d'une chute inéluctable de toute idée dans la matérialité et le prosaïsme. À moins qu'un spectacle mineur comme celui de la pantomime ou celui des marionnettesévoqué dans un de ses derniers feuilletons, le 18 décembre 1871 dans la Gazette de Paris -assure une pérennité transhistorique à l'art de la scène, maintenant intactes dans le processus symbolique les possibilités d'échanges entre idée et matière [START_REF] Kleist En Allemagne | Nodier, Magnin ou Sand en France, la marionnette apparaît également comme l'origine de tout théâtre mais aussi comme une possible résolution des défauts humains et techniques de la scène moderne[END_REF] . Sauver le théâtre de la pure matérialité en prônant un retour à la convention et à la poésie des gestes, des répliques et des masques, n'est-ce pas, finalement, conjurer la loi historique, le nécessaire devenir théâtral de la civilisation, ou, si l'on préfère, la fatalité de son matérialisme comme de son utilitarisme [START_REF]Il s'agirait tout à la fois de conjurer l'oubli de l'esprit dans la matière et la négation de la forme au nom de l'idée ou de « l'âme » : dans l'article « Plastique de la civilisation -Du beau antique et du beau moderne[END_REF] ? La vision historique s'annulerait une fois encore en rêverie sur la sortie possible d'un régime historique confondu avec le fatal enchaînement des lois de la matière et des sociétés : seule demeure, en guise d'échappatoire ou de ligne de fuite, l'anhistoricité de ce qu'on appellera -faute de mieux ? -le « poétique ».

  », en 1845. Toutefois, Dumas fils n'est pas l'auteur le plus avancé dans le XIX e siècle que considéra et commenta Gautier, lequel consacra par exemple des lignes enthousiastes à Victorien Sardou et à son drame Patrie ! dans le Journal officiel du 22 mars 1869 4 . Cela dit, le titre Les Maîtres du théâtre français de Rotrou « à Sardou » nous paraîtrait aujourd'hui aussi incongru que le raccourci historique proposé par Amédée Britsch, « de Rotrou à Dumas fils ». La tentation de transformer le chroniqueur des théâtres de son temps en historien du théâtre n'est pas nouvelle en 1929 -même si elle se comprend dans le contexte d'une III e République fondatrice d'une histoire littéraire nationale 5 au service de laquelle Gautier, avec sa saisie décalée d'une histoire ouverte sous Louis XIII, se trouve embrigadé post mortem. Déjà en 1858, avec l'aval de Gautier et la contribution de son fils, étaient publiés aux éditions Hetzel les fameux volumes intitulés Histoire de l'art dramatique en France depuis vingt-cinq ans. Ce titre est d'une certaine manière oxymorique puisque la perspective historique

.

  Demeure toutefois, face à ces éditions en recueil, le soupçon d'un artifice et d'un abus : artifice d'un montage après-coup et d'un « effet-recueil » censé construire une vision historicisée du théâtre à partir des comptes rendus d'un simple « lundiste » ; abus qui consiste à transformer des témoignages, certes dotés comme tels d'une historicité et d'une valeur pour l'histoire, en discours historique, supposant une distance, une mise en série causale, un sens, signification et orientation construites et assumées. À ce jeu du recueil factice, Théophile Gautier, comme bien d'autres feuilletonistes, serait un historien du théâtre malgré lui. Pour autant, est-il entièrement illégitime de tenter de cerner chez l'auteur des Grotesques une vision historique du théâtre dans ses développements séculaires, tant son discours critique se caractérise en son temps non seulement par la durée de son magistère, mais par la permanence de ses principes et par la congruence de ses points de vue ? N'est-il pas, à la fin de sa vie, l'auteur d'une Histoire du Romantisme, galerie de portraits à fonction mythographique, résumé de ses goûts et combats littéraires 9 ? Loin d'adapter son discours au mouvement de l'affiche contemporaine des théâtres principaux et secondaires, Gautier analyse les nouveautés à l'aune de quelques exigences, elles-mêmes fondées sur la profondeur culturelle et temporelle d'une compréhension englobante du théâtre. Celle-ci, du reste, ne s'élabore pas seulement dans la critique : elle se construit et s'affirme autant, avec une semblable constance, dans l'oeuvre fictionnelle, romanesque ou dramatique de Gautier. Aussi est-il nécessaire d'ouvrir l'éventail des textes au-delà des seuls feuilletons pour replacer et relire ceux-ci à l'intérieur d'une oeuvre continue. Les articles fondus dans le recueil des Grotesques 10 , qui abordent le théâtre de l'époque Louis XIII à travers les figures de Théophile de Viau, de Colletet ou de Georges de Scudéry, entrent en écho avec le déploiement romanesque et la fiction historique du Capitaine Fracasse, en longue gestation avant sa parution en 1863 : le répertoire des comédiens ambulants est celui de quelques dramaturges « grotesques », Viau et Scudéry, à côté de Corneille, Mairet ou Hardy. Autre exemple, la rêverie sur le théâtre antique, dans Arria Marcella en 1852, nourrie du Voyage à Pompéi de l'abbé Romanelli (1829) ou du Palais de Scaurus et des Ruines de Pompéi de l'architecte-archéologue François Mazois (entre 1819 et 1829), se prolonge par la grâce de plusieurs digressions du feuilleton, par exemple dans celui du 14 janvier 1856, au Moniteur universel, consacré à L'Orestie revue par Dumas. Enfin, l'imagination d'un théâtre impossible, libre et extravagant, dans Mademoiselle de Maupin, si elle s'inscrit dans le moment « Jeune-France » et dessine les arabesques de la fantaisie romantique au souvenir des comédies shakespeariennes, s'épand aussi dans les feuilletons pour y rappeler les exigences du rêve et de la poésie face aux mécaniques vaudevillesques laissées sans chair ni esprit par les carcassiers de théâtre 11 . Aussi faut-il l'énoncer d'emblée, pour résister à la tentation de reconstituer chez Gautier une histoire du théâtre : les scènes du passé et les dramaturgies anciennes, dont le rappel circule entre articles critiques et oeuvres romanesques, ne fondent pas véritablement le discours d'un historien de la scène ; elles nourrissent régulièrement la rêverie sur d'autres théâtres, pratiquent une trouée dans le présent des spectacles trop communs et connus ; elles font office de contrepoint critique. Le passé idéalisé est cette démesure à l'aune de laquelle est jugée l'étroite mesure du théâtre d'aujourd'hui. Enfin, il n'est pas jusqu'à l'oeuvre dramatique de Gautier qui ne soit visité par l'histoire des planches, nourri par le fantasme des scènes passées : Une larme du diable, en 1839, redécouvre, fût-ce avec la désinvolture de la parodie, le mystère médiéval dont Gautier regrettera encore l'impossibilité moderne dans un feuilleton du Moniteur universel, le 31 mars 1856 : « […] nous nous demandions si notre âge sceptique, ou, si vous l'aimez mieux, critique, possédait la simplicité d'âme nécessaire pour voir avec édification ces chapitres de la Bible transformés en actes de drame, et formant, pour ainsi dire, une sorte de féerie sacrée 12 ». Le proverbe La Fausse Conversion convoque en 1846, côté coulisses, les artistes de l'Opéra et du ballet du XVIII e siècle. Regardez, mais ne touchez pas ressuscite en 1847, sur la scène de l'Odéon, la comédie de cape et d'épée à l'espagnole, tandis que l'arlequinade Pierrot posthume (1847), après la bastonnade Le Tricorne enchanté (1845), grave dans le vers les scénarios pantomimiques et les types comiques hérités de la Foire 13 . L'histoire passée du théâtre offre d'abord à Gautier un réservoir de sujets, d'images et de formes qu'il revient au poète, romancier, dramaturge, critique de ranimer imaginairement : dans cet art qui consiste à se laisser hanter par d'autres temps, l'historique se confond avec le fantomatique. Ainsi s'explique l'attachement de Gautier, manifeste dans nombre d'articles consacrés à l'ancien répertoire, à la reconstitution intégrale, exact et fidèle des chefs-d'oeuvre du passé. La prise de position est forte en ce dominante nourrit une pratique historienne chez Gautier, dès lors que le propre des « oubliés », ces auteurs de simple talent effacés des mémoires, est d'éclairer sous un jour plus franc les reliefs non seulement esthétiques mais aussi linguistiques, culturels, moraux et sociaux d'une époque. Gautier justifie en ces termes son intérêt pour les « Grotesques », dans la postface de son recueil : En s'habituant au commerce de ces auteurs de troisième ordre, dédaignés ou tombés en désuétude, on finit par se remettre au point de vue de l'époque, non sans quelque difficulté, et l'on arrive à comprendre jusqu'à un certain point les succès qu'ils ont obtenus, et qui paraissent tout d'abord inexplicables 18 . L'interrogation sur l'effacement des oeuvres de simple talent, l'enquête fébrile sur les raisons d'un oubli, forcent Gautier à se faire historien des formes littéraires, de leurs conditions, notamment sociales et institutionnelles, d'émergence et de disparition : histoire morale et histoire culturelle s'articulent alors sous sa plume.

  […] un jour, [Chapelain] ayant parlé de la fameuse règle des trois unités, parfaitement ignorée alors, non seulement du cardinal-duc, mais même des gens du métier, il dit tant de belles choses sur ce propos, et donna des raisons si justes et si pertinentes, que le cardinal, émerveillé et ravi , lui accorda une pension de mille écus 21 […]. La sacro-sainte unification organique de l'action, assurant l'illusion par la mise en perspective des actes représentés en scène, est régulièrement sapée par l'ironie de Gautier. Les drames originaux de Shakespeare valent toujours mieux que leurs adaptations modernes au goût et à la raison des contemporains ; ainsi de l'Hamlet revu par Dumas et Meurice pour le Cirque en 1855 : MM. Alexandre Dumas et Paul Meurice ont cru devoir donner plus d'ordre et de logique au dénouement, où ils ont ramené l'ombre prononçant l'arrêt de chacun -scène imitée de Richard III. Nous préférons cette tuerie vague, ce hasard ivre, cette fatalité folle, qui précipite les morts les unes sur les autres, rend les assassins victimes, et fait arriver par aventure la vengeance longtemps méditée. La pièce sort de la nuit et y rentre 22 .Le feuilleton rejoint bien la fiction romanesque, celle de Mademoiselle de Maupin, et l'imagination d'un théâtre impossible dont la vertu consiste surtout à offrir, dans la liberté d'une action en apesanteur, une image de la vie humaine dégagée des nécessités fatales de l'enchaînement causal censé faire l'histoire -du moins dans la représentation scénique d'une action organiquement liée au nom de la vraisemblance.Pour autant, l'attachement aux talents oubliés comme la défense d'un théâtre de la fantaisie arraché aux lois du néo-aristotélisme classique ne suffisent pas à fonder durablement une pensée historienne du théâtre : la construction intellectuelle et discursive d'un devenir orienté, d'une évolution dont on postule après-coup, dans l'énoncé de quelques lois, la nécessité historique. À suivre, dans la pluralité de leurs supports et de leurs modes d'énonciation, les discours de Gautier sur le théâtre dans l'histoire, il semble qu'une vision profondément anhistorique voire anti-historique l'emporte régulièrement chez lui.

XIX e siècle où l'on ne joue d'abord Dom Juan que dans la version de Thomas Corneille et Le Cid amputé du rôle de l'Infante -sans parler des oeuvres de Shakespeare adaptées à la raison et au goût français modernes. Il s'agit moins d'un souci historien de vérité du texte-document, que d'une exigence propre à la rétrospection, celle de la reconquête intégrale et vivifiante d'une oeuvre inactuelle. Ainsi, Gautier écrit à propos d'une reprise du Cid : En attendant les pièces nouvelles, la direction du Théâtre-Français reprend les chefs-d'oeuvre de l'ancien répertoire. Cette revue rétrospective est intéressante, et pourrait l'être davantage si l'on cherchait à rajeunir par une mise en scène plus exacte, des détails curieusement étudiés, des expressions heureusement restituées, les oeuvres que l'on veut remettre en lumière. […] Nous regrettons que M. Empis n'ait pas eu le courage de risquer les changements à vue que la tragédie de Corneille réclame aussi impérieusement qu'une pièce de Shakespeare pour être intelligible à l'oeil et à la raison 14 . L'intérêt pour les oeuvres oubliées nourrit aussi chez Gautier une rêverie sur les possibles de l'histoire des arts : découvrant La Mère confidente de Marivaux, le feuilletoniste s'attache à traquer dans cette pièce sortie du répertoire « le germe de théories dont l'insuccès a empêché le développement 15 ». De même, dans l'article consacré à la disparition de Rachel, Gautier imagine que le retour à la tragédie suscité par la comédienne a bloqué des évolutions potentielles du drame, à jamais enfouies dans les possibles d'une histoire inaboutie : « […] en ressuscitant la vieille tragédie morte, elle [Rachel] enraya le grand mouvement romantique qui eût peut-être doté la France d'une forme nouvelle de drame 16 ». Le virtuel redécouvert dans le passé méconnu des répertoires dramatiques vient ainsi combattre l'actuel -ce théâtre trop asservi aux besoins des foules contemporaines, que la reconquête authentique de répertoires oubliés vient renouveler.L'imprégnation de l'oeuvre de Gautier, critique, romanesque ou théâtrale, par le passé de la scène, laisse une nouvelle fois imaginer la présence sous-jacente, souterrainement organisatrice, d'un discours historique sur le théâtre. Si celui-ci existe, il est essentiellement caractérisé par la place accordée aux artistes oubliés et aux minores. L'histoire gautiériste du théâtre adopte volontiers le cours de la contre-histoire, qui inverse la logique de consécration propre aux histoires officielles constituées en doxa, en particulier par le discours des classiques. À la manière des historiens romantiques de la littérature, Gautier décale son regard du siècle de Louis XIV pour s'arrêter à l'époque Louis XIII, qu'un Sainte-Beuve considère comme « une période de décadence dont les ombres s'effacent seulement », « chaos littéraire » bientôt vivifié par les « feux » et les « clartés » du siècle de Louis XIV[START_REF] Sainte-Beuve | Tableau historique et critique de la poésie française et du théâtre français au XVI e siècle[END_REF] . Gautier se fait historiographe romantique, attentif à reconstituer la totalité des traits et des productions d'une époque, à intégrer dans celle-ci la bigarrure des productions communes que l'on qualifie de « populaires » -le geste reproduit celui, hugolien, de promotion du grotesque dans la préface de Cromwell. Une telle attention portée aux à côtés de l'histoire


Le silence des choses. La pantomime romantique, spectacle de l'immanence ? La pantomime des Funambules, à l'ère de Deburau, n'existe pour nous que magnifiée, élevée à un haut degré de symbolisation, dans le discours des écrivains romantiques, de Nodier à Gautier, de Janin à Sand. Les scénarios pantomimiques aujourd'hui accessibles et lisibles sont à l'usage de leur héros, Pierrot : maigres et presque mutiques (rares, elliptiques, peu ou mal édités). En dehors de leur reviviscence posthume, et largement mythographique, dans Les Enfants du paradis, les textes et les spectacles déployés à partir d'eux demeurent aujourd'hui, littéralement, lettres mortes : à la fois absents et écrasés par les écrits dérivés, critiques, biographiques, hagiographiques, qu'ils ont suscités. L'usage de la pantomime, sous la plume des écrivains romantiques, est en réalité critique, c'est-à-dire orienté, motivé par une stratégie qui vise au-delà de la modeste pantomime du pauvre Deburau : le spectacle d'en bas, théâtre « à quatre sous » produit par un boui-boui du Boulevard du Temple comme les Funambules, ex-théâtre des Chiens savants, est érigé en conservatoire d'un art menacé par les développements modernes de la scène, à l'heure du théâtre industriel, comme par la persistance des formes classiques. Le geste romantique de défense et illustration de la pantomime est donc d'accaparement et peut-être de trahison : tantôt mus par la volonté de découvrir là, dans ce spectacle élémentaire, le « vrai » peuple, tantôt portés par le désir de retrouver, sur la scène muette, les origines sauvegardées d'un théâtre métaphysique, les écrivains, de la fin de la Restauration à celle de la monarchie de Juillet, ne passent-ils pas à côté d'un théâtre burlesque de l'immanence en s'obstinant à le tirer vers un spectacle du Sens ? Sans doute faut-il apprécier dans la pantomime romantique, avant « l'âme du peuple » révélé dans le corps de Deburau, avant l'éloquence muette du langage gestuel plus pur que la parole, avant les débats métaphysiques figurés dans l'espace visible par les coups de pieds et de poings de Pierrot et Arlequin, le spectacle de l'être-là des corps et des choses.

Le parti pris spectaculaire des choses

Jules Janin fait partie, dès 1832, des premiers explorateurs des Funambules et des premiers exégètes des spectacles muets de Pierrot avec Deburau, histoire du théâtre à quatre sous, pour faire suite à l'histoire du Théâtre-Français, publié chez Gosselin en deux volumes. Le titre l'indique ironiquement : l'éloge (paradoxal) de l'infiniment petit vise le sommet de la hiérarchie des spectacles, la Comédie-Française dont l'épuisement artistique se lirait (se dirait) à travers l'énergie déployée par la pantomime. Aussi Janin recourt-il à deux procédés conjoints. Il écrit une biographie romancée, en partie imaginaire, de Deburau, fidèle à l'esprit goguenard des petites revues comme au ton de la conversation déployé dans la critique dramatique : « Un feuilleton du Journal des Débats sur le célèbre Paillasse des Funambules nous a suggéré l'idée de réunir en deux petits volumes tous les documents relatifs à cette grande célébrité », relate Janin en ouverture de sa Préface. Il use du style héroï-comique, engagé dans l'héroïsation du Paillasse, ex « artiste d'agilité » ambulant : « La Biographie dont il s'agit est faite avec toute conscience et vérité. L'auteur n'a visé ni à l'effet ni au sophisme. Quand il s'est emparé si hardiment de ce héros tout neuf, son but unique a été de résumer l'Histoire de l'Art Dramatique considéré sous son aspect ignoble, le seul aspect nouveau sous lequel il puisse être encore envisagé. » Là est le coeur du projet de Janin, son ambiguïté aussi : la mort du Théâtre-Français, hérité du siècle classique, est révélée par la vitalité du théâtre « ignoble », dont la célébration ne va pas sans réprobation. Janin n'adhère à son objet que dans la mesure où il sert d'étalon de la déconfiture des traditions artistiques et littéraires de la scène, mais il ne saurait se complaire sans distance au spectacle nouveau de l'ère prédémocratique : « Autrefois l'Art Dramatique avait ses fêtes de la nuit, ses arrêts du matin, des princes et des rois à ses genoux, un palais au Palais-Royal ; aujourd'hui l'Art Dramatique mange des pommes frites sur le boulevard du Temple, il raccommode ses bas troués à la porte de son théâtre, il s'enivre chez le marchand de vin ; il avait du fard autrefois, il a de la farine à présent. Autrefois il s'appelait Molé ou Talma, aujourd'hui il s'appelle tout simplement Deburau. Tout se compense. » Car la modernité théâtrale n'est autre chose que l'invasion de la salle et de la scène par le monde matériel et physique : le spectacle désormais offert est celui des besoins humains, de la misérable incomplétude humaine que ne travestit plus aucune langue poétique ni aucune forme dramatique. L'objectivation de l'existence est réalisée à hauteur de plateau : « Et, avec cet acteur [Deburau], figurez-vous toute la décoration du peuple : le balai, le chaudron, la cuve au linge, le bahut, le tabouret, la table, le verre, le peigne, la pipe, le briquet, le miroir, le tire-pied, l'échelle, l'écuelle ; qui peut dire tout ? […] La décoration change toujours, toujours ce monde tourne, la pluie succède au soleil, il fait nuit, il fait jour, la grêle tombe, et toujours, quel que soit le lieu de la scène, notre Gilles est à la hauteur des choses qui s'y passent […] ». « Des choses qui s'y passent » : voilà où l'art dramatique exilé du Temple de Racine a trouvé refuge, dans les tableaux animés du monde matériel tel qu'il se vit dans le bas peuple. Spectacle de la pure extériorité des choses banales de la vie quotidien où l'on cherchera en vain quelque vérité spirituelle ou morale. A moins que le bric-à-brac déployé sur scène, dans la disparate même des choses (chinées aux puces par Deburau ou par l'accessoiriste), ne laisse une petite place à la poésie, immiscée dans l'improbable et inutile juxtaposition de tant d'objets nommés accessoires, servant pourtant moins au jeu dramatique qu'à leur spectaculaire exhibition. Du moins est-ce le détournement tenté par Janin, dans l'invention avant l'heure d'un inventaire à la Prévert déployé en une « liste générale des accessoires du théâtre des Funambules ». La liste couvre quatorze pages, part d' « une chaîne de montre en acier » pour mener à « douze têtes de mort », place « une bouilloire » entre « une baguette de magicien » et « un bidon de fer blanc », organise la rencontre de « dix croix de Saint-Louis » et de « neuf crachats », marie « un coucou avec ses poids » et « un bilboquet », met en contact « une toque virginale » et « une poêle à marrons », ne fait guère de différence entre la valeur de « deux couverts brisés » et le prix d'« un crucifix », confond le « tambour à broder » avec les instruments de musique, finit par jeter pêle-mêle sur le papier « une palette en faïence », « un livre de la loi, doré », « un vieux cor de chasse », « un miroir à main », « une petite malle d'osier, couverte de toile peinte », le tout formant in fine, par l'ajout des « douze têtes de mort », une vanité des temps modernes, temps de l'horizontalité plane, sans hiérarchie ni transcendance, monde immanent des déesses choses. « Le drame moderne a fait de l'accessoire une condition indispensable », regrette Janin, qu'inquiète la promotion de l'accessoire de théâtre au rang d'objet spectaculaire, dans un théâtre de la matière. Heureusement pour l'Art, selon Janin, Deburau a inventé, avec la pantomime muette, une éloquence nouvelle, mutisme sur fond blanc, renvoyant les choses encombrantes à leur statut d'utilités inessentielles : « […] Deburau vous laisse tout cela ; il ne faut à Deburau qu'une casaque de Paillasse, un peu de farine sur la figure, quatre chandelles pour son théâtre, deux violons faux, et pour poète le premier décorateur venu qui lui donnera une forêt, un temple, une taverne, un enfer, un ciel, mêlant tout cela sans art, sans apprêt, comme dans le chaos ». Qu'arrive Pierrot-Deburau, et le chaos du drame moderne, image d'une société horizontale, anomique et désertée par l'Ordre, se résout « à merveille » et s'offre à « la rêverie » des « artistes » et des « poètes » qui « cherchent de l'art tout neuf ». Ou comment dénoncer ce que l'on feint de célébrer pour finalement le trahir : Janin, comme d'autres écrivains du temps, dégage Pierrot de la gangue matérielle où s'anime sa silhouette, ne retient que le visage et le costume immaculés du type comique, page blanche où s'écrit un autre théâtre, rêvé, dématérialisé.

L'ordre dramatique des choses

Force est de revenir aux textes, aux scénarios pantomimiques, pour y découvrir le spectacle qu'organisent tant d'accessoires mêlés aux corps acrobates des artistes des Funambules. On y découvre certes un univers féerique où une surnature (fées, sorcières, démons, enfers et paradis) se mêle et s'unit au monde commun, comme dans les contes. On y trouve surtout tout un monde de corps chosifiés et d'objets animés, engagés dans de constants échanges.

Olivier bara UMR Lire


Jacques Garrigue

Didier Rémy

Ambivalent Types for Principal Type Inference with GADTs

GADTs, short for Generalized Algebraic DataTypes, which allow constructors of algebraic datatypes to be non-surjective, have many useful applications. However, pattern matching on GADTs introduces local type equality assumptions, which are a source of ambiguities that may destroy principal typesand must be resolved by type annotations. We introduce ambivalent types to tighten the definition of ambiguities and better confine them, so that type inference has principal types, remains monotonic, and requires fewer type annotations.

Introduction

GADTs, short for Generalized Algebraic DataTypes, extend usual algebraic datatypes with a form of dependent typing by enabling type refinements in pattern-matching branches [START_REF] Cheney | First-class phantom types[END_REF][START_REF] Xi | Guarded recursive datatype constructors[END_REF][START_REF] Baars | Typing dynamic typing[END_REF]. They can express many useful invariants of data-structures, provide safer typing, and allow for more polymorphism [START_REF] Sheard | Programming in Omega[END_REF]. They have already been available in some Haskell implementations (in particular GHC) for many years and now appear as a natural addition to strongly typed functional programming languages.

However, this addition is by no means trivial. In their presence, full type inference seems undecidable in general, even in the restricted setting of ML-style polymorphism [START_REF] Schrijvers | Complete and decidable type inference for gadts[END_REF]. Moreover, many well-typed programs lack a most general type. Using explicit type annotations solves both problems. Unfortunately, while it is relatively easy to design a sound typing algorithm for a language with GADTs, it is surprisingly difficult to keep principal types without requesting full type annotations on every case analysis.

Repeatedly writing full type annotations being cumbersome, a first approach to a stronger type inference algorithm is to propagate annotations. This comes from the basic remark that, in many cases, the type of a function contains enough information to determine the type of its inner case analyses. A simple way to do this is to use program transformations, pushing type annotations inside the body of expressions.

Stratified type inference for GADTs [START_REF] Pottier | Stratified type inference for generalized algebraic data types[END_REF] goes further in that direction, converting from an external language where type annotations are optional to an internal language where the scrutinee of case analysis and all coercions between equivalent types must be annotated. This conversion is an elaboration phase that collects all typing information -not only type annotations-and propagates it where it is needed. The internal language allows for straightforward type inference and it has the principal type property.

Part of this work has been done at IRILL. It also enjoys monotonicity: strengthening the type of a free variable by making it more general preserves well-typedness. As expected, principality does not hold in general in the external type system (a program may be typable but have no principal type), but it does hold if we restrict ourselves to those programs whose elaboration in the internal language is typable. However, since elaboration extracts information from the typing context, monotonicity is lost: strengthening the type of a free variable by making it more general before elaboration can reduce the amount of type information available on the elaborated program and make it ill-typed. Monotonicity is a property that has often been underestimated, because it usually (but not always) holds in languages with principal types. However, losing monotonicity can be worse for the programmer than losing principal types. It reveals a lack of modularity in the language, since some simple program transformations such as simplifying the body of a function may end up inferring more general types, which may subsequently break type inference. Propagating only type annotations would preserve monotonicity, but it is much weaker.

GHC 7 follows a similar strategy, called OutsideIn [START_REF] Vytiniotis | OutsideIn(X) Modular type inference with local assumptions[END_REF], using constraint solving rather than elaboration to extract all typing information from the outer context. As a result, propagation and inference are interleaved. That is, the typing information obtained by solving constraints on the outer context enclosing a GADT case analysis is directly used to determine the types of both the scrutinee and the result in this case analysis. Type inference can then be performed in the body of the case analysis. By allowing information to flow only from the outside to the inside, principality is preserved when inference succeeds. Yet, as for stratified type inference [START_REF] Pottier | Stratified type inference for generalized algebraic data types[END_REF], it lacks monotonicity.

While previous approaches have mostly attempted to propagate types to GADT case analyses, we aim in the opposite direction at reducing the need for type information in case analysis. This aspect is orthogonal to propagation and improving either one improves type inference as a whole. Actually, OutsideIn already goes one step in that direction, by allowing type information to flow out of a pattern-matching case when no type equation was added. But it stops there, because if type equations were added, they could have been used and consequently the type of the branch is flagged ambiguous.

This led us to focus our attention on the definition of ambiguity. Type equations are introduced inside a pattern-matching branch, but with a local scope: the equation is not valid outside of the branch. This becomes a source of ambiguities. Indeed, a type equation allows implicit type conversions, i.e. there are several inter-convertible forms for types that we need not distinguish while in the scope of the equation, but they become nonconvertible-hence ambiguous-when leaving its scope, as the equation can no longer be used. Ambiguity depends both on the equations available, and on the types that leak outside of the branch: if removing the equation does not impair convertibility for a type, either because it was not convertible to start with, or because other equations are available, it need not be seen as ambiguous.

Since ambiguities must generally be solved by adding type annotations, a more precise definition and better detection of ambiguities become essential to reduce the need for explicit type information. By defining ambiguity inside the type system, we are able to restrict the set of valid typings. In this paper we present a type system such that among the valid typings there is always a principal one (i.e. subsuming all of them) and we provide a type inference algorithm that returns the principal solution when it exists. Moreover, our type system keeps the usual properties of ML, including monotonicity. This detection of ambiguity is now part of OCaml [START_REF] Leroy | The OCaml system release 4.00, Documentation and user's manual[END_REF].

Since propagating type information and reducing the amount of type information needed by case analysis are orthogonal issues, our handling of ambiguity could be combined with existing type inference algorithms to further reduce the need for type annotations. As less type information is needed, it becomes possible to use a weaker propagation algorithm that preserves monotonicity. This is achieved in OCaml by relying on the approach previously developed for first-class polymorphism [START_REF] Garrigue | Semi-explicit first-class polymorphism for ML[END_REF].

The rest of this paper is organized as follows. We give an overview of our solution in §2. We present our system formally and state its soundness in §3. We state principality and monotonicity in §4; by lack of space, we leave out some technical developments, all proofs, and the description of the type inference algorithm, which can all be found in the accompanying technical report [START_REF] Garrigue | Ambivalent types for principal type inference with GADTs[END_REF]. Finally, we compare with related works in §5.

An overview of our solution

The standard notion of ambiguity is so general that it may just encompass too many cases. Consider the following program. 3type (_,_) eq = Eq : (α,α) eq let f (type a) (x : (a,int) eq) = match x with Eq -> 1

Type eq is the classical equality witness. It is a GADT with two index parameters, denoted by the two underscores, and a single case Eq, for which the indices are the same type variable α. Thus, a value of type (a, b) eq can be seen as a witness of the equality between types a and b.

In the definition of f, we first introduce an explicit universal variable a, called a rigid variable, treated in a special way in OCaml as it can be refined by GADT pattern matching. By constraining the type of x to be (a,int) eq, we are able to refine a when pattern-matching x against the constructor Eq: the equation a = int becomes available in the corresponding branch, i.e. when typechecking the expression 1, which can be assigned either type a or int. As a result, f can be given either type (α, int) eq → int or (α, int) eq → α. This fulfills the standard definition of ambiguity and so should be rejected. But should we really reject it? Consider these two slight variations in the definition of f: let f 1 (type a) (x : (a,int) eq) = match x with Eq -> true let f 2 (type a) (x : (a,int) eq) (y : a) = match x with Eq -> (y > 0)

In f 1 , we just return true, which has the type bool, unrelated to the equation. In f 2 , we actually use the equation to turn y into an int but eventually return a boolean. These variants are not ambiguous. How do they differ from the original f? The only reason we have deemed f to be ambiguous is that 1 could potentially have type a by using the equation. However, nothing forces us to use this equation, and, if we do not use it, the only possible type is int. It looks even more innocuous than f 2 , where we indirectly need the equation to infer the type of the body.

So, what would be a truly ambiguous type? We obtain one by mixing a's and int's in the returned value (the left-margin vertical rules indicate failure): let g (type a) (x : (a,int) eq) (y : a) = match x with Eq -> if y > 0 then y else 0

Here, the then branch has type a while the else branch has type int, so choosing either one would be ambiguous. How can we capture this refined notion of ambiguity? The idea is to track whether such mixed types are escaping from their scope. Intuitively, we may do so by disallowing the expression to have either type and instead viewing it with an ambivalent type a ≈ int, which we just see syntactically as a set of types.

An ambivalent type must still be coherent, i.e. all the types it contains must be provably equal under the equations available in the current scope. Hence, although a ≈ int can be interpreted as an intersection type, it is not more expressive than choosing either representation (since by equations this would be convertible to the other type), but more precise: it retains the information that the equivalence of a and int has been assumed to give the expression the type a or int.

Since coherence depends on the typing context, a coherent ambivalent type may suddenly become incoherent when leaving the scope of an equation. This is where ambiguity appears. Hence, while an ambivalent type is a set of types that have been assumed interchangeable, an ambiguity arises only when an ambivalent type becomes incoherent by escaping the scope of an equation it depends on.

Ambiguous programs are to be rejected. Fortunately, ambiguities can be eliminated by using type annotations. Intuitively, in an expression (e : τ), the expressions e and (e : τ) have sets of types ψ 1 and ψ 2 that may differ, but such that τ is included in both, ensuring soundness of the change of view. In particular, while the inner view, e.g. ψ 1 , may be large and a potential source of ambiguities, the outer view, e.g. ψ 2 , may contain fewer types and remain coherent; this way the ambivalence of the inner view does not leak outside and does not create ambiguities. Consider, for example the program: let g 1 (type a) (x : (a,int) eq) y = match x with Eq -> (if (y : a) > 0 then (y : a) else 0 : a)

Type annotations on y and the conditional let them have unique outer types, which are thus unambiguous when leaving the scope of the equation. More precisely, (y : a) and 0 can be both assigned type a ≈ int, which is also that of the conditional if ... else 0, while the annotation (if ... else 0 : a) and variable y both have the singleton type a. (Note that the type of the annotated expression is the inner view for y but the outer view for the conditional.) Of course, it would be quite verbose to write annotations everywhere, so in a real language we shall let annotations on parameters propagate to their uses and annotations on results propagate inside pattern-matching branches. The function g 1 may be written more concisely as follows-but we will ignore this aspect in this work: let g 2 (type a) (x : (a,int) eq) (y : a) : a = match x with Eq -> if y > 0 then y else 0

A natural question at this point is why not just require that the type of the result of pattern-matching a GADT be fully known from annotations? This would avoid the need for this new notion of ambiguity. This is perhaps good enough if we only consider small functions: as shown for g 2 , we may write the function type in one piece and still get the full type information. However, the situation degrades with local let bindings: let p (type a) (x : (a,int) eq) : int = let y = (match x with Eq -> 1) in y * 2

The return type int only applies to y*2, so we cannot propagate it automatically as an annotation for the definition of y. Basically, one would have to explicitly annotate all let bindings whose definitions use pattern-matching on GADTs. This may easily become a burden, especially when the type is completely unrelated to the GADTs (or accidentally related as in the definition of f, above).

We believe that our notion of ambiguity is simple enough to be understood easily by users, avoids an important number of seemingly redundant type annotations, and provides an interesting alternative to non-monotonic approaches (see §5 for comparison).

Formal presentation

Since our interest is type inference, we may assume without loss of generality that there is a unique predefined (binary) GADT eq(•, •) with a unique constructor Eq of type ∀(α) eq(α, α). The type eq(τ 1 , τ 2 ) denotes a witness of the equality of τ 1 and τ 2 and Eq is the unique value of type eq(τ 1 , τ 2 ). For conciseness, we specialize pattern matching to this unique constructor and just write use

M 1 : τ in M 2 for match M 1 : τ with Eq -> M 2 .
Types occurring in the source program are simple types:

τ ::= α | a | τ → τ | eq(τ, τ) | int
Type variables are split into two different syntactic classes: flexible type variables, written α, and rigid type variables, written a. As usual, flexible type variable are meant to be instantiated by any type-either during type inference or after their generalization. Conversely, rigid variables stand for some unknown type and thus are not meant to be instantiated by an arbitrary type. They behave like skolem constants. We write V , V f , and V r for the set of variables, flexible variables, and rigid variables. Terms are expressions of the λ -calculus with constants (written c), the datatype Eq, pattern matching use M 1 : τ in M 2 , the introduction of a rigid variable ν(a) M or a type annotation (τ), i.e. the usual annotation (M : τ) is seen as the application (τ) M:

M ::= x | c | M 1 M 2 | λ (x) M | let x = M 1 in M 2 | Eq | use M 1 : τ in M 2 | ν(a) M | (τ)
Although type annotations in source programs are simple types, their flexible type variables are interpreted as universally quantified in the type of the annotation (see §3.5).

Besides, we use-and infer-ambivalent types internally to keep track of the use of typing equations and detect ambiguities more accurately.

Ambivalent types

Intuitively, ambivalent types are sets of types. Technically, they refine simple types to express certain type equivalences within the structure of types. Every node becomes a set of type expressions instead of a single type expression and is labeled with a flexible type variable. More precisely, ambivalent types, written ζ , are recursively defined as:

ρ ::= a | ζ → ζ | eq(ζ , ζ ) | int ψ ::= ε | ρ ≈ ψ ζ ::= ψ α σ ::= ∀( ᾱ) ζ
A raw type ρ is a rigid type variable a, an arrow type ζ → ζ , an equality type eq(ζ , ζ ), or the base type int. A proper raw type is one that is not a rigid type variable. An (ambivalent) type ζ is a pair ψ α of a set ψ of raw types ρ labeled with a flexible type variable α. We use ≈ to separate the elements of sets of raw types: it is associative commutative, has the empty set ε for neutral element, and satisfies the idempotence axiom (ψ ≈ ψ) = ψ. An ambivalent type ζ is always of the form ψ α and we write ζ for ψ. When ψ is empty ζ is a leaf of the form ε α , which corresponds to a type variable in simple types, hence we may just write α instead of ε α , as in the examples above. Type schemes σ are defined as usual, by generalizing zero or more flexible type variables. Rigid type variables may only be used free and cannot be quantified over. We introduce them in the typing environment but turn them into flexible type variables before quantifying over them, so they never appear as bound variables in type schemes.

In our representation, every node is labeled by a flexible type variable. This is essential to make type inference modular, as it is needed for incremental instantiation.

To see this, consider a context that contains a rigid type variable a, an equation a .

= int, and a variable x of type a, under which we apply a function choice of type α → α → α to x and 1. We first reason in the absence of labels on inner nodes. The partial application choice x has type a → a. To further apply it to 1, we must use the equation to convert both 1 of type int and the domain of the partial application to the ambivalent type int ≈ a. The type of the full application is then a. However, if we inverted the order of arguments, it would be int. Something must be wrong. In fact, if we notice in advance that both types a and int will eventually have to be converted to int ≈ a, we may see both x and 1 with type int ≈ a before performing the applications. In this case, we get yet another result int ≈ a, which happens to be the right one.

What is still wrong is that as soon as we instantiate α, we lose the information that all occurrences of α must be synchronized. The role of labels on inner nodes is to preserve this information. Revisiting the example, the partial application now has type a α → a α (we still temporarily omit the annotation on arrow types, as they do not play a role in this example). This is saying that the type is currently a → a but remembering that the domain and codomain must be kept synchronized. Then, the integer 1 of type int γ can also be seen with type (int ≈ a) γ and unified with the domain of the function a α , with the effect of replacing all occurrences of a α and of int γ by (int ≈ a) α . Thus, the function has type (int≈a) α → (int≈a) α and the result of the application has type (int ≈ a) α -the correct one. We now obtain the same result whatever the scenario.

This result type may still be unified with some other rigid variable a , as long as this is allowed by having some equation a .

= int or a . = a in the context, and refine its type to (int ≈ a ≈ a ) α . Since we cannot tell in advance which type constructors will eventually be mixed with other ones, all nodes must keep their label when substituted.

Replaying the example with full label annotations, choice has type ∀(α, γ, γ ) (α → (α → α) γ ) γ and its partial application to x has type ∀(α, γ) (a α → a α ) γ after generalization. Observe that this is less general than

∀(α, α , γ) (a α → a α ) γ but more general than ∀(α, γ) ((int ≈ a) α → (int ≈ a) α ) γ .
Type variables. Type variables are either rigid variables a or flexible variables α. We write frv(ζ ) for the set of rigid variables that are free in ζ and ffv(ζ ) for the set of flexible variables that are free in ζ . These definitions are standard. For example, free flexible variables are defined as:

ffv(ψ α ) = {α} ∪ ffv(ψ) ffv(ε) = / 0 ffv(ρ ≈ ψ) = ffv(ρ) ∪ ffv(ψ) ffv(∀(α) σ ) = ffv(σ ) \ {α} ffv(a) = / 0 ffv(int) = / 0 ffv(ζ 1 → ζ 2 ) = ffv(ζ 1 ) ∪ ffv(ζ 2 ) ffv(eq(ζ 1 , ζ 2 )) = ffv(ζ 1 ) ∪ ffv(ζ 2 )
The definition is analogous for free rigid variables, except that frv(ψ α ) is equal to frv(ψ) and frv(a) is equal to {a}. We write ftv(ζ ) the subset of ffv(ζ ) of variables that appear as leaves, i.e. labeling empty nodes and fnv(ζ ) the subset of ffv(ζ ) that are labeling nonempty nodes. In well-formed types these two sets are disjoint, i.e. ffv(ζ ) is the disjoint union of ftv(ζ ) and fnv(ζ ).

Rigid type variables lie between flexible type variables and type constructors. A rigid variable a stands for explicit polymorphism: it behaves like a nullary type constructor and clashes, by default, with any type constructor and any other rigid variable but itself. However, pattern matching a GADT may introduce type equations in the typing context while type checking the body of the corresponding branch, which may allow a rigid type variable to be compatible with another type. Type equations are used to verify that all ambivalent types occurring in the type derivation are well-formed, which requires in particular that all types of a same node can be proved equal.

Interpretation of types. Ambivalent types may be interpreted as sets of simple types by unfolding ambivalent nodes as follows:

[[ε α ]] = {α} [[(ρ 1 ≈ ψ) α ]] = ρ∈ρ 1 ≈ψ [[ρ]] [[a]] = a [[int]] = int [[ζ 1 → ζ 2 ]] = {τ 1 → τ 2 | τ 1 ∈ [[ζ 1 ]], τ 2 ∈ [[ζ 2 ]]} [[eq(ζ 1 , ζ 2 )]] = {eq(τ 1 , τ 2 ) | τ 1 ∈ [[ζ 1 ]], τ 2 ∈ [[ζ 2 ]]}
The interpretation ignores labels of inner nodes. It is used below for checking coherence of ambivalent types, which is a semantic issue and does not care about sharing of inner nodes. For example, types (int ≈ a) α → (int ≈ a) α and (int ≈ a) α 1 → (int ≈ a) α 2 are interpreted in the same way, namely as {int → int, a → a, a → int, int → a}.

A type ζ is said truly ambivalent if its interpretation is not a singleton. Notice that ψ may be a singleton ρ even though ψ α is truly ambivalent, since ambivalence may be buried deeper inside ρ, as in

((int ≈ a) α → (int ≈ a) α ) α 0 .
Converting a simple type to an ambivalent type. Given a simple type τ, we may build a (not truly) ambivalent type ζ such that [[ζ ]] = {τ}. This introduces new variables γ that are in fnv(ζ ), while the variables of ftv(ζ ) come from τ. We write τ for the most general type scheme of the form ∀( γ) ζ , which is obtained by labeling all inner nodes of τ with different labels and quantifying over these fresh labels. For example,

int → int is ∀(γ 0 , γ 1 , γ 2 ) (int γ 1 → int γ 2 ) γ 0 and α → α is ∀(γ 0 ) (ε α → ε α ) α 0 .
Notice that free type variables of τ remain free in τ .

Typing contexts

Typing contexts Γ bind program variables to types, and introduce rigid type variables a, type equations τ 1 . = τ 2 , and node descriptions α :: ψ:

Γ ::= / 0 | Γ , x : σ | Γ , a | Γ , τ 1 . = τ 2 | Γ , α :: ψ WF-CTX-EQUAL Γ Γ τ 1 . = τ 2 Γ , τ 1 . = τ 2 WF-TYPE-EQUAL Γ τ 1 Γ τ 2 ftv(τ 1 ) = ftv(τ 2 ) = / 0 Γ τ 1 . = τ 2 WF-TYPE-FLEX Γ α :: ψ ∈ Γ Γ ψ α WF-CTX-FLEX Γ Γ ψ α / ∈ dom(Γ ) Γ , α :: ψ WF-TYPE-AMBIVALENT (Γ ρ) ρ∈ψ Γ ψ |ψ \ V r | ≤ 1 Γ ψ
Fig. 1. Well-formedness of contexts and types (excerpt)

Both flexible and rigid type variables are explicitly introduced in typing contexts. Hence, well-formedness of types is defined relatively to some typing context.

In addition to routine checks, well-formedness judgments also ensure soundness of ambivalent types and coherent use of type variables.

Well-formedness of contexts Γ is recursively defined with the well-formedness of types Γ ρ and type schemes Γ σ . Characteristic rules are in Figure 1. It also uses the entailment judgment Γ ψ, which means, intuitively, that all raw types appearing in the set ψ can be proved equal from the equations in Γ (see §3.3). The last premise of Rule WF-TYPE-AMBIVALENT ensures that ambivalent types contain at most one raw-type that is not a rigid variable. As usual well-formedness of contexts ensures that type variables are introduced before being used and that types are well-formed. It also ensures coherent use of type variables: alias constraints α :: ψ in the context Γ define a mapping that provides evidence that α is used coherently in the type σ . This is an essential feature of our system so that refining ambivalence earlier or later commutes, as explained above.

Entailment

Typing contexts may contain type equations. Type equations are used to express equalities between types that are known to hold when the evaluation of a program has reached a given program point. Type equations are added to the typing context while typechecking the expression at the current program point.

The set of equations in the context defines an equivalence between types. Rule WF-TYPE-AMBIVALENT shows that ambivalent types can only be formed between equivalent types: the well-formedness of the judgment Γ ψ requires Γ ψ, i.e. that all types in ψ are provably equal under the equations in Γ , which is critical for type soundness; the rightmost premise requires that at most one type in ψ is not a rigid variable. For example, the ambivalent types int ≈ (int γ → int γ ) and (int γ → int γ ) ≈ (a γ → a γ ) are ill-formed. This is however not restrictive as the former would be unsound in any consistent context while the later could instead be written (int ≈ a) γ → (int ≈ a) γ .

Well-formedness of a type environment requires that its equations do not contain free type variables. Equalities in Γ may thus be seen as unification problems where rigid variables are the unknowns. If they admit a principal solution, it is a substitution of the form (a i → τ i ) i∈I ; then, the set of equations (a i . = τ i ) i∈I is equivalent to the equations in Γ . If the unification problem fails, then the equations are inconsistent-in the standard model where type constructors cannot be equated 4 . This is acceptable and it just means

(ψ α i )θ = ζ i (ψ γ )θ = (ψθ ) γ (ρ i∈I i )θ = (ρ i θ ) i∈I (∀(α) ζ )θ = ∀(α) ζ (θ \ {α}) (a)θ = a (int)θ = int (ζ 1 → ζ 2 )θ = ζ 1 θ → ζ 2 θ (eq(ζ 1 , ζ 2 ))θ = eq(ζ 1 θ , ζ 2 θ ) Fig. 2. Application of substitution θ equal to [α i ← ζ i ] i∈I
that the current program point cannot be reached. Therefore, any ambivalent type is admissible in an inconsistent context.

The semantic judgment Γ ψ means by definition that any ground instance of Γ that satisfies the equations in Γ makes all types in the semantics of ψ equal. Formally: Definition 1 (Entailment). Let Γ be a typing environment. A ground substitution θ from rigid variables to simple types models Γ if θ (τ 1 ) and θ (τ 2 ) are equal for each equation τ 1 . = τ 2 in Γ . We say that Γ entails ψ and write

Γ ψ if θ ([[ψ]]
) is a singleton for any ground substitution θ that models Γ . This gives a simple algorithm to check for entailment: compute the most general unifier θ of Γ ; then Γ ψ holds if and only if θ ([[ψ]]) is a singleton or θ does not exist.

Substitution

In our setting, substitutions operate on ambivalent types where type variables are used to label inner nodes of types and not just their leaves. They allow the replacement of an ambivalent node ψ α by a "more ambivalent" one ψ ≈ ψ α , using the substitution [α ← (ψ ≈ ψ ) α ]; or merging two ambivalent nodes ψ α 1 1 and ψ α 2 2 using the substitution

[α 1 , α 2 ← ψ 1 ≈ ψ 2 α 1 ].
To capture all these cases with the same operation, we define in Figure 2 a general form of substitution [α i ← ζ i ] i∈I that may graft arbitrary nodes ζ i at every occurrence of a label α i , written

[α ← ζ ];
As a result of this generality, substitutions are purely syntactic and may replace an ambivalent node with a less ambivalent one-or even prune types replacing a whole subtree by a leaf. Of course, we should only apply substitutions to types when they preserve (or increase) ambivalence. Definition 2. A substitution θ preserves ambivalence in a type ζ if and only if, for any α in dom(θ ) and any node ψ α in ζ , we have ψθ ⊆ (ψ α )θ .

As a particular case, an atomic substitution [α ← ζ 0 ] preserves ambivalence in ζ if for any node ψ α in ζ , we have ψ ⊆ ζ 0 -since well-formedness of ψ α implies that α may not occur free in ψ, hence ψθ is just ψ.

Typing rules

Typing judgments are of the form Γ M : σ as in ML. However, typing rules, defined in Figure 3, differ from the traditional presentation of ML typing rules in two ways. On the one hand, we use a constraint framework where Γ carries node descriptions α :: ψ to enforce their sharing within different types. On the other hand, typing rules = τ 2 in typing contexts that are used to show the coherence of ambivalent types via direct or indirect uses of well-formedness judgments.

Γ Γ Eq : ∀(α, γ) eq(α, α) γ M-USE Γ (eq(τ 1 , τ 2 )) M 1 : ζ 1 Γ , τ 1 . = τ 2 M 2 : ζ 2 Γ use M 1 : eq(τ 1 , τ 2 ) in M 2 : ζ 2
All axioms require well-formedness of Γ so that whenever a judgment Γ M : σ holds, we have Γ . Rule M-INST instantiates the outermost variable of a type scheme. It is unusual in two ways. First, we write σ [α ← ψ α 0 ] rather than just σ in the quantified type. This trick ensures that all nodes labeled with α were indeed ψ α 0 and overcomes the absence of ψ 0 in the binder. Intuitively, the instantiated type should be σ

[α ← ψ α 0 ][α ← ψ γ ],
but this happens to be equal to σ [α ← ψ γ ]. Second, we require ψ 0 ⊆ ψ to ensure preservation of ambivalence, as explained in the previous subsection. Finally, the premise Γ ψ γ ensures that the resulting type is well-formed.

Rule M-GEN introduces polymorphism implicitly, as in ML: variables that do not appear in the context can be generalized. The following rule is derivable from M-GEN and M-INST, and can be used as a shortcut when variable α does not appear in ψ γ : M-BIND Γ , α :: ψ 1 M : ψ γ α = γ Γ M : ψ γ Rule M-NEW enables explicit polymorphism (and explicit type equations using witnesses). For that purpose, it introduces a rigid type variable a in the typing context that may be used inside M-typically for introducing type annotations. However, polymorphism becomes implicit in the conclusion by turning the rigid type variable a into a quantified flexible type variable α when exiting the scope of the ν-form. Polymorphism can then be eliminated implicitly 5 as regular polymorphism in ML. The second premise ensures that the rigid type variable a does not appear anywhere else but in a α .

Our version of Rule M-FUN generalizes the type γ introduced for annotating the arrow type, which avoids introducing γ :: ζ 0 → ζ in the premise. Rule M-APP differs from the standard application rule in two ways: a minor difference is that the arrow type has a label as in Rule M-FUN; a major difference is that the type of M 1 may be ambivalent-as long as it contains an arrow (raw) type of the form ζ 2 → ζ . In particular, the premise Γ M 1 :

((ζ 2 → ζ ) ≈ ψ) α does not, in general, imply Γ M 1 : (ζ 2 → ζ ) α ,
as this could lose sharing. Hence, we have to read the arrow structure directly from the ambivalent type. Rule M-LET is as usual.

Rule M-ANN allows explicit loss of sharing via type annotations. It is presented as a retyping function of type scheme (τ), i.e. a function that changes the labeling of the type of its argument without changing its behavior. The types of the argument and the result need not be exactly τ but consistent instances of τ-see the definition of τ , above. Annotations are typically meant to be used in expressions such as (τ) M, which forces M to have a type that is an instance of τ. While this is the only effect it would have in ML, here it also duplicates the polymorphic skeleton of M, which allows different labeling of inner nodes in the type of M passed to the annotation and its type after the annotation. By contrast, free type variables of τ remain shared between both types. The example below illustrates how type annotations can be used to remove ambivalence.

Rule M-WITNESS says that the Eq type constructor can be used to witness an equality between equal types as eq(ζ , ζ ) γ , for any type ζ . Conversely, an equality type eq(ζ 1 , ζ 2 ) γ , can only have been built from the Eq type constructor.

Rule M-USE uses this fact to learn and add the equation τ 1 . = τ 2 in the typing context while typechecking the body of M 2 ; the witness M 1 must be typable as an instance of the type eq(τ 1 , τ 2 ) up to sharing of inner nodes. Since the equation is only available while typechecking M 2 , it is not present in the typing context of the conclusion. Hence, the type ζ 2 must be well-formed in Γ . But this is a direct consequence of the second premise: it implies Γ , τ 1 . = τ 2 ζ 2 , which in turn requires that all labels of ζ 2 (which contain no quantifiers) have node descriptions in Γ , so that they cannot depend on τ 1 . = τ 2 . Typically, ambivalent types needed for the typing of M 2 are introduced using rule M-BIND, which means that they cannot remain inside ζ 2 , so that there is no way to keep an ambiguous type. Notice that the well-formedness of Γ , τ 1 . = τ 2 implies that τ 1 and τ 2 contain no flexible type variables (rules WF-TYPE-EQUAL and WF-CTX-EQUAL).

We now illustrate the typing rules on an example. Assume that (if then else ) is given as a primitive with type scheme

∀(γ b , γ 2 , γ 1 , γ 0 ) ∀(α) (bool γ b → (α → (α → α) γ 2 ) γ 1 ) γ 0 . Let Γ be Γ a , ∆ , ∆ , y : (int ≈ a) α where Γ a is a, a . = int and ∆ is α :: int, γ 2 :: α → α, γ 1 :: α → (α → α) γ 2 and ∆ is γ b :: bool, γ 0 :: γ b → (α → (α → α) γ 2 ) γ 1 .
Using M-VAR for premises, we have:

M-APP Γ if then else : (bool γ b → (α → (α → α) γ 2 ) γ 1 ) γ 0 Γ true : γ b Γ if true then else : (α → (α → α) γ 2 ) γ 1
We also have Γ 1 : (int ≈ a) α and Γ y : (int ≈ a) α by M-INST and M-VAR. Hence, we have Γ if true then 1 else y : (int ≈ a) α by M-APP. This leads to:

M-FUN Γ if true then 1 else y : (int ≈ a) α M-INST Γ a , ∆ , ∆ λ (y) if true then 1 else y : ∀(γ) ((int ≈ a) α → (int ≈ a) α ) γ M-BIND Γ a , ∆ , ∆ M : ((int ≈ a) α → (int ≈ a) α ) γ 2 M-GEN Γ a , ∆ M : ((int ≈ a) α → (int ≈ a) α ) γ 2 Γ a M : ∀(α, γ) ((int ≈ a) α → (int ≈ a) α ) γ
where M is λ (y) if true then 1 else y. Rule M-BIND is used for variables γ b and γ 0 in ∆ that are no longer used (we omitted the other premises), while Rule M-GEN is used for variables α and γ 2 in ∆ . Notice that neither Γ a M :

∀(α, α , γ) ((int ≈ a) α → int ≈ a α ) γ nor Γ a M : ∀(α, γ) (int α → int α ) γ are derivable.
It is a key feature of our system that sharing and ambivalence can only be increased implicitly. Still, it is sound to decrease them explicitly, using a type annotation, as in Γ a (a → int) M : ∀(α, α , γ) (a α → int α ) γ . This is obtained by applying the coercion (a → int) of type (a → int) → (a → int) , i.e.

∀(α 1 , α 2 , α 1 , α 2 , γ, γ , γ 0 ) (a α 1 → int α 2 ) γ → (a α 1 → int α 2 ) γ γ 0
to M. The expression M 0 equal to use x : eq(a, int) in (a → int) M is not ambiguous thanks to the annotation around M. Hence, we have:

M-USE* Γ (eq(a, int)) x : ζ 1 Γ , a . = int (a → int) M : a → int M-APP* M-NEW M-FUN* ∆ , a, ∆ , x : eq(a γ 1 , int γ 2 ) γ M 0 : a → int ∆ , a, α :: a λ (x) M 0 : eq(a, int) → a → int ∆ ν(a) λ (x) M 0 : ∀(α) eq(α, int) → α → int ∆ Eq : . . . (ν(a) λ (x) M 0 ) Eq : int → int
for some well-chosen ∆ , ∆ and Γ , where R * means R preceded and followed by a sequence of M-INST, M-BIND, and M-GEN. The rigid variable a is turned into the polymorphic variable α which is then instantiated to int α before the application to Eq.

Properties

By lack of space, we omit formal statements and their proofs, as well as a description of type inference, and we refer the reader to the accompanying technical report [START_REF] Garrigue | Ambivalent types for principal type inference with GADTs[END_REF].

Type soundness Type soundness is established by seeing our system as a subset of HMG(X) [START_REF] Simonet | A constraint-based approach to guarded algebraic data types[END_REF]. Formally, we exhibit a translation from our language to HMG(X) that preserves typing judgments. The key is that well-formed ambivalent types are such that all simple types in their interpretation are provably equal in the current context, i.e. under the equations introduced by use expressions. Ambivalent types are only used for type inference and are dropped during the translation.

Monotonicity Let Γ σ ≺ σ be the instantiation relation, which says that any monomorphic instance of σ well-formed in Γ is also a monomorphic instance of σ . This relation is extended point-wise to typing contexts: Γ ≺ Γ if for any term variable x in dom(Γ ), Γ Γ (x) ≺ Γ (x), all other components of Γ and Γ being identical. We may now state monotonicity: in our system, if Γ M : ζ and Γ ≺ Γ , then Γ M : ζ .

Existence of principal solutions to type inference problems This is our main result. A typing problem is a typing judgment skeleton Γ M : ζ , where Γ omits all node descriptions α :: ψ (hence, Γ is usually not well-formed, but can be extended into a well-formed environment by interleaving the appropriate node descriptions with bindings in Γ ). A solution to a typing problem is a pair of a substitution θ that preserves ambivalence for the types in Γ and ζ , together with a context ∆ that contains only node descriptions, such that Γ θ and ∆ can be interleaved to produce a well-formed typing context, written Γ θ | ∆ , and the judgment Γ θ | ∆ M : ζ θ holds.

For any typing problem, the set of solutions is stable by substitution and is either empty or has a principal solution (∆ , θ ), i.e. one such that any other solution (∆ , θ ) is of the form θ = θ • θ for some substitution θ that preserves well-formedness in Γ θ | ∆ , i.e. for any type

ζ such that Γ θ | ∆ ζ , we have Γ θ | ∆ ζ θ .
Sound and complete type inference Principality of type inference is proved as usual by exhibiting a concrete type inference algorithm. This algorithm (presented in the extended version) relies on a variant of the standard unification algorithm that works on ambivalent types and preserves their sharing. It uses a typing constraint approach, which converts typing problems to unification problems, while also ensuring that inferred types are well-formed, i.e. coherent, properly scoped, and acyclic. The use of constraints here is however just a convenience: since the ambivalence information is contained in types themselves, constraints can always be solved prior to type generalization so that we do not need constrained type schemes. That is, constraints are just a way to describe the algorithmic steps without getting into implementation details: OCaml itself uses a variant of Milner's algorithm J [START_REF] Milner | A theory of type polymorphism in programming[END_REF].

Related works

While GADTs have been an active research area for about 10 years, early works usually focused on their type checking and expressiveness, ignoring ML-style type inference. Typically, they rely on an explicitly typed core language and use local type inference techniques to leave some type information implicit. Other recent works with rich dependent type systems also fit in this category and are only loosely related to ours.

Relatively few papers are dedicated to principal type inference for GADTs. The tension between ambiguity and principality is so strong that it has been assumed that the only way to reach principality is to know exactly the external type of each GADT match case. As a result, research has not been so much focused on finding a type system with principal types, but rather on clever propagation of type information so that programs have enough type annotations after propagation to admit principal types-or are rejected otherwise. Hence, some existing approaches always return principal solutions, but do not have a clear specification of when they will succeed, because this depends on the propagation algorithm (or some idealized version of it) which does not have a compositional specification.

OutsideIn improves on this by using uses constraint solving in place of directional annotation propagation, which greatly reduces the need for annotations. Stratified type inference [START_REF] Pottier | Stratified type inference for generalized algebraic data types[END_REF] is another interesting approach to type inference for GADTs that uses several sophisticated passes to propagate local typing constraints (and not just type annotations) progressively to the rest of the program.

The following table summarizes the typability of the programs given in the overview, for our approach (including simple syntactic propagation of type annotations), Out-sideIn 6 , and stratified type inference [START_REF] Pottier | Stratified type inference for generalized algebraic data types[END_REF].

Program f f 1 f 2 g g 1 g 2 p p 1 Ambivalent √ √ √ - √ √ √ - OutsideIn ----- √ √ √ Stratified - √ √ -- √ --
The results for f are unsurprising: this example is not even principal in the naive type system: without an internal notion of ambivalence, a type system is unable to tell that the equality between two types is only accidental and should not be considered as a source of ambiguity. The results for f 1 and f 2 are more interesting. While OutsideIn requires an external type annotation in both cases, stratified type inference accepts to infer the type of the branch from its body. More precisely, the propagation algorithm operates in a bi-directional way and is able to extract non-ambiguous information from GADT pattern-matching branches. The exported information is pruned so that it remains compatible with any interpretation of the internal information, even in a context with fewer type equations. Thus, the type of the result is pruned in function f, but it can be propagated for f 1 and f 2 . This corresponds exactly to the naive notion of ambiguity.

Typing of g fails in all three systems, as it is fundamentally ambiguous, whichever definition is chosen. The results for g 1 may look surprising: while it contains many type annotations, both OutsideIn and stratified type inference still fail on it. The reason is that type annotations are inside the branch: in both systems, only type annotations outside of a branch can disambiguate types for which an equation has been introduced. We find this behavior counter-intuitive. The freedom of where to add type annotations stands as a clear advantage of ambivalent types. By contrast, g 2 provides full type annotations in a standard style, so that all systems succeed-although ambivalent types need some (simple) propagation mechanism to push annotations inside.

Programs p and p 1 demonstrate the power of OutsideIn. The program p 1 is the following variant of p, which we deem ambiguous: let p 1 (type a) (x : (a,int) eq) (y : a) = let z = (match x with Eq -> if y>0 then y else 0) in z + 1

Indeed, the match expression in p 1 would have to be given the ambivalent type a ≈ int, which is not allowed outside the scope of the equation a = int. Both p and p 1 are accepted by OutsideIn, since type information can be propagated upward, even for local let definitions. This comes at a cost, though: local let-definitions are monomorphic by default (but can be made polymorphic by adding a type annotation). While local polymorphic definitions are relatively rare, so that this change of behavior appears as a good compromise for Haskell, they are still frequent enough, and their corresponding type annotations large enough, so that we prefer to keep local polymorphism in OCaml [START_REF] Garrigue | Monomophic let in OCaml? Blog article at[END_REF]. Moreover, local polymorphism is critical to the annotation propagation mechanism used by OCaml, originally for polymorphic methods, and now for GADTs too.

All examples above are specifically chosen to illustrate the mechanisms underlying ambivalence and do not cover all uses of GADTs. Thus, they do not mean that our approach always outperforms other ones, but they emphasize the relevance of ambivalence. The question is not whichever approach taken alone performs better, but rather how ambivalence can be used to improve type inference with GADTs. Indeed, ambivalence could be added to other existing approaches to improve them as well.

Besides this comparison on examples, the main advantage of ambivalent types is to preserve principal type inference and monotonicity, so that type inference and program refactoring are less surprising.

An interesting proposal by Lin and Sheard [START_REF] Lin | Pointwise generalized algebraic data types[END_REF], called point-wise type inference, is also tackling type inference à la ML, but restricting the expressiveness of the systemsome uses of GADT will be rejected-so that more aggressive type propagation can be done in a principal way. Point-wise type inference is hard to compare to our approach, as many programs have to be modified. For instance, it rejects all our examples, because equality witnesses can only be matched on if they relate two rigid type variables. To be accepted, we could replace eq by a specialized version, type t = Int : int t.

Ambivalent types borrow ideas from earlier works. The use of sharing to track known type information was already present in our work on semi-explicit first-class polymorphism [START_REF] Garrigue | Semi-explicit first-class polymorphism for ML[END_REF]. There, we only tracked sharing on a special category of nodes containing explicitly polymorphic types. Here, we need to track sharing on all nodes, as any type can become ambivalent. In our type inference algorithm, we also reuse the same definition style, describing type inference as a constraint resolution process, but introducing some points where constraints have to be solved before continuing.

The formalization itself borrows a lot from previous work on structural polymorphism for polymorphic variant and record types [START_REF] Garrigue | A certified implementation of ML with structural polymorphism[END_REF]. In particular, unification of ambivalent types, which merges sets of rigid variables and requires checking coherence constraints, can be seen as an instance of the unification of structurally polymorphic nodes. The difference is again that all nodes are potentially ambivalent in our case, while structural polymorphism only cares about variant and record types.

Conclusion

Ambivalent types are a refinement of ML types, which represents within types themselves ambiguities resulting from the use of local equations. They permit a more accurate definition of ambiguity, which in turn reduces the need for type annotations while preserving both the principal type property and monotonicity.

This approach has been implemented in OCaml. We have not addressed propagation of type information in this work, although this is quite useful in practice. A simple propagation mechanism based on polymorphism, similar to that used for semi-explicit first-class polymorphism, as already in use in OCaml, seems sufficient to alleviate the need for most local type annotations, while preserving principality of type inference.

The notion of ambivalence is orthogonal to previous techniques used for GADT type inference. Therefore, it should also benefit other approaches such as OutsideIn or stratified type inference. Hopefully, ambivalent types might be transferable to ML F

Fig. 3 .

 3 Fig. 3. Typing rules also carry type equations τ 1 .= τ 2 in typing contexts that are used to show the coherence of ambivalent types via direct or indirect uses of well-formedness judgments.All axioms require well-formedness of Γ so that whenever a judgment Γ M : σ holds, we have Γ . Rule M-INST instantiates the outermost variable of a type scheme. It is unusual in two ways. First, we write σ [α ← ψ α 0 ] rather than just σ in the quantified type. This trick ensures that all nodes labeled with α were indeed ψ α 0 and overcomes the absence of ψ 0 in the binder. Intuitively, the instantiated type should be σ[α ← ψ α 0 ][α ← ψ γ ],but this happens to be equal to σ [α ← ψ γ ]. Second, we require ψ 0 ⊆ ψ to ensure preservation of ambivalence, as explained in the previous subsection. Finally, the premise Γ ψ γ ensures that the resulting type is well-formed.Rule M-GEN introduces polymorphism implicitly, as in ML: variables that do not appear in the context can be generalized. The following rule is derivable from M-GEN and M-INST, and can be used as a shortcut when variable α does not appear in ψ γ :

Examples in this section use OCaml syntax[START_REF] Leroy | The OCaml system release 4.00, Documentation and user's manual[END_REF]. Letter α stands for a flexible variable as usual while letter a stands for a rigid variable that cannot be instantiated. This will be detailed later.

This is not always true for ML abstract types, as type constructors may be compatible in another context, but we do not address this problem here.

Jacques Garrigue and Didier RémyM-VAR Γ x : σ ∈ Γ Γ x : σ M-INST Γ M : ∀(α) (σ [α ← ψ α 0 ]) ψ 0 ⊆ ψ Γ ψ γ Γ M : σ [α ← ψ γ ] M-GEN Γ , α :: ψ M : σ Γ M : ∀(α) σ M-NEW Γ, a, α :: a M : σ Γ ∀(α) σ [α ← ε α ] Γ ν(a) M : ∀(α) σ [α ← ε α ] M-FUN Γ , x : ζ 0 M : ζ Γ λ (x) M : ∀(γ) (ζ 0 → ζ ) γ M-APP Γ M 1 : ((ζ 2 → ζ ) ≈ ψ) α Γ M 2 : ζ 2 Γ M 1 M 2 : ζ M-LET Γ M 1 : σ 1 Γ , x : σ 1 M 2 : ζ 2 Γ let x = M 1 in M 2 : ζ 2 M-ANN Γ ∀(ftv(τ)) τ Γ (τ) : ∀(ftv(τ)) τ → τ M-WITNESS

This is why we write this ν(a) M rather than Λ a M.

Results differ for GHC

7.6, as it slightly departs from OutsideIn allowing some biased choices, but next versions of GHC should strictly comply with OutsideIn.

Acknowledgments We thank Gabriel Scherer and the anonymous reviewers for detailed comments on this paper.