2.3. Rust as a statically-typed language with type-inference

In this chapter, we will take a look at the type system of Rust. We will learn what a type system is in the context of programming languages and will look at different approaches to dealing with types. For systems programming, we will see that languages with a good type system often make the development process easier.

What are types?

One of the first things that is usually taught to new programmers is the concept of data types. You can define variables in your program, and these variables can be of different types: Integers, floating-point values, strings etc. At this early stage of learning programming, the necessity of assigning types to variables is usually explained through the way that computers handle information, i.e. the way these variables are stored in memory. An integer has a different memory representation than a floating-point number, or a string. The concept of types however goes beyond the simple mapping of variables to memory. It is fundamentally about enforcing rules in your program. The set of rules that a programming language defines for the interplay of types is called its type system. You can think of the type system as an agent with two tasks: It assigns a property called type to all code statements, and it enforces a set of logical rules using these types. Depending on the kind of type system, violating these rules might result in a compilation error or a runtime error.

Let's take a look at some code to get a better understanding of types. For now, we will look at types in C++, we will get to Rust in just a moment.

int foo(int val) {
    return val * 2;
}

int main() {
    int val = 42;
    long long long_val = val;
    int* val_ptr = &val;
    float what_are_types = *reinterpret_cast<float*>(val_ptr);
    int val_twice = foo(val);
    //foo("hello"); //Does not compile because of invalid types
}

Before reading on, just by intuition, try to do the following exercise:

Exercise 2.3: How many distinct types can you identify in the previous code snippet?

In this piece of code, a lot of different types can be seen. Some of them are explicitly stated in the code, others arise implicitly due to the rules of C++. We already saw that variables have types. These are identified by the statements immediately preceeding the name of a variable. So the statement int val = 42 assigned the type int to the variable val.

The other kind of explicit types can be found in the function declarations. Each function in C++ must have a type, just as each variable must have a type. The type of a function is given through its parameters and its return type. So the statement int foo(int val) introduces a function foo with the type int(int), which is shorthand for saying "A function returning an int and accepting one int as parameter" This might read a bit weird to you, at least if you're coming from a western country, where you are used to reading from left to right. Your expectation might be that input parameters come first, then output parameters, but C++ has the opposite syntax (return type first, then input parameters). While this is the default in C++, there is also the trailing return type syntax, where the return type comes at the end of the function. This is actually the default for writing functions in Rust!.

Beyond these explicit types, there are a large number of implicit types assigned by the rules of the C++ programming language to every expression in the code. The C++ standard defines an expression as "a sequence of operators and operands that specifies a computation". C++ is a fairly complex language, as such there are a myriad of different possible expressions. For our purposes, it is only important to note that each expression gets a type assigned to it by the compiler. So in the statement int val = 42, 42 is an expression with an implicit type (int in this case).

At this point we will take a step back from all these definitions and will take a look at the bigger picture. No matter the actual rules for assigning types to statements, expressions and the likes, the existence of types gives a programming language a framework through which it can enforce rules. While these rules could be quite arbitrary in principle, in practice they are aimed at preventing bugs in the code. Since code is meant to be run on actual hardware at some point, the properties and inner workings of the hardware have to be taken into consideration in a programming language. This is where the type system becomes very useful: Think of the type int int C++ code. Even if you did not know the underlying representation of such a type in memory (and indeed the memory representation of int in C++ depends on the system architecture), you could still use the type system to reason about the ways in which the int type can be used. It makes intuitive sense that we can assign an expression of type int to a variable of type int, which is why the statement int val = 42; is well-formed. Assigning an expression of type int to a variable of type std::string makes little sense, and the type system enforces this rule, hence giving us a compilation error when we try to write std::string str = 42;. The same goes for calling functions. Calling our function int foo(int val) with a variable (or expression) of type int works because the types match. Calling foo("hello") does not work, because the type of the "hello" expression (const char[6]You might be used to string literals in C++ being represented by the type const char* (a pointer to constant characters), however the C++ compiler actually treats string literals as character arrays, which is why the length of the string literal (including the null terminator) is part of its type.) does not match the expected type.

