Lightnews — Scholar-powered news

Patrick Dubroy

@dubroy.com

1.5K followers 270 following 590 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

Pinned

Patrick Dubroy @dubroy.com · Mar 10

Here it is — very happy to officially release the book that @marianoguerra.org and I have been working on for the past 2½ years.

If you bought it in early access, thanks for your support! 🙏

If you haven't bought it yet, please check it out!!

WebAssembly from the Ground Up @wasmgroundup.com · Mar 10

Excited to announce the official launch of our online book, WebAssembly from the Ground Up! 🎉

It's the book we wish we'd had 3 years ago.

No messing with tools and frameworks. It's a hands-on guide to the core of Wasm: the instruction set and module format.

Link below. 👇

Learn Wasm by building a simple compiler in JavaScript. No compiler expertise necessary. All the code is in the book; we'll take you through it step by step. Get your hands dirty and see for yourself what WebAssembly is all about.

Patrick Dubroy

@dubroy.com

TIL: V8 Natives syntax
→ github.com/pdubroy/til/...

V8 has a number of built-in, runtime support functions that are written in C++. For debugging purposes, if you run with the --allow-natives-syntax flag, it's possible to call these functions directly from JavaScript with a % prefix. For example:

function getTypeTagged(node) {
return node.type;
}

console.log('=== Optimization Status (after warmup) ===');
const taggedStatus = %GetOptimizationStatus(getTypeTagged);
console.log(`getTypeTagged status: ${taggedStatus}`);
The full list of functions is in src/runtime/runtime.h in the V8 source. Here are a few that I found useful/interesting:

%GetOptimizationStatus
%HaveSameMap
%HasFastProperties

December 24, 2025 at 1:20 AM

Reposted by Patrick Dubroy

dietrich

@burrito.space

fun romp through the Chromium graphics stack from an @electronjs.org dev

www.electronjs.org/blog/tech-ta...

Tech Talk: Improving Window Resize Behavior | Electron

We're launching a new blog post series where we share glimpses into our work on Electron. If you find this work interesting, please consider contributing!

www.electronjs.org

December 21, 2025 at 10:55 AM

Reposted by Patrick Dubroy

WebAssembly from the Ground Up

@wasmgroundup.com

We just sent out our last newsletter of the year, chock full of Wasm tidbits and captivating compiler content.

Not signed up? You're missing out!

Get on the list at sendfox.com/wasmgroundup

Wasm tidbits

• All the videos from the WebAssembly Workshop at ICFP/SPLASH '25 are up on YouTube. There are a bunch of interesting ones, but we particularly enjoyed Oscar Spencer's Wasm GC and the Future of High-Level Language Compilation.
• The Feature Status page on webassembly.org has been updated to include a bunch of new engines and tools, including Wizard, wazero, and Binaryen.
• It's not directly related to WebAssembly, but we've been following Matt Godbolt's Advent of Compiler Optimizations, and it's been great so far. It's a nice way to learn a bit more about x86 and ARM assembly, and about the various optimizations that C++ compilers do. You can follow it on his blog or on YouTube.
• Andy Wingo: "If anyone has never worked on a baseline compiler before, they are a really funny space; my first experience with Firefox's Wasm baseline compiler was an eye-opener for me." Firefox's low-latency WebAssembly compiler (2020).
• For a deeper look at strategies for baseline compilation, see Ben Titzer's Whose baseline compiler is it anyway?. "We demystify single-pass compilers for Wasm, explaining their internal algorithms and tradeoffs, as well as providing a detailed empirical study of those employed in production."
• We recently met some folks from CedarDB (the commercial version of the Umbra database system), who told us about how they use Wasm for user-defined operators. The details can be found in Moritz Sichert's PhD dissertation, Efficient and Safe Integration of User-Defined Operators into Modern Database Systems.

December 18, 2025 at 3:06 PM

Reposted by Patrick Dubroy

OhmJS

@ohmjs.org

Just added an example to the Ohm repo of implementing something like Zed's SumTree.

(aka "monoid-cached trees" if you want to sound clever)

Full example here: github.com/ohmjs/ohm/bl...

$Screenshot of the following code: // In abstract algebra, a _monoid_ is a set (or a data type) that has // (a) a "combine" operation that's associative, i.e. (a + b) + c = a + (b + c) // (b) an identity or neutral element. // This is our identity element… const LOC_IDENTITY = {line: 0, col: 0}; // …and this is our "combine" operator. function sumLocations(a, b) { return { line: a.line + b.line, // If `b` has more than one line, we can ignore `a.col`. col: b.line > 0 ? b.col : a.col + b.col, }; } function compareLocations(a, b) { return a.line - b.line || a.col - b.col; } const semantics = g.createSemantics(); // A helper operation to get the "size" of a node, such that // endLoc = sumLocations(startLoc, size). semantics.addAttribute('_size', { _default(...children) { return children.reduce((acc, node) => sumLocations(acc, node._size), LOC_IDENTITY); }, _terminal() { const lines = this.sourceString.split('\n'); return { line: lines.length - 1, col: lines.at(-1)?.length || 0, }; }, });$

