Patrick Dubroy
LightNews LightNews
dubroy.com
Patrick Dubroy
@dubroy.com
1.5K followers 270 following 570 posts
Programmer & researcher, co-creator of https://ohmjs.org. 🇨🇦 🇩🇪 🇪🇺

Co-author of https://wasmgroundup.com — learn Wasm by building a simple compiler in JavaScript.

Prev: CDG/HARC, Google, BumpTop
Posts Replies Media Videos
dubroy.com
Honestly all survey papers should include a graphical taxonomy of related work.
A timeline from 1990 to 2023, covering 50+ papers on skip lists. Each paper is represented by one of 11 different shapes (circle, square, triangle, diamond, etc.) The position of the shape represents the paper's publication date, and arrows between the shapes describe the relationships between them: either "evolved from" or "related".
November 29, 2025 at 7:42 AM
dubroy.com
Not often that I’m reading a CS paper and think, damn, now there’s a good diagram.

These pretty good…love the ✂️s

From ”The Ubiquitous Skip List: A Survey…” dl.acm.org/doi/pdf/10.1...
November 27, 2025 at 7:25 PM
dubroy.com
Definitely one of the cooler language playgrounds I've seen: pinky.cool.omg.lol
November 21, 2025 at 3:46 PM
dubroy.com
TIL: Branded types in TypeScript
→ github.com/pdubroy/til/...
Branded types in TypeScript TypeScript is structurally typed: the type system doesn't distinguish between types that are structurally identical. By sometimes you want something more like nominal typing (like C, Java, Swift, Rust, etc.) In TypeScript, it's possible to do that via a pattern known as branded types. I first heard about this a few months ago, but really only learned how it works the other day. An example The book Learning TypeScript uses the example of currency conversion. Suppose you have the following types: type Euro = number; type USD = number; …and you wanted to prevent mistakes with mixing currencies, and you don't want to change the runtime representation. Enter branded types! Branded types Here's how we can address this with branded types: type Currency<T> = number & { __brand: T }; type Euro = Currency<"EUR">; type USD = Currency<"USD">; const eur = (amount: number) => amount as Euro; const usd = (amount: number) => amount as USD; function usdToEur(amount: USD): Euro { return eur(amount * 0.87); } usdToEur(usd(35)); // this works // `usdToEur(35)` fails to compiile: // Argument of type 'number' is not assignable to parameter of type 'USD'. // Type 'number' is not assignable to type '{ __brand: "USD"; }'.(2345)``` Note that this is purely in the type system — the runtime values are just numbers. As Learning TypeScript puts it: Branded types are a useful lie to the type system: our positive numbers will never actually have that __brand property. We're just making sure that no developer accidentally provides a value of a non-branded type to a location that requires one that is branded. Also, the name __brand is not important here — we could have used __currency or any other name we wanted. Preventing forging When you use a regular property like __brand, it doesn't prevent someone from forging values: import {usdToEur} from "./currency.ts"; type Greenbux = number & { __brand: "USD" }; usdToEur(50 as Greenbux); To protect against this, you can use a Symbol for the property: const brand = Symbol(); type Currency<T> = number & { [brand]: T }; type USD = Currency<"USD">; If you do it this way, it's no longer purely in the types — your generated JS code will have a const brand = Symbol() (though it's never used). To eliminate that, you can use declare const with unique symbol: declare const brand: unique symbol; type Currency<T> = number & { [brand]: T }; type USD = Currency<"USD">; AFAIK, this is equivalent to the previous example, but it's a type-only declaration.
November 19, 2025 at 7:40 PM
dubroy.com
"Some compiler-development experiences are long slogs where you write code for months without ever having a thing that produces an actual executable that you can run."

