How to Make Racket Go (Almost) As Fast As C

15 Oct 2024

I recently wrote about using first-class functions to help make a BF interpreter. This is a follow-up post to describe a nifty solution to a tricky problem that made my program go 2–5× faster and put it about on-par with an interpreter written in pure C.

A basic interpreter works by walking down the AST and evaluating nodes recursively: when the interpreter encounters an expression, it dispatches on the type of expression to decide how to perform the evaluation. Here’s the key insight to get a massive speed bump with very little effort: that dispatch is expensive and can be performed ahead-of-time. We can walk through the code once and precompute all the dispatching work.

First-Class Helper Functions

11 Sep 2024

We’re going to be writing a BF compiler for a class I’m in. Last night I threw together a little interpreter for the program in about an hour; it doesn’t do input—that should be easy to add—but it’s enough to handle some benchmarks for the language, albeit slowly. You can see my repository on Codeberg for the source code.

I needed one function to do two closely related jobs—the logic was identical, but some parameters needed to change. Fortunately, first-class functions in your language make it trivial to parameterize your programs in elegant ways.

Boilerplate Busting in Functional Languages

6 May 2024

This is the story of how I solved a problem (ugly, cumbersome boilerplate code) that I ran into while writing a program in a functional language (Elixir). Functional programming languages often pride themselves on expressiveness and elegance; but occasionally they are not amenable to the most obvious solutions to the problems we wish to solve. In this case, the simplest solution to my problem would have been to have a global mutable variable. But no one likes those.

Warp Factor Refactoring in Emacs

1 Jun 2023

Here’s a nifty Emacs workflow for doing a project-wide search-and-replace on steroids. While I do use refactor tools that come with language servers,¹ sometimes those aren’t enough. Consider the case where you not only need to change the name of a function, but also e.g. need to swap the order of two of its arguments. Or you’ve broken one function out into two that need to be chained together. Whatever—there are plenty of ways where the IDE won’t be able to do everything that you need. Enter: Emacs.

Praise for the pragmatic third camp

16 Mar 2023

Some years ago I came across a blog post that described programmers as being in one of three camps. It's a fun, short post, so I encourage you to go read that real quick, but the gist of it is that programmers generally fall into one of three categories according to what they primarily value:

1. Applied mathematicians, who appreciate elegant solutions to problems. Program execution on von Neumann machines is incidental. These programmers like high-level languages and mathematically correct reasoning about programs.
2. Bit hackers, who like making the machine run as efficiently as possible. Without a von Neumann machine, programs are pointless. These programmers like low-level languages that let them get into the guts of things.
3. Product makers, who care about the ideals of the first and second camps in as much as they help them accomplish the task of delivering more features. Most industry programmers probably fall into this category. They like high-level languages as long as performance doesn't suffer too much and that it's pragmatic. (E.g. JavaScript, Ruby, Python, Go, etc.)

The author of the post talks a little bit about the tension between the camps. I won't reproduce it here, but it can be amusing, so you should give it a read.

Continuations—what are they?

17 Nov 2022

I had a friend ask me what continuations are, and why they're useful. There's a ton of literature about continuations; this is just a simple example meant to showcase something small and hopefully grokkable.

You will need to understand a little bit of Racket, but if you know any Scheme, that should be good enough. If you just want a quick primer, check out Learn X in Y minutes for Racket.

#lang racket

;;; Export these symbols
(provide fail pick non-deterministic-factor)

;;; Global stack of choices (only visible to this module)
(define *choices* '())

;;; Pop a value off of the alternate choices stack
(define (fail)
  (if (null? *choices*)
      #f
      (let ([next-choice (car *choices*)])
        (set! *choices* (cdr *choices*))
        (next-choice))))

This next function pick is where we capture the continuation. I've named it return-from-pick to illustrate that when you call this function, it will jump back to the point in the code where pick returns. However, this works even if you use the continuation after the thing the called pick itself has returned.

Unix as a tool forge

7 Nov 2022

Wikipedia¹ cites a few different sources on what "Unix Philosophy" is. Peter Salus summarizes it as:

• Write programs that do one thing and do it well.
• Write programs to work together.
• Write programs to handle text streams, because that is a universal interface.

That second bullet point is my favorite: making composable programs rather than monolithic systems. In this way, Unix is designed to be a forge for easily building new tools. The first rule—writing programs that do one thing well—is largely a means to the second. When you have building blocks that take simple shapes, you can compose them easily like Lego pieces.

A New Font

1 Aug 2022

This week I created a custom build of the Iosevka font. I've used Input Mono for a long time now, and was very happy with it. However, it was missing a few glyphs that I wanted to use. Moreover, I didn't have a license for the Input font to use on e.g. my blog. Iosevka is stupendously customizable, so I thought I'd see if I could get something close to Input's styles.

Iosevka's default style is extremely narrow. However, I discovered that the width of Iosevka extended at 13pt matched Input at 12pt exactly. Here's a side-by-side comparison: the first picture is with Input Mono, and the second is with my new Iosevka Output font:

Programs and Intent

9 Nov 2021

What does this program do? At the most reduced level, one could say that a program’s behavior is defined by the effect it has on the hardware running it. That’s not very useful however; when we’re programming, we often have to deal with legacy code and tease out the original intent of the code.

Saying that the meaning of a program is entirely encapsulated by the code is saying that the intent and the implementation are the same. They so rarely are!

Models of Programming

24 Oct 2021

Last week I was studying outside of a lecture hall where someone was teaching an introductory course on computer programming. There was a lot that I overheard that I disagreed with; this essay is an attempt to help me crystallize what exactly I disagreed with.