December 10, 2025 at 3:59 PM

Reposted by Patrick Dubroy

WebAssembly from the Ground Up

@wasmgroundup.com

A very readable doc about V8's new bytecode verifier.

Readers of our book may notice the similarity to the Wasm security model — see this excerpt from the chapter "What makes WebAssembly safe?"

Excerpt from the V8 Sandbox - Bytecode Verification doc, reading:

"The bytecode verifier needs to ensure that the execution of verified bytecode does not lead to out-of-sandbox corruption, specifically stack corruption. As the bytecode is fairly simple, this reduces down to a few basic properties that must be verified:
Spatial memory safety: stores (and potentially loads) to/from the stack stay inside the stack frame and so do not corrupt stack memory
Control-flow Integrity (CFI): jumps within the bytecode land at a valid instruction (otherwise, we might execute arbitrary instruction and so the first property could not be guaranteed)
No unsafe functions: the bytecode should not call unsafe runtime or native functions

These properties are verifiable in linear time (constant per bytecode) with a relatively simple validator."

An excerpt from WebAssembly from the Ground Up, showing a section entitled "Sandboxed execution". The excerpt reads:

"WebAssembly sandboxed execution is based on a technique known as Software-based Fault Isolation (SFI). It’s a remarkably simple idea. Here’s how it works —

The “sandbox” consists of two regions of memory: a code region and a data region. Then, the host must enforce two policies:

- A data-access policy ensures that any memory access in the untrusted module can only target its designated data region.
- A control-flow policy ensures that the untrusted module can’t transfer control outside its own code region — except by calling explicitly-allowed functions."

December 9, 2025 at 11:13 AM

Reposted by Patrick Dubroy

Tomas Petricek

@tomasp.net

What defines a correct program? What education makes a good programmer? The answer depends on what culture of programming you subscribe to!

This has been a long time in the making, but my open access book on the history of programming is available for pre-order!

www.cambridge.org/core/books/c...

December 9, 2025 at 9:52 AM

Patrick Dubroy

@dubroy.com

TIL: Monoid
→ github.com/pdubroy/til/...