"My First Fifteen Compilers" by Lindsey Kuper
blog.sigplan.org/2019/07/09/m...
Backend-first compiler development Although the nanopass approach doesn’t specifically mandate implementing a compiler in a back-to-front manner — starting with code generation and working upward from there — the back-to-front approach was a hallmark of P523 in the year I took it. For me, a first-year grad student who had never worked on compilers before, this way of organizing the work was incredibly motivating: at the end of week one of the course (and at the end of week two, and so on for each week), I had written a compiler! Admittedly, what I had at the end of week one was a compiler for an input language that wasn’t very different from the output language. But it converted code in its input language to honest-to-goodness x86 assembly code on which I could then run an off-the-shelf assembler and produce a working executable. Some compiler-development experiences are long slogs where you write code for months without ever having a thing that produces an actual executable that you can run. But with the back-to-front nanopass approach, we got that hit of gratification every week! Furthermore, thinking of each component of the compiler as itself being a compiler was useful because it encouraged us to structure our code in a readable, modular, and maintainable way, in much the same way that parser combinator libraries support the development of readable, modular, maintainable parsers.
November 18, 2025 at 12:34 PM
dubroy.com
A new blog post —

devlog: garbage collection is useful
→ dubroy.com/blog/garbage...

Trying something new: quick, technical posts about things I'm working on. Let's see if it sticks.
devlog: garbage collection is useful November 14, 2025 A long time ago, I spent a few years working on garbage collection in the J9 Java VM. And even though I’ve since done mostly done higher-level stuff, having a deeper knowledge of GC has continued to come in useful. Yesterday, it was an insight from one of my favourite GC papers, A Unified Theory of Garbage Collection, which helped me solve a tricky problem. ohm’s incremental parsing I’m working with a team that’s using Ohm to parse text documents and render a rich text version in ProseMirror. The goal is bidirectional updates: changes in ProseMirror should propagate to the text version, and vice versa. Ohm supports incremental parsing, which means that if you parse some text and then make a small edit, it can quickly reparse by reusing portions of the previous result.
November 14, 2025 at 4:14 PM
dubroy.com
In basically every TypeScript codebase I touch, I end up adding a `checkNotNull` function exactly like the one from the Kotlin stdlib.

So useful! Surprisingly I haven't seen many TS resources which mention this specific pattern.
checkNotNull inline fun <T : Any> checkNotNull(value: T?): T(source) Throws an IllegalStateException if the value is null. Otherwise returns the not null value.
November 14, 2025 at 8:05 AM
dubroy.com
Bjarne Stroustrup: "Subscripts and sizes should be signed" open-std.org/jtc1/sc22/wg...
I will dig into the arguments and consider alternatives, but my conclusion stands: Use signed subscripts and sizes for span as it was deliberately designed to do. The original use of unsigned for the STL was a bad mistake and should be corrected (eventually). Why we have unsigned subscripts in the STL As far as I remember (the STL is 25 years old so my memory may not be completely accurate) three reasons were given for the STL using unsigned types for subscripts • (As opposed to pointer subscripts) vector subscripts can’t be negative, so unsigned is obviously the right type. • We get one more bit to play with so we can get larger vectors; this is important on machines with 16-bit address spaces. • Range checking needs only one check (no need to check for less than 0). I have heard such rationales many times over the years, but • C/C++’s unsigned is a very odd set of types. They do not model natural numbers. In particular, they have modular arithmetic and conversions to/from signed ints that can be very surprising. Beware of any argument using the word “obvious”.
November 12, 2025 at 5:35 AM
dubroy.com
Somewhat surprising (to me) advice in Google's C++ style guide:

"Try to avoid unsigned types (except for representing bitfields or modular arithmetic). Do not use an unsigned type merely to assert that a variable is non-negative."

Example of a possible bug: abseil.io/tips/227

(via @wingolog.org)
On Unsigned Integers Unsigned integers are good for representing bitfields and modular arithmetic. Because of historical accident, the C++ standard also uses unsigned integers to represent the size of containers - many members of the standards body believe this to be a mistake, but it is effectively impossible to fix at this point. The fact that unsigned arithmetic doesn't model the behavior of a simple integer, but is instead defined by the standard to model modular arithmetic (wrapping around on overflow/underflow), means that a significant class of bugs cannot be diagnosed by the compiler. In other cases, the defined behavior impedes optimization. That said, mixing signedness of integer types is responsible for an equally large class of problems. The best advice we can provide: try to use iterators and containers rather than pointers and sizes, try not to mix signedness, and try to avoid unsigned types (except for representing bitfields or modular arithmetic). Do not use an unsigned type merely to assert that a variable is non-negative.
November 11, 2025 at 3:45 PM
dubroy.com
A cool paper from OOPSLA '25 —

