Note: While this post was authored in June 2023, I got sidetracked by other things, and am only getting around to publishing it and the accompanying code now, in late 2024. Hopefully it’s still relevant.

I’m no fan of rote memorization, but once in a while there are sets of facts that come up that you just need to commit to memory. Flashcards can be very useful when faced with such situations, and particularly when paired with the concept of spaced repetition for making efficient use of your mental muscles. The basic idea is pretty intuitive: you should be spending most of your practice time on the items (specific facts, terms to memorize, etc) you find most challenging to recall. Other items that you’ve mastered still need to be revisited, but can be reviewed less frequently.

Spaced repetition is an application of the broader concept of deliberate practice, a powerful principle for improving at any skill centered on the idea of measuring performance and consciously identifying and targeting weak points for improvement.

If you’re at all familiar with these principles in the context of memorization, you’ve undoubtedly heard of Anki, an open source app applying these techniques to flashcard training. After completing a flashcard, the user rates their degree of mastery over the contents of the card. This rating then influences how soon the user will see the card again.

Anki is great, and I’ve had much success with it in the past! It provides multiple graphical interfaces on different platforms, but in recent years I’ve found myself wishing for a minimal command line interface for both training and card creation. That lead me to look into some of Anki’s internals and the details of the spaced repetition algorithm it uses. It seemed to me that there might be a case for a lighter-weight alternative – or perhaps more importantly, it seemed like a fun excuse to try writing some string-heavy Hare code. ;)

In this this post I’ll outline the very simple, but seemingly effective, card selection algorithm I came up with for cards, my own spaced repetition flashcard application.

Disclaimer: There are people who study these kinds of memorization methods for a living - and I am not one of them! What follows isn’t based on any kind of evidence of its efficacy, and I also have to assume I’m not the first person to implement something along these lines. While I didn’t come across this kind of approach in my research, I also didn’t look very hard at all! If you’re aware of other work in the space of deriving (and especially evaluating) small and elegant deliberate practice / spaced repetition algorithms, please let me know! With that out of the way, this is what I came up with…

Selection algorithm overview

In contrast to algorithms like SuperMemo, which deterministically schedules the best card to present next given the current state of the deck, my crackpot approach is fully probabilistic, with cards being drawn from the deck at random, but with some cards given higher priority (and therefore assigned a higher likelihood of selection) than others.

Like other algorithms, there are two pieces of information about each card that influence its selection probability: how long it’s been since the card was last drawn, and how comfortable the user is with the contents of the card, based on feedback provided by the user after seeing the question and correct response. Both of these measures (hereafter referred to as “age” and “difficulty”) are then converted to indices in the range of zero to one. These two values can then be plugged into a weighting function to determine the probability of selecting any given card, and a random number can be generated to determine which card will ultimately be selected and shown to the user.

Calculating the age index

As far as I can tell there are basically two options for expressing how “recent” a given card is: how many cards have been drawn since the card was last seen, and how much time has elapsed since the card was last seen.

Of course, in a world where cards are viewed constantly and at an even rate, these two metrics would be essentially equivalent. In reality, people take breaks – either short ones, on the order of minutes, during a training session, or long ones, on the order of days or weeks, between training sessions. They may also spend more time on certain cards than others. There are certainly benefits to each choice:

Age based on elapsed draws:

• Based on simple counting logic, so no potential for complications arising from depending on a system clock (which might change between uses and break things)
• Raw metadata (count of draws since last viewed) is easily understood by both humans and machines (vs other timestamping measures like seconds since Unix epoch, ISO 8601, etc)
• Length of time spent on specific cards doesn’t impact results

Age based on elapsed time:

• Able to discriminate cards viewed just-before vs just-after breaks (e.g. when starting a new training session, you’re more concerned about whether you’ve already seen a card this training session, but less worried about whether you saw a card at the beginning or end of your session yesterday
• Age metadata (timestamp at last time viewed) only needs to be updated when the card is viewed, unlike card counts which need to be incremented for every card whenever any card is viewed (barring some more complicated use of a global view counter, etc)

In the end I elected to track age based on elapsed time, but I think either approach could work just fine.

Each time a card is viewed, its metadata is updated to reflect the current timestamp. Then, when calculating the card’s recency index in preparation for drawing subsequent cards, this timestamp is considered relative to the largest and smallest timestamps of cards in the deck as follows:

               timestamp of most recent card - timestamp of current card
Age index = ----------------------------------------------------------------
             timestamp of most recent card - timestamp of least recent card

The result is that the most recently practiced card scores 0.0, while the least recently practiced card scores 1.0. The score of other cards is the result of a linear interpolation in time between those two extremes. My implementation uses the number of seconds since the Unix epoch for timestamps, so cards that haven’t yet been seen can just be assigned a default timestamp of zero (making them look very stale and therefore highly likely to be selected). Finally, in my implementation, if all cards in the deck happen to have identical timestamps (which happens when using a flashcard deck for the first time), the index is arbitrarily set to 0.0 for all cards.

Calculating the difficulty index

To calculate the “difficulty” index we need to introduce a new field of metadata, the “mastery” of a given card. In my initial implementation this was the long-run average of individual mastery values that have been provided for this card each time after seeing it. This running average can be recomputed continuously while storing only two numbers, the total sum of mastery values assigned to the card to date, and the number of times the card has been scored. Dividing the former by the latter yields the long-run average.

This running average has the effect of infinite memory, where every mastery entry, whether provided the first time you saw the card or just now, is weighted equally. Thinking about it more though, it seemed perhaps preferable to gradually discount old ratings in order to better represent the card’s “current” mastery estimate, rather than the long-run historical average. This is easily accomplished by updating the card’s mastery value using a weighted average of the previous mastery value and the just-provided rating. The first time a card’s mastery is rated it can be directly assigned as the new mastery value.

This approach is mathematically-equivalent to assigning an exponentially-decaying weighting to older ratings, with the weighted average coefficient determining how quickly weights for older ratings die off. This approach has the added benefit that updated card mastery values can be calculated based on a single state variable (the previous mastery value) rather than two (the previous mastery sum and number of times the card’s been rated) as required for the uniform weighting method.

Once each card has been assigned a mastery value (or a default value, say zero, is used when the card hasn’t yet been rated), the card’s difficulty index can be computed. The formula for calculating the difficulty index is analogous to calculating the age index:

                    max mastery in deck - mastery of current card
Difficulty index = -----------------------------------------------
                      max mastery in deck - min mastery in deck

Just as with age, this means the card with the highest mastery in the deck (therefore needing the least practice) will have an difficulty index of 0.0, while the card with the lowest mastery (needing the most practice) will have an index of 1.0. If all cards in the deck have identical masteries, the difficulty indices are all arbitrarily set to zero.

Calculating probability weightings

Once difficulty and age indices have been computed for each card, we can convert them into probability weights. Obviously, cards with both difficulty and age indices near 1.0 should be more likely to be chosen, while having both indices near 0.0 should correspond to a low probability. But how should age vs difficulty be weighted? And how much more likely should a high-index card be to be chosen than a low-index card?

After a bit of fiddling to find a weighting function with both nice theoretical properties and satisfying practical performance, the solution I settled on was:

priority = mastery weight * difficulty index + (1-mastery weight) * age index
weight = (skew + 1) ^ priority  - 1

This function involves two parameters:

1. the mastery weight, another weighted averaging coefficient that determines whether age or difficulty should have more impact on selection probability (with a default of 0.5 representing an even emphasis between the two)

2. the skew, a positive parameter than defines how biased selection probabilities should be towards high-priority cards and away from low-priority ones. In my tests I found that a value of 20 felt about right for a default, but this can be adjusted by the user.

This function has some nice theoretical properties:

• Cards with both difficulty and age indices of zero receive a weight of zero, and so will never be selected randomly (unless all cards have a weight of zero)
• Cards with difficulty and age indices of one have a finite upper bound on their weight (equal to skew), rather than going to infinity which causes numerical issues
• Cards with one low index and one high index won’t have their overall index dominated by one or the other (which was the case in earlier version of the function where I was multiplying the two indices together - an index of zero in one dimension could cause a card to not be drawn, regardless of how high the other index might be
• As an exponential function, different low indices receive relatively similar small weights, while weights grow rapidly and differentiate as indices approach 1.0, making high-priority cards appear satisfyingly commonly while still allowing for the possibility of seeing lower-priority cards from time to time.
• A skew approaching zero causes asymptotic convergence to a uniform probability weighting across all cards, disregarding age or difficulty. As skew goes to infinity, the probability density concentrates into the highest-priority cards, converging asymptotically to a deterministic strategy of always drawing the highest-priority card in the deck

Once weights are calculated for each card, they can be converted to probabilities by normalizing on the sum of all weights in the deck. A random number between zero and one can then be generated and used to select a card based on standard inverse cumulative distribution function techniques.

That’s all for now - hopefully you found it helpful, or at least interesting! If you want to dive deeper, feel free to poke around the cards source code.

Source code disclaimer: Hare has evolved a fair bit since I wrote this, and there are likely aspects of the code that are no longer idiomatic (or, let’s be honest, never were). Also, feel free to let me know about all the memory leaks you find… Manual memory management is a skill I lack but would like to cultivate. More generally, constructive feedback is very welcome!

After several years of desktop-only computing for personal use, I recently acquired a new-to-me laptop and figured it was time I finally figured out what the deal was with full-drive encryption on Linux.

The Alpine Linux wiki includes a page stepping through an “LVM on LUKS” install, but my partitioning needs are pretty simple - I usually just use a catch-all root partition with the EFI system partition mounted at /boot/efi. The more general Alpine wiki page on setting up disks manually mentions that you can set up an encrypted LUKS partition and just pass the mapped mountpoint into setup-disk, but that will give you the default Alpine partitioning scheme, with seperate root, boot, and swap partitions.

What follows is the final sequence of steps I took to achieve the simpler partition scheme I wanted (with UEFI and GPT). Most of this is adapted from the aforementioned LVM on LUKS guide, but there were enough differences/simplifications/corrections involved that I figured it was worth writing them down. You may want to consult that page as well for additional information. Know that this is mainly the result of combining fragments from the Alpine and Arch wikis, plus some educated guessing, and lots of trial-and-error - I’m not an expert in any of this. You results may vary…

Basic Setup

To start, manually run the various Alpine setup scripts and rc commands:

# setup-keymap
# setup-hostname
# setup-interfaces
# rc-service networking start
# passwd
# setup-timezone
# rc-update add networking boot
# rc-update add urandom boot
# rc-update add acpid default
# rc-service acpid start

Edit /etc/hosts appropriately:

127.0.0.1   <hostname> <hostname>.localdomain localhost localhost.localdomain
::1     <hostname> <hostname>.localdomain localhost localhost.localdomain

Run some more setup scripts:

# setup-ntp
# setup-apkrepos
# apk update
# setup-sshd

Partitioning, Encryption, and Formatting

At this point you should have a functional internet connection and package database, which will let you install some additional packages to perform the disk partitioning and encryption:

# apk add util-linux cryptsetup e2fsprogs dosfstools parted mkinitfs

util-linux gives you the lsblk command which you can use to figure out the name of the storage device you want to install to. Here we’ll assume it’s /dev/sda, and that your desired partition scheme looks like:

Partition             Filesystem  Note
============================================================
 /dev/sda1             fat32       EFI system partition
 /dev/sda2             LUKS        LUKS container
  ↳ /dev/mapper/crypt  ext4        Encrypted root partition

Nice and simple :) Let’s create the two partitions on /dev/sda, using parted:

# parted -a optimal /dev/sda
(parted) mklabel gpt
(parted) mkpart primary fat32 0% 200M
(parted) name 1 esp
(parted) set 1 esp on
(parted) mkpart primary ext4 200M 100%
(parted) name 2 crypto-luks

Now we can set up encryption on our newly-created /dev/sda2 partition. Note that with LUKS2, cryptsetup defaults to using the argon2id PBKDF, which doesn’t seem to work with GRUB. So we need to manually specify pbkdf2 when formatting the partition:

# cryptsetup --pbkdf pbkdf2 luksFormat /dev/sda2

We can now open, format, and mount our newly-encrypted partition:

# cryptsetup luksOpen /dev/sda2 crypt
# mkfs.ext4 /dev/mapper/crypt
# mount -t ext4 /dev/mapper/crypt /mnt/

We can also format and mount the EFI system partition:

# mkfs.fat -F32 /dev/sda1
# mkdir -p /mnt/boot/efi
# mount -t vfat /dev/sda1 /mnt/boot/efi

lsblk -f is handy for checking your work.

At this point we’re ready to install Alpine Linux to our mounted partitions:

# setup-disk -m sys /mnt/

Congratulations, Alpine Linux is now installed! Of course, that doesn’t mean it will boot yet…

Bootloader, initial RAM disk, and decryption

It’s worth noting that when we boot, our encrypted partition will need to be decrypted twice: once for GRUB to access the kernel and initramfs, and a second time to actually launch the OS. Providing the encryption password twice is a bit of a pain, so instead we can define an alternate decryption keyfile for the partition, which can be stored in the initramfs (only accessible after the initial decryption) and used to decrypt the drive the second time.

Obviously, to do this you need to generate the keyfile before you create the initramfs. (For some reason the Alpine wiki page covers these topics in the opposite order…)

To create the file and use it as a decryption key:

# touch /mnt/crypto_keyfile.bin
# chmod 600 /mnt/crypto_keyfile.bin
# dd bs=512 count=4 if=/dev/urandom of=/mnt/crypto_keyfile.bin
# cryptsetup luksAddKey /dev/sda2 /mnt/crypto_keyfile.bin

Now we need to configure the initramfs to do decryption and use the keyfile. This is done by editing /mnt/etc/mkinitfs/mkinitfs.conf and appending cryptsetup and cryptkey to the features parameter. The Alpine wiki mentions some other modules (kms, etc) you may need to add as well.

With the keyfile in place and the configuration set up to use it, we can regenerate the initial RAM disk:

# mkinitfs -c /mnt/etc/mkinitfs/mkinitfs.conf -b /mnt/ $(ls /mnt/lib/modules/)

If you want, you can inspect the contents of the initramfs file to confirm that it contains the keyfile:

zcat /mnt/boot/initramfs-lts | cpio -t | less

Next we need to configure the bootloader. The wiki provides a neat tip for writing the encrypted partition UUID into a file that you can easily read into vi later:

blkid -s UUID -o value /dev/sda2 > /mnt/root/uuid

At this point we’re almost ready to chroot into our new filesystem, which is always exciting. First, mount a few more devices:

# mount -t proc /proc /mnt/proc
# mount --rbind /dev /mnt/dev
# mount --make-rslave /mnt/dev
# mount --rbind /sys /mnt/sys

Here we go! The wiki also suggests changing the prompt to make the chroot environment more explicit:

# chroot /mnt
# source /etc/profile
# export PS1="(chroot) $PS1"

Now we can install GRUB in our new filesystem, and remove syslinux if it’s there:

(chroot) # apk add grub grub-efi efibootmgr
(chroot) # apk del syslinux

We’re ready to start configuring GRUB. First we edit /etc/default/grub to make sure the following are provided in the GRUB_CMDLINE_LINUX_DEFAULT parameter:

cryptroot=UUID=<UUID> cryptdm=crypt cryptkey

<UUID> is the UUID of the encrypted partition, which you can insert into the file with the :r /root/uuid command in vi if you wrote it to a file as discussed above.

In that same file, add the following additional parameters:

GRUB_PRELOAD_MODULES="luks cryptodisk part_gpt"
GRUB_ENABLE_CRYPTODISK=y

Next, create /root/grub-pre.cfg and populate it with:

set crypto_uuid=<UUID>
cryptomount -u $crypto_uuid
set root='crypto0'
set prefix=($root)/boot/grub
insmod normal
normal

Here, <UUID> is the encrypted partition’s UUID again, but with the hyphens removed this time.

We’re almost done now. At this point it’s worth checking your /boot/efi mount point to see if the Alpine installation put anything there - in my case I had existing GRUB images in EFI/boot and EFI/alpine. You could delete or move these to avoid confusion, since we’re about to re-install GRUB (to EFI/grub) with the new configuration applied.

Speaking of which… Let’s do a vanilla grub-install first, which will create the necessary ancillary files in /boot and configure an EFI boot variable. Then we’ll install our customized GRUB image and config file:

(chroot) # grub-install --target=x86_64-efi --efi-directory=/boot/efi
(chroot) # grub-mkimage -p /boot/grub -O x86_64-efi -c /root/grub-pre.cfg \
                        -o /tmp/grubx64.efi luks2 part_gpt cryptodisk \
                           ext2 gcry_rijndael pbkdf2 gcry_sha256
(chroot) # install -v /tmp/grubx64.efi /boot/efi/EFI/grub/
(chroot) # grub-mkconfig -o /boot/grub/grub.cfg

To finish, exit the chroot and do some final cleanup:

# umount -l /mnt/dev
# umount -l /mnt/proc
# umount -l /mnt/sys
# umount /mnt/boot/efi
# umount /mnt
# cryptsetup luksClose crypt

Now, brave soul, you can reboot and see if it all worked.

If all goes well you should get an early password prompt from GRUB, before it proceeds to its boot menu and, if the second keyfile decryption works, the usual Linux startup process and login prompt.

If it doesn’t work, there’s a good chance the problem is somewhere in the custom initramfs or bootloader configuration. You can repeat the “Basic Setup” steps above to fully initialize the installer, decrypt /dev/sda2 and re-mount everything, and chroot into the filesystem to investigate.

A few things that tripped me up, in case they’re helpful for you:

• The default cryptsetup luksFormat command doesn’t use pbkdf2
• If you can’t get to the GRUB password prompt - you may not have your EFI boot variables for GRUB set correctly (or at all)
• If you get prompted for a password twice, despite the keyfile: the initramfs may not be properly configured, or may not contain the keyfile

While it took me a few tries to get everything working, my hope is that the outline above will make it a bit easier for you - good luck!

I like to think of C and Haskell as my two favorite programing languages that I (almost) never use. While they inhabit opposite ends of the programming language spectrum – C isn’t much more than a minimal convenience layer over assembly code, while Haskell is all about representing logic in terms of abstract mathematical concepts, far removed from the messy realities of computing hardware – they both espouse a certain conceptual minimalism that I quite appreciate.

In spite of that, neither is my go-to language for daily work. C is so minimal that common tasks like string manipulation and error handling become overly complicated and error prone. The language is also a victim of its own success, with decades of ubiquity locking in sometimes-awkward syntax and design decisions. Meanwhile, while Haskell source code is a thing of beauty, it’s also so abstracted from concrete computational actions that performing what should be simple tasks (in terms of processor instructions) and reasoning about code performance is much more complicated than it needs to be.

In practise, I usually find myself settling for a language that strikes a more pragamatic balance between these two extremes. Julia, Rust, Go, and Zig are all interesting modern alternatives making different design tradeoffs, but they all also tend to be just a little more complicated than I think I need for the small, ‘aggressively simple’ kinds projects I like to work on for fun. I’ve taken to working in POSIX(ish) shell for many of these kinds of projects, but let’s not kid ourselves, as a ‘proper’ programming language a shell (of any variety) kind of sucks.

For all these reasons, when Drew DeVault started hinting that he was working on a “C-but-cleaner-simpler-and-more-elegant” programming language, first on his now-defunct Mastadon and later on his blog, I was very much interested. Drew pursues software simplicity even more aggressively than I do, while also building and maintaining a truly prolific and diverse portfolio of open source software projects.

A few years of not-always-so-private development later, and the language (called Hare) was released publicly last month.

I’m neither a Hare expert nor a programming language expert, but am quite intrigued with the language and plan to try it instead of C for a small few projects I’ve had on the backburner for a while, and will post about those experiences here.

If you’re interested, you can find out more about Hare on the official website. There’s a formal specification that provides the gory details of the language definition, as well as a more conversational introductory tutorial (mostly, although not entirely, complete as of the time of writing), which I’ve enjoyed working through.

TL;DR: I made a thing for blogging!

Self-aggrandizing history lesson

A few years ago I found myself wanting to quickly stitch a collection of folders of Emacs Org-Mode files into a web site. I had used mkdocs for that in the past (albeit with Markdown, not Org-Mode), which had worked reasonably well, other than the fact that you needed to install Python and a bunch of dependencies. I was running Arch Linux (by the way) and the supposedly simple task of installing mkdocs started breaking things. On top of that, I had also been using Jekyll for some other sites and so had bunch of Ruby gems cluttering up my package manager as well.

This all seemed overly complicated. Do you really need multiple levels of package management infrastructure and fancy languages to glue together some text files? I already knew I wanted to use Pandoc for converting Org-Mode to HTML, could the rest of the work not be done in a shell script?

As it turns out, yes, it could, and pdsite was born. In retrospect, pdsite was a bit of a mess, spewing a bunch of little temporary files across your folder structure to address the fact that shell scripts don’t really have a good way of dealing with hierarchical data structures (or any data structures, for that matter). Much of the text processing relied on sed and awk one-liners that were anything but readable. There were also some GNU-isms that caused issues for POSIX compliance.

Fast-forward five years, and I found myself wanting to set up a simple blog. Could I use pdsite? Sure. Should I? Probably not? I wanted something simpler (no multi-level folder structures) but also a little different (a chronological index on the home page). But hey, pdsite was only 200 lines of shell, a blogging analog (pdblog, if you will) should be easier, right?

pdblog: working hard at doing less

Turns out, simple blogs are simple. I give you, pdblog.sh! The script weighs in at just over 100 lines, nearly half of which is setting config variables or passing those variables into pandoc. There’s really not much going on: it’s signficantly simpler and easier to understand than pdsite. Hooray!

You can read the code yourself, but the basic premise is:

• iterate through a flat collection of text files in a specific folder: each file name provides the publication date (for ordering) and post title
• convert each file to an HTML page via Pandoc
• along the way, append HTML with the post titles and dates to the index page

Do you really need anything more in a blog? I don’t - that’s why I’m using it to generate this very site. I made another website (also using pdblog, of course) which gets into more details on usage and theming, if you’re interested in trying it out for yourself.

Syntax highlighting

In addition to converting between pretty much every document format you can think of and providing a full document templating engine, pandoc will highlight code syntax for you as well, using KDE’s text editor parsing and coloring standards. Pandoc’s default color scheme is the pygments default, which is… not my favorite. I’m a big fan of the Base16 system, as well as its default color palette, which surprisingly didn’t seem to be available as a KDE theme. So I figured I could manually set up the subset of a full-blown KDE color theme that pandoc uses:

The KDE elements also include BuiltIn (which I left unthemed), Error and Alert (which I set to red), Warning, and Information (which I set to yellow and cyan, respectively).

Here’s the result, using some Julia code as an example:

# This is myfun written in Julia
function myfun(w::Bool, x::Int, y::Float64, z::String)
    println("Hello world!")
    println(z, "\t", 35 + 12.2, "\t", w * (x + y))
    return w ? x + y : x - y
end

Pretty snazzy, right? The theme file is available as part of the pdblog default theme.

Future work (or lack thereof)

pdblog is intentionally very simple, and I don’t intend to change that by adding too many new features. I’ll probably add an RSS feed (handled in the same way as the index page), but beyond that I suspect most of my future enhancements will be to my site’s theme as opposed to the core pdblog script. I’m quite pleased with the tool as-is, and hope others find it useful as well.

I don’t have a great track record with blogs. First, there was the 2007 Blogger site, promoting my high school web design company. Those bits long ago succumbed to the march of entropy, scattered like dust on the winds of the web.

Then in 2009, there was the Wordpress blog. I wrote about video production projects and technology. The Wayback Machine still remembers, though I doubt anyone else would. I barely do - that archive also reports that I redesigned it on a new domain in 2011, and redesigned it again in 2012 - I’d forgotten both! The wonders of digital archeology…

My final post there, just as I finished undergrad in 2013, said a lot in a few short sentences. Like many new grads, I had big ambitions and no idea about what to do with them. A few months later, no doubt looking for a fresh foundation upon which to build all my dreams, I took down the site altogether, leaving only a Walden quote in its place.

In 2015 (by this point we have git, the great chonicler of text, to tell the tale), I repurposed the blog’s domain as a mini-CV. Now the second blog was truly gone, too.

I don’t know what the fate of this blog will be. I suspect it won’t be lost to the abyss, the way the first one was. Freed from the tyranny of dynamic code execution, it also seems more likely than the second to live on in its true form, persisting in whole beyond the Internet Archive’s fragmented memories. But it remains to be seen whether that life will be one of rich new experiences or lonely neglect.

Time will tell. The story begins…