Tab Completion

I'm Tab Atkins Jr, and I wear many hats. I work for Google on the Chrome browser as a Web Standards Hacker. I'm also a member of the CSS Working Group, and am either a member or contributor to several other working groups in the W3C. You can contact me here.
Listing of All Posts

Cleanly Handling a Fork on GitHub

Last updated:

One of the greatest things about GitHub is the ease with which you can fork a project and make your own changes.

One of the worst things about GitHub is the ease with which you can fork a project and then lose track of the changes upstream is making.

This is extra-true when you want to make occasional PRs for a project with regular commits; it's easy for your fork to get way behind in a way that makes it really annoying to write patches that'll merge cleanly later. This guide collects my personal experience in handling this situation with minimal pain.

One: Set an "upstream" remote

If you run git remote -v in your repo, you'll see the remote repositories that your local copy knows about. These are things that are easy to push to. By default, it'll only contain the GitHub URL for your fork, labeled "origin". You're gonna be interacting with the original repo you forked from a lot, so you want to give it an easy name, too:

git remote add upstream https://github.com/ORIGINAL_OWNER/ORIGINAL_REPOSITORY.git

Now you can easily refer to the original repo as upstream.

Two: Regularly re-sync with upstream

Whenever you're about to start some new work in your fork, re-sync it with the upstream first, so you have all the new commits and are less likely to conflict badly:

git fetch upstream
git checkout master
git merge upstream/master
git push

This should cleanly merge and just do a "fast-forward" on your repo, rather than actually making a merge commit, as long as you faithfully do what I suggest in the next step.

Three: NEVER COMMIT TO YOUR MASTER BRANCH

If you want a clean, easy workflow, you want to NEVER, EVER commit to your local master branch. The master branch's sole purpose is to track upstream exactly, so you can always cleanly work against the current version and write easy-to-merge PRs.

Instead, always make your changes in branches. When you push the branch to your remote, you can do a PR; when the PR is accepted, you can pull the newly-updated upstream and then delete your branch. master always remains a source of upstream truth, unpolluted by your personal code unless blessed by the upstream maintainers.

(This is good advice in general; always make changes in branches and only commit to master when you're done, but I'm usually lazy and just always commit to master for personal projects. But it's super-important to get this right for forks, or else you're in for a lot of pain.)

Four: Rebase your branches regularly

Say you're in the middle of writing a new proposed feature (in a branch, of course) and you notice that upstream has some new commits that touch code you're going to be modifying soon. You'd like to get that code into your branch now, before you start modifying things, so you don't have merge conflicts later. But how?

First, resync your master as stated in step 2. Then, rebase your topic branch on top of the new upstream code:

git checkout MY_COOL_BRANCH
git rebase master

This'll undo your commits, pull in the new stuff from upstream, then replay your commits on top of it, so when you eventually make a PR, the upstream maintainers will have a perfect clean merge, with your commits sitting on top of their latest code.

Five: Force-push commits that just fix PR nitpicks

When you eventually do submit your PR, the review will probably catch some small mistakes you need to fix. You can just make those fixes and push them to the PR branch, but then when it's eventually merged there will be a lot of silly little "fix typo" commits scattered around.

Instead, just fix the commit itself, using the git commit --amend option, then force-push that to your remote with git push --force. Force-pushing is normally a very bad idea, because git is usually rightfully trying to stop you from making a mistake when it rejects a push, but in this case changing the history of a short-lived PR branch is unimportant and makes things look cleaner overall.

Magical Metaphysics

Last updated:

I've been working on a homebrew fantasy world in my spare time for years. It'll probably never go anywhere, but it's fun to think about! One of the things I've wanted to nail down for a long time was the magic physics of the world, what elements made up reality in this extremely magical world.

I had a few requirements to keep in mind when developing this.