An Empirical Evaluation of Property-Based Testing in Python
→ dl.acm.org/doi/pdf/10.1...

Some interesting findings:
- "Each property-based test finds about 50x as many mutations as the average unit test"
- "76% of mutations were found within the first 20 inputs"
Property-based testing (PBT) is a testing methodology with origins in the functional programming community. In recent years, PBT libraries have been developed for non-functional languages, including Python. However, to date, there is little evidence regarding how effective property-based tests are at finding bugs, and whether some kinds of property-based tests might be more effective than others. To gather this evidence, we conducted a corpus study of 426 Python programs that use Hypothesis, Python’s most popular library for PBT. We developed formal definitions for 12 categories of property-based test and implemented an intraprocedural static analysis that categorizes tests. Then, we evaluated the efficacy of test suites of 40 projects using mutation testing, and found that on average, each property-based test finds about 50 times as many mutations as the average unit test. We also identified the categories with the tests most effective at finding mutations, finding that tests that look for exceptions, that test inclusion in collections, and that check types are over 19 times more effective at finding mutations than other kinds of property-based tests. Finally, we conducted a parameter sweep study to assess the strength of property-based tests as a function of the number of random inputs generated, finding that 76% of mutations found were found within the first 20 inputs To address RQ2, assessing the effectiveness of test categories, we used mutation testing to assess the bug-finding power of each project’s test suite. Mutation testing or mutation analysis is a method of evaluating a test suite’s effectiveness. In a mutation test, small changes are made to a program’s source code, called mutations. The mutations are generated by mutation operators, which are syntactic transformation rules. Mutation operators often include swapping arithmetic operators (+ to -), flipping logical operators (and to or), and changing literals. The test suite is then run on the mutated program, and if any test fails, then the mutation is considered caught or killed. If no test fails, then the test suite did not identify the bug. The number of mutations caught is the test suite’s mutation score, and a higher score is indicative of a more robust test suite.
November 8, 2025 at 7:31 PM
dubroy.com
Did you know that Microsoft MakeCode (a Scratch-like coding environment) supports a variant of TypeScript called "Static TypeScript"?

github.com/microsoft/px...

