Skip to content

Instantly share code, notes, and snippets.

View g0xA52A2A's full-sized avatar

George Brown g0xA52A2A

View GitHub Profile
@pizlonator
pizlonator / pizlossafull.md
Last active February 19, 2025 05:16
How I implement SSA form

This document explains how I would implement an SSA-based compiler if I was writing one today.

This document is intentionally opinionated. It just tells you how I would do it. This document is intended for anyone who has read about SSA and understands the concept, but is confused about how exactly to put it into practice. If you're that person, then I'm here to show you a way to do it that works well for me. If you're looking for a review of other ways to do it, I recommend this post.

My approach works well when implementing the compiler in any language that easily permits cyclic mutable data structures. I know from experience that it'll work great in C++, C#, or Java. The memory management of this approach is simple (and I'll explain it), so you won't have to stress about use after frees.

I like my approach because it leads to an ergonomic API by minimizing the amount of special cases you have to worry about. Most of the compiler is analyses and transformations ov

@VictorTaelin
VictorTaelin / truly_optimal_evaluation_with_unordered_superpositions.md
Last active December 25, 2024 09:58
Truly Optimal Evaluation with Unordered Superpositions

Truly Optimal Evaluation with Unordered Superpositions

In this post, I'll address two subjects:

  1. How to solve HVM's quadratic slowdown compared to GHC in some cases

  2. Why that is relevant to logic programming, unification, and program search

Optimal Evaluators aren't Optimal

@VictorTaelin
VictorTaelin / hvm3_atomic_linker.md
Last active February 8, 2025 05:15
HVM3's Optimal Polarized Atomic Linker

HVM3's Optimal Atomic Linker (with Polarization)

Atomic linking is at the heart of HVM's implementation: it is what allows threads to collaborate towards massive parallelism. All major HVM versions started with a better atomic linker. From slow, buggy locks (HVM1), to AtomicCAS (HVM1.5), to AtomicSwap (HVM2), the algorithm became simpler and faster over the years.

On the initial HVM3 implementation, I noticed that one of the cases on the atomic linker never happened. After some reasoning, I now understand why, and

@AndrasKovacs
AndrasKovacs / TwoStageRegion.md
Last active February 2, 2025 12:58
Lightweight region memory management in a two-stage language
@VictorTaelin
VictorTaelin / hoc_historical_overview.md
Last active February 9, 2025 09:35
Higher Order Company: Complete Historical Overview - WIP

Higher-Order Company: Complete Historical Overview

This document is a complete historical overview of the Higher Order Company. If you want to learn anything about our background, a good way to do so is to feed this Gist into an AI (like Sonnet-3.5) and ask it any question!

My Search for a Perfect Language

It all started around 2015. I was an ambitious 21-year-old CS student who, somehow, had been programming for the last 10 years, and I had a clear goal:

I want to become the greatest programmer alive

@timothyham
timothyham / ipv6guide.md
Last active February 18, 2025 05:31
A Short IPv6 Guide for Home IPv4 Admins

A Short IPv6 Guide for Home IPv4 Admins

This guide is for homelab admins who understand IPv4s well but find setting up IPv6 hard or annoying because things work differently. In some ways, managing an IPv6 network can be simpler than IPv4, one just needs to learn some new concepts and discard some old ones.

Let’s begin.

First of all, there are some concepts that one must unlearn from ipv4:

Concept 1

Understanding the Phases Applicative

While I was researching how to do level-order traversals of a binary tree in Haskell, I came across a library called tree-traversals which introduced a fancy Applicative instance called Phases. It took me a lot of effort to understand how it works. Although I still have some unresolved issues, I want to share my journey.

Note: I was planning to post this article on Reddit. But I gave up because it was too long so here might be a better place.

See the discussion.

Note: This article is written in a beginner-friendly way. Experts may find it tedious.

@kwonoj
kwonoj / blanche.json
Last active February 21, 2024 05:37
Zed theme: Blanche Light
{
"$schema": "https://zed.dev/schema/themes/v0.1.0.json",
"name": "Blanche",
"author": "OJ Kwon<oj@inbox.kwon.page>",
"description": "Naive port for the VS code theme Blanche https://marketplace.visualstudio.com/items?itemName=shytikov.blanche . Credits to https://github.com/shytikov/blanche",
"themes": [
{
"name": "Blanche light",
"appearance": "light",
"style": {
@VictorTaelin
VictorTaelin / sat.md
Last active December 7, 2024 20:59
Simple SAT Solver via superpositions

Solving SAT via interaction net superpositions

I've recently been amazed, if not mind-blown, by how a very simple, "one-line" SAT solver on Interaction Nets can outperform brute-force by orders of magnitude by exploiting "superposed booleans" and optimal evaluation of λ-expressions. In this brief note, I'll provide some background for you to understand how this works, and then I'll present a simple code you can run in your own computer to observe and replicate this effect. Note this is a new observation, so I know little about how this algorithm behaves asymptotically, but I find it quite

@kprotty
kprotty / lz4_block.zig
Last active January 2, 2024 11:14
Simple LZ4 block enc/dec in 100 LOC
const assert = @import("std").debug.assert;
fn compressBlock(writer: anytype, src: []const u8) !void {
var table = [_]u32{0} ** 4096; // size is pow2. bump to match more. ideal = (0xffff+1) / sizeof(u32)
var anchor: u32 = 0;
if (src.len > 12) { // LZ4 spec restriction: last match must start 12b before end of block.
var pos: u32 = 0;
while (pos + 4 < src.len - 5) { // LZ4 spec restriction: last 5b are always literal.
const blk: u32 = @bitCast(src[pos..][0..4].*);