はてなブックマーク

Primitive Recursive Functions For A Working Programmer Aug 1, 2024 Programmers on the internet often use “Turing-completeness” terminology. Typically, not being Turing-complete is extolled as a virtue or even a requirement in specific domains. I claim that most such discussions are misinformed — that not being Turing complete doesn’t actually mean what folks want it to mean, and is instead a stand

Properly Testing Concurrent Data Structures Jul 5, 2024 There’s a fascinating Rust library, loom, which can be used to thoroughly test lock-free data structures. I always wanted to learn how it works. I still do! But recently I accidentally implemented a small toy which, I think, contains some of the loom’s ideas, and it seems worthwhile to write about that. The goal here isn’t to teach you what y

Regular, Recursive, Restricted Jun 4, 2024 A post/question about formal grammars, wherein I search for a good formalism for describing infix expressions. Problem statement: it’s hard to describe arithmetic expressions in a way that: declaratively captures the overall shape of expression, and has a clear precedence semantics Let’s start with the following grammar for arithmetic expressions: Expr =

Zig defer Patterns Mar 21, 2024 A short note about some unexpected usages of Zig’s defer statement. This post assumes that you already know the basics about RAII, defer and errdefer. While discussing the differences between them is not the point, I will allow myself one high level comment. I don’t like defer as a replacement for RAII: after writing Zig for some time, I am relatively confident that

LSP could have been better Oct 12, 2023 We talk about programming like it is about writing code, but the code ends up being less important than the architecture, and the architecture ends up being less important than social issues. The Success and Failure of Ninja The Why LSP post discusses the “social issues” solved by LSP. LSP (as a part of overarching Microsoft strategy) is brilliant, because i

TypeScript is Surprisingly OK for Compilers Aug 17, 2023 There are two main historical trends when choosing an implementation language for something compiler-shaped. For more language-centric tasks, like a formal specification, or a toy hobby language, OCaml makes most sense. See, for example, plzoo or WebAssembly reference interpreter. For something implementation-centric and production ready, C+

Fantastic Learning Resources Aug 6, 2023 People sometimes ask me: “Alex, how do I learn X?”. This article is a compilation of advice I usually give. This is “things that worked for me” rather than “the most awesome things on earth”. I do consider every item on the list to be fantastic though, and I am forever grateful to people putting these resources together. Learning to Code I don’t think I hav

Zig And Rust Mar 26, 2023 This post will be a bit all over the place. Several months ago, I wrote Hard Mode Rust, exploring an allocation-conscious style of programming. In the ensuing discussion, @jamii name-dropped TigerBeetle, a reliable, distributed, fast, and small database written in Zig in a similar style, and, well, I now find myself writing Zig full-time, after more than seven years of Ru

<3 Deno Feb 12, 2023 Deno is a relatively new JavaScript runtime. I find quite interesting and aesthetically appealing, in-line with the recent trend to rein in the worse-is-better law of software evolution. This post explains why. The way I see it, the primary goal of Deno is to simplify development of software, relative to the status quo. Simplifying means removing the accidental complexity. To

Next Rust Compiler Jan 25, 2023 In Rust in 2023, @nrc floated an idea of a Rust compiler rewrite. As my hobby is writing Rust compiler frontends (1, 2), I have some (but not very many) thoughts here! The post consists of two parts, covering organizational and technical aspects. Organization Writing a production-grade compiler is not a small endeavor. The questions of who writes the code, who pays

