Actualités / Jeux

Sous-typage sémantique en Luau

Sous-typage sémantique en Luau

Luau est le premier langage de programmation à mettre la puissance du sous-typage sémantique entre les mains de millions de créateurs.

Minimiser les faux positifs

L’un des problèmes liés au signalement des erreurs de type dans des outils tels que le widget d’analyse de script dans Roblox Studio est faux positifs. Ce sont des avertissements qui sont des artefacts de l’analyse et qui ne correspondent pas à des erreurs pouvant survenir lors de l’exécution. Par exemple, le programme

local x = CFrame.new()
local y
if (math.random()) then
  y = CFrame.new()
else
  y = Vector3.new()
end
local z = x * y

signale une erreur de type qui ne peut pas se produire à l’exécution, puisque CFrame prend en charge la multiplication par les deux Vector3 et CFrame. (Son type est ((CFrame, CFrame) -> CFrame) & ((CFrame, Vector3) -> Vector3).)

Les faux positifs sont particulièrement faibles pour l’intégration de nouveaux utilisateurs. Si un créateur curieux de type active la vérification de type et est immédiatement confronté à un mur de faux gribouillis rouges, il y a une forte incitation à le désactiver immédiatement.

Les inexactitudes dans les erreurs de type sont inévitables, car il est impossible de décider à l’avance si une erreur d’exécution sera déclenchée. Les concepteurs de systèmes de typage doivent choisir de vivre avec des faux positifs ou des faux négatifs. À Luau, cela est déterminé par le mode : strict mode se trompe du côté des faux positifs, et nonstrict mode se trompe du côté des faux négatifs.

Bien que les inexactitudes soient inévitables, nous essayons de les supprimer dans la mesure du possible, car elles entraînent de fausses erreurs et une imprécision dans les outils basés sur le type comme la saisie semi-automatique ou la documentation de l’API.

Le sous-typage comme source de faux positifs

L’une des sources de faux positifs en Luau (et de nombreux autres langages similaires comme TypeScript ou Flow) est sous-typage. Le sous-typage est utilisé chaque fois qu’une variable est initialisée ou affectée à, et chaque fois qu’une fonction est appelée : le système de type vérifie que le type de l’expression est un sous-type du type de la variable. Par exemple, si nous ajoutons des types au programme ci-dessus

local x : CFrame = CFrame.new()
local y : Vector3 | CFrame
if (math.random()) then
  y = CFrame.new()
else
  y = Vector3.new()
end
local z : Vector3 | CFrame = x * y

alors le système de type vérifie que le type de CFrame la multiplication est un sous-type de (CFrame, Vector3 | CFrame) -> (Vector3 | CFrame).

Le sous-typage est une fonctionnalité très utile, et il prend en charge les constructions de type riches comme type union (T | U) et intersection (T & U). Par exemple, number? est implémenté en tant que type d’union (number | nil)habité par des valeurs qui sont soit des nombres soit nil.

Malheureusement, l’interaction du sous-typage avec les types d’intersection et d’union peut avoir des résultats étranges. Un cas simple (mais plutôt artificiel) dans l’ancien Luau était:

local x : (number?) & (string?) = nil
local y : nil = nil
y = x -- Type '(number?) & (string?)' could not be converted into 'nil'
x = y

Cette erreur est causée par un échec du sous-typage, l’ancien algorithme de sous-typage signale que (number?) & (string?) n’est pas un sous-type de nil. Il s’agit d’un faux positif puisque number & string est inhabitée, donc le seul habitant possible de (number?) & (string?) est nil.

Ceci est un exemple artificiel, mais il y a de vrais problèmes soulevés par les créateurs causés par les problèmes, par exemple https://devforum.roblox.com/t/luau-recap-july-2021/1382101/5. Actuellement, ces problèmes affectent principalement les créateurs qui utilisent des fonctionnalités de système de type sophistiquées, mais à mesure que nous rendons l’inférence de type plus précise, les types d’union et d’intersection deviendront plus courants, même dans le code sans annotations de type.

Cette classe de faux positifs ne se produit plus à Luau, car nous avons abandonné notre ancienne approche de sous-typage syntaxique à une alternative appelée sous-typage sémantique.

Sous-typage syntaxique

AKA “ce que nous faisions avant.”

