A number of 70s computing systems had nine-bit bytes, most prominently the PDP-10, but today1 [1 Apparently, it was the System/360 that really set the standard here.] all systems use 8-bit bytes and that now seems natural.2 [2 Though you st…
I had a blast at PLDI'25 this year! The best part, of course, was Marisa's talk about Spineless Traversal, but I wanted to take list the other highlights of the event, both for my own memory and for others who share my research taste. My in…
I just read David's paper on floating-point accumulation networks. It's fantastic work: he's developed a new abstraction of floating-point numbers that allows him to verify error bounds for sequences of TwoSum-like operations, and then used…
I've recently been on a tear writing about Egraphs modulo T, first writing about polynomials specifically and later about the general case. My main insight is that pattern-matching, specifically relational e-matching, is related to quantifi…
One thing Herbie does is simplify stuff, and one that I am personally interested in is simplifying trigonometric expressions. For example, did you know that sin(x) / (1 + cos(x)) and (1 - sin(x)) / cos(x) are the same? Or that both are equa…
In Herbie we use e-graphs to do algebraic rewriting of mathematical expressions. For example, in the Rust standard library's acosh function, e-graphs rewrite log(sqrt(x^2 + 1))… Still, they're bad at some things, and one that really stands
I have long been interested in CSS selector matching algorithms. In short: existing selector matching algorithms are \(O(d^2)\) at worst, where \(d\) is the tree depth, and there are better algorithms that are \(O(d)\). But of course the co…
Alright, I'm back at it: comparing Herbie against LLMs to see who is best at numerical rewriting. If you're new here, Herbie is a research compiler I've been working on for about a decade that helps compile mathematical expressions to fast
This proposal suggests a radically different way Herbie could work, making use of high-quality oracle-free methods of evaluating error. This new method would make Herbie simpler, faster, and possibly better, while (I hope) maintaining all t…
This post is the third in a series of me trying to work out batches, a new data structure I am testing for Herbie and more generally for programming with recursive data structures. In my first post I laid out a type theory for batches, and
A year and a half ago, I wrote a blog post comparing Herbie to the first ChatGPT (which we now call, I think, GPT 3.5). I chose 11 floating-point repair benchmarks, and fed all of them to Herbie and ChatGPT. Herbie is a tool my students and…
Last time, I talked about batches, my term for an arena-allocated, flattened form of an AST, which I think is going to be a key data structure in Herbie. That post covered basics and sketched out a type theory; in this post I want to dive d…