Ok, we can define some types and apply some rules on them and sometimes get some errors. What is is really useful for though? Remember how types are a way to represent meaning for constructs in a programming language? This is especially interesting in systems programming, when we look at how the code in our programming language is translated into actual instructions running on a target machine. The meaning associated with types helps guide the compiler to select the correct machine code instructions for statements in your code. Let us look at our foo function again:

int foo(int val) {
    return val * 2;
}

It performs a simple computation, doubling the value in the variable val. To run this code on an actual computer, we need some way to translate the concept of "doubling the value in val" into machine code instructions. Most modern computers will use one of a handful of so-called instruction sets, which essentially define the capabilities of the processor and how these capabilities can be controlled through machine code statements called instructions. The language that these raw processor instructions can be written in is called assembly languageAs there are many different instruction sets, there are also many different assembly languages, sometimes refered to as dialects. Popular assembly language dialects include x86-64, the 64-bit version of the x86 instruction set used by most Intel and AMD CPUs, and ARM, used by many CPUs in smartphones and tablets as well as the latest generation of Apple devices.. We can tell the C++ compiler to output the corresponding instructions for a piece of code in assembly language, for example by using the compiler explorer tool we saw earlier. Putting our foo function into compiler explorer and compiling it for the x86-64 instruction set (which is used by most Intel and AMD CPUs nowadays) yields the following assembly code:

foo(int):
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, eax
        pop     rbp
        ret

There are a bunch of weird-looking statements here, called mov and add and pop etc. These are the instructions that your processor will execute, with their arguments on the right. What is most interesting to us are the two statements mov eax, DWORD PTR [rbp-4] and add eax, eax. Any sort of computation that your CPU performs, it can only apply to special memory regions called registers. Think of these as small memory cells sitting right on your processor. The variables we declare in our code live in main memory. To move values from main memory into a register (or from register to main memory), the x86-64 instruction set defines the mov instruction, which is defined as: mov D, S. This reads as "move the value from S (the source) into D (the destination)". In our case, the source is a memory address in main memory, which is what the [rbp-4] syntax indicates. rbp is a specific register, and [rbp-4] refers to the address in main memory at which our variable val resides. In order to do the correct calculation, the CPU now has to know how many bytes our variable val takes up in memory. This is where the type system comes in again. We gave our variable the type int, and on the target system that this code was compiled on, a variable of type int is always exactly 4 bytes large. The compiler used this information to create the correct mov instruction to load 4 bytes from main memory into the register eax. This is what the DWORD PTR stands for: DWORD is an abbreviation for "double word", where a "word" refers to a value that is 2 bytes long, hence "DWORD" refers to four bytes. Once the value has been loaded into the eax register, the add instruction is used to add the value to itself (which is the same as multiplying it by 2).

Now, think about how this code would behave without the type system to enforce the size of the int type. Without type checks, if we used this function with a variable that is only two bytes large (for example a short), the statement DWORD PTR [...] would be wrong, as it would read too many bytes, potentially reading garbage memory. Had we used a larger type instead, such as long long, which is 8 bytes large, DWORD PTR [...] would read too few bytes, and our addition would be wrong. Even more strangely, what if our variable were a character string instead of a number? What does "loading the first four characters and adding them onto themselves" even mean? Without type information, there would be no way to know which instruction to use.

For systems programming, where we often care about the inner workings of our code and how it maps onto hardware, a good type system with well-defined types is immensely helpful. Languages such as C++ where type information is fully available to the compiler are called statically typed languages, and they play a central role in allowing the compiler to generate efficient machine code. There are also dynamically typed languages, where type information is only available at runtime. You might also find the term untyped language being used, which is a synonym for dynamically typed language. We will take a closer look at the differences between these two approaches in the next section.

