Semantische Subtypisierung in Luau

Luau ist die erste Programmiersprache, die die Macht der semantischen Subtypisierung in die Hände von Millionen von Entwicklern legt.

Minimieren Sie Fehlalarme

Eines der Probleme beim Melden von Typfehlern in Tools wie dem Skriptanalyse-Widget in Roblox Studio ist Fehlalarm. Dies sind Warnungen, die Artefakte der Analyse sind und nicht mit Fehlern übereinstimmen, die während der Ausführung auftreten können. Zum Beispiel das Programm

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

meldet einen Typfehler, der zur Laufzeit nicht auftreten kann, da CFrame unterstützt die Multiplikation mit beiden Vector3 et CFrame. (Sein Typ ist ((CFrame, CFrame) -> CFrame) & ((CFrame, Vector3) -> Vector3).)

Fehlalarme sind besonders gering beim Onboarding neuer Benutzer. Wenn eine neugierige Schreibmaschine die Typprüfung einschaltet und sofort mit einer Wand aus gefälschten roten Schnörkeln konfrontiert wird, besteht ein starker Anreiz, sie sofort auszuschalten.

Ungenauigkeiten bei Typfehlern sind unvermeidlich, da nicht im Voraus entschieden werden kann, ob ein Laufzeitfehler ausgelöst wird. Typsystemdesigner müssen sich entscheiden, ob sie mit falsch positiven oder falsch negativen Ergebnissen leben möchten. In Luau wird dies durch den Modus bestimmt: strict Modus irrt auf der Seite falsch positiver Ergebnisse, und nonstrict Mode irrt auf der Seite falscher Negative.

Obwohl Ungenauigkeiten unvermeidlich sind, versuchen wir, sie wann immer möglich zu entfernen, da sie zu falschen Fehlern und Ungenauigkeiten in typbasierten Tools wie der automatischen Vervollständigung oder der API-Dokumentation führen.

Subtypisierung als Quelle falsch positiver Ergebnisse

Eine der Quellen für Fehlalarme in Luau (und vielen anderen ähnlichen Sprachen wie TypeScript oder Flow) ist Subtypisierung. Subtyping wird immer dann verwendet, wenn eine Variable initialisiert oder ihr zugewiesen wird und wann immer eine Funktion aufgerufen wird: Das Typsystem prüft, ob der Typ des Ausdrucks ein Subtyp des Typs der Variablen ist. Zum Beispiel, wenn wir dem obigen Programm Typen hinzufügen

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

dann überprüft das Typsystem, ob der Typ von CFrame Multiplikation ist eine Unterart von (CFrame, Vector3 | CFrame) -> (Vector3 | CFrame).

Subtyping ist eine sehr nützliche Funktion und unterstützt Rich-Type-Konstrukte wie Union Type (T | U) und Kreuzung (T & U). Zum Beispiel, number? ist als Union-Typ implementiert (number | nil)bewohnt von Werten, die entweder Zahlen sind oder nil.

Leider kann die Interaktion von Subtyping mit Schnitt- und Vereinigungstypen zu seltsamen Ergebnissen führen. Ein einfacher (aber ziemlich erfundener) Fall im alten Luau war:

local x: (Zahl?) & (String?) = nil local y: nil = nil y = x -- Der Typ '(Zahl?) & (String?)' konnte nicht in 'nil' x = y konvertiert werden

Dieser Fehler wird durch einen Subtyping-Fehler verursacht, der alte Subtyping-Algorithmus meldet dies (number?) & (string?) ist kein Subtyp von nil. Dies ist ein falsches Positiv, da number & string ist unbewohnt, also der einzig mögliche Einwohner (number?) & (string?) wurde nil.

Dies ist ein erfundenes Beispiel, aber es gibt echte Probleme, die von den Erstellern aufgrund der Probleme aufgeworfen werden, z. Derzeit betreffen diese Probleme hauptsächlich Ersteller, die anspruchsvolle Typsystemfunktionen verwenden, aber da wir die Typinferenz präziser machen, werden Vereinigungs- und Schnittmengentypen häufiger vorkommen, selbst in Code ohne Typanmerkungen.

Diese Klasse von Fehlalarmen tritt bei Luau nicht mehr auf, da wir unseren alten Ansatz aufgegeben haben syntaktische Subtypisierung zu einer angerufenen Alternative semantische Subtypisierung.

Syntaktische Subtypisierung

AKA "was wir früher gemacht haben."

Syntaktische Subtypisierung ist ein syntaxgesteuerter rekursiver Algorithmus. Die interessanten Fälle zur Behandlung der Schnitt- und Vereinigungstypen sind:

