TypeScript And C++ Type Challenges

Battle of the Turing Complete Type Systems

I recently was made aware of the TypeScript type challenges. TypeScript is known for having a rather capable type system, meaning it’s Turing Complete. Which means that there will be a lot that can be done in the type system. I haven’t done too much advanced TypeScript types. But, I have done some advanced typing with C++, which also has a Turing Complete type system.

So, my thought was simple. Go through the TypeScript type challenges, and then translate it into a C++ type challenge, present it, and then go through that myself as well. In the end, we’ll have a decent view of both type systems - and we can appreciate the absolute monstrosities of code that will come out the other side.

Plus, and this is more important to me, we can compare the philosophies of the template/generic types in the languages. TypeScript’s philosophy is very eager evaluation, which means that types must be constrained to have a property or function before it can be used. C++ is a very lazy evaluation, meaning that types aren’t constrained until the last possible moment - and only for code paths used. This provides some very weird mechanisms in C++.

Also, I’m going to use “templates” and “generics” interchangeably throughout the series. They’re similar enough features that I’m going to get the words mixed up, especially as I switch between languages in the same post.

Warm-Up

Since this is the series intro, I’m going to start with the “warm-up” challenge. In TypeScript land, it looks like this:

type HelloWorld = any // expected to be a string

/* _____________ Test Cases _____________ */
import type { Equal, Expect, NotAny } from '@type-challenges/utils'

type cases = [
  Expect<NotAny<HelloWorld>>,
  Expect<Equal<HelloWorld, string>>,
]

That’s not too bad. The solution is also very simple.

type HelloWorld = string

Where things get interesting is the Equal and Expect types defined in the utils. Expect is pretty basic.

type Expect<T extends true> = T

The way this would read in TypeScript land is that T must be the type true or extend it in some way. In C++ land, I would imagine this being a static assertion that the compile-time expression must evaluate to true.

The Equal type is very much a weird type. Here it is:

type Equal<X, Y> =
  (<T>() => T extends X ? 1 : 2) extends
  (<T>() => T extends Y ? 1 : 2) ? true : false

We have two input generics, but three are present in the body. And, we have that weird function definition. Remember what I said about the philosophy of TypeScript types? TypeScript types, generally, are eagerly evaluated. From what I can tell, that <T>() => T is used to introduce an unevaluated type into the type expression, which then turns the type from an eager evaluation into a deferred (or lazy) evaluation. And somehow, this deferral changes how that middle extends operates - which is crucial for this type to works.

Remember how I said extends is the same type or a type which extends it in some way? Well, it turns out TypeScript has some special super types like any, never, and unknown which all behave differently depending on which side they are on in the extends expression. These special cases makes the more trivial type EqualBroken<X, Y> = X extends Y ? Y extends X ? true : false : false actually not work. So, we end up with the lazy evaluation.

Oh, and before you ask, yes, TypeScript types can have ternary expressions in them. Those expressions are how we get if statements and branches in our types.

I feel like I’ve gotten far enough in the weeds for TypeScript, let’s introduce the C++ side of things.

The C++ Type Challenge

Here’s the challenge in C++20 (I’m going to use at least C++20 since it’ll make some of the later challenges a lot easier).

// C++20
#include <type_traits>
#include <string>

using HelloWorld = void;

static_assert(std::is_same_v<HelloWorld, std::string>);

The C++ Solution

The solution for C++ is very simple - just like the JavaScript case.

using HelloWorld = std::string;

Where things are interesting is how things diverge. First, instead of using a custom type to assert, I’m using the builtin keyword static_assert. It does a compile-time assertion and will fail the build if it is false.

Second, we didn’t have to define an “is same” type as that’s provided by the standard library. That said, we could just as easily implement it ourselves. This is the code to implement it from scratch:

// Normally we'd use std::true_type and std::false_type as they are more complete
// These definitions are illustrative-only
struct true_type { static constexpr bool value = true; };

struct false_type { static constexpr bool value = false; };

template<class T, class Y>
struct is_same : false_type {};

template<class T>
struct is_same<T, T> : true_type {};

template<class T, class U>
constexpr auto is_same_v = is_same<T, U>::value;

That’s quite a bit different.

In C++, types are tied to something “concrete” like a struct, class, function, or variable. They can’t just be “standalone” like they are in TypeScript. Which means, when we do type manipulation, we always need something concrete like a struct¹ to tie it down to. So, we’ll see a ton of structs throughout. You might wonder why we don’t just use empty function definitions, and that’s because in C++ templates behave differently depending on what they’re tied to! So, depending on what we need, we’ll use different concrete types.

The other thing you’ll notice is that we define the is_same struct twice! What we’re doing is partial template specialization. What this allows us to do is define a generic “fallback” template first. Then, we can define overrides (or conditions) for when an alternative struct will be used instead.

In this case, we define a struct that defaults to having a false value, and we only use a true value when our input templates are the same (which is why we have is_same<T, T> - we’re conditioning that specialization to when we have the same type in both template inputs).

We also have the constexpr stuff that anybody who’s looked away from C++ doesn’t recognize. constexpr is a new keyword which says “this expression can be ran at compile time.” It’s much stronger than const - and it can be used as a modifier for functions, methods, if statements, etc. It’s basically the new way C++ does compile-time evaluation. We also use it a lot when working with types since it lets us switch between type expressions and value expressions (we can also switch back because a constexpr value can be passed as a template parameter in some cases).

Since constexpr is a compile time expression, we can also templatize constexpr variables - which is how we define is_same_v. We’re basically saying that is_same_v for two given types T and U takes the value of the static property “value” on the type is_same<T, U>".

Finally, here I use another keyword you may not have seen before, auto, which means “infer the type based on the expression.” Auto really isn’t needed here, I could have easily used bool (and it probably would be more legible), but it does let me showcase auto since it will probably come up in the future.

As I said, this was a warm-up. And in our case, the warm up was less about solving the problem (it was super trivial), and more about understanding the framework around how the challenge works. That framework will be important for us moving forward since I’ll be translating a lot of these challenges over to C++, and knowing how the frameworks translate will be important (at least for me).

These frameworks also serve as great introductions to techniques in how things will be done in the future. TypeScript will be making heavy use of ternary operations. C++ will make heavy use of partial template specializations. If you’re interested in seeing the inner workings of both type systems, then subscribe and stay tuned!

1. We could use a class instead, but using structs is the convention I’ve seen in the standard, in tutorials, books, and codebases, so that’s what we’ll stick to.