Flappy Bird Implemented in Typescript types

The ultimate type-level trickery

I wrote a 2D flappy bird game, purely in Typescript types:

Yes you heard that right, this game is written entirely in Typescript type annotations, which—if you didn’t know—are Turing complete.

So how the hell am I runnning it in the browser and rendering the game in Typescript types?

The basic rundown is that I created a type-level Typescript runtime, allowing Typescript types to be run outside of the Typescript compiler/language server.

This “runtime” is a custom VM implemented in Zig, which executes a custom bytecode format I compile Typescript code into.

Let me go into more detail.

(Run the game here)

The gameλ

So instead of mutating some global game state (bird position, the pipes, etc.), we thread the game state through a series of functions which each return a new copy of the game state updated. Every frame, the game does something like this:

type newGameState = MovePipes<ApplyGravity<HandleJump<gameState>>>

I find this elegantly beautiful, it’s very clear to see the transformations that happen on the game state.

The next tricky part is rendering the game. We need to draw the bird, the pipes, and the background.

Drawing inspiration from graphics APIs, I had the idea to give the game state a command buffer: an array of drawing commands. A draw command looks a bit like this:

export type DrawCommand =
  // Draw an image/sprite
  | {
      type: DrawCommandKindImage;
      img: string;
      x: number;
      y: number;
      width: number;
      height: number;
    }
  // Clear the screen
  | {
      type: DrawCommandKindClearCanvas;
      x: number;
      y: number;
      width: number;
      height: number;
    };

Then the task of “rendering” is really just filling the command buffer with the appropriate draw commands to display our game, which can be neatly done at the end of our game state transformations:

// Returns new GameState with draw commands for this frame added
type Draw<State extends GameState> = State & {
  drawCommands: [
    // Draw the background
    {
      type: Image;
      imgUrl: "/background.png";
      x: 0;
      y: 0;
      width: canvasWidth;
      height: canvasHeight;
    },

    // Draw the bird
    {
      type: Image;
      imgUrl: "/bird.png";
      x: birdX;
      y: birdY;
      width: birdW;
      height: birdHeight;
    },

    // Draw every pipe
    ...DrawPipes<State["pipes"]>
  ];
};

Each frame, the game state is updated, the command buffer populated, and then the runtime takes these draw commands and executes them.

And that’s the core game loop! Obviously, I skipped over a lot of details. The rest is just mostly verbose Typescript code for checking collision of the bird on the pipes, ground etc. You can check out the full game code here.

The runtimeλ

There are two main parts:

• The compiler: Written in Rust, takes Typescript source code and spits out bytecode

• The VM: Written in Zig, a custom stack-based virtual machine that runs the bytecode to evaluate types

I’ve compiled the runtime to Wasm, so it takes the draw commands from the game and executes them using the web canvas API. Conceptually, the runtime could use any graphics backend like OpenGL, Vulkan, Metal, etc.

The VM has specialized instructions for computations that would otherwise be expensive in regular type-level Typescript. A prominent group of such expensive computations are arithmetic operations.

In type-level Typescript, you can “hack” arithmetic by using arrays, or template strings. Both are extremely expensive operations, especially in comparison to how trivial arithmetic is for the CPU to compute normally.

I decided to provide a standard library with functions that get compiled into specialized and very performant instructions in the VM:

import {
  // Prints a value to console
  Print,
  // Addition
  Add,
  // Subtraction
  Sub,
  // Less-than-or-equal-to operator
  Lte,
} from "std";

// Compute the Xth fibonnaci number
type Fib<X extends number> = Lte<X, 1> extends true
  ? X
  : Add<Fib<Sub<X, 1>>, Fib<Sub<X, 2>>>;

// The "main" function
// Compute the 35th fibonacci number and print it
export type Main<Args extends string[]> = Print<Fib<35>>;

I’m pretty excited about all the cool optimizations I can implement in the VM. I mentioned earlier that type-level Typescript is like a purely functional programming language. We can actually borrow a lot of cool optimizations from the implementation of FP languages:

• Performant immutable data structures: hash array mapped tries, RRB trees

• Specialized reference counting with reuse (Perceus)

• Tail call optimization (I’ve already implemented this)

Why Zig and Rustλ

Rust’s high-level and zero-cost abstractions make it well suited for walking ASTs and generating bytecode, with speed. Also, instead of writing another Typescript parser, I get to leverage the Typescript parser of the oxc project, which is the best JS/TS parser I’ve used so far¹.

The future: tyvm, a performant type-checkerλ

The idea of using a VM to exponentially speed up type-checking has been tried before.

I decided to try my hand at it because:

1. I just find this stuff fun!

2. I had the idea to focus on supporting only type-level Typescript first.

My plan was that, because of the simplicity of just type-level Typescript, we could nail down that aspect first, before moving onto type-checking the entirety of Typescript.

This would allow tyvm to be useful far more quickly.

An example is that it could be used for Typescript tooling. There are a lot of tools that convert Typescript types to X (where X is something like GraphQL, Prisma schemas, JSON types, etc.), but all of them are pretty limited by not being able to support complex Typescript types.

This could jumpstart my dream of making type-level Typescript a very powerful DSL for writing schemas. For example:

export type User = {
  id: string;
  name: string;
  age: number;
};

export type Mutation = {
  updateUser: (args: { id: User['id'], fields: Partial<Omit<User, 'id'>> }) => Promise<User>
}

When running the updateUser mutation, we can update any field from the User type (except for its ID of course). Without Typescript types, I’d have to rewrite all the field types, and that can be error prone if I change User but forget to update the mutation arguments.

To me it’s way more expressive to use Typescript’s type manipulation utilities to write schemas.

Check out the code for the flappy bird game and tyvm here!

Footnotesλ