• Reflexivität: T ist ein Untertyp von T
• L-Kreuzung: (T₁ & … & Tⱼ) ist ein Untertyp von U wann immer einige der Tᵢ sind Unterarten von U
• Union L: (T₁ | … | Tⱼ) ist ein Untertyp von U jedes Mal alle Tᵢ sind Unterarten von U
• R-Kreuzung: T ist ein Untertyp von (U₁ & … & Uⱼ) jedes Mal T ist eine Unterart von allem Uᵢ
• Syndikat R: T ist ein Untertyp von (U₁ | … | Uⱼ) jedes Mal T ist eine Unterart von einigen der Uᵢ.

Zum Beispiel:

• Durch Reflexivität: nil ist ein Untertyp von nil
• also von Union R: nil ist ein Untertyp von number?
• und: nil ist ein Untertyp von string?
• also nach Schnittpunkt R: nil ist ein Untertyp von (number?) & (string?).

Yay! Leider mit diesen Regeln:

• number ist kein Subtyp von nil
• Also von Union L: (number?) ist kein Subtyp von nil
• und: string ist kein Subtyp von nil
• Also von Union L: (string?) ist kein Subtyp von nil
• also nach Kreuzung L: (number?) & (string?) ist kein Subtyp von nil.

Dies ist typisch für syntaktisches Subtyping: Wenn es ein „Ja“-Ergebnis zurückgibt, ist es richtig, aber wenn es ein „Nein“-Ergebnis zurückgibt, kann es falsch sein. Der Algorithmus ist a konservative Annäherungund da ein "nein"-Ergebnis zu Tippfehlern führen kann, ist es eine Quelle falsch positiver Ergebnisse.

Semantische Subtypisierung

AKA „was wir jetzt tun“.

Anstatt zu denken, dass die Subtypisierung syntaxgesteuert ist, betrachten wir zuerst ihre Semantik und kehren dann dazu zurück, wie die Semantik implementiert wird. Dazu übernehmen wir die semantische Subtypisierung:

• Die Semantik eines Typs ist eine Menge von Werten.
• Kreuzungstypen werden als festgelegte Kreuzungen betrachtet.
• Vereinigungstypen werden als Vereinigungen von Mengen betrachtet.
• Die Subtypisierung wird als Set-Inklusion betrachtet.

Zum Beispiel:

und da Untertypen als Mengeneinschlüsse interpretiert werden:

Somit ist nach semantischer Subtypisierung (number?) & (string?) ist äquivalent zu nilaber die syntaktische Subtypisierung unterstützt nur eine Richtung.

Das ist alles großartig, aber wenn wir semantische Subtypisierung in Tools verwenden wollen, brauchen wir einen Algorithmus, und es stellt sich heraus, dass die Überprüfung auf semantische Subtypisierung nicht trivial ist.

Semantische Subtypisierung ist schwierig

NP-schwer um genau zu sein.

Wir können das Färben von Graphen auf semantische Subtypisierung reduzieren, indem wir einen Graphen als einen Luau-Typ codieren, sodass die Überprüfung auf Subtypisierung von Typen dasselbe Ergebnis hat wie die Überprüfung, dass der Graph nicht gefärbt werden kann

Beispielsweise kann das Einfärben eines Diagramms mit drei Knoten und zwei Farben mithilfe von Typen erfolgen:

Typ Rot = "Rot" Typ Blau = "Blau" Typ Farbe = Rot | Blauer Typ Färbung = (Farbe) -> (Farbe) -> (Farbe) -> boolescher Typ Nicht färbbar = (Farbe) -> (Farbe) -> (Farbe) -> falsch

Dann kann ein Graph als Überladungsfunktionstyp mit einem Untertyp codiert werden Uncolorable und Supertyp Coloringals überladene Funktion, die zurückkehrt false wenn eine Beschränkung verletzt wird. Jede Überladung codiert eine Einschränkung. Beispielsweise hat eine Linie Einschränkungen, die darauf hinweisen, dass benachbarte Knoten nicht dieselbe Farbe haben können:

type Line = Färbung & ((Rot) -> (Rot) -> (Farbe) -> falsch) & ((Blau) -> (Blau) -> (Farbe) -> falsch) & ((Farbe) -> ( Rot) -> (Rot) -> falsch) & ((Farbe) -> (Blau) -> (Blau) -> falsch)

Ein Dreieck ist ähnlich, aber die Enden können auch nicht die gleiche Farbe haben:

Typ Dreieck = Linie & ((Rot) -> (Farbe) -> (Rot) -> falsch) & ((Blau) -> (Farbe) -> (Blau) -> falsch)

