Archive for the ‘Uncategorized’ Category

When last we left our hero, he had successfully implemented Rigged Regular Expressions in Rust. There’s been a lot of progress since then. Matt Might’s Parse Result Data Type Is A Semiring! One of my strongest intuitions when I started reading A Play on Regular Expressions was that under the covers Matt Might’s implementation of […]

Okay, in part one I showed you what I’ve learned about writing regular expression engines in Haskell. The example shown uses Haskell chars, so is unicode-compliant. I also mentioned a semiring. Here’s what a Haskell semiring’s class looks like. (A Haskell ‘class’ is more like a Trait in Rust, or an Interface is Java; it […]

I’ve been working my way through A Play on Regular Expressions, a programming pearl by Sebastian Fischer, Frank Huch, and Thomas Wilke on the use of weighted values in regular expressions. The paper has six parts, and I’ve understood everything up through part two, and what I’ve understood already blows my mind. I recently put […]

Last night, I went to a huge “Tech Talk and Happy Hour” put on by one of the major automobile manufacturers. They were recruiting talent for their engineering teams to develop a new infrastructure for self-driving cars. They even had an example on display. It was invitation-only and the recruiter tried extra hard to make […]


I installed LSP and I Liked It

Posted by Elf Sternberg as Uncategorized

I was wrong about Visual Studio Code. Not in the particulars, mind you. I’m still an Emacs user. It’s still my one and only IDE. But there was something about Visual Studio Code that bugged the hell out of me: on-the-fly syntactic analysis. I hated it. I thought it was a lazy developer’s feature, a […]


Barre, progress report: IT LIVES!

Posted by Elf Sternberg as Uncategorized

Barre: Progress Report, second week of December The develop branch of Barre now fully implements all of the features of Adams, Might & Darais’s 2015 implementation, only it does so in Rust. The current price of running seems to be about 15μs (15 microseconds) per operation, although that’s a preliminary finding based on very short […]


A bit of analysis while working on Barre.

Posted by Elf Sternberg as Uncategorized

I’ve been worrying a lot about the next stage of my project and realizing that I had seriously screwed up somewhere along the way. The next task on my list is to convert the recognizer into a parser. I’m going to refer to a couple of different things here. A quick bibliography: Herp, Rerp, and […]


Making Things and Going Slowly

Posted by Elf Sternberg as Uncategorized

For the record, version 1.0 is supposed to support POSIX-style regular expressions with character classes, ranges, and limited backtracking, providing a drop-in API compatible with the Rust regex library without the PCRE context-sensitive expressions such as ‘(x?)’ and ”. I maintain that there’s something wrong with a regular expression library that can’t use itself to […]

Theoretical computer science is fascinating. There are all sorts of papers out there about advanced topics which haven’t quite reached mainstream acceptance or awareness, and once in a while you find a fascinating topic and start chasing down the rabbit hole of implementations and papers trying to wrap your head around the ideas presented. I’ve […]

For the past two weeks, I’ve been working my way through Matt Might’s paper Yacc is Dead, which describes and implementing it in Rust. The result is BARRE: Brzozowski Antimirov Rusty Regular Expressions. So far as I’ve been able to determine, I’m the first person to try implementing it in a systems language, one without […]

Subscribe to Feed



May 2019
« Apr