Sottotipizzazione semantica a Luau

Luau è il primo linguaggio di programmazione a mettere il potere della sottotipizzazione semantica nelle mani di milioni di creatori.

Ridurre al minimo i falsi positivi

Uno dei problemi con gli errori di tipo di segnalazione in strumenti come il widget di analisi degli script in Roblox Studio è falsi positivi. Questi sono avvisi che sono artefatti dell'analisi e non corrispondono a errori che possono verificarsi durante l'esecuzione. Ad esempio, il programma

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

segnala un errore di tipo che non può verificarsi in fase di esecuzione, poiché CFrame supporta la moltiplicazione per entrambi Vector3 et CFrame. (Il suo tipo è ((CFrame, CFrame) -> CFrame) & ((CFrame, Vector3) -> Vector3).)

I falsi positivi sono particolarmente bassi per l'onboarding di nuovi utenti. Se una macchina da scrivere ficcanaso attiva il controllo del tipo e si trova immediatamente di fronte a un muro di falsi scarabocchi rossi, c'è un forte incentivo a spegnerlo immediatamente.

Le imprecisioni negli errori di tipo sono inevitabili, perché è impossibile decidere in anticipo se verrà generato un errore di runtime. I progettisti di sistemi di tipi devono scegliere di convivere con falsi positivi o falsi negativi. In Luau, questo è determinato dalla modalità: strict mode pecca per eccesso di falsi positivi e nonstrict la moda pecca per eccesso di falsi negativi.

Sebbene le imprecisioni siano inevitabili, cerchiamo di rimuoverle quando possibile, in quanto portano a errori e imprecisioni spuri negli strumenti basati sui tipi come il completamento automatico o la documentazione API.

Sottotipizzazione come fonte di falsi positivi

Una delle fonti di falsi positivi in ​​Luau (e in molti altri linguaggi simili come TypeScript o Flow) è sottotipizzazione. Il subtyping viene utilizzato ogni volta che una variabile viene inizializzata o assegnata a e ogni volta che viene chiamata una funzione: il sistema di tipi controlla che il tipo dell'espressione sia un sottotipo del tipo della variabile. Ad esempio, se aggiungiamo tipi al programma precedente

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

quindi il sistema di tipo verifica che il tipo di CFrame la moltiplicazione è un sottotipo di (CFrame, Vector3 | CFrame) -> (Vector3 | CFrame).

La sottotipizzazione è una funzionalità molto utile e supporta costrutti di tipo avanzato come il tipo di unione (T | U) e intersezione (T & U). Per esempio, number? è implementato come tipo di unione (number | nil)abitato da valori che sono numeri o nil.

Sfortunatamente, l'interazione del sottotipo con i tipi di intersezione e unione può avere strani risultati. Un caso semplice (ma piuttosto artificioso) nel vecchio Luau era:

x locale: (numero?) & (stringa?) = nil y locale: nil = nil y = x -- Il tipo '(numero?) & (stringa?)' non può essere convertito in 'nil' x = y

Questo errore è causato da un errore di sottotipizzazione, come riporta il vecchio algoritmo di sottotipizzazione (number?) & (string?) non è un sottotipo di nil. Questo è un falso positivo da allora number & string è disabitata, quindi l'unico possibile abitante di (number?) & (string?) è nil.

Questo è un esempio artificioso, ma ci sono problemi reali sollevati dai creatori causati dai problemi, ad esempio https://devforum.roblox.com/t/luau-recap-july-2021/1382101/5. Attualmente, questi problemi interessano principalmente i creatori che utilizzano funzionalità sofisticate del sistema di tipi, ma man mano che rendiamo l'inferenza del tipo più precisa, i tipi di unione e intersezione diventeranno più comuni, anche nel codice senza annotazioni di tipo.

Questa classe di falsi positivi non si verifica più a Luau, poiché abbiamo abbandonato il nostro vecchio approccio sottotipo sintattico a un'alternativa chiamata sottotipi semantici.

Sottotipi sintattici

AKA "quello che facevamo".

La sottotipizzazione sintattica è un algoritmo ricorsivo diretto dalla sintassi. I casi interessanti per trattare i tipi di intersezione e unione sono:

• Riflessività: T è un sottotipo di T
• Giunzione a L: (T₁ & … & Tⱼ) è un sottotipo di U ogni volta che alcuni dei Tᵢ sono sottotipi di U
• Unione L: (T₁ | … | Tⱼ) è un sottotipo di U ogni volta tutto Tᵢ sono sottotipi di U
• Intersezione R: T è un sottotipo di (U₁ & … & Uⱼ) ogni volta T è un sottotipo di tutti Uᵢ
• Sindacato R: T è un sottotipo di (U₁ | … | Uⱼ) ogni volta T è un sottotipo di alcuni dei Uᵢ.

Per esempio:

• Per riflessività: nil è un sottotipo di nil
• quindi per l'Unione R: nil è un sottotipo di number?
• et: nil è un sottotipo di string?
• quindi per Intersezione R: nil è un sottotipo di (number?) & (string?).

Sìì! Sfortunatamente, usando queste regole:

• number non è un sottotipo di nil
• quindi dall'Unione L: (number?) non è un sottotipo di nil
• et: string non è un sottotipo di nil
• quindi dall'Unione L: (string?) non è un sottotipo di nil
• quindi per Intersezione L: (number?) & (string?) non è un sottotipo di nil.

Questo è tipico del sottotipo sintattico: quando restituisce un risultato "sì", è corretto, ma quando restituisce un risultato "no", potrebbe essere sbagliato. L'algoritmo è A approssimazione conservativae poiché un risultato "no" può portare a errori di battitura, è fonte di falsi positivi.

Sottotipi semantici

Ovvero "cosa facciamo adesso".

Piuttosto che pensare che la sottotipizzazione sia guidata dalla sintassi, consideriamo prima la sua semantica e poi torniamo a come la semantica viene implementata. Per questo, adottiamo il sottotipo semantico:

• La semantica di un tipo è un insieme di valori.
• I tipi di intersezione sono considerati intersezioni impostate.
• I tipi di unione sono considerati unioni di insiemi.
• La sottotipizzazione è considerata inclusione di insiemi.

Per esempio:

e poiché i sottotipi sono interpretati come inclusioni di set:

Quindi, secondo la sottotipizzazione semantica, (number?) & (string?) è equivalente a nilma il sottotipo sintattico supporta solo una direzione.

Va tutto bene, ma se vogliamo usare la sottotipizzazione semantica negli strumenti, abbiamo bisogno di un algoritmo e si scopre che il controllo della sottotipizzazione semantica non è banale.

La sottotipizzazione semantica è difficile

NP-difficile per essere precisi.

Possiamo ridurre la colorazione del grafo alla sottotipizzazione semantica codificando un grafo come un tipo Luau in modo tale che il controllo della sottotipizzazione sui tipi abbia lo stesso risultato del controllo che il grafo non può essere colorato

Ad esempio, la colorazione di un grafico con tre nodi e due colori può essere eseguita utilizzando i tipi:

tipo Rosso = tipo "rosso" Blu = tipo "blu" Colore = Rosso | Tipo blu Coloring = (Colore) -> (Colore) -> (Colore) -> tipo booleano Uncolorable = (Colore) -> (Colore) -> (Colore) -> false

Quindi un grafico può essere codificato come un tipo di funzione di sovraccarico con un sottotipo Uncolorable e supertipo Coloringcome una funzione sovraccaricata che restituisce false quando viene violato un vincolo. Ogni overload codifica un vincolo. Ad esempio, una linea ha vincoli che indicano che i nodi adiacenti non possono avere lo stesso colore:

type Line = Coloring & ((Rosso) -> (Rosso) -> (Colore) -> false) & ((Blu) -> (Blu) -> (Colore) -> false) & ((Colore) -> ( Rosso) -> (Rosso) -> falso) & ((Colore) -> (Blu) -> (Blu) -> falso)

Un triangolo è simile, ma neanche le estremità possono avere lo stesso colore:

digitare Triangolo = Linea & ((Rosso) -> (Colore) -> (Rosso) -> falso) & ((Blu) -> (Colore) -> (Blu) -> falso)