Jetzt Triangle ist ein Untertyp von Uncolorablemehr Line nicht, da die Linie zweifarbig sein kann. Dies kann auf jeden endlichen Graphen mit jeder endlichen Anzahl von Farben verallgemeinert werden, und daher ist die Subtypprüfung NP-schwer.

Wir gehen damit auf zwei Arten um:

• Wir cachen die Typen, um den Speicherbedarf zu reduzieren, und
• mit einem "Code too complex"-Fehler abbrechen, wenn der Type-Cache zu groß wird.

Hoffentlich macht sich das in der Praxis nicht bemerkbar. Es gibt gute Beweise dafür, dass solche Probleme in der Praxis nicht aus der Erfahrung mit Typsystemen wie Standard MLs entstehen, die EXPTIME-vollständig sind, aber in der Praxis müssen Sie alles tun, um Turing-Machine-Bänder als .

Typnormalisierung

Der zur Entscheidung über die semantische Subtypisierung verwendete Algorithmus ist Typ Normalisierung. Anstatt syntaxgesteuert zu sein, schreiben wir zuerst die zu normalisierenden Typen neu und prüfen dann, ob die normalisierten Typen subtypisiert sind.

Ein normalisierter Typ ist eine Vereinigung von:

• ein normalisierter Nulltyp (d. h. never ou nil)
• eine Art normalisierte Zahl (entweder never ou number)
• ein normalisierter boolescher Typ (entweder never ou true ou false ou boolean)
• eine Art von normalisierter Funktion (entweder never oder eine Schnittmenge von Funktionstypen) usw.

Sobald die Typen normalisiert sind, ist es einfach, die semantische Subtypisierung zu überprüfen.

Jeder Typ kann normalisiert werden (seufz, mit einigen technischen Einschränkungen bei generischen Typpaketen). Die wichtigen Schritte sind:

• Entfernen von Schnittpunkten inkompatibler Primitive, z. number & bool wird ersetzt durch neveret
• Funktionsvereinigungen entfernen, z.B. ((number?) -> number) | ((string?) -> string) wird ersetzt durch (nil) -> (number | string).

Zum Beispiel normalisieren (number?) & (string?) supprime number & stringalso bleibt nur nil.

Unser erster Versuch, die Typnormalisierung zu implementieren, wandte sie großzügig an, führte jedoch zu einer schrecklichen Leistung (komplexer Code wurde von der Typprüfung in weniger als einer Minute auf die Ausführung über Nacht umgestellt). Der Grund dafür ist sehr einfach: Es gibt eine Optimierung im Subtyping-Algorithmus von Luau, um Reflexivität zu handhaben (T ist ein Untertyp von T), die eine billige Zeigergleichheitsprüfung durchführt. Die Typnormalisierung kann zeigeridentische Typen in semantisch äquivalente (aber nicht zeigeridentische) Typen umwandeln, wodurch die Leistung erheblich beeinträchtigt wird.

Aufgrund dieser Leistungsprobleme verwenden wir immer die syntaktische Subtypisierung als erste Subtypisierungsprüfung und führen die Typnormalisierung nur durch, wenn der syntaktische Algorithmus fehlschlägt. Dies ist sinnvoll, da die syntaktische Subtypisierung eine konservative Annäherung an die semantische Subtypisierung ist.

Pragmatische semantische Subtypisierung

Die standardmäßige semantische Untertypisierung unterscheidet sich geringfügig von der Implementierung in Luau, da Modelle erforderlich sind Mengenlehre, was erfordert, dass Bewohner des Funktionstyps „wie Funktionen handeln“. Es gibt zwei Gründe, warum wir diese Anforderung fallen lassen.

erstensWir normalisieren Funktionstypen auf eine Schnittmenge von Funktionen, zum Beispiel ein schreckliches Durcheinander von Vereinigungen und Schnittmengen von Funktionen:

((Zahl?) -> Zahl?) | (((Zahl) -> Zahl) & ((String?) -> String?))

normalisiert sich zu einer überladenen Funktion:

((Zahl) -> Zahl?) & ((nil) -> (Zahl | Zeichenkette)?)

Die semantische Untertypisierung von Sätzen unterstützt diese Normalisierung nicht und normalisiert stattdessen Funktionen für disjunktive Normalform (Vereinigungen von Schnittmengen von Funktionen). Wir tun dies aus ergonomischen Gründen nicht: Überladene Funktionen sind in Luau idiomatisch, DNF jedoch nicht, und wir möchten Benutzer nicht mit solchen nicht idiomatischen Typen bekannt machen.