Rust’s Ugly Syntax Jan 26, 2023 People complain about Rust syntax. I think that most of the time when people think they have an issue with Rust’s syntax, they actually object to Rust’s semantics. In this slightly whimsical post, I’ll try to disentangle the two. Let’s start with an example of an ugly Rust syntax: pub fn read<P: AsRef<Path>>(path: P) -> io::Result<Vec<u8>> { fn inner(path: &Path) ->

Hard Mode Rust Oct 6, 2022 This post is a case study of writing a Rust application using only minimal, artificially constrained API (eg, no dynamic memory allocation). It assumes a fair bit of familiarity with the language. The back story here is a particular criticism of Rust and C++ from hard-core C programmers. This criticism is aimed at RAII — the language-defining feature of C++, which was wh

Caches In Rust Jun 11, 2022 In this post I’ll describe how to implement caches in Rust. It is inspired by two recent refactors I landed at nearcore (nearcore#6549, nearcore#6811). Based on that experience, it seems that implementing caches wrong is rather easy, and making a mistake there risks “spilling over”, and spoiling the overall architecture of the application a bit. Let’s start with an imag

Why LSP? Apr 25, 2022 LSP (language server protocol) is fairly popular today. There’s a standard explanation of why that is the case. You probably have seen this picture before: I believe that this standard explanation of LSP popularity is wrong. In this post, I suggest an alternative picture. Standard Explanation The explanation goes like this: There are M editors and N languages. If you want to

Self Modifying Code Mar 26, 2022 This post has nothing to do with JIT-like techniques for patching machine code on the fly (though they are cool!). Instead, it describes a cute/horrible trick/hack you can use to generate source code if you are not a huge fan of macros. The final technique is going to be independent of any particular programming language, but the lead-up is going to be Rust-specifi

Fast Rust Builds Sep 4, 2021 It’s common knowledge that Rust code is slow to compile. But I have a strong gut feeling that most Rust code out there compiles much slower than it could. As an example, one fairly recent post says: With Rust, on the other hand, it takes between 15 and 45 minutes to run a CI pipeline, depending on your project and the power of your CI servers. This doesn’t make sense t

Large Rust Workspaces Aug 22, 2021 In this article, I’ll share my experience with organizing large Rust projects. This is in no way authoritative — just some tips I’ve discovered through trial and error. Cargo, Rust’s build system, follows convention over configuration principle. It provides a set of good defaults for small projects, and it is especially well-tailored for public crates.io librarie

Inline In Rust Jul 9, 2021 There’s a lot of tribal knowledge surrounding #[inline] attribute in Rust. I often find myself teaching how it works, so I finally decided to write this down. Caveat Emptor: this is what I know, not necessarily what is true. Additionally, exact semantics of #[inline] is not set in stone and may change in future Rust versions. Why Inlining Matters? Inlining is an optimizi

How to Test May 31, 2021 Alternative titles: Unit Tests are a Scam Test Features, Not Code Data Driven Integrated Tests This post describes my current approach to testing. When I started programming professionally, I knew how to write good code, but good tests remained a mystery for a long time. This is not due to the lack of advice — on the contrary, there’s abundance of information & terminology

Goroutines Are Not Significantly Smaller Than Threads Mar 12, 2021 The most commonly cited drawback of OS-level threads is that they use a lot of RAM. This is not true on Linux. Let’s compare memory footprint of 10_000 Linux threads with 10_000 goroutines. We spawn 10k workers, which sleep for about 10 seconds, waking up every 10 milliseconds. Each worker is staggered by a pseudorandom delay up to

For the Love of Macros Feb 14, 2021 I’ve been re-reading Ted Kaminski blog about software design. I highly recommend all the posts, especially the earlier ones (here’s the first). He manages to offer design advice which is both non-trivial and sound (a subjective judgment of course), a rare specimen! Anyway, one of the insights of the series is that, when designing an abstraction, we always face t

ARCHITECTURE.md Feb 6, 2021 If you maintain an open-source project in the range of 10k-200k lines of code, I strongly encourage you to add an ARCHITECTURE document next to README and CONTRIBUTING. Before going into the details of why and how, I want to emphasize that this is not another “docs are good, write more docs” advice. I am pretty sloppy about documentation, and, e.g., I often use just “si

Study of std::io::Error Oct 15, 2020 In this article we’ll dissect the implementation of std::io::Error type from the Rust’s standard library. The code in question is here: library/std/src/io/error.rs. You can read this post as either of: A study of a specific bit of standard library. An advanced error management guide. A case of a beautiful API design. The article requires basic familiarity with

Fast Thread Locals In Rust Oct 3, 2020 Rust thread-locals are slower than they could be. This is because they violate zero-cost abstraction principle, specifically the “you don’t pay for what you don’t use” part. Rust’s thread-local implementation( 1, 2 ) comes with built-in support for laziness — thread locals are initialized on the first access. Sometimes this overhead is a big deal, as thread l

Why Not Rust? Sep 20, 2020 I’ve recently read an article criticizing Rust, and, while it made a bunch of good points, I didn’t enjoy it — it was an easy to argue with piece. In general, I feel that I can’t recommend an article criticizing Rust. This is a shame — confronting drawbacks is important, and debunking low effort/miss informed attempts at critique sadly inoculates against actually good ar

Simple but Powerful Pratt Parsing Apr 13, 2020 Welcome to my article about Pratt parsing — the monad tutorial of syntactic analysis. The number of Pratt parsing articles is so large that there exists a survey post :) The goals of this particular article are: Raising an issue that the so-called left-recursion problem is overstated. Complaining about inadequacy of BNF for representing infix expressi

Mutexes Are Faster Than Spinlocks Jan 4, 2020 (at least on commodity desktop Linux with stock settings) This is a followup to the previous post about spinlocks. The gist of the previous post was that spinlocks have some pretty bad worst-case behaviors, and, for that reason, one shouldn’t blindly use a spinlock if using a sleeping mutex or avoiding blocking altogether is cumbersome. In the comments