I decided to try running Mezzano on real hardware. I figured my Librebooted ThinkPads would be good targets, since, thanks to Coreboot and the Linux kernel, I have reference source code for all the hardware.

On boot, these machines load Libreboot from SPI flash; included in this Libreboot image is GRUB, as a Coreboot payload.

Mezzano, on the other hand, uses the KBoot bootloader. I considered chainloading KBoot from GRUB, but I wondered if I could have GRUB load the Mezzano image directly, primarily to save a video mode switch.

Read More

Working as a professional software engineer can be tiring: you’re often working on a small part of a larger system, making small changes and fixing bugs. Over time you also learn to rigidly follow best practises: write code that is efficient, document your functions, always check error codes, etc. It’s easy to forget the fun of just programming and the satisfaction of creating something.

I set out to try to reclaim some of that fun by setting myself a challenge: implement a Lisp interpreter in a weekend. How much could I achieve? I wasn’t sure but I figured it should be achievable. The nice thing about Lisp is the lack of syntax, meaning that parsing of the program text isn’t difficult. But there are still lots of other things to take into account. I was also curious as to how small (in terms of lines of code) a Lisp interpreter could be.

Read More

Every time I want to quickly understand something about an advanced type system or programming language concept I get lost when I see something like this on Wikipedia:

Linear type systems are the internal language of closed symmetric monoidal categories, much in the same way that simply typed lambda calculus is the language of Cartesian closed categories. More precisely, one may construct functors between the category of linear type systems and the category of closed symmetric monoidal categories.

Why there’s so much research around types if perfectly applying them to programming languages is impractical? 1 It turns out mathematicians are the ones behind the development of most of the work related to type systems – type theory.2 One might think they do this to support programming languages. After all, it’s part of the job of mathematicians to formalize what other disciplines developed with a more practical mindset. Infinitesimal calculus was greatly advanced by Isaac Newton to solve immediate problems in physics for example. But the development and study of type theory pre-dates programming languages! What problems were mathematicians trying to solve when they developed type theory, a curious programmer might ask.

Read More

The Apple IIgs came out on September 15, 1986. It featured a 2.8 MHz WDC 65816 CPU (the same one that powered the SNES and other similar computers of that era, a 16-bit CPU with 24-bit addressing), 256k or 1MB RAM (upgradable to 8 MB), and an Ensoniq 8-bit stereo synth (which was a welcome upgrade from the bit-speaker of the Apple II family). For reference, the original Apple II family was built around the 6502 CPU (8 bit, 16-bit addressing), and had at most 1 MB of RAM in the IIe and II+. However, it was not until 1988 that Apple had released an operating system for the new computer that was able to meaningfully leverage the newer hardware. GS/OS was written in native 16-bit code, and more importantly, was intended to be used via its new shiny GUI.

This article is about how I built a tiny ‘text editor’ for the IIgs, from start to finish.

Read More

What is it about voxels that makes people go crazy? Throughout the past decade, there have been SO many developers obsessed with shrinking them down to have as many as possible (1, 2, 3, 4, 5), admittedly including myself. It’s exciting both as a developer and to the gaming community to see amazing algorithms produce so much detail and think about the possibilities it brings to virtual worlds.

Voxels = destruction!
Voxels = building!
Voxels = the universe!

And yet, there’s no commercially available, general-purpose, widely-used voxel engines which games are built on. The term “(micro) voxel engine” is basically synonymous with vaporware. We see jaw-dropping showcases that are sometimes accompanied by hyperbolic claims (“UNLIMITED DETAIL”) and then radio silence. But why?

Read More

My original aim was to write a chess program smaller than 1024 characters. I could not do it, so far. Even when I dropped the nitty gritty details of the FIDE rules, like castling and en-passant capture, I could not get the size much below 1200 characters.