Unsere Normalisierung beruht auf dem Umschreiben von Vereinigungen von Funktionstypen:

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

Diese Normalisierung gilt in unserem Modell, aber nicht in den Ensemble-Modellen.

zweitensin Luau der Anwendungstyp einer Funktion f(x) wurde B si f hat den Typ (A) -> B et x hat den Typ A. Unerwarteterweise trifft dies in mengentheoretischen Modellen aufgrund unbewohnter Typen nicht immer zu. In mengentheoretischen Modellen, wenn x hat den Typ never alors f(x) hat den Typ never. Wir möchten Benutzer nicht mit der Vorstellung belasten, dass die Funktionsanwendung einen Sonderfall hat, zumal dieser Sonderfall nur in totem Code auftreten kann.

In mengentheoretischen Modellen (never) -> A ist ein Untertyp von (never) -> Begal was A et B sind. Bei Luau ist dies nicht der Fall.

Aus diesen beiden Gründen (die sich größtenteils eher auf die Benutzerfreundlichkeit als auf technische Aspekte beziehen) lassen wir die Anforderungen und die Verwendung der Mengentheorie fallen pragmatisch semantische Subtypisierung.

Arten der Negation

Der andere Unterschied zwischen dem Typsystem von Luau und der standardmäßigen semantischen Untertypisierung besteht darin, dass Luau nicht alle negierten Typen unterstützt.

Der übliche Fall für den Wunsch nach negierten Typen sind Typprüfungsbedingungen:

-- anfänglich hat x den Typ T if (type(x) == "string") then -- in diesem Zweig hat x den Typ T & string else -- in diesem Zweig hat x den Typ T & ~string end

Dies verwendet einen negierten Typ ~string von Werten bewohnt, die keine Strings sind.

In Luau erlauben wir nur diese Art der Eingabeverfeinerung Arten von Tests Comme string, function, Part und so weiter und nicht auf Strukturtypen wie (A) -> Bwodurch der übliche Fall von allgemeinen negierten Typen vermieden wird.

Prototyping und Verifikation

Beim Entwerfen des semantischen Subtypisierungsalgorithmus von Luau wurden einige Änderungen vorgenommen (z. B. dachten wir ursprünglich, wir könnten Set-Subtyping verwenden). In dieser Zeit des schnellen Wandels war es wichtig, schnell iterieren zu können, also haben wir zunächst einen Prototyp implementiert, anstatt direkt mit einer Produktionsimplementierung zu beginnen.

Die Validierung von Prototypen war wichtig, da Subtypisierungsalgorithmen unerwartete Ausreißer aufweisen können. Aus diesem Grund haben wir Agda als unsere Prototyping-Sprache übernommen. Zusätzlich zur Unterstützung von Komponententests unterstützt Agda die mechanisierte Verifizierung, sodass wir uns auf das Design verlassen können.

Der Prototyp implementiert nicht das gesamte Luau, nur die funktionale Teilmenge, aber es reichte aus, um subtile Funktionsinteraktionen aufzudecken, die wahrscheinlich als schwer zu behebende Fehler in der Produktion aufgetaucht wären.

Das Prototyping ist nicht perfekt, zum Beispiel waren die Hauptprobleme, auf die wir in der Produktion gestoßen sind, die Leistung und die C++-Standardbibliothek, die niemals von einem Prototyp abgefangen werden. Aber die Produktionsimplementierung war ansonsten ziemlich einfach (oder zumindest so einfach, wie eine 3kLOC-Änderung sein kann).

Nächste Schritte

Durch semantische Subtypisierung wurde eine Quelle falsch positiver Ergebnisse entfernt, aber wir müssen noch mehr ausfindig machen:

• Überladene Anwendungen und Funktionsoperatoren
• Zugreifen auf Eigenschaften für komplexe Typausdrücke
• Schreibgeschützte Tabelleneigenschaften
• Variablen, die ihren Typ im Laufe der Zeit ändern (auch bekannt als Typestates)

Die Suche nach dem Entfernen falscher roter Schnörkel geht weiter!

remerciements

Danke an Giuseppe Castagna und Ben Greenman für hilfreiche Kommentare zu Entwürfen dieses Artikels.

Alan koordiniert das Design und die Implementierung des Luau-ähnlichen Systems, das viele Entwicklungsfunktionen in Roblox Studio vorantreibt. Dr. Jeffrey verfügt über mehr als 30 Jahre Erfahrung in der Erforschung von Programmiersprachen, war aktives Mitglied zahlreicher Open-Source-Softwareprojekte und hat einen Doktortitel in Juris von der University of Oxford, England.