Le sous-typage syntaxique est un algorithme récursif dirigé par la syntaxe. Les cas intéressants pour traiter les types d’intersection et d’union sont :

  • Réflexivité : T est un sous-type de T
  • Intersection L : (T₁ & … & Tⱼ) est un sous-type de U chaque fois que certains des Tᵢ sont des sous-types de U
  • Syndicat L : (T₁ | … | Tⱼ) est un sous-type de U chaque fois que tous les Tᵢ sont des sous-types de U
  • Intersection R : T est un sous-type de (U₁ & … & Uⱼ) chaque fois que T est un sous-type de tous les Uᵢ
  • Syndicat R : T est un sous-type de (U₁ | … | Uⱼ) chaque fois que T est un sous-type de certains des Uᵢ.

Par exemple:

  • Par réflexivité : nil est un sous-type de nil
  • donc par Union R : nil est un sous-type de number?
  • et: nil est un sous-type de string?
  • donc par Intersection R : nil est un sous-type de (number?) & (string?).

Yay! Malheureusement, en utilisant ces règles :

  • number n’est pas un sous-type de nil
  • donc par Union L : (number?) n’est pas un sous-type de nil
  • et: string n’est pas un sous-type de nil
  • donc par Union L : (string?) n’est pas un sous-type de nil
  • donc par Intersection L : (number?) & (string?) n’est pas un sous-type de nil.

C’est typique du sous-typage syntaxique : lorsqu’il renvoie un résultat « oui », il est correct, mais lorsqu’il renvoie un résultat « non », il peut être erroné. L’algorithme est un approximation conservatriceet comme un résultat « non » peut entraîner des erreurs de type, il s’agit d’une source de faux positifs.

Sous-typage sémantique

AKA “ce que nous faisons maintenant”.

Plutôt que de penser que le sous-typage est dirigé par la syntaxe, nous considérons d’abord sa sémantique, puis revenons à la façon dont la sémantique est implémentée. Pour cela, nous adoptons le sous-typage sémantique :

  • La sémantique d’un type est un ensemble de valeurs.
  • Les types d’intersection sont considérés comme des intersections d’ensembles.
  • Les types d’union sont considérés comme des unions d’ensembles.
  • Le sous-typage est considéré comme une inclusion d’ensemble.

Par exemple:

Taper Sémantique
number { 1, 2, 3, … }
string { “foo”, “bar”, … }
nil { néant }
number? { néant, 1, 2, 3, … }
string? { néant, “foo”, “bar”, … }
(number?) & (string?) { néant, 1, 2, 3, … } ∩ { néant, “foo”, “bar”, … } = { néant }

et puisque les sous-types sont interprétés comme des inclusions d’ensemble :

Sous-type Supertype Car
nil number? { néant } ⊆ { néant, 1, 2, 3, … }
nil string? { néant } ⊆ { néant, “foo”, “bar”, … }
nil (number?) & (string?) { néant } ⊆ { néant }
(number?) & (string?) nil { néant } ⊆ { néant }

Ainsi, selon le sous-typage sémantique, (number?) & (string?) est équivalent à nilmais le sous-typage syntaxique ne prend en charge qu’une seule direction.

Tout cela est très bien, mais si nous voulons utiliser le sous-typage sémantique dans les outils, nous avons besoin d’un algorithme, et il s’avère que la vérification du sous-typage sémantique n’est pas triviale.

Le sous-typage sémantique est difficile

NP-difficile d’être précis.

Nous pouvons réduire la coloration du graphe au sous-typage sémantique en codant un graphe comme un type Luau de sorte que la vérification du sous-typage sur les types a le même résultat que la vérification de l’impossibilité de colorer le graphe

Par exemple, la coloration d’un graphique à trois nœuds et deux couleurs peut être effectuée à l’aide de types :

type Red = "red"
type Blue = "blue"
type Color = Red | Blue
type Coloring = (Color) -> (Color) -> (Color) -> boolean
type Uncolorable = (Color) -> (Color) -> (Color) -> false

Ensuite, un graphe peut être encodé comme un type de fonction de surcharge avec un sous-type Uncolorable et surtype Coloringcomme une fonction surchargée qui renvoie false lorsqu’une contrainte est violée. Chaque surcharge encode une contrainte. Par exemple, une ligne a des contraintes indiquant que les nœuds adjacents ne peuvent pas avoir la même couleur :