So I shifted my aim somewhat, and wrote something less minimalistic in up to 2000 characters of source-code. This gave me enough space to implement a (hash) transposition table, checking of the legality of the input moves, and full FIDE rules. Except for under-promotions, which I considered a dull input problem, since the program is unlikely to ever find itself in a situation where it would be useful to play one.

(For real purists: a close-to-minimal version that does understand full FIDE rules including under-promotion can be found here. It measures 1433 characters. The under-promotions are implemented in a single line that wastes 32 characters. To play one, type 1, 2, or 3 as the 5th character of the input move, for promotion to R, B, or N, respectively. If you type nothing, or 0, promotion is to Q.)

As far as I am aware, this still makes micro-Max the smallest C Chess program in existence. A close competitor for this honor, Toledo, measures 2168 characters. Despite its smaller size, micro-Max seems to beat Toledo easily.

Read More

C++ 17 has introduced the std::optional<T> template class that is analogous to the Maybe/Optional monad implementation in many other languages. “Analogous” is doing a lot of work in this statement because the C++ type checker is not going to help you avoid dereferencing an empty optional like Rust, Haskell, Scala, Kotlin, TypeScript and many other languages will do.

That does not make it useless. As with many things in C++, we will be careful™ when using it and write only programs that do not dereference an empty optional.

In languages that deal mostly with reference types, an optional type can be implemented as an object that wraps a reference and a tag bit that tells if the optional has some data or nothing.1 In C++ on the other hand, the std::optional<T> will inline the value type T onto itself. That means the general behavior of an optional of T depends a lot on the specifics of the type it’s wrapping.

Read More

A few months back (at the start of this blog) I was thinking about interesting things you can find in C++, then I realized one thing: the keyword class doesn’t really have a good reason to exists!

This may seem a bit harsh said that way, but I will explain my statement later in the article.

Anyway, studying the reason for the word class to exist lead me to look into the history of the language. It was very interesting and I really enjoyed it.

So I decided to write a mini-series of articles about the history of C++ aiming to present concepts that may be outdated today, in C++20, and explain why some strange or debatable things were made that way in the past.

Read More

Hello! I was talking to a friend yesterday who was studying for a programming interview and trying to learn some algorithms basics.

The topic of quadratic-time vs linear-time algorithms came up, I thought this would be fun to write about here because avoiding quadratic-time algorithms isn’t just important in interviews – it’s sometimes good to know about in real life too! I’ll explain what a “quadratic-time algorithm is” in a minute :)

here are the 3 things we’ll talk about:

  1. quadratic time functions are WAY WAY WAY slower than linear time functions

  2. sometimes you can make a quadratic algorithm into a linear algorithm by using a hashmap

  3. this is because hashmaps lookups are very fast (instant!)

I’m going to try to keep the math jargon to a minimum and focus on real code examples and how fast/slow they are.

Read More

Engineering alone can’t fix what’s wrong with the internet - a short reflection on the lessons we learn by caring for the software we create.

This article attempts to give a sort of ‘orientation tour’ for people whose previous programming background is in high (ish) level languages such as Java or Python, and who now find that they need or want to learn C.

C is quite different, at a fundamental level, from languages like Java and Python. However, well-known books on C (such as the venerable Kernighan & Ritchie) tend to have been written before Java and Python changed everyone’s expectations of a programming language, so they might well not stop to explain the fundamental differences in outlook before getting into the nitty-gritty language details. Someone with experience of higher-level languages might therefore suffer a certain amount of culture shock when picking up such a book. My aim is to help prevent that, by warning about the culture shocks in advance.

This article will not actually teach C: I’ll show the occasional code snippet for illustration and explain as much as I need to make my points, but I won’t explain the language syntax or semantics in any complete or organised way. Instead, my aim is to give an idea of how you should expect C to differ from languages you previously knew about, so that when you do pick up an actual C book, you won’t be distracted from the details by the fundamental weirdness.

I’m mostly aiming this article at people who are learning C in order to work with existing C programs. So I’ll discuss ways in which things are commonly done, and things you’re likely to encounter in real-world code, but not things that are theoretically possible but rare. (I do have other articles describing some of those.)