Also described in a 2019 MPLR paper: www.microsoft.com/en-us/resear...
Static TypeScript ~ hint This is a draft reflecting the design of Static TypeScript (STS) - not exactly what is implemented, but quite close. Comments welcome. ~ TypeScript is a typed superset of JavaScript designed to enable JavaScript developers to take advantage of code intellisense, static checking and refactoring made possible by types. TypeScript is gradually typed, meaning that types are optional. Type inference helps to assign types to untyped code. In this document, we define a subset of TypeScript called Static TypeScript (STS, for short), which was created to make it possible to use a scripting language to program physical computers based on microcontrollers with small amounts of memory. The first use of Static TypeScript is for the micro:bit, which has 16Kb of RAM. The best way to think of STS is as C#/Java/C++ subset of TypeScript where all types are known at compile time, which permits efficient linking to a C++ runtime (in the case of the micro:bit, the Lancaster University micro:bit DAL). STS tries to maintain as much of JavaScript semantics as much as possible, given the constraints imposed by a static typing discipline. Goodbye to Any, Union, Intersection Types and the Bad Parts In TypeScript, the Any type is “the one type that can represent any JavaScript value with no constraints”. In TypeScript, every program expression, value, and function must have some type, even if not explicitly provided by the programmer. Per the TypeScript Language Reference: “in places where a type is not explicitly provided and TypeScript cannot infer one, the Any type is assumed.” STS does not permit use of the Any, Union and Intersection types. The result of this is that STS disallows programs where a program element can denote many kinds of runtime values (for example, a variable that is a string at one point in execution and a number at another point, as specified by the union type string | number). Static TypeScript: An Implementation of a Static Compiler for the TypeScript Language. Abstract: While the programming of microcontroller-based embeddable devices typically is the realm of the C language, such devices are now finding their way into the classroom for CS education, even at the level of middle school. As a result, the use of scripting languages (such as JavaScript and Python) for microcontrollers is on the rise. We present Static TypeScript (STS), a subset of TypeScript (itself, a gradually typed superset of JavaScript), and its compiler/linker toolchain, which is implemented fully in TypeScript and runs in the web browser. STS is designed to be useful in practice (especially in education), while being amenable to static compilation targeting small devices. A user’s STS program is compiled to machine code in the browser and linked against a precompiled C++ runtime, producing an executable that is more efficient than the prevalent embedded interpreter approach, extending battery life and making it possible to run on devices with as little as 16 kB of RAM (such as the BBC micro:bit). This paper is primarily a description of the STS system and the technical challenges of implementing embedded programming platforms in the classroom.
October 31, 2025 at 8:58 AM
dubroy.com
Working on a diagram for an upcoming @wasmgroundup.com blog post.
Diagram showing WebAssembly bytecode execution with a horizontal memory strip containing hexadecimal values (41 03 41 02 6c 41 04 6a 0a 46). Above the strip are labels 'instructions' and 'pc' (program counter) with arrows pointing to specific bytes. The program counter highlights byte '6c'. Below the strip, purple arrows point to different instruction bytes, labeled with their corresponding WebAssembly operations: 'i32.const' (pointing to 41 03 and 41 02), 'i32.mul' (pointing to 6c), 'i32.add' (pointing to 6a), and 'i32.eq' (pointing to 46). On the right side is a stack representation showing values '2' and '3' in rectangular boxes.
October 29, 2025 at 10:24 AM
dubroy.com
(Needed a thread here where I can post new examples!)

Dodrio (by Nick Fitzgerald) is an experimental virtual DOM library for Rust and Wasm. It uses bump allocation for the VDOM nodes and uses a stack machine language to represent change lists: github.com/fitzgen/dodrio
Change List as Stack Machine The change list that represents the difference between how the physical DOM currently looks, and our ideal virtual DOM state is encoded in a tiny stack machine language. A stack machine works particularly well for applying DOM diffs, a task that is essentially a tree traversal.
October 29, 2025 at 7:25 AM
dubroy.com
A blog post from last year, which I never posted here —

Bytecode VMs in surprising places
→ dubroy.com/blog/bytecod...
Bytecode VMs in surprising places April 30, 2024 In response to a question on Twitter1, Richard Hipp wrote about why SQLite uses a bytecode VM for executing SQL statements. Most people probably associate bytecode VMs with general-purpose programming languages, like JavaScript or Python. But sometimes they appear in surprising places! Here are a few that I know about. eBPF Did you know that inside the Linux kernel, there’s an extension mechanism that includes a bytecode interpreter and a JIT compiler? I had no idea. Well, it’s called eBPF, and it’s pretty interesting: a register-based VM with ten general-purpose registers and over a hundred different opcodes.
October 29, 2025 at 7:19 AM
dubroy.com
To be clear, I'm only talking about those 4 functions.

Take useContext, why do you say this doesn't involve hidden state?

And how is Provider/useContext not dynamic scoping? (Just using the standard trick to emulate dynamic scoping in a lexically-scoped lang, set and restore a long-lived var.)
October 26, 2025 at 7:58 AM
dubroy.com
If you're interested in UI frameworks/architectures, @raphlinus.bsky.social's writings on the evolution of Xilem (Rust UI toolkit) are an incredible resource: github.com/linebender/x...