type Line = Coloring
  & ((Red) -> (Red) -> (Color) -> false)
  & ((Blue) -> (Blue) -> (Color) -> false)
  & ((Color) -> (Red) -> (Red) -> false)
  & ((Color) -> (Blue) -> (Blue) -> false)

Un triangle est similaire, mais les extrémités ne peuvent pas non plus avoir la même couleur :

type Triangle = Line
  & ((Red) -> (Color) -> (Red) -> false)
  & ((Blue) -> (Color) -> (Blue) -> false)

À présent, Triangle est un sous-type de Uncolorablemais Line ne l’est pas, car la ligne peut être bicolore. Cela peut être généralisé à n’importe quel graphe fini avec n’importe quel nombre fini de couleurs, et donc la vérification de sous-type est NP-difficile.

Nous traitons cela de deux manières :

  • nous mettons en cache les types pour réduire l’empreinte mémoire, et
  • abandonner avec une erreur « Code trop complexe » si le cache de types devient trop volumineux.

Espérons que cela ne se présente pas beaucoup dans la pratique. Il existe de bonnes preuves que des problèmes comme celui-ci ne surviennent pas dans la pratique à partir de l’expérience avec des systèmes de type comme celui de Standard ML, qui est EXPTIME-complet, mais dans la pratique, vous devez faire tout votre possible pour coder les bandes de Turing Machine en tant que types .

Normalisation de type

L’algorithme utilisé pour décider du sous-typage sémantique est normalisation des types. Plutôt que d’être dirigé par la syntaxe, nous réécrivons d’abord les types à normaliser, puis vérifions le sous-typage sur les types normalisés.

Un type normalisé est une union de :

  • un type nul normalisé (soit never ou nil)
  • un type de nombre normalisé (soit never ou number)
  • un type booléen normalisé (soit never ou true ou false ou boolean)
  • un type de fonction normalisée (soit never ou une intersection de types de fonctions) etc.

Une fois les types normalisés, il est simple de vérifier le sous-typage sémantique.

Chaque type peut être normalisé (soupir, avec quelques restrictions techniques autour des packs de types génériques). Les étapes importantes sont :

  • suppression des intersections de primitives incompatibles, par exemple number & bool est remplacé par neveret
  • supprimer les unions de fonctions, par exemple ((number?) -> number) | ((string?) -> string) est remplacé par (nil) -> (number | string).

Par exemple, normaliser (number?) & (string?) supprime number & stringil ne reste donc que nil.

Notre première tentative d’implémentation de la normalisation de type l’a appliquée généreusement, mais cela a entraîné des performances épouvantables (le code complexe est passé de la vérification de type en moins d’une minute à l’exécution pendant la nuit). La raison en est extrêmement simple : il existe une optimisation dans l’algorithme de sous-typage de Luau pour gérer la réflexivité (T est un sous-type de T) qui effectue une vérification d’égalité de pointeur bon marché. La normalisation de type peut convertir des types identiques au pointeur en types sémantiquement équivalents (mais pas identiques au pointeur), ce qui dégrade considérablement les performances.

En raison de ces problèmes de performances, nous utilisons toujours le sous-typage syntaxique comme première vérification du sous-typage et n’effectuons la normalisation de type que si l’algorithme syntaxique échoue. C’est logique, car le sous-typage syntaxique est une approximation prudente du sous-typage sémantique.

Sous-typage sémantique pragmatique

Le sous-typage sémantique standard est légèrement différent de ce qui est implémenté dans Luau, car il nécessite que les modèles soient théorie des ensembles, qui exige que les habitants des types de fonctions “agissent comme des fonctions”. Il y a deux raisons pour lesquelles nous abandonnons cette exigence.

Premièrementnous normalisons les types de fonctions à une intersection de fonctions, par exemple un horrible gâchis d’unions et d’intersections de fonctions :

((number?) -> number?) | (((number) -> number) & ((string?) -> string?))

normalise à une fonction surchargée :

((number) -> number?) & ((nil) -> (number | string)?)