First and foremost, it had to be "complex". By this I mean--well, it's easiest to explain by contrast. In the real world, physics is "simple". The fundamental units of reality (quarks, photons, etc) have basically nothing to them. They're just a few numbers that combine together in trivial ways. The complexity of our world comes not from any fundamental complexity, but rather from enormous numbers of these super-simple things combining together. Even tho each individual thing has no complexity at all, and neither does the way they interact, the aggregate is capable of displaying tons of complexity.

Magic, on the other hand, is always "complex" at its root. It generally assumes the existence of minds as a fundamental unit of reality (whereas in the real world minds are just one of the patterns that vast quantities of unthinking particles can arrange themselves into). Sometimes it has "morality" baked in as a physical force; often it has complex things like "fire" or "earth" as core concepts. This makes magic easier to comprehend at a surface level, because it's made out of "big" things we can wrap our minds around, which combine in ways that are complex and ideosyncratic, but don't involve the dizzying amounts of data that the real world's fundamentals do. The elements of magic thus have to reflect this.

Secondly, it has to involve fives. Five is a good number of things, mentally and spiritually significant. So early on, long before I knew what anything would be, I knew I'd have five spheres of five atoms each.

So let's dive in!

The Sphere of Elements

Fire, Water, Earth, Wind, Wood