Read More

Agilebits recently caused a stir with their announcement that they’ve rewritten 1Password 8 as a cross-platform Electron app, replacing their well-loved native Mac app. The takes came hot and fast. Like many developers, I love and appreciate a well-crafted native UI, and I’ve been somewhat skeptical of the consistent trend towards cross-platform app UIs.

Now, the discourse around cross-platform app technologies has traditionally revolved around a simple idea: cross-platform development is cheaper, while native development leads to better apps.

Read More

I recently read Ruben Schade’s I’m not sure that UNIX won (via) and had a number of reactions to it. One of them is about the portability of programs among Unixes, which is one of the issues that Schade sees as a problem today. Unfortunately, I have bad news for people who are yearning for the (good) old days. The reality is that significant Unix programs have never been really portable between Unix variants, and if anything today is at an all-time high for program portability by default between Unixes.

Back in the days (the late 1980s and early 1990s specifically), one of the things that Larry Wall was justly famous for was his large, intricate, and comprehensive configure scripts that made rn and Perl build on pretty much any Unix and Unix-like system that you could name. Wall’s approach of configure scripts was generalized and broadened by GNU Autoconf, GNU Autotools, and so on. These tools did not automatically make your complex programs portable between different Unixes, but they gave you the tools that you could use to sort out how to achieve that, and to automatically detect various things you needed to do to adopt to the local Unix (and if you used some of them, you automatically got pointed to the right include directories and the right libraries to link with).

Read More

It is not difficult to find some incredibly shitty takes on Electron, and every time it boils down to: It’s slow. Downloads are huge, and it uses a lot of memory. Electron apps are just websites. Developers that are using Electron are taking the lazy or easy approach to cross-platform development. Native apps are just better in every single way. 

And somehow, these arguments often come from Apple fans when they discover one of their apps isn’t “native” or when a macOS favourite is considering moving to Electron. How dare they!

And on the surface, I agree with pretty much everything that people say about Electron. And at the same time, I don’t care at all. And neither should you.

Let’s take a look at some of these arguments:

Read More

VLA is an acronym of variable-length array, which is an array (actual array, not just block of memory which can act like one) that have size (at least one dimension) determined during runtime (instead of at compile time).

Languages supporting VLAs in one form or another include: Ada, Algol 68, APL, C, C#, COBOL, Fortran, J and Object Pascal. As you may notice, beside C and C#, those aren’t languages one would call mainstream nowadays.

VLAs were introduced with the revision C99 of the C standard. At first glance they seem convenient and efficient, but it’s just an illusion. In reality they are just sources of constant issues. Truly a stain on otherwise really good revision.

As you could have guessed by the quote at the beginning, project which used to rely on VLA quite extensively is nothing else than Linux kernel. Maintainers spent a lot of effort to get rid of all VLA and as of version 4.20 (year 2018) it’s completely VLA-free.

Read More
Aug 28

In some domains of programming it’s common to want to write a data structure or algorithm that can work with elements of many different types, such as a generic list or a sorting algorithm that only needs a comparison function. Different programming languages have come up with all sorts of solutions to this problem: From just pointing people to existing general features that can be useful for the purpose (e.g C, Go) to generics systems so powerful they become Turing-complete (e.g. Rust, C++). In this post I’m going to take you on a tour of the generics systems in many different languages and how they are implemented. I’ll start from how languages without a special generics system like C solve the problem and then I’ll show how gradually adding extensions in different directions leads to the systems found in other languages.

One reason I think generics are an interesting case is that they’re a simple case of the general problem of metaprogramming: writing programs that can generate classes of other programs. As evidence I’ll describe how three different fully general metaprogramming methods can be seen as extensions from different directions in the space of generics systems: dynamic languages like Python, procedural macro systems like Template Haskell, and staged compilation like Zig and Terra.

Read More