Le sous-typage sémantique ensembliste ne prend pas en charge cette normalisation et normalise à la place les fonctions pour forme normale disjonctive (unions d’intersections de fonctions). Nous ne le faisons pas pour des raisons ergonomiques : les fonctions surchargées sont idiomatiques en Luau, mais DNF ne l’est pas, et nous ne voulons pas présenter aux utilisateurs de tels types non idiomatiques.

Notre normalisation repose sur la réécriture des unions de types de fonctions :

((A) -> B) | ((C) -> D)   →   (A & C) -> (B | D)

Cette normalisation est valable dans notre modèle, mais pas dans les modèles ensemblistes.

Deuxièmementen Luau, le type d’application d’une fonction f(x) est B si f a le genre (A) -> B et x a le genre A. De manière inattendue, ce n’est pas toujours vrai dans les modèles de la théorie des ensembles, en raison des types inhabités. Dans les modèles de la théorie des ensembles, si x a le genre never alors f(x) a le genre never. Nous ne voulons pas accabler les utilisateurs avec l’idée que l’application de la fonction a un cas particulier, d’autant plus que ce cas particulier ne peut survenir que dans du code mort.

Dans les modèles de la théorie des ensembles, (never) -> A est un sous-type de (never) -> Bpeu importe ce que A et B sommes. Ce n’est pas vrai à Luau.

Pour ces deux raisons (qui concernent en grande partie l’ergonomie plutôt que quelque chose de technique), nous abandonnons l’exigence de la théorie des ensembles et utilisons pragmatique sous-typage sémantique.

Types de négation

L’autre différence entre le système de type de Luau et le sous-typage sémantique standard est que Luau ne prend pas en charge tous les types niés.

Le cas courant pour vouloir des types niés est dans les conditions de vérification de type :

-- initially x has type T
if (type(x) == "string") then
  --  in this branch x has type T & string
else
  -- in this branch x has type T & ~string
end

Ceci utilise un type nié ~string habité par des valeurs qui ne sont pas des chaînes.

Dans Luau, nous n’autorisons ce type de raffinement de typage que sur types d’essais Comme string, function, Part et ainsi de suite, et ne pas sur des types structurels comme (A) -> Bce qui évite le cas courant des types généraux niés.

Prototypage et vérification

Lors de la conception de l’algorithme de sous-typage sémantique de Luau, des modifications ont été apportées (par exemple, au départ, nous pensions pouvoir utiliser le sous-typage ensembliste). Pendant cette période de changement rapide, il était important de pouvoir itérer rapidement, nous avons donc initialement implémenté un prototype plutôt que de passer directement à une implémentation de production.

La validation du prototype était importante, car les algorithmes de sous-typage peuvent avoir des cas particuliers inattendus. Pour cette raison, nous avons adopté Agda comme langage de prototypage. En plus de prendre en charge les tests unitaires, Agda prend en charge la vérification mécanisée, nous sommes donc confiants dans la conception.

Le prototype n’implémente pas tout Luau, juste le sous-ensemble fonctionnel, mais cela a suffi pour découvrir des interactions de fonctionnalités subtiles qui auraient probablement fait surface en tant que bogues difficiles à corriger en production.

Le prototypage n’est pas parfait, par exemple les principaux problèmes que nous avons rencontrés en production concernaient les performances et la bibliothèque standard C++, qui ne seront jamais rattrapés par un prototype. Mais la mise en œuvre de la production était par ailleurs assez simple (ou du moins aussi simple qu’un changement de 3kLOC peut l’être).

Prochaines étapes

Le sous-typage sémantique a supprimé une source de faux positifs, mais nous en avons encore d’autres à traquer :

  • Applications et opérateurs de fonctions surchargés
  • Accès aux propriétés sur les expressions de type complexe
  • Propriétés en lecture seule des tables
  • Variables qui changent de type au fil du temps (alias typesstates)

La quête pour supprimer les faux gribouillis rouges continue !

Remerciements

Merci à Giuseppe Castagna et Ben Greenman pour leurs commentaires utiles sur les brouillons de cet article.


Alan coordonne la conception et la mise en œuvre du système de type Luau, qui aide à piloter de nombreuses fonctionnalités de développement dans Roblox Studio. Le Dr Jeffrey a plus de 30 ans d’expérience dans la recherche sur les langages de programmation, a été un membre actif de nombreux projets de logiciels open source et est titulaire d’un doctorat en droit de l’Université d’Oxford, en Angleterre.