This was the simplest of all. I knew I needed to involve the classical "elements" of fire/water/earth/air, and I had a few common choices for what to make the fifth. I chose to go for "wood" for a few reasons. One, it's very physical, and helps tie together "elemental" magic with a druid-ish theme. Two, I already knew from my fantasy races that I wanted elves to have wooden skeletons, and for this to be properly mystically significant, I'd need wood to be a fundamental force. Three, wood is usually mystically significant in stories, which means its likely to be pretty core to the magic system, so I had to include it somewhere. Some other common choices I rejected are "metal" (already served by "earth"), "void" (too abstract/encompassing for what's supposed to be only one sphere of the world, also this feels a little sci-fi-y and I ended up letting Energies have that), and "heart" (very non-physical, so it doesn't fit well, and it's more over in the mental sphere that I knew I wanted to do).

A wrinkle: atoms can be "hard" or "soft"; the "hard" ones are suitable for making magical staffs with that aid in channeling related atoms. The hard/soft dichotomy is pretty literal, so Wood and Earth are both hard. This explains why staffs are commonly wood or metal, and/or contain gems (which are Earth) - they help channel elemental magic!

The Sphere of Energies

Heat/Light, Electricity/Magnetism, Kinetic, Entropy, Void

Lacking any hard atoms to make staves from, the energies are somewhat difficult to channel directly, particularly in the heat of combat. Instead they're usually admixed with an appropriate element, to aid in using an elemental staff to channel them. This produces the so-called "Wizard's Elements": Fire (Heat+Fire, or something Heat+Earth or Heat+Air), Lightning (Electricity+Air/Earth), Thunder (Kinetic+Air), Acid (Entropy+Water, or sometimes Entropy+Earth for Corrosion), and Cold (Void+Water/Air).

This one started out easy. I knew I wanted the D&D damage types, because I intended this world to be D&D-based, and what do you know, there are five common damage types. I also wanted to somehow include some slightly science-y things, but it seemed too on-the-nose to make them a sphere of their own, and I couldn't come up with a decent pentad for them anyway. I was pretty happy when I realized I could combine those two and get a more flexible sphere out of the deal.

The Sphere of Biology

Flesh, Blood, Bone, Elan, Soul

Flesh, Blood, and Bone are fairly self-explanatory. They cover all the things bodies are made of: cartilage and bone are both Bone; skin, muscle, and organs are mostly Flesh; mucus, blood, tears, and other liquids are variations on Blood.

Soul is the thinking substance, that our identities and selves are made of. Brains are a Flesh/Soul melange, for example.

Elan is "life energy", the animating force that distinguishes living things from dead. Without Elan infusing it, flesh is inert, and decomposes. With Elan, it's vital, active, and growing. Many simple healing spells are nothing more than increasing Elan in the body and letting natural healing take place, albeit at an accelerated pace.

Biology has more complex atomic interactions than the previous spheres. Bone is another "hard" atom, and thus suitable for making staffs with that aid in channeling, particularly other Biology atoms. But curiously, Bone is almost impervious to Elan; healing bone breaks is very difficult unless you have skill in Bone, and a Bone staff is absolutely worthless for channeling Elan. This has curious consequences! For one, healers are stuck using elemental staffs, at lower efficiency, which partially explains why it's always easier to harm than to heal. For two, it means that Biology specialists carrying Bone wands are definitely not healers, and the second most common use of Biology is... necromancy. (Note: Bone instruments are useful to actual surgeons, who have real training in Flesh/Blood/Bone beyond just "throw Elan at it until it's better".)

Necromancy uses all the non-Elan parts of Biology to do its work, warping bodies and souls in unnatural ways. (They can't use Elan, actually - it encourages natural growth and forms, which would unravel the work they're doing.) Bone is great for necromancers, then, as it enhances all of their spells.

This split in Biology carries over to its interactions with the Energies. Bone has a strong affinity to Void and Entropy; necromancers are well-known for an Entropy/Flesh blend known as "Necrotic energy", and some specialize in a powerful Void/Entropy blend known as "Uttercold". Flesh and Electricity have a unique affinity as well, such that some necromancers use it as an alternative animating energy. On the other hand, Elan has a strong affinity with Light, blending to produce the popular "Radiant energy" that is particularly damaging to undead. Soul has a unique affinity with Kinetic Energy, such that most Soul practitioners pick up some Kinetic skill as a matter of course, and is readily channeled by Earth wands, particularly crystalline ones.

The Sphere of Psychology

Joy, Sadness, Disgust, Anger, Fear

These are the five atoms of minds. Note that we do our actual thinking with our souls; these atoms constitute the emotional core of our being that our minds are built around.

Like the other spheres, many simple spells are just raw application of these atoms. The classic fear spell is just pumping the target with excess Fear; simple heroism spells are just elevating Anger. Many warding and shielding spells involve use of Disgust. And of course, the representative skill of the mentalist discipline, charming, is in its simplest form just overloading the target with Joy - an ecstatic person is literally happy to do whatever you say.

Of course, these are not without downsides. A simple charm is immediately recognized by the target (tho they don't care about it until it wears off), as sudden euphoria is not a normal feeling, and is easy to spot in others. And the mind is not unfeeling Earth, able to be crudely shoveled around without damage; flooding a mind with an excess of psychological atoms can do permanent damage to a person's psyche.

Skilled users instead carefully manipulate the psychological atoms, weaving them together in complex interactions that use little actual force, and are much more difficult to detect.

The common "psionic" discipline is often considered to be psychological by laypeople, but this is mistaken. While psionics traditionally includes some psychology, its flashier effects (telepathy, telekinesis, etc) are actually usually based in the Soul/Kinetic affinity pair.

The Sphere of the Divine

White, Blue, Black, Red, Green

Divine magic flows directly from the gods, and comes bundled with each god's own idiosyncratic preferences and restrictions. Within that chaos, tho, arcanists have discovered five consistent aspects. Not only do gods themselves tend to organize around these aspects, but entire pantheons tend to stabilize around filling the five aspects equally. As such, most arcanists consider the five divine aspects to be the fifth atomic sphere, thus completing the pentad.

[snip explanation, they're the Magic: the Gathering color-wheel philosophies]

These can manifest in dramatically different ways. For example, one of the more popular pantheons is the Unconquered Sun, a triune deity preaching Right Thoughts (Blue), Right Body (Green), and Right Heart (White), opposed by the twin evils of the quick death (murder, Red) and the slow death (decay, Black). On a very different spectrum, the Garlandite pantheon is led by Garland, god of blood and pain (cast as the good god of this pantheon, believe it or not), opposed by the Four Distractions, each associated with one of the other four aspects.

"Arc" pantheons that center in one aspect but embrace the two neighboring ones are common. Druidic religions, for example, are almost always centered in Green with a reverence for nature, but embrace both organization (White) and savagery (Red), while typically fighting against death/corruption (Black) and technology/artifice (Blue). The Unconquered Sun's White-centered arc structure is common in many folk pantheons.

Destiny scholars suggest that the Divine sphere, more than any other, is strongly self-balancing. If a particular aspect becomes strong in an area, it automatically draws strong opposition from its enemy aspects to counter it. There is no known instance of a stable, long-lived religion that did not incorporate the five aspects in major positions, whether good or evil, balanced in some significant way.

This requirement for balance can manifest in fairly simple dualities, like the Unconquered Sun's pantheon, or in vastly more intricate pantheons, like the ten carefully intertwined cults of Ravnican society, each embracing a different pair of aspects and all serving a vital role in the maintenance of the Infinite City, or the five unbalanced "wedges" (two neighboring aspects and their mutual enemy) exemplified by the Dragonlords.

Other Symmetries and Patterns

Many traditions organize the spheres into two overlapping pair structures: Elements and Energies are of the world, while Biology and Psychology are of the body; Elements and Biology are physical, Energies and Psychology are ephemeral. Divinity is usually seen as above and transcending each of these divisions; the "pyramid metaphor" is common, with the four "base" spheres holding up the Divine peak.

Some theorists insist that the pure "greater pentad" structure laid out here is too pat, and the actual structure is much messier and harder to categorize. It's not uncommon to view Elements and Energies as two lobes of a conjoined structure, sharing a single Fire/Light atom. Similarly, Biology and Psychology are sometimes merged into a greater structure, with the five mental atoms emerging from Soul.

More Efficient Encoding of Primes

Last updated:

Earlier I talked about efficiently encoding lists of primes via encoding the gaps between them, in a UTF-8 inspired encoding. That's great, but there's a much simpler, even more efficient way to encode a list of all primes - use bitfields!

In its simplest, least efficient form, you just associate each successive bit with each successive integer - the first bit is for 1, the second is for 2, etc. The bit is 1 if the associated number is prime, and 0 if it's composite.

This trivial, stupid encoding has an efficiency of 8 numbers per byte, which means it's equivalent to the previous gap-encoding as long as the average gap is less than 8 (which covers quite a lot of numbers!). But we can, of course, make it much better.

The first and most obvious improvement is to throw out all the even numbers. Past 2, every prime is odd, so all the even bits are guaranteed to be 0 in the naive scheme. That's wasted space; we can just assume they're composite and spend our actual data budget on the odd numbers. So now the Nth bit corresponds to the (2N + 1)th number. This *doubles our efficiency, encoding 16 numbers per byte, and roughly doubling the number of digits for which this is more efficient than the gap-encoding (covering the primes up to e^16, or ~9 million).

At this point we should pause and recognize the additional benefits we get from this encoding. Not only is it more efficient for quite a lot of primes (the primes up to 9M fill about 500kB of memory, and allow efficient prime testing/factorizing of numbers up to nearly 100 trillion), but it also gives us constant-time random access to the primality information. If you want to find out whether a random N is prime or not, you just look up the (N/16)th byte, and then check the (N/2 + 1)%8th bit. For some algorithms this is really important!

Okay, back to efficiency. Excluding all the even numbers is great, but it's of course also true that, once you get past 3, all the numbers divisible by 3 are composite. Combining that with the previous "no evens" insight, we can chop down the relevant set to just two out of every six numbers - only the values that are equal to 1mod6 or 5mod6. With this, we can encode 50% more numbers in a given number of bits! To be specific, it gives us 24 numbers per byte, exceeding the efficiency of gap-encoding up to e^24, or about 20 billion.

And we can go further! We can additionally exclude the numbers divisible by 5, leaving us with only 8 possibilities out of every 30 numbers (1, 7, 11, 13, 17, 19, 23, 29; mod 30), for an extra 25% density, winning the efficiency race up to ~10 trillion. This has some additional benefits, too - each "set" of possibles is 8 large, same as the number of bits in a byte, which simplifies the math considerably - you look in the N/30th byte, then grab the corresponding bit from the group. This limit also exceeds what we can reasonably use - storing the numbers up to 10 trillion would take about a third of a terabyte, greatly exceeding the RAM of desktop machines. So even in extreme cases, you'll get to store/use more primes with this method than the gap-encoding, and you get the random-access benefit to boot.

We could go further and exclude the multiples of 7, but the benefits are fairly small (encode about 16% more in a given space) and the math becomes a lot more annoying (49 possible primes spread across 210 numbers) and loses the nice symmetries of the previous values, so it's best to probably just stop there.

If I Had A Time Machine

Last updated:

An incomplete and growing list of mistakes that I'd fix if I had a time machine:

Languages

Make all languages be written vertically, and stack their lines left-to-right. Everyone being on one writing direction is A+, and vertical writing gives more time for the ink to dry before your hand has to touch it when you're left-handed.

Figure out a universal script that everyone can use. Doesn't have to be too complicated; tons of languages with different sounds use the Latin alphabet fine. I'm kinda in love with the Korean script, tho - it's alphabetic, but is written like it's ideographic, with the letters arranged into syllable-blocks in a standard way. Something like that would be good.

Putting everyone on a single language would be good too, but probably really hard to maintain. Just making sure everyone's writing in a mutually intelligible way is a good start.

Numbers

Switch everyone to base 6 counting. It's got some great reasons behind it!

  1. Each of your hands is a single base-6 digit (can represent the values 0-5), so you could count to 35 instead of just 10.
  2. It's got good divisibility - /2 and /3 (and /6 of course) are just "check the last digit", /4 and /9 are "check the last two digits", /5 is "sum the digits and check if they're /5" (same as /9 in base 10), /7 is "alternately add/subtract the digits and check if they're /7" (same as /11 in base 10).
  3. The multiplication table is really trivial, almost insultingly so. Similar to the divisibility, multiplying by 2 and 3 are now super easy (like multiplying by 2 and 5 are in base 10).
* | 1| 2| 3| 4| 5| 10|
----------------------
 1| 1| 2| 3| 4| 5| 10|
 2| 2| 4|10|12|14| 20|
 3| 3|10|13|20|23| 30|
 4| 4|12|20|24|32| 40|
 5| 5|14|23|32|41| 50|
10|10|20|30|40|50|100|

Numbers in base 6 are about 50% longer than in base 10, which isn't a huge loss. We can compensate for it by making sure the names for the digits are single-syllable, as that boosts your ability to remember strings of digits. Grouping digits into sets of 3 would also feel more "natural" - we might even be able to go up to sets of 6 instead.

I guess when talking about computers, we'd generally use octal (like we use hexadecimal in base 10) - 012345TE. Octal is a lot easier to learn than hex, too.

Dates

The Gregorian calendar is stupid. We can't control the length of a day or year, so we can't do anything perfect, but we can at least improve the situation by switching to a consistent 30-day month, with 6 5-day weeks. 12 of these months leaves us with a single 5-day week left over at the end, which should be treated as intercalary and placed at the end. Leap days also go at the end. This makes days consistent across months and years (the 2nd of every month is always the same day of the week, etc), and gives us much easier math in general, in both base 10 and base 6. In base 6, we have 20 months, each containing 10 5-day weeks, or 50 days total. 👌

Time

Keeping time is... fine. It's not great; our time system is clearly based on the dozenal roots in some of our old numbering systems (a day is two dozen hours, an hour is 5 dozen minutes, a minute is 5 dozen seconds), but we can still do better.

We're lucky in that, unlike calendars stuck with the unchangeable physical constants of "day" and "year" (and their terrible ratios), time-keeping is only beholden to the day - the rest of the units are human-made, and can be adjusted as we see fit. So we can switch to proper metric time! In base 10, I prefer dividing the day into 100 "hours", each equivalent to about about 15 of our old minutes, and then further subdividing into 100 "seconds", each very close to our old seconds. 15-minute chunks are very tractable, I feel - we often informally divide the hour into quarter-hours already, because it's a convenient length of time, neither too short to get anything done nor too long to keep track of.

In base 6 I'd do similar, but you can fit in three divisions - 100 hours (each about 40 of our old minutes), split into 100 minutes (each about equal to our old minute), split into 100 seconds (each about 2 of our old seconds).

Time Zones

Time zones, on the other hand, can get fucked. We don't have "season zones" for dates - when it's March 1st, it's March 1st everywhere in the world, regardless of whether that means it's snowy or cool or starting to warm up. Instead we have much fuzzier "seasons" to correspond to the weather, and those do fluctuate based on where you are.

Time should work the same. We should have a single consistent global time, and then pair it with a set of fuzzier "moments" that describe roughly what the light-level/meal time is. Then it's easy to describe when a meeting will happen (at hour 34, or something), but also tell people it's too early (it's still dawn over here at that time), same as we can tell people when we'll vacation (January) and what it'll be like (middle of summer, because we're doing a beach vacation in New Zealand).

I Understand Platonic Solids A Little Better Now

Last updated:

So I was watching this experimental gameplay video for Miegakure, a 4d indie video game. It's like Fez, which was a 2d platformer in a 3d world that involved "rotating" things in 3d to solve puzzles, except lifted one level, so it's a 3d game in a 4d world.

Anyway, it mentioned the 24-cell, a weird 4d shape that I've always wanted to understand better, so I started on a Wikipedia binge. This immediately led me back to the platonic solids, when I realized something.

It always struck me as weird that there are an infinite number of regular 2d polygons, one for every number of sides - equilateral triangle, square, regular pentagon, regular hexagon, etc - but there were only five regular 3d polyhedrons - with dice names, the d4, d6, d8, d12, and d20. Going from infinite to finite is always interesting, and I didn't get it before, but I got to thinking about the patterns in the shapes, and suddenly it clicked - there just isn't enough space for any more regular polyhedrons!

See, the dice shapes can be split into two lines. The d4, d6, and d12 form the "increasing polygon side-count" line, while the d4, d8, and d20 form the "increasing number of triangles" line. (Yes, the d4 is the base of both.)

The "increasing polygon side-count" line goes from triangle (3) sides, to square (4) sides, to pentagon (5) sides. As you increase the number of sides, the angles get larger, so you have lay the shapes out "flatter" to get them to fit together snugly, reducing the curvature and increasing the size of the die. But what happens when you fit hexagons together? They tile the plane. Put hexagons together snugly, and they perfectly fill up a flat 2d plane - 120° × 3 = 360°. You can't curve them at all, there's not enough space. So there's no way to make a polyhedron with a regular hexagon - it can't curve around to form a ball!

The same argument happens with "increasing numbers of triangles". It's easy to fit together three triangles - you get the d4. Spread them out a little and you make space for a fourth, getting the d8. A little more flattening makes room for a fifth, making the d20. You can still squeeze in one more triangle, putting six together snugly, but only by flattening them into a plane again. It's the same problem as the hexagon tiling - 60° × 6 = 360° again. The triangles don't curve around at all, so you once again can't form a ball!

7 (whether 7-sided shapes, or 7 triangles) is of course right out. You can't fit those together no matter how you try.

I presume this is why there are only three regular solids in 5+ dimension: the simplex (analogue of the d4), the measure complex (analogue of the d6), and the cross complex (analogue of the d8). In higher dimensions the volumes take up more "room", so you just can't fit as many together, and aren't able to go up to the "5" shapes (analogues of the five-sided or 5-triangled shapes).

This still doesn't answer what the fuck is up with four dimensions, tho. 4d has six regular solids - 5 analogues of the 3d solids, and 1 special. There's the three made out of increasing-size dice: the 5-cell, made out of d4s; the 8-cell, made out of d6s; and the 120-cell, made out of d12s. There's the three made out of tetrahedrons: the 5-cell, where 4 meet at each vertex; the 16-cell, where 5 meet at each vertex; and the 600-cell, where 6 meet at each vertex.

Then there's the 24-cell, made out of d8s. What the fuck. Geometry is weird.