# Type Inference in Luau

May 11, 2021

by Andy Friesen

Product & Tech

Since 2006, Roblox developers have been using the Lua programming language to create games and interactive experiences on Roblox. Roblox developers come from all walks of life and all levels of experience and their creations are just as varied.

Some of those creations are truly sophisticated pieces of software. Many weigh tens of thousands of lines of code.

While Lua is a wonderful programming language and we like it a lot, we have been learning the same lesson that the web developer community has been learning: writing large applications with dynamically typed programming languages is difficult!

We created Luau to fill this gap.

At its heart, Luau is a type inference engine first and a type checker second. We draw this philosophy from successful prior work like the OCaml and TypeScript compilers.

However, Lua really isn’t quite the same as either OCaml or JavaScript. To make Luau as great as it can be, it’s very important that we accurately model the things that make Lua special.

First, let’s explain some basics.

Type Inference 101

Type inference is almost always about observing that some type A must be the same as some other type B. This is a simplification, but less so than one might think.

```function id(x)
return x
end

local a = 5
local b = id(a)```

When we check the type of `id`, we create two placeholder types: the type of `x` and the return type of the function.

These placeholders only indicate one thing: We know nothing about them.

We then analyze the `return` statement. We observe that, whatever type the function might return, it is the same as the type of `x`. As `x` has no other constraints placed on it, the final inferred type of `id` is inferred to be the generic function `(T)` -> `T`.

(Luau does not yet provide syntax for generic functions but the internal data structures can represent them.)
When the time comes to infer a type for b, we can put our knowledge of id to work. We take the type of `id` and bind its parameter type to the concrete argument type we have. Since the function’s return type is bound to its parameter type already, `(T) -> T` is instantiated as `(number) -> number`. From this, we can deduce that the type of b is number.

Almost all of the type checking work done by Luau is an extension of this idea.

Multiple Returns

In almost every programming language in widespread use, functions return exactly one value. Many languages (especially functional languages) afford lightweight tuples to make multiple returns easy and convenient.

Lua bucks this trend by allowing every function to return 0 or more values. No tuple mechanism is at play here as there is no way to bind the whole tuple to a single name.

```function take_five(a, b, c, d, e)
print(a, b, c, d, e)
end

function get_five()
return 1, 2, 3, 4, 5
end
local a = get_five()
-- foo, bar, and baz receive 1, 2, and 3, respectively.
-- Arguments 4 and 5 are discarded.
local foo, bar, baz = get_five()
-- the 5 return values from get_five are passed as
-- parameters to take_five
take_five(get_five())```

This poses some novel challenges. What is the type of `compose` below?

```function compose(f, g)
return function(...)
return f(g(...))
end
end```

In other languages, we would be able to conclude that the return type of `g` must be the same as the argument type to `f`. In Lua, `f` must accept the same argument count and types as those returned by `g`.

In Luau, we represent this with something we call a type pack. It is very similar to the data structure we use to describe a type but it represents 0 or more types.

Like types, type packs support the notion of placeholders that can later be bound to other packs. Type packs have some other properties: Their lengths may be known or unknown and if known, they may either have fixed or variable size.

Luau models functions as a pair of type packs: One for the argument list and one for the return values.
If we posit the syntax `A...` to indicate a generic type pack, we can write a type for `compose`:

`((B...) -> C..., (A...) -> B...) -> (A...) -> C...`

(Luau does not support this syntax yet either. Coming soon!)

Tables

Tables are very important when writing Lua. They are our arrays, hash maps, and objects all in one. It stands to reason that properly inferring table types from Lua code is pretty important.

In Luau, we break tables up into 4 categories:

• Tables whose exact structure we know
• Tables that are constructed piecewise
• Table-likes that are passed as function parameters, and
• Roblox API data types

We call these sealed tables, unsealed tables, generic tables, and native classes.

Sealed tables

A very common bug that we want to be able to catch is a misspelled property name in a table property assignment.

```local some_table = {some_property=0}
-- oops.  I got the name of the property wrong
some_table.sone_property = 55```

Tables are generally sealed by default.

Unsealed tables

To work smoothly with idiomatic Lua, we need some way to support functions and modules that build up tables over multiple statements.

```local Counter = {}
Counter.value = 0

function Counter.increment()
Counter.value = Counter.value + 1
return Counter.value
end```

In this example, it would be foolish for us to look at the first line, deduce the type `{}` and produce a type error on the second line because we expect `Counter` to remain empty forever.

We therefore take the stance that `Counter` is an unsealed table. Luau is easily able to know the exact shape of this table, but we consider it open to extension.

We don’t want to make it too easy for a table to be unsealed, so we apply some simple heuristics:

• A table’s type is unsealed when it is initialized with a literal empty table, and
• Unsealed tables are converted to sealed tables whenever we encounter one in a function signature.

This yields us pretty good usability.

```function new_counter()
local Counter = {}
Counter.value = 0 -- OK.  Counter is unsealed.

function Counter.increment()
Counter.value = Counter.value + 1
return Counter.value
end

return Counter
end

local c = new_counter()
c.value_ = 5 -- Not allowed.  c is a sealed table here.```

Generic Tables

When dealing with unannotated function parameters, it is rarely possible to pin down the exact shape of an argument that is used in a table-like way:

```local function print_point(p)
print(‘X =’, p.X, ‘Y =’, p.Y)
end```

We can know that `p` has `X` and `Y`, but, since the `print` function can print anything, that’s about it. Those properties could have any type. Any number of other properties could also be present. It doesn’t even need to actually be a table; it could be a Roblox API type like `Vector3`.

(More on the Roblox API in a moment)

Like OCaml and certain other programming languages, Luau table parameters are row polymorphic. In Luau, we call them generic tables. Fields inferred to be present on a generic table are requirements imposed upon callers. Other properties are permitted as long as the required structure is there:

```local a = print_point({X=3, Y=4})
local c = print_point({X=4, Y=3, Name='The Best Point'})
local b = print_point(Vector3.new(3, 4, 0))```

The Roblox API

The Roblox API lays quite a lot of powerful tools at the feet of our ambitious developer community. The API consists of quite a lot of C++ classes that have been reflected into Lua.

It is obviously the case that Luau needs to be aware of this API. Part of that awareness is the knowledge that Roblox class instances are not actually Lua tables. For example, the built-in `pairs()` function cannot be used to iterate over the properties of a Roblox API type.

The type system we have described for Luau so far is a fully structural type system. Lua (and Luau) consider tables to be nothing more or less than the set of properties they hold. The Roblox API does not fit this model. C++ provides a nominal type system where every class has its own “self-ness.” It is entirely typical to have two classes that are distinct despite sharing exactly the same structure. There are actual Roblox classes that satisfy this property and Luau needs to model them correctly.

We solve this by introducing a table-like type for builtin Roblox class instances. Class types are different from table types in that they have identities that distinguish them even if they support all the same methods with all the same types. They also support the notion of inheritance, just like the C++ classes they are made to model.

Conclusion

Drawing static types out of a dynamic language like Lua poses a lot of challenges. Many of these challenges are specific to Lua, but they are quite solvable. We think it works pretty well! 🙂

— — —

Andy Friesen is technical lead for the Luau type checker. He is excited to work at the intersection of video games, developer tools, and programming languages.

Neither Roblox Corporation nor this blog endorses or supports any company or service. Also, no guarantees or promises are made regarding the accuracy, reliability or completeness of the information contained in this blog.

©2021 Roblox Corporation. Roblox, the Roblox logo and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.

Recommended