Covers details basically all the modern paradigms/toolkits: React, SwiftUI, Flutter, Compose, ImGui, etc.
Xilem is a framework that aims to provide a performant and productive option for Rust GUI. This crates evolved from various experiments in the Linebender community (Druid, masonry, idiopath, lasagna, crochet, etc) This document describes the high-level architecture of xilem. If you want to familirize yourself with the code base, you are just in the right place! An evolution of the ideas implemented in xilem can be found in the following resources: Data Oriented GUI (2018) A Journey through incremental computation (2020) Raph Levien on UI Frameworks (2021) High Performance Rust UI (2022) Ergonomic APIs for hard problems (2022) Xilem Vector Graphics (2023) Announcing Masonry 0.1, and my vision for Rust UI (2023) So you want to write a GUI framework (2021) Rust GUI Infrastructure (2021) Towards a unified theory of reactive UI (2019) Towards principled reactive UI (2020) Xilem: an architecture for UI in Rust (2022) Advice for the next dozen Rust GUIs (2022)
October 25, 2025 at 6:26 AM
dubroy.com
Hmmm, this paper from this year's OOPSLA looks interesting…

React-tRace: A Semantics for Understanding React Hooks
→ dl.acm.org/doi/pdf/10.1...
React has become the most widely used web front-end framework, enabling the creation of user interfaces in a declarative and compositional manner. Hooks are a set of APIs that manage side effects in function components in React. However, their semantics are often seen as opaque to developers, leading to UI bugs. We introduce React-tRace, a formalization of the semantics of the essence of React Hooks, providing a semantics that clarifies their behavior. We demonstrate that our model captures the behavior of React, by theoretically showing that it embodies essential properties of Hooks and empirically comparing our React-tRace-definitional interpreter against a test suite. Furthermore, we showcase a practical visualization tool based on the formalization to demonstrate how developers can better understand the semantics of Hooks
October 24, 2025 at 7:53 PM
dubroy.com
Under the CLOUD Act, isn't the physical location of the servers irrelevant if it's a US company?

www.forbes.com/sites/emmawo...
In sworn testimony before a French Senate inquiry into the role of public procurement in promoting digital sovereignty, Anton Carniaux, Microsoft France's director of public and legal affairs, was asked whether he could guarantee that French citizen data would never be transmitted to U.S. authorities without explicit French authorization. And, he replied, "No, I cannot guarantee it." He said that the company resisted requests from the US authorities "when they are not well-founded", but that under the U.S. Cloud Act, U.S. companies can be forced to hand over data, regardless of where it is stored.
October 23, 2025 at 11:03 AM
dubroy.com
The "Inside Flutter" page from the @flutter.dev docs is a joy: docs.flutter.dev/resources/in....

Would love to see more libraries document their philosophy/approach and "what makes us different" like this.
This document describes the inner workings of the Flutter toolkit that make Flutter's API possible. Because Flutter widgets are built using aggressive composition, user interfaces built with Flutter have a large number of widgets. To support this workload, Flutter uses sublinear algorithms for layout and building widgets as well as data structures that make tree surgery efficient and that have a number of constant-factor optimizations. With some additional details, this design also makes it easy for developers to create infinite scrolling lists using callbacks that build exactly those widgets that are visible to the user. Aggressive composability One of the most distinctive aspects of Flutter is its aggressive composability. Widgets are built by composing other widgets, which are themselves built out of progressively more basic widgets. For example, Padding is a widget rather than a property of other widgets. As a result, user interfaces built with Flutter consist of many, many widgets. The widget building recursion bottoms out in RenderObjectWidgets, which are widgets that create nodes in the underlying render tree. The render tree is a data structure that stores the geometry of the user interface, which is computed during layout and used during painting and hit testing. Most Flutter developers do not author render objects directly but instead manipulate the render tree using widgets. In order to support aggressive composability at the widget layer, Flutter uses a number of efficient algorithms and optimizations at both the widget and render tree layers, which are described in the following subsections.
October 20, 2025 at 5:12 PM
dubroy.com
🤔
The splashcon.org schedule for Thu 16 Oct, showing the papers presented in the session called "Parallelism". Three of paper titles have the word "concurrency" or "concurrent" in them (but not parallel/parallelism).
October 16, 2025 at 6:21 PM
dubroy.com
DanielRosenwasser gets increasingly agitated
October 15, 2025 at 7:29 AM
dubroy.com
This place is not a place of honor…
Screenshot of a GitHub documentation page from the TypeScript repository, reading: """ STOP READING IMMEDIATELY THIS PAGE PROBABLY DOES NOT PERTAIN TO YOU. These are Coding Guidelines for Contributors to TypeScript. This is NOT a prescriptive guideline for the TypeScript community. These guidelines are meant for contributors to the TypeScript project's codebase. We have chosen many of them for team consistency. Feel free to adopt them for your own team. AGAIN: This is NOT a prescriptive guideline for the TypeScript community Please do not file issues about these guidelines. """
October 15, 2025 at 7:23 AM
dubroy.com
TIL: [JS] Explicit resource management
→ github.com/pdubroy/til/...