Statically typed vs. dynamically typed languages

If you have some experience with scripting languages, such as Python or JavaScript, you might notice that there are languages which use a much looser kind of type system. Here is the code from the previous code snippet, translated into JavaScript:

function foo(val) {
    return val * 2;
}

const val = 42;
const other_val = val;
// Pointers and casts don't translate well to JavaScript...
// We can do more crazy stuff however
const val_twice = foo(val);
const hello_twice = foo("hello");
const crazy = foo({
    member: 42
});

Compared to the C++-case, there are no explicit types in this code. Yet you might wonder, how does the JavaScript interpreter know how to treat these variables, which code to execute in the multiply-statement, and how much memory to reserve in each case? JavaScript still has types, but instead of defining them statically at compile-time (JavaScript isn't even a compiled language), type information exists at runtime in each variable, object, function etc. We call a language that stores type information only at runtime a dynamically typed language, in contrast to statically typed languages which define type information at compile time.

In a dynamically typed language, since the type information is held at runtime, the type of a variable might change at runtime:

let val = 42;
val = "hello";

This is typically not possible in statically typed languages. In contrast, in a statically typed language, types often exist purely at compile time, with no type information available at runtime. Since keeping type information available at runtime results in some overhead, systems programming languages generally refrain from using this runtime type information (RTTI) unless strictly necessary. The concept of polymorphism that we saw in the previous chapter is typically implemented using a form of RTTI.

There are many arguments for and against either statically typed languages or dynamically typed languages. We already saw some arguments for statically typed languages from a systems programming perspective, namely the ability to generate efficient machine code using type information. Dynamically typed languages are often used where programming time is more valuable than program efficiency, since the flexibility in the type system makes it easy to rapidly try out different things or work with abstract concepts without knowing their exact types or memory layouts. This is arguably one of the aspects that made the Python programming language so popular.

It is worth addressing at least one common criticism of statically typed languages: Verbosity. In the next section, we will look at a concept called type inference that can simplify the way we write code in a statically typed language.

Type inference - Letting the compiler figure it out for you

Perhaps the most common criticism of statically typed languages, especially for programmers that are used to dynamically typed languages, is their verbosity. Doing the same thing in Python often takes significantly less lines of code than in C++, for example. Disregarding the question of whether this is a fair assessment (or whether lines of code are a good metric at all), statically typed languages do often require the programmer to be far more explicit about what they want to achieve. In particular, the necessity for every variable to have a well-defined type means that composite or generic types tend to get very large names. The prime example of this were iterators in legacyLegacy code is such a popular term that can mean many different things. In the context of C++, we refer to any code written in a C++-standard prior to C++11 as legacy code. The changes that C++11 introduced were so substantial that there was a paradigm shift in what is considered idiomatic C++-code from C++11 onward. C++ code:

#include <vector>

int main() {
    std::vector<std::pair<int, float>> elements;
    elements.push_back(std::make_pair(1, 1.0f));

    std::vector<std::pair<int, float>>::iterator iter = elements.begin();
    for(; iter != elements.end(); ++iter) {
        std::pair<int, float>& element = *iter;
    }
}

Run this code

These long statements are neither fun to write nor easy to read. One could make the observation that they are also somewhat redundant. Since C++ functions cannot be overloaded by return type alone, the compiler should be able to figure out the exact type that the statement elements.begin() will return (in this case the super-verbose iterator type). Indeed this is exactly what the compiler can do, which is why with C++11, a new keyword called auto was introduced which can be used to tell the compiler to deduce the type of a variable. This is what type deduction does: Whenever applicable, instead of manually writing out verbose types, it lets the compiler figure out the correct type for a statement. Here is the same code using type deduction:

#include <vector>

int main() {
    std::vector<std::pair<int, float>> elements;
    elements.push_back(std::make_pair(1, 1.0f));

    auto iter = elements.begin();
    for(; iter != elements.end(); ++iter) {
        auto& element = *iter;
    }
}

Run this code

Type deduction is a handy feature that makes writing statically typed code more convenient. At the same time, there are limits to type deduction, as some statements might be ambiguous for the compiler without explicit type annotations. In addition, there are corner-cases where type deduction might yield unexpected results. As an example, new C++ programmers are often confused by the difference between string literals and the std::string type in C++:

#include <string>
#include <iostream>

int main() {
    std::string str = "hello";
    auto str2 = "hello";
    if(sizeof(str) == sizeof(str2)) {
        std::cout << "str and str2 have the same size" << std::endl;
    } else {
        std::cout << "str and str2 do not have the same size..." << std::endl;
    }
}

Run this code

String literals in C++ have the type const char[N], where N is the length of the string including the null terminator. There is a conversion between const char[N] and the std::string type, which is why the first statement compiles correctly, however type deduction is very exact, so the type of str2 will be const char[6] instead of std::string.

Now that we learned a bit about type systems in various programming languages, it is time to take a look at Rust and the way it handles types.

The Rust type system

Rust is also a statically typed language, similar to C++. It also supports type deduction, however the type deduction in Rust is more powerful than the one in C++. In particular, where the auto keyword in C++ can optionally be used as a replacement for the type of a variable, in Rust all (non-member) variables are declared with the keyword let:

fn main() {
    let var = 42;
    let var2 = var;
    let var3 = "hello";
    let var4 : u8 = 42;
}

At first, this reads very similar to the dynamically typed languages that we have seen, in particular to JavaScript, which also has a let keyword for declaring variables. Since Rust is statically typed, every variable declared with let has a well defined type at compile-time, the type of which is deduced by the compiler. If we want a different type, Rust also supports type annotations, as is shown in the case of var4, which is declared to be of type u8. These type annotations are mandatory for all situations in which type deduction is not possible, either because there is no statement to deduce from (in the case of member variables), or the statement is ambiguous. The type deduction mechanism in Rust is quite powerful, working well even for complex types:

fn main() {
    let elements = vec![1, 2, 3, 4];
    let complex_iter = elements
        .iter()
        .enumerate()
        .filter(|(_, v)| (*v % 2) == 0)
        .map(|(idx, v)| idx * v);
    let result : Vec<_> = complex_iter.collect();
    println!("{:?}", result);
}

Run this code

The variable complex_iter in this example was created through a chain of operations on the elements vector. Don't worry if this looks confusing to you, we will dive deeper into iterators in a later chapter. For now, all we have to know is that this creates a fairly complex, nested, generic type for the variable complex_iter. The Rust type deduction system is still able to figure out what exactly this type is, without us having to explicitly state the type. If you're curious, the actual type is something like this: Map<Filter<Enumerate<std::slice::Iter<'_, usize>>, [closure@src/main.rs:6:17: 6:39]>, [closure@src/main.rs:7:14: 7:32]> Not something that you would want to write by hand very often.

Perhaps more interestingly, type deduction can also be used with generic types, as is shown with the variable result. Here, the result of the iterator chain is collected into a collection, and since there are many different collections, we have to tell Rust exactly which collection we want (a vector in this case, which is called Vec in Rust). But Vec is a generic type, so it requires the type of the elements that it stores. Instead of explicitly stating this type, we can use an underscore (_) to tell Rust to deduce the type of the vector elements.

Type deduction becomes very helpful once we start to use functional programming concepts in our code, as we will see in future chapters. Functional programming is all about composition and chaining, which quickly results in complex, hard-to-read types. For this reason, traditionally many concepts from functional programming were used mostly in dynamically typed languages such as Python or JavaScript. Rust's type deduction makes it easy to write code that is similarily concise, while at the same time maintaining the advantages of static typing.

Metaprogramming - The demon child of strong type systems

One last feature that is worth mentioning is that of metaprogramming. Metaprogramming refers to the concept of code that generates other code, roughly speaking. There are many different approaches to metaprogramming, such as compile-time code generation, self-modifying code or reflection. For systems programming, metaprogramming techniques that use the type system at compile time are most interesting, as they enable optimizations without the runtime overhead of concepts such as reflection.

Generic code is a simple form of metaprogramming. Here, the programmer writes a piece of code once based on a generic type, and the compiler then creates the appropriate code for specific types through a processed called instancing. Both C++ templates and Rust generics work this way. A more powerful way of metaprogramming that became popular in C++ is template metaprogramming. Templates in C++ are very powerful (in fact they have been shown to be turing complete) and enable the programmer to perform computations based on types. One practical use-case for this is to provide multiple implementations for an algorithm based on the capabilities of a type. As an example, the std::partition_point algorithm in the C++ standard template library (STL) looks for the first element in a range sorted by a predicate for which the predicate does not hold. This can be implemented as a form of binary search, however not all ranges in C++ provide random access to their elements (linked-lists don't, for example). The algorithm std::partition_point is a template function which uses metaprogramming to decide how exactly the algorithm is implemented based on the properties of the type that it is called with. At the end of the day, this is a convenience feature which alleviates the programmer from the need to care about the implementation of this algorithm. Without metaprogramming, it would absolutely be possible to write two separate version of std::partition_point, perhaps called std::partition_point_with_random_access and std::partition_point_without_random_access, that the programmer then has to choose from. As with most language features, the ability to write less code and have things happen automatically, thus reducing the mental load of the programmer, often tends to be worthwhile, which is why we see so many convenience features in modern programming languages.

Metaprogramming is particularily useful when code is expected to change. Consider the case of the std::partition_point function. Without metaprogramming, the programmer might have started out with a linked-list datastructure, forcing him to call std::partition_point_without_random_access. At a later point, he then realizes that he can use a vector instead, which is a contiguous memory data structure and thus provides random access. The code should still compile, however now it uses an unnecessarily slower implementation. With metaprogramming, the code would adapt to such a change. When it comes to performance, as it often does in systems programming, this can be a valuable tool to have in a programming language.

Rust also supports some form of metaprogramming, however instead of going the same route as C++ and effectively introducing a "language within a language" (template metaprogramming), it uses a different approach. As metaprogramming fundamentally is about writing code that creates other code, Rust provides a way to modify the language constructs on the compiler level, namely the abstract syntax tree (AST). The way to do this in Rust is through macros. We won't dive into too much detail on macros at this point, but it is important to note that some very common functionalities in Rust are implemented through macros. One such example is the creation of a vector (Vec) from elements using the vec! macro:

fn main() {
    let elements = vec![1, 2, 3, 4];
}

The vec! macro generates efficient code that creates a new Vec from the slice of numbers [1,2,3,4]. Using a macro results in some node code being generated as a replacement for the macro statement. In this case, the statement vec![1,2,3,4] resolves to something like this:

fn main() {
    let elements = <[_]>::into_vec(Box::new([1, 2, 3, 4]));
}

It might seem strange that something as trivial as creating a vector with a bunch of elements requires a feature as powerful as metaprogramming in Rust. In chapter 4 we will dive deeper into this observation when we talk about zero-overhead abstractions, for now think of it as a consequence of systems programming languages aiming at excellent perfomance.

Recap

In this chapter, we learned about the concept of a type system in a programming language. Through types, the rules of a programming language can be enforced and bugs can be prevented. We learned that there are two major categories of programming languages called statically typed languages and dynamically typed languages. In a statically typed language, type information is available at compile-time, in a dynamically typed language it is held and enforced at runtime. We saw that statically typed languages can use the type information to create efficient machine code, which is why these kinds of languages are good candidates for systems programming. We learned about type inference, which can help to write concise code even in the presence of complex nested types. We saw our first glimps of the type system in Rust and even learned about the technique metaprogramming, which can be used to write code that creates other code.

In the next chapter, we will look at one of the features that makes Rust very unique among programming language, which is its concept of ownership.