Luau is the primary programming language to place the ability of semantic subtyping within the fingers of hundreds of thousands of creators.
Minimizing false positives
One of many points with sort error reporting in instruments just like the Script Evaluation widget in Roblox Studio is false positives. These are warnings which can be artifacts of the evaluation, and don’t correspond to errors which might happen at runtime. For instance, this system
native x = CFrame.new() native y if (math.random()) then y = CFrame.new() else y = Vector3.new() finish native z = x * y
studies a kind error which can’t occur at runtime, since CFrame
helps multiplication by each Vector3
and CFrame
. (Its sort is ((CFrame, CFrame) -> CFrame) & ((CFrame, Vector3) -> Vector3)
.)
False positives are particularly poor for onboarding new customers. If a type-curious creator switches on typechecking and is straight away confronted with a wall of spurious pink squiggles, there’s a robust incentive to instantly change it off once more.
Inaccuracies in sort errors are inevitable, since it’s unimaginable to resolve forward of time whether or not a runtime error shall be triggered. Sort system designers have to decide on whether or not to dwell with false positives or false negatives. In Luau that is decided by the mode: strict
mode errs on the aspect of false positives, and nonstrict
mode errs on the aspect of false negatives.
Whereas inaccuracies are inevitable, we attempt to take away them at any time when attainable, since they lead to spurious errors, and imprecision in type-driven tooling like autocomplete or API documentation.
Subtyping as a supply of false positives
One of many sources of false positives in Luau (and plenty of different comparable languages like TypeScript or Circulate) is subtyping. Subtyping is used at any time when a variable is initialized or assigned to, and at any time when a operate is named: the kind system checks that the kind of the expression is a subtype of the kind of the variable. For instance, if we add varieties to the above program
native x : CFrame = CFrame.new() native y : Vector3 | CFrame if (math.random()) then y = CFrame.new() else y = Vector3.new() finish native z : Vector3 | CFrame = x * y
then the kind system checks that the kind of CFrame
multiplication is a subtype of (CFrame, Vector3 | CFrame) -> (Vector3 | CFrame)
.
Subtyping is a really helpful function, and it helps wealthy sort constructs like sort union (T | U
) and intersection (T & U
). For instance, quantity?
is carried out as a union sort (quantity | nil)
, inhabited by values which can be both numbers or nil
.
Sadly, the interplay of subtyping with intersection and union varieties can have odd outcomes. A easy (however somewhat synthetic) case in older Luau was:
native x : (quantity?) & (string?) = nil native y : nil = nil y = x -- Sort '(quantity?) & (string?)' couldn't be transformed into 'nil' x = y
This error is attributable to a failure of subtyping, the previous subtyping algorithm studies that (quantity?) & (string?)
isn’t a subtype of nil
. It is a false constructive, since quantity & string
is uninhabited, so the one attainable inhabitant of (quantity?) & (string?)
is nil
.
That is a synthetic instance, however there are actual points raised by creators attributable to the issues, for instance https://devforum.roblox.com/t/luau-recap-july-2021/1382101/5. At present, these points largely have an effect on creators making use of refined sort system options, however as we make sort inference extra correct, union and intersection varieties will develop into extra frequent, even in code with no sort annotations.
This class of false positives not happens in Luau, as we’ve got moved from our previous method of syntactic subtyping to another known as semantic subtyping.
Syntactic subtyping
AKA “what we did earlier than.”
Syntactic subtyping is a syntax-directed recursive algorithm. The fascinating instances to cope with intersection and union varieties are:
- Reflexivity:
T
is a subtype ofT
- Intersection L:
(T₁ & … & Tⱼ)
is a subtype ofU
at any time when a number of theTᵢ
are subtypes ofU
- Union L:
(T₁ | … | Tⱼ)
is a subtype ofU
at any time when all theTᵢ
are subtypes ofU
- Intersection R:
T
is a subtype of(U₁ & … & Uⱼ)
at any time whenT
is a subtype of all theUᵢ
- Union R:
T
is a subtype of(U₁ | … | Uⱼ)
at any time whenT
is a subtype of a number of theUᵢ
.
For instance:
- By Reflexivity:
nil
is a subtype ofnil
- so by Union R:
nil
is a subtype ofquantity?
- and:
nil
is a subtype ofstring?
- so by Intersection R:
nil
is a subtype of(quantity?) & (string?)
.
Yay! Sadly, utilizing these guidelines:
quantity
isn’t a subtype ofnil
- so by Union L:
(quantity?)
isn’t a subtype ofnil
- and:
string
isn’t a subtype ofnil
- so by Union L:
(string?)
isn’t a subtype ofnil
- so by Intersection L:
(quantity?) & (string?)
isn’t a subtype ofnil
.
That is typical of syntactic subtyping: when it returns a “sure” consequence, it’s right, however when it returns a “no” consequence, it is likely to be incorrect. The algorithm is a conservative approximation, and since a “no” consequence can result in sort errors, this can be a supply of false positives.
Semantic subtyping
AKA “what we do now.”
Reasonably than considering of subtyping as being syntax-directed, we first take into account its semantics, and later return to how the semantics is carried out. For this, we undertake semantic subtyping:
- The semantics of a kind is a set of values.
- Intersection varieties are regarded as intersections of units.
- Union varieties are regarded as unions of units.
- Subtyping is considered set inclusion.
For instance:
Sort | Semantics |
---|---|
quantity |
{ 1, 2, 3, … } |
string |
{ “foo”, “bar”, … } |
nil |
{ nil } |
quantity? |
{ nil, 1, 2, 3, … } |
string? |
{ nil, “foo”, “bar”, … } |
(quantity?) & (string?) |
{ nil, 1, 2, 3, … } ∩ { nil, “foo”, “bar”, … } = { nil } |
and since subtypes are interpreted as set inclusions:
Subtype | Supertype | As a result of |
---|---|---|
nil |
quantity? |
{ nil } ⊆ { nil, 1, 2, 3, … } |
nil |
string? |
{ nil } ⊆ { nil, “foo”, “bar”, … } |
nil |
(quantity?) & (string?) |
{ nil } ⊆ { nil } |
(quantity?) & (string?) |
nil |
{ nil } ⊆ { nil } |
So based on semantic subtyping, (quantity?) & (string?)
is equal to nil
, however syntactic subtyping solely helps one course.
That is all positive and good, but when we need to use semantic subtyping in instruments, we want an algorithm, and it seems checking semantic subtyping is non-trivial.
Semantic subtyping is tough
NP-hard to be exact.
We will cut back graph coloring to semantic subtyping by coding up a graph as a Luau sort such that checking subtyping on varieties has the identical consequence as checking for the impossibility of coloring the graph
For instance, coloring a three-node, two colour graph might be carried out utilizing varieties:
sort Pink = "pink" sort Blue = "blue" sort Colour = Pink | Blue sort Coloring = (Colour) -> (Colour) -> (Colour) -> boolean sort Uncolorable = (Colour) -> (Colour) -> (Colour) -> false
Then a graph might be encoded as an overload operate sort with subtype Uncolorable
and supertype Coloring
, as an overloaded operate which returns false
when a constraint is violated. Every overload encodes one constraint. For instance a line has constraints saying that adjoining nodes can’t have the identical colour:
sort Line = Coloring & ((Pink) -> (Pink) -> (Colour) -> false) & ((Blue) -> (Blue) -> (Colour) -> false) & ((Colour) -> (Pink) -> (Pink) -> false) & ((Colour) -> (Blue) -> (Blue) -> false)
A triangle is comparable, however the finish factors additionally can’t have the identical colour:
sort Triangle = Line & ((Pink) -> (Colour) -> (Pink) -> false) & ((Blue) -> (Colour) -> (Blue) -> false)
Now, Triangle
is a subtype of Uncolorable
, however Line
isn’t, because the line might be 2-colored. This may be generalized to any finite graph with any finite variety of colours, and so subtype checking is NP-hard.
We cope with this in two methods:
- we cache varieties to scale back reminiscence footprint, and
- quit with a “Code Too Complicated” error if the cache of varieties will get too giant.
Hopefully this doesn’t come up in follow a lot. There may be good proof that points like this don’t come up in follow from expertise with sort methods like that of Commonplace ML, which is EXPTIME-complete, however in follow it’s important to exit of your technique to code up Turing Machine tapes as varieties.
Sort normalization
The algorithm used to resolve semantic subtyping is sort normalization. Reasonably than being directed by syntax, we first rewrite varieties to be normalized, then examine subtyping on normalized varieties.
A normalized sort is a union of:
- a normalized nil sort (both
by no means
ornil
) - a normalized quantity sort (both
by no means
orquantity
) - a normalized boolean sort (both
by no means
ortrue
orfalse
orboolean
) - a normalized operate sort (both
by no means
or an intersection of operate varieties) and so forth
As soon as varieties are normalized, it’s simple to examine semantic subtyping.
Each sort might be normalized (sigh, with some technical restrictions round generic sort packs). The vital steps are:
- eradicating intersections of mismatched primitives, e.g.
quantity & bool
is changed byby no means
, and - eradicating unions of capabilities, e.g.
((quantity?) -> quantity) | ((string?) -> string)
is changed by(nil) -> (quantity | string)
.
For instance, normalizing (quantity?) & (string?)
removes quantity & string
, so all that’s left is nil
.
Our first try at implementing sort normalization utilized it liberally, however this resulted in dreadful efficiency (complicated code went from typechecking in lower than a minute to operating in a single day). The explanation for that is annoyingly easy: there’s an optimization in Luau’s subtyping algorithm to deal with reflexivity (T
is a subtype of T
) that performs an inexpensive pointer equality examine. Sort normalization can convert pointer-identical varieties into semantically-equivalent (however not pointer-identical) varieties, which considerably degrades efficiency.
Due to these efficiency points, we nonetheless use syntactic subtyping as our first examine for subtyping, and solely carry out sort normalization if the syntactic algorithm fails. That is sound, as a result of syntactic subtyping is a conservative approximation to semantic subtyping.
Pragmatic semantic subtyping
Off-the-shelf semantic subtyping is barely totally different from what’s carried out in Luau, as a result of it requires fashions to be set-theoretic, which requires that inhabitants of operate varieties “act like capabilities.” There are two the reason why we drop this requirement.
Firstly, we normalize operate varieties to an intersection of capabilities, for instance a horrible mess of unions and intersections of capabilities:
((quantity?) -> quantity?) | (((quantity) -> quantity) & ((string?) -> string?))
normalizes to an overloaded operate:
((quantity) -> quantity?) & ((nil) -> (quantity | string)?)
Set-theoretic semantic subtyping doesn’t help this normalization, and as an alternative normalizes capabilities to disjunctive regular kind (unions of intersections of capabilities). We don’t do that for ergonomic causes: overloaded capabilities are idiomatic in Luau, however DNF isn’t, and we don’t need to current customers with such non-idiomatic varieties.
Our normalization depends on rewriting away unions of operate varieties:
((A) -> B) | ((C) -> D) → (A & C) -> (B | D)
This normalization is sound in our mannequin, however not in set-theoretic fashions.
Secondly, in Luau, the kind of a operate utility f(x)
is B
if f
has sort (A) -> B
and x
has sort A
. Unexpectedly, this isn’t at all times true in set-theoretic fashions, as a consequence of uninhabited varieties. In set-theoretic fashions, if x
has sort by no means
then f(x)
has sort by no means
. We don’t need to burden customers with the concept operate utility has a particular nook case, particularly since that nook case can solely come up in useless code.
In set-theoretic fashions, (by no means) -> A
is a subtype of (by no means) -> B
, it doesn’t matter what A
and B
are. This isn’t true in Luau.
For these two causes (that are largely about ergonomics somewhat than something technical) we drop the set-theoretic requirement, and use pragmatic semantic subtyping.
Negation varieties
The opposite distinction between Luau’s sort system and off-the-shelf semantic subtyping is that Luau doesn’t help all negated varieties.
The frequent case for wanting negated varieties is in typechecking conditionals:
-- initially x has sort T if (sort(x) == "string") then -- on this department x has sort T & string else -- on this department x has sort T & ~string finish
This makes use of a negated sort ~string
inhabited by values that aren’t strings.
In Luau, we solely enable this type of typing refinement on check varieties like string
, operate
, Half
and so forth, and not on structural varieties like (A) -> B
, which avoids the frequent case of common negated varieties.
Prototyping and verification
Throughout the design of Luau’s semantic subtyping algorithm, there have been modifications made (for instance initially we thought we have been going to have the ability to use set-theoretic subtyping). Throughout this time of speedy change, it was vital to have the ability to iterate shortly, so we initially carried out a prototype somewhat than leaping straight to a manufacturing implementation.
Validating the prototype was vital, since subtyping algorithms can have sudden nook instances. For that reason, we adopted Agda because the prototyping language. In addition to supporting unit testing, Agda helps mechanized verification, so we’re assured within the design.
The prototype doesn’t implement all of Luau, simply the purposeful subset, however this was sufficient to find refined function interactions that will in all probability have surfaced as difficult-to-fix bugs in manufacturing.
Prototyping isn’t excellent, for instance the primary points that we hit in manufacturing have been about efficiency and the C++ commonplace library, that are by no means going to be caught by a prototype. However the manufacturing implementation was in any other case pretty simple (or not less than as simple as a 3kLOC change might be).
Subsequent steps
Semantic subtyping has eliminated one supply of false positives, however we nonetheless have others to trace down:
- Overloaded operate purposes and operators
- Property entry on expressions of complicated sort
- Learn-only properties of tables
- Variables that change sort over time (aka typestates)
The hunt to take away spurious pink squiggles continues!
Acknowledgments
Because of Giuseppe Castagna and Ben Greenman for useful feedback on drafts of this publish.
Alan coordinates the design and implementation of the Luau sort system, which helps drive most of the options of growth in Roblox Studio. Dr. Jeffrey has over 30 years of expertise with analysis in programming languages, has been an energetic member of quite a few open-source software program tasks, and holds a DPhil from the College of Oxford, England.