Per [Wikipedia](https://en.wikipedia.org/wiki/Monoid):

> In abstract algebra, a _monoid_ is a set equipped with an associative binary operation and an identity element. For example, the natural numbers with addition form a monoid, the identity element being 0.

I'm sure I've come across the term before, but never in a context where it was very relevant to me — until this week!

The article [Zed Decoded: Rope & SumTree](https://zed.dev/blog/zed-decoded-rope-sumtree) covers a bunch of real-world problems in text editing that involve monoids. It's also relevant to parsing: for Ohm's [incremental parsing][sle17], we use a very similar approach in the internal syntax tree. It lets us have position-independent memo table entries, while being able to cheaply compute the absolute offset of a node on-demand.

The generalized version Zed's SumTree is also referred to as a _monoid-cached tree_.

See also:

- [Four Solutions to a Trivial Problem](https://www.youtube.com/watch?v=ftcIcn8AmSY), a talk by Guy Steele that discusses monoid-cached trees.
- Blelloch's [Prefix sums and their applications](https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf) (1990)

[sle17]: https://ohmjs.org/pubs/sle2017/incremental-packrat-parsing.pdf

December 7, 2025 at 3:21 PM

Patrick Dubroy

@dubroy.com

This document radicalized me.

The first page of Guy E. Blelloch's "Prefix Sums and Their Applications" (1990).

Abstract:

"Experienced algorithm designers rely heavily on a set of building blocks and on the tools needed to put the blocks together into an algorithm. The understanding of these basic blocks and tools is therefore critical to the understanding of algorithms. Many of the blocks and tools needed for parallel algorithms extend from sequential algorithms, such as dynamic-programming and divide-and-conquer, but others are new. This paper introduces one of the simplest and most useful building blocks for parallel algorithms: the all-prefix-sums operation. The paper defines the operation, shows how to implement it on a P-RAM and illustrates many applications of the operation. In addition to being a useful building block, the all-prefix-sums operation is a good example of a computation that seems inherently sequential, but for which there is an efficient parallel algorithm."

December 5, 2025 at 2:21 PM

Patrick Dubroy

@dubroy.com

No tumblr lives rent-free in my head the way accidentallyquadratic.tumblr.com does.

Accidentally Quadratic

accidentallyquadratic.tumblr.com

December 5, 2025 at 10:30 AM

Patrick Dubroy

@dubroy.com

Periodic reminder — bunny.net is great!

I pay them…*checks notes* $1/month for a better version of everything I used Cloudflare for.

Patrick Dubroy @dubroy.com · Mar 8

For…reasons, I've been investigating non-US alternatives for some of the services I use.

TIL that @BunnyCDN offers a drop-in replacement for Google Fonts: fonts.bunny.net/

Also Bunny itself is a great EU-based alternative to most of what Cloudflare offers.

December 5, 2025 at 10:27 AM

Patrick Dubroy

@dubroy.com

TIL: Printing V8 bytecode
→ github.com/pdubroy/til/...

$Sometimes I want a lower-level picture of how my JavaScript code will be executed by the JS engine. In V8, one way to do that is to look at the bytecode for the Ignition interpeter. In Node.js and d8 (the V8 developer shell), you can do that with --print-bytecode. But, that will dump bytecode for everything, including V8 and Node internals. You can use --print-bytecode-filter to limit it to certain functions. E.g., if you have the following source code: const add = (a, b) => a + b; function onePlusTwo() { return add(1, 2); } console.log(onePlusTwo()); Then, node --print-bytecode --print-bytecode-filter=onePlusTwo myScript.js will show: [generated bytecode for function: onePlusTwo (0x3670aa458b39 <SharedFunctionInfo onePlusTwo>)] Bytecode length: 17 Parameter count 1 Register count 3 Frame size 24 56 S> 0x3309ab60a9d8 @ 0 : 19 03 LdaImmutableCurrentContextSlot [3] 0x3309ab60a9da @ 2 : b4 00 ThrowReferenceErrorIfHole [0] 0x3309ab60a9dc @ 4 : ce Star0 0x3309ab60a9dd @ 5 : 0d 01 LdaSmi [1] 0x3309ab60a9df @ 7 : cd Star1 0x3309ab60a9e0 @ 8 : 0d 02 LdaSmi [2] 0x3309ab60a9e2 @ 10 : cc Star2 63 E> 0x3309ab60a9e3 @ 11 : 6a f9 f8 f7 00 CallUndefinedReceiver2 r0, r1, r2, [0] 73 S> 0x3309ab60a9e8 @ 16 : b3 Return Constant pool (size = 1) 0x3309ab60a981: [TrustedFixedArray] - map: 0x0241845c09e1 <Map(TRUSTED_FIXED_ARRAY_TYPE)> - length: 1 0: 0x0241845c63b9 <String[3]: #add> Handler Table (size = 0) Source Position Table (size = 9) 0x3309ab60a9f1 <Other heap object (TRUSTED_BYTE_ARRAY_TYPE)> See Kuter Dinel's V8 bytecode reference for help in understanding the meaning of the instructions themselves.$

December 3, 2025 at 7:35 PM

Reposted by Patrick Dubroy

Sam Rose

@samwho.dev

A lot of folks know me for one or two posts, and might not know I've created nine (9!) visual explanations of computer science topics, aimed at practitioners.

If you're looking for things to read this Thanksgiving, I think you'll love them.

Computer science is a lot of fun, when explained well. ❤️

November 28, 2025 at 4:34 PM

Patrick Dubroy

@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

Patrick Dubroy

@dubroy.com

I'm working on something that benefited from a sprinkle of PBT, and this was *very* useful —

Choosing properties for property-based testing
→ fsharpforfunandprofit.com/posts/proper...

Choosing properties for property-based testing

Or, I want to use PBT, but I can never think of any properties to use

fsharpforfunandprofit.com

November 26, 2025 at 1:33 PM

Patrick Dubroy

@dubroy.com

Definitely one of the cooler language playgrounds I've seen: pinky.cool.omg.lol

November 21, 2025 at 3:46 PM

Patrick Dubroy

@dubroy.com

Excited to finally release the blog post that @marianoguerra.org has been working on for a while!

WebAssembly from the Ground Up @wasmgroundup.com · Nov 20

Per your request, please find enclosed…a new blog post!

A WebAssembly interpreter (Part 1)
→ wasmgroundup.com/blog/wasm-vm...

We build up a simple interpreter from scratch, in JavaScript, for a small subset of Wasm instructions (arithmetic and comparison).

A WebAssembly interpreter (Part 1)

Implementing a Wasm Interpreter to explore its design and semantics

wasmgroundup.com

November 20, 2025 at 2:02 PM

Patrick Dubroy

@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

Patrick Dubroy

@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

Patrick Dubroy

@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

Patrick Dubroy

@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

Patrick Dubroy

@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

Patrick Dubroy

@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

Reposted by Patrick Dubroy

Chrome for Developers

@developer.chrome.com

Ever thought about writing #WebAssembly by hand? 🤔

Authors Patrick @dubroy.com and @marianoguerra.org think it's crucial for learning. They join #WasmAssembly host Thomas Steiner to discuss their ebook, "WebAssembly from the Ground Up" → goo.gle/3Ln67Pp

WebAssembly from the Ground Up with Patrick Dubroy and Mariano Guerra

November 4, 2025 at 9:00 PM

Patrick Dubroy

@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...