Don't miss the getter trick! It's super helpful and not well-documented.
After learning about FinalizationRegistry, I also learned about the using statement: The using declaration declares block-scoped local variables that are synchronously disposed. Like const, variables declared with using must be initialized and cannot be reassigned. The variable's value must be either null, undefined, or an object with a [Symbol.dispose]() method. When the variable goes out of scope, the [Symbol.dispose]() method of the object is called, to ensure that resources are freed. It's useful in scenarios where you might otherwise use a try/finally, e.g.: let normalMap; try { tex = textureLoader.load('muppet.jpg'); tex.doSomething(); // … } finally { tex.dispose(); } With a using statement, and assuming the texture object implemented [Symbol.dispose](), you could write it like this instead: using tex = textureLoader.load('muppet.jpg'); tex.doSomething(); [Symbol.dispose]() will be called when tex goes out of scope. Unlike FinalizationRegistry — but just like a finally block — it's guaranteed to be called, so you can depend on it (in environments that support it). It's currently supported in Chromium-based browsers, Node, and Firefox, but not yet in Safari. It's also been supported in TypeScript since v5.2, which was released in August 2023. Required dispose A non-obvious thing is how to deal with objects that must be disposed. In other words, if a programmer accidentally writes const instead of using, can we catch it? For many scenarios, we can — by writing a getter for [Symbol.dispose](): import assert from 'node:assert/strict'; class MyResource { constructor() { this._using = false; } doSomething() { assert(this._using, 'Did you forget `using`?'); // … } get [Symbol.dispose]() { this._using = true; return () => { // Actual dispose logic goes here. } } } using res1 = new MyResource(); // ok const res2 = new MyResource(); res2.doSomething(); // Throws
October 9, 2025 at 12:22 PM
dubroy.com
Causal Separation Diagrams (CSDs) from "Inductive Diagrams for Causal Reasoning" by Castello et al (2024)

dl.acm.org/doi/pdf/10.1...
The image contains six rectangular tiles arranged in two rows of three, each with a blue border and red dashed outline: **Top row:** - **tick**: Shows a horizontal line with a black dot in the middle **fork**: Shows two lines diverging from a single point on the left, spreading outward to the right **join**: Shows two lines converging from separate points on the left to meet at a single point on the right **Bottom row:** - **noop**: Shows two parallel horizontal lines **swap**: Shows two lines crossing each other in an X pattern **assoc**: Shows curved lines that appear to rearrange or regroup connections At the bottom of the image is a larger diagram showing how these atomic steps can be combined, featuring a rectangular grid with curved and straight lines demonstrating the composition of multiple atomic steps into a complete CSD structure.
October 8, 2025 at 7:01 AM
dubroy.com
I like this —

A case for learning GPU programming with a compute-first mindset: themaister.net/blog/2025/10...
I would argue we should start teaching compute with a debugger/profiler first mindset, building up the understanding of how GPUs execute code, and eventually introduce the fixed-function rasterization pipeline as a specialization once all the fundamentals are already in place. The raster pipeline was simple enough to teach 20 years ago, but those days are long gone, and unless you plan to hack on pre-historic games as a hobby project, it’s an extremely large API surface to learn.
October 7, 2025 at 2:37 PM