ora Triangle è un sottotipo di Uncolorablema Line non lo è, perché la linea può essere bicolore. Questo può essere generalizzato a qualsiasi grafico finito con qualsiasi numero finito di colori, e quindi il controllo del sottotipo è NP-difficile.

Lo affrontiamo in due modi:

• memorizziamo nella cache i tipi per ridurre l'impronta di memoria e
• interrompere con un errore "Codice troppo complesso" se la cache dei tipi diventa troppo grande.

Spero che questo non si presenti molto nella pratica. Ci sono buone prove che problemi come questo non sorgono in pratica dall'esperienza con sistemi di tipo come Standard ML, che è EXPTIME-completo, ma in pratica devi fare tutto il possibile per codificare i nastri di Turing Machine come file .

Normalizzazione del tipo

L'algoritmo utilizzato per decidere il sottotipo semantico è normalizzazione del tipo. Invece di essere diretti dalla sintassi, prima riscriviamo i tipi da normalizzare, quindi controlliamo la sottotipizzazione sui tipi normalizzati.

Un tipo normalizzato è un'unione di:

• un tipo null normalizzato (ad es. never ou nil)
• un tipo di numero normalizzato (o never ou number)
• un tipo booleano normalizzato (o never ou true ou false ou boolean)
• un tipo di funzione normalizzata (o never o un'intersezione di tipi di funzione) ecc.

Una volta normalizzati i tipi, è semplice controllare il sottotipo semantico.

Ogni tipo può essere normalizzato (sigh, con alcune restrizioni tecniche sui pacchetti di tipi generici). I passaggi importanti sono:

• rimuovendo intersezioni di primitive incompatibili, ad es. number & bool è sostituito da neveret
• rimuovere le unioni di funzioni, ad es. ((number?) -> number) | ((string?) -> string) è sostituito da (nil) -> (number | string).

Ad esempio, normalizzare (number?) & (string?) supprime number & stringquindi tutto ciò che rimane è nil.

Il nostro primo tentativo di implementare la normalizzazione del tipo lo ha applicato liberamente, ma ha portato a prestazioni terribili (il codice complesso è passato dal controllo del tipo in meno di un minuto all'esecuzione durante la notte). La ragione di ciò è estremamente semplice: esiste un'ottimizzazione nell'algoritmo di sottotipizzazione di Luau per gestire la riflessività (T è un sottotipo di T) che esegue un controllo di uguaglianza del puntatore economico. La normalizzazione del tipo può convertire i tipi identici al puntatore in tipi semanticamente equivalenti (ma non identici al puntatore), riducendo significativamente le prestazioni.

A causa di questi problemi di prestazioni, utilizziamo sempre la sottotipizzazione sintattica come primo controllo della sottotipizzazione ed eseguiamo la normalizzazione del tipo solo se l'algoritmo sintattico fallisce. Questo ha senso, perché la sottotipizzazione sintattica è un'approssimazione conservativa della sottotipizzazione semantica.

Sottotipizzazione semantica pragmatica

La sottotipizzazione semantica standard è leggermente diversa da quella implementata in Luau, poiché richiede che lo siano i modelli insiemistica, che richiede che gli abitanti di tipo funzione "agiscano come funzioni". Ci sono due motivi per cui stiamo eliminando questo requisito.

in primo luogonormalizziamo i tipi di funzione in un'intersezione di funzioni, ad esempio un orribile pasticcio di unioni e intersezioni di funzioni:

((numero?) -> numero?) | (((numero) -> numero) & ((stringa?) -> stringa?))

si normalizza a una funzione di sovraccarico:

((numero) -> numero?) & ((nil) -> (numero | stringa)?)

La sottotipizzazione set semantica non supporta questa normalizzazione e invece normalizza le funzioni per forma normale disgiuntiva (unione di intersezioni di funzioni). Non lo facciamo per motivi ergonomici: le funzioni sovraccaricate sono idiomatiche in Luau, ma DNF non lo è, e non vogliamo presentare agli utenti tali tipi non idiomatici.

La nostra normalizzazione si basa sulla riscrittura di unioni di tipi di funzione:

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

Questa normalizzazione è valida nel nostro modello, ma non nei modelli di ensemble.

in secondo luogoin Luau, il tipo di applicazione di una funzione f(x) è B si f ha il tipo (A) -> B et x ha il tipo A. Inaspettatamente, questo non è sempre vero nei modelli di teoria degli insiemi, a causa dei tipi disabitati. Nei modelli insiemistici, if x ha il tipo never alors f(x) ha il tipo never. Non vogliamo gravare gli utenti con l'idea che l'applicazione della funzione abbia un caso speciale, soprattutto perché quel caso speciale può verificarsi solo in dead code.

Nei modelli di teoria degli insiemi, (never) -> A è un sottotipo di (never) -> Bnon importa cosa A et B siamo. Questo non è vero a Luau.

Per questi due motivi (che riguardano in gran parte l'ergonomia piuttosto che qualcosa di tecnico), abbandoniamo i requisiti e l'uso della teoria degli insiemi pragmatico sottotipi semantici.

Tipi di negazione

L'altra differenza tra il sistema di tipi di Luau e il sottotipo semantico standard è che Luau non supporta tutti i tipi negati.

Il caso comune per volere tipi negati è nelle condizioni di controllo del tipo:

-- inizialmente x ha il tipo T if (type(x) == "string") then -- in questo ramo x ha il tipo T & string else -- in questo ramo x ha il tipo T & ~string end

Questo utilizza un tipo negato ~string abitato da valori che non sono stringhe.

In Luau, consentiamo solo questo tipo di perfezionamento della digitazione tipi di test Comme string, function, Part e così via, e non su tipi strutturali come (A) -> Bche evita il caso comune di tipi generali negati.

Prototipazione e verifica

Durante la progettazione dell'algoritmo di sottotipizzazione semantica di Luau, sono state apportate alcune modifiche (ad esempio, inizialmente pensavamo di poter utilizzare la sottotipizzazione degli insiemi). Durante questo periodo di rapidi cambiamenti, era importante essere in grado di iterare rapidamente, quindi inizialmente abbiamo implementato un prototipo piuttosto che passare direttamente a un'implementazione di produzione.

La convalida del prototipo era importante perché gli algoritmi di sottotipizzazione possono avere valori anomali imprevisti. Per questo motivo, abbiamo adottato Agda come nostro linguaggio di prototipazione. Oltre a supportare i test unitari, Agda supporta la verifica meccanizzata, quindi siamo fiduciosi nel design.

Il prototipo non implementa tutto Luau, solo il sottoinsieme funzionale, ma è stato sufficiente per scoprire sottili interazioni tra funzionalità che probabilmente sarebbero emerse come bug difficili da correggere in produzione.

La prototipazione non è perfetta, ad esempio i problemi principali che abbiamo riscontrato in produzione riguardavano le prestazioni e la libreria standard C++, che non verranno mai catturati da un prototipo. Ma l'implementazione della produzione è stata per il resto abbastanza semplice (o almeno tanto semplice quanto può ottenere una modifica di 3kLOC).

Prossimi passi

La sottotipizzazione semantica ha rimosso una fonte di falsi positivi, ma ne abbiamo ancora altre da scovare:

• Applicazioni e operatori di funzioni sovraccarichi
• Accesso alle proprietà nelle espressioni di tipo complesso
• Proprietà della tabella di sola lettura
• Variabili che cambiano tipo nel tempo (dette anche stati di tipo)

La ricerca per rimuovere i falsi scarabocchi rossi continua!

Remerciements

Grazie a Giuseppe Castagna e Ben Greenman per i loro utili commenti sulle bozze di questo articolo.

Alan coordina la progettazione e l'implementazione del sistema simile a Luau, che aiuta a guidare molte funzionalità di sviluppo in Roblox Studio. Il Dr. Jeffrey ha oltre 30 anni di esperienza nella ricerca sui linguaggi di programmazione, è stato un membro attivo di numerosi progetti di software open source e ha conseguito un dottorato in giurisprudenza presso l'Università di Oxford, in Inghilterra.