Typecheckers built for fun
The League of Moveable Type
The first open-source foundry. And your spot to learn how to use, make, and work with type.
Typechecker Zoo - Stephen Diehl
Personal blog of Stephen Diehl - Software engineer writing about technology, programming, and the future
Types and Programming Languages
A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute. The study of type systems--and of programming languages from a type-theoretic perspective -- -has important applications in software engineering, language design, high-performance compilers, and security. This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages. The approach is pragmatic and operational; each new concept is motivated by programming examples and the more theoretical sections are driven by the needs of implementations. Each chapter is accompanied by numerous exercises and solutions, as well as a running implementation, available via the Web. Dependencies between chapters are explicitly identified, allowing readers to choose a variety of paths through the material. The core topics include the untyped lambda-calculus, simple type systems, type reconstruction, universal and existential polymorphism, subtyping, bounded quantification, recursive types, kinds, and type operators. Extended case studies develop a variety of approaches to modeling the features of object-oriented languages.
typelex – An experimental TypeSpec syntax for Lexicon
An experimental TypeSpec syntax for AT Protocol Lexicons. Write Lexicons in a more readable syntax using TypeSpec.
Designing type-safe sync/async mode support in TypeScript
I recently added sync/async mode support to Optique, a type-safe CLI parserfor TypeScript. It turned out to be one of the trickier features I'veimplemented—the object() combinator alone needed to compute a combined modefrom all its child parsers, and TypeScript's inference kept hitting edge cases. What is Optique? Optique is a type-safe, combinatorial CLI parser for TypeScript, inspired byHaskell's optparse-applicative. Instead of decorators or builder patterns,you compose small parsers into larger ones using combinators, and TypeScriptinfers the result types. Here's a quick taste: import { object } from "@optique/core/constructs";import { argument, option } from "@optique/core/primitives";import { string, integer } from "@optique/core/valueparser";import { run } from "@optique/run";const cli = object({ name: argument(string()), count: option("-n", "--count", integer()),});// TypeScript infers: { name: string; count: number | undefined }const result = run(cli); // sync by default The type inference works through arbitrarily deep compositions—in most cases,you don't need explicit type annotations. How it started Lucas Garron (@lgarron) opened an issue requestingasync support for shell completions. He wanted to provideTab-completion suggestions by running shell commands likegit for-each-ref to list branches and tags. // Lucas's example: fetching Git branches and tags in parallelconst [branches, tags] = await Promise.all([ $`git for-each-ref --format='%(refname:short)' refs/heads/`.text(), $`git for-each-ref --format='%(refname:short)' refs/tags/`.text(),]); At first, I didn't like the idea. Optique's entire API was synchronous, whichmade it simpler to reason about and avoided the “async infection” problem whereone async function forces everything upstream to become async. I argued thatshell completion should be near-instantaneous, and if you need async data, youshould cache it at startup. But Lucas pushed back. The filesystem is a database, and many usefulcompletions inherently require async work—Git refs change constantly, andpre-caching everything at startup doesn't scale for large repos. Fair point. What I needed to solve So, how do you support both sync and async execution modes in a composableparser library while maintaining type safety? The key requirements were: parse() returns T or Promise<T> complete() returns T or Promise<T> suggest() returns Iterable<T> or AsyncIterable<T> When combining parsers, if any parser is async, the combined resultmust be async Existing sync code should continue to work unchanged The fourth requirement is the tricky one. Consider this: const syncParser = flag("--verbose");const asyncParser = option("--branch", asyncValueParser);// What's the type of this?const combined = object({ verbose: syncParser, branch: asyncParser }); The combined parser should be async because one of its fields is async.This means we need type-level logic to compute the combined mode. Five design options I explored five different approaches, each with its own trade-offs. Option A: conditional types with mode parameter Add a mode type parameter to Parser and use conditional types: type Mode = "sync" | "async";type ModeValue<M extends Mode, T> = M extends "async" ? Promise<T> : T;interface Parser<M extends Mode, TValue, TState> { parse(context: ParserContext<TState>): ModeValue<M, ParserResult<TState>>; // ...} The challenge is computing combined modes: type CombineModes<T extends Record<string, Parser<any, any, any>>> = T[keyof T] extends Parser<infer M, any, any> ? M extends "async" ? "async" : "sync" : never; Option B: mode parameter with default value A variant of Option A, but place the mode parameter first with a defaultof "sync": interface Parser<M extends Mode = "sync", TValue, TState> { readonly $mode: M; // ...} The default value maintains backward compatibility—existing user code keepsworking without changes. Option C: separate interfaces Define completely separate Parser and AsyncParser interfaces withexplicit conversion: interface Parser<TValue, TState> { /* sync methods */ }interface AsyncParser<TValue, TState> { /* async methods */ }function toAsync<T, S>(parser: Parser<T, S>): AsyncParser<T, S>; Simpler to understand, but requires code duplication and explicit conversions. Option D: union return types for suggest() only The minimal approach. Only allow suggest() to be async: interface Parser<TValue, TState> { parse(context: ParserContext<TState>): ParserResult<TState>; // always sync suggest(context: ParserContext<TState>, prefix: string): Iterable<Suggestion> | AsyncIterable<Suggestion>; // can be either} This addresses the original use case but doesn't help if async parse() isever needed. Option E: fp-ts style HKT simulation Use the technique from fp-ts to simulate Higher-Kinded Types: interface URItoKind<A> { Identity: A; Promise: Promise<A>;}type Kind<F extends keyof URItoKind<any>, A> = URItoKind<A>[F];interface Parser<F extends keyof URItoKind<any>, TValue, TState> { parse(context: ParserContext<TState>): Kind<F, ParserResult<TState>>;} The most flexible approach, but with a steep learning curve. Testing the idea Rather than commit to an approach based on theoretical analysis, I createda prototype to test how well TypeScript handles the type inference in practice.I published my findings in the GitHub issue: Both approaches correctly handle the “any async → all async” rule at thetype level. (…) Complex conditional types likeModeValue<CombineParserModes<T>, ParserResult<TState>> sometimes requireexplicit type casting in the implementation. This only affects libraryinternals. The user-facing API remains clean. The prototype validated that Option B (explicit mode parameter with default)would work. I chose it for these reasons: Backward compatible: The default "sync" keeps existing code working Explicit: The mode is visible in both types and runtime (via a $modeproperty) Debuggable: Easy to inspect the current mode at runtime Better IDE support: Type information is more predictable How CombineModes works The CombineModes type computes whether a combined parser should be sync orasync: type CombineModes<T extends readonly Mode[]> = "async" extends T[number] ? "async" : "sync"; This type checks if "async" is present anywhere in the tuple of modes.If so, the result is "async"; otherwise, it's "sync". For combinators like object(), I needed to extract modes from parserobjects and combine them: // Extract the mode from a single parsertype ParserMode<T> = T extends Parser<infer M, unknown, unknown> ? M : never;// Combine modes from all values in a record of parserstype CombineObjectModes<T extends Record<string, Parser<Mode, unknown, unknown>>> = CombineModes<{ [K in keyof T]: ParserMode<T[K]> }[keyof T][]>; Runtime implementation The type system handles compile-time safety, but the implementation also needsruntime logic. Each parser has a $mode property that indicates its executionmode: const syncParser = option("-n", "--name", string());console.log(syncParser.$mode); // "sync"const asyncParser = option("-b", "--branch", asyncValueParser);console.log(asyncParser.$mode); // "async" Combinators compute their mode at construction time: function object<T extends Record<string, Parser<Mode, unknown, unknown>>>( parsers: T): Parser<CombineObjectModes<T>, ObjectValue<T>, ObjectState<T>> { const parserKeys = Reflect.ownKeys(parsers); const combinedMode: Mode = parserKeys.some( (k) => parsers[k as keyof T].$mode === "async" ) ? "async" : "sync"; // ... implementation} Refining the API Lucas suggested an important refinement during ourdiscussion. Instead of having run() automatically choose between sync andasync based on the parser mode, he proposed separate functions: Perhaps run(…) could be automatic, and runSync(…) and runAsync(…) couldenforce that the inferred type matches what is expected. So we ended up with: run(): automatic based on parser mode runSync(): enforces sync mode at compile time runAsync(): enforces async mode at compile time // Automatic: returns T for sync parsers, Promise<T> for asyncconst result1 = run(syncParser); // stringconst result2 = run(asyncParser); // Promise<string>// Explicit: compile-time enforcementconst result3 = runSync(syncParser); // stringconst result4 = runAsync(asyncParser); // Promise<string>// Compile error: can't use runSync with async parserconst result5 = runSync(asyncParser); // Type error! I applied the same pattern to parse()/parseSync()/parseAsync() andsuggest()/suggestSync()/suggestAsync() in the facade functions. Creating async value parsers With the new API, creating an async value parser for Git branches lookslike this: import type { Suggestion } from "@optique/core/parser";import type { ValueParser, ValueParserResult } from "@optique/core/valueparser";function gitRef(): ValueParser<"async", string> { return { $mode: "async", metavar: "REF", parse(input: string): Promise<ValueParserResult<string>> { return Promise.resolve({ success: true, value: input }); }, format(value: string): string { return value; }, async *suggest(prefix: string): AsyncIterable<Suggestion> { const { $ } = await import("bun"); const [branches, tags] = await Promise.all([ $`git for-each-ref --format='%(refname:short)' refs/heads/`.text(), $`git for-each-ref --format='%(refname:short)' refs/tags/`.text(), ]); for (const ref of [...branches.split("\n"), ...tags.split("\n")]) { const trimmed = ref.trim(); if (trimmed && trimmed.startsWith(prefix)) { yield { kind: "literal", text: trimmed }; } } }, };} Notice that parse() returns Promise.resolve() even though it's synchronous.This is because the ValueParser<"async", T> type requires all methods to useasync signatures. Lucas pointed out this is a minor ergonomic issue. If onlysuggest() needs to be async, you still have to wrap parse() in a Promise. I considered per-method mode granularity (e.g., ValueParser<ParseMode, SuggestMode, T>), but the implementation complexity would multiplysubstantially. For now, the workaround is simple enough: // Option 1: Use Promise.resolve()parse(input) { return Promise.resolve({ success: true, value: input });}// Option 2: Mark as async and suppress the linter// biome-ignore lint/suspicious/useAwait: sync implementation in async ValueParserasync parse(input) { return { success: true, value: input };} What it cost Supporting dual modes added significant complexity to Optique's internals.Every combinator needed updates: Type signatures grew more complex with mode parameters Mode propagation logic had to be added to every combinator Dual implementations were needed for sync and async code paths Type casts were sometimes necessary in the implementation to satisfyTypeScript For example, the object() combinator went from around 100 lines to around250 lines. The internal implementation uses conditional logic based on thecombined mode: if (combinedMode === "async") { return { $mode: "async" as M, // ... async implementation with Promise chains async parse(context) { // ... await each field's parse result }, };} else { return { $mode: "sync" as M, // ... sync implementation parse(context) { // ... directly call each field's parse }, };} This duplication is the cost of supporting both modes without runtime overheadfor sync-only use cases. Lessons learned Listen to users, but validate with prototypes My initial instinct was to resist async support. Lucas's persistence andconcrete examples changed my mind, but I validated the approach with aprototype before committing. The prototype revealed practical issues (likeTypeScript inference limits) that pure design analysis would have missed. Backward compatibility is worth the complexity Making "sync" the default mode meant existing code continued to workunchanged. This was a deliberate choice. Breaking changes should requireuser action, not break silently. Unified mode vs per-method granularity I chose unified mode (all methods share the same sync/async mode) overper-method granularity. This means users occasionally writePromise.resolve() for methods that don't actually need async, but thealternative was multiplicative complexity in the type system. Designing in public The entire design process happened in a public GitHub issue. Lucas, Giuseppe,and others contributed ideas that shaped the final API. TherunSync()/runAsync() distinction came directly from Lucas's feedback. Conclusion This was one of the more challenging features I've implemented in Optique.TypeScript's type system is powerful enough to encode the “any async means allasync” rule at compile time, but getting there required careful design work andprototyping. What made it work: conditional types like ModeValue<M, T> can bridge the gapbetween sync and async worlds. You pay for it with implementation complexity,but the user-facing API stays clean and type-safe. Optique 0.9.0 with async support is currently in pre-release testing. Ifyou'd like to try it, check out PR #70 or install the pre-release: npm add @optique/core@0.9.0-dev.212 @optique/run@0.9.0-dev.212deno add --jsr @optique/core@0.9.0-dev.212 @optique/run@0.9.0-dev.212 Feedback is welcome!
software-mansion/TypeGPU
A modular and open-ended toolkit for WebGPU, with advanced type inference and the ability to write shaders in TypeScript
Functional Query Languages with Categorical Types
We study three category-theoretic types in the context of functional query languages (typed lambda-calculi extended with additional operations for bulk data processing). The types we study are:
Generic deriving of generic traversals | Proceedings of the ACM on Programming Languages
Functional programmers have an established tradition of using traversals as a design pattern to work with recursive data structures. The technique is so prolific that a whole host of libraries have been designed to help in the task of automatically ...
Categories of Containers
We introduce the notion of containers as a mathematical formalisation of the idea that many important datatypes consist of templates where data is stored. We show that containers have good closure properties under a variety of constructions including the formation of initial algebras and final coalgebras. We also show that containers include strictly positive types and shapely types but that there are containers which do not correspond to either of these. Further, we derive a representation result classifying the nature of polymorphic functions between containers. We finish this paper with an application to the theory of shapely types and refer to a forthcoming paper which applies this theory to differentiable types.
