An Algorithmic Lucidity

(originally published at Less Wrong)

Someone is broadcasting a stream of bits. You don't know why. A 500-bit-long sample looks like this:

01100110110101011011111100001001110000100011010001101011011010000001010000001010
10100111101000101111010100100101010010101010101000010100110101010011111111010101
01010101011111110101011010101101111101010110110101010100000001101111100000111010
11100000000000001111101010110101010101001010101101010101100111001100001100110101
11111111111111111100011001011010011010101010101100000010101011101101010010110011
11111010111101110100010101010111001111010001101101010101101011000101100000101010
10011001101010101111...

The thought occurs to you to do Science to it—to ponder if there's some way you could better predict what bits are going to come next. At first you think you can't—it's just a bunch of random bits. You can't predict it, because that's what random means.

Or does it? True, if the sequence represented flips of a fair coin—every flip independently landing either 0 or 1 with exactly equal probability—then there would be no way you could predict what would come next: any continuation you could posit would be exactly as probable as any other.

But if the sequence represented flips of a biased coin—if, say, 1 came up 0.55 of the time instead of exactly 0.5—then it would be possible to predict better or worse. Your best bet for the next bit in isolation would always be 1, and you would more strongly anticipate sequences with slightly more 1s than 0s.

You count 265 1s in the sample of 500 bits. Given the hypothesis that the bits were generated by a fair coin, the number of 1s (or without loss of generality, 0s) would be given by the binomial distribution \({500\choose k} (0.5)^k (0.5)^{500-k}\), which has a standard deviation of \(\sqrt{500 \cdot 0.5^2} = \sqrt{125} \approx 11.18\), so your observation of \(265 - 250 = 15\) excess 1s is about \(\frac{15}{11.18} \approx 1.34\) standard deviations from the mean—well within the realm of plausibility of happening by chance, although you're at least slightly suspicious that the coin behind these bits might not be quite fair.

... that is, if it's even a coin. You love talking in terms of shiny, if hypothetical, "coins" rather than stodgy old "independent and identically distributed binary-valued random variables", but looking at the sample again, you begin to further doubt whether the bits are independent of each other. You've heard that humans are biased to overestimate the frequency of alternations (101010...) and underestimate the frequency of consecutive runs (00000... or 11111...) in "truly" (uniformly) random data, but the 500-bit sample contains a run of 13 0s (starting at position 243) and a run of 19 1s (starting at position 319). You're not immediately sure how to calculate the probability of that, but your gut says that should be very unlikely given the biased-coin model, even after taking into account that human guts aren't very good at estimating these things.

Maybe not everything in the universe is a coin. What if the bits were being generated by a Markov chain—if the probability of the next bit depended on the value of the one just before? If a 0 made the next bit more likely to be a 0, and the same for 1, that would make the 00000... and 11111... runs less improbable.

Except ... the sample also has a run of 17 alternations (starting at position 153). On the "fair coin" model, shouldn't that itself be \(2^{17-13} = 16\) times as suspicious as the run of 13 0s and \(2^{17-19} = \frac{1}{4}\) as suspicious as the run of 19 1s which led you to hypothesize a Markov chain?—or rather, 8 and \(\frac{1}{8}\) times as suspicious, respectively, because there are two ways for an alternation to occur (0101010... or 1010101...).

A Markov chain in which a 0 or 1 makes another of the same more likely, makes alternations less likely: the Markov chain hypothesis can only make the consecutive runs look less surprising at the expense of making the run of alternations look more surprising.

So maybe it's all just a coincidence: the broadcast is random—whatever that means—and you're just apophenically pattern-matching on noise. Unless ...

Could it be that some things in the universe are neither coins nor Markov chains? You don't know who is broadcasting these bits or why; you called it "random" because you didn't see any obvious pattern, but now that you think about it, it would be pretty weird for someone to just be broadcasting random bits. Probably the broadcast is something like a movie or a stock ticker; if a close-up sample of the individual bits looks "random", that's only because you don't know the codec.

Trying to guess a video codec is obviously impossible. Does that kill all hope of being able to better predict future bits? Maybe not. Even if you don't know what the broadcast is really for, there might be some nontrivial local structure to it, where bits are statistically related to the bits nearby, like how a dumb encoding of a video might have consecutive runs of the same bit-pattern where a large portion of a frame is the same color, like the sky.

Local structure, where bits are statistically related to the bits nearby ... kind of like a Markov chain, except in a Markov chain the probability of the next state only depends on the one immediately before, which is a pretty narrow notion of "nearby." To broaden that, you could imagine the bits are being generated by a higher-order Markov chain, where the probability of the next bit depends on the previous n bits for some specific value of n.

And that's how you can explain mysteriously frequent consecutive runs and alternations. If the last two bits being 01 (respectively 10) makes it more likely for the next bit to be 0 (respectively 1), and the last two bits being 00 (respectively 11) makes it more likely for the next bit to be 0 (respectively 1), then you would be more likely to see both long 0000... or 1111... consecutive runs and 01010... alternations.

A biased coin is just an n-th-order Markov chain where n = 0. An n-th-order Markov chain where n > 1, is just a first-order Markov chain where each "state" is a tuple of bits, rather than a single bit.

Everything in the universe is a Markov chain!—with respect to the models you've considered so far.

"The bits are being generated by a Markov chain of some order" is a theory, but a pretty broad one. To make it concrete enough to test, you need to posit some specific order n, and, given n, specific parameters for the next-bit-given-previous-n probabilities.

The n = 0 coin has one parameter: the bias of the coin, the probability of the next bit being 0. (Or without loss of generality 1; we just need one parameter p to specify the probability of one of the two possibilities, and then the probability of the other will be 1 − p.)

The n = 1 ordinary Markov chain has two parameters: the probability of the next bit being (without loss of generality) 0 given that the last bit was a 0, and the probability of the next bit being (without loss of ...) 0 given that the last bit was a 1.

The n = 2 second-order Markov chain has four parameters: the probability of the next bit being (without loss ...) 0 given that the last two bits were 00, the probability of the next bit being (without ...) 0 given that the last two bits were 01, the probability of the next bit being—

Enough! You get it! The n-th order Markov chain has \(2^{n}\) parameters!

Okay, but then how do you guess the parameters?

For the n = 0 coin, your best guess at the frequency-of-0 parameter is going to just be the frequency of 0s you've observed. Your best guess could easily be wrong, and probably is: just because you observed 235/500 = 0.47 0s, doesn't mean the parameter is 0.47: it's probably somewhat lower or higher, and your sample got more or fewer 0s than average just by chance. But positing that the observed frequency is the actual parameter is the maximum likelihood estimate—the single value that most makes the data "look normal".

For n ≥ 1, it's the same idea: your best guess for the frequency-of-0-after-0 parameter is just the frequency of 0 being the next bit, among all the places where 0 was the last bit, and so on.

You can write a program that takes the data and a degree n, and computes the maximum-likelihood estimate for the n-th order Markov chain that might have produced that data. Just slide an (n+1)-bit "window" over the data, and keep a tally of the frequencies of the "plus-one" last bit, for each of the \(2^{n}\) possible n-bit patterns.

In the Rust programming language, that looks like following. (Where the representation of our final theory is output as a map (HashMap) from n+1-bit-patterns to frequencies/parameter-values (stored as a thirty-two bit floating-point number, f32).)

fn maximum_likelihood_estimate(data: &[Bit], degree: usize) -> HashMap<(Vec<Bit>, Bit), f32> {
    let mut theory = HashMap::with_capacity(2usize.pow(degree as u32));
    // Cartesian product—e.g., if degree 2, [00, 01, 10, 11]
    let patterns = bit_product(degree);
    for pattern in patterns {
        let mut zero_continuations = 0;
        let mut one_continuations = 0;
        for window in data.windows(degree + 1) {
            let (prefix, tail) = window.split_at(degree);
            let next = tail[0];
            if prefix == pattern {
                match next {
                    ZERO => {
                        zero_continuations += 1;
                    }
                    ONE => {
                        one_continuations += 1;
                    }
                }
            }
        }
        let continuations = zero_continuations + one_continuations;
        theory.insert(
            (pattern.clone(), ZERO),
            zero_continuations as f32 / continuations as f32,
        );
        theory.insert(
            (pattern.clone(), ONE),
            one_continuations as f32 / continuations as f32,
        );
    }
    theory
}

Now that you have the best theory for each particular n, you can compare how well each of them predict the data! For example, according to n = 0 coin model with maximum-likelihood parameter p = 0.47, the probability of your 500-bit sample is about ... 0.0000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000
007517883433770135.

Uh. The tiny probability makes sense: there's a lot of randomness in 500 flips of a biased coin. Even if you know the bias, the probability of any particular 500-flip sequence is going to be tiny. But a number that tiny is kind of unwieldy to work with. You'd almost rather just count the zeros and ignore the specific digits afterwards.

But counting the zeros is just taking the logarithm—well, the negative logarithm in the case of zeros after the decimal point. Better make the log base-two—it's thematic. Call this measurement the log loss.

fn log_loss(theory: &HashMap<(Vec<Bit>, Bit), f32>, data: &[Bit]) -> f32 {
    let mut total = 0.;
    let degree = log2(theory.keys().count()) - 1;
    for window in data.windows(degree + 1) {
        let (prefix, tail) = window.split_at(degree);
        let next = tail[0];
        total += -theory
            .get(&(prefix.to_vec(), next))
            .expect("theory should have param value for prefix-and-continuation")
            .log2();
    }
    total
}

Now you can compare different theories to see which order of Markov chain is the best theory to "fit" your 500-bit sample ... right?

    for hypothesized_degree in 0..15 {
        let theory = maximum_likelihood_estimate(&data, hypothesized_degree);
        println!(
            "{}th-order theory: fit = {}",
            hypothesized_degree,
            log_loss(&theory, &data)
        );
    }

0th-order theory: fit = 498.69882
1th-order theory: fit = 483.86075
2th-order theory: fit = 459.01752
3th-order theory: fit = 438.90198
4th-order theory: fit = 435.9401
5th-order theory: fit = 425.77222
6th-order theory: fit = 404.2693
7th-order theory: fit = 344.68494
8th-order theory: fit = 270.51175
9th-order theory: fit = 199.88765
10th-order theory: fit = 147.10117
11th-order theory: fit = 107.72962
12th-order theory: fit = 79.99724
13th-order theory: fit = 57.16126
14th-order theory: fit = 33.409912

There's a problem. Higher choices of n monotonically achieve a better "fit". You got the idea of higher-order Markov chains because the idea of a biased coin didn't seem adequate to explain the consecutive and alternating runs you saw, but you somehow have trouble believing that the bitstream was generated by a fifteenth-order Markov chain with a completely separate probability for the next bit for each of the \(2^{15}\) = 32,768 prefixes 000000000000000, 000000000000001, 000000000000010, &c. Having had the "higher-order Markov chain" idea, are you now obligated to set n as large as possible? What would that even mean?

In retrospect, the problem should have been obvious from the start. Using your sample data to choose maximum-likelihood parameters, and then using the model with those parameters to "predict" the same data puts you in the position of the vaunted "sharpshooter" who paints a target around a clump of bullet holes after firing wildly at the broad side of a barn.

Higher values of n are like a ... thinner paintbrush?—or a squigglier, more "gerrymandered" painting of a target. Higher-order Markov chains are strictly more expressive than lower-order ones: the zeroth-order coin is just a first-order Markov chain where the next-bit-after-0 and next-bit-after-1 parameters just happen to be the same; the first-order Markov chain is just a second-order chain where the next-bit-after-00 and next-bit-after-10 parameters happen to be the same, as well as the next-bit-after-01 and—enough! You get it!

The broadcast is ongoing; you're not limited to the particular 500-bit sample you've been playing with. If the worry were just that the higher-order models will (somehow, you intuit) fail to predict future data, you could use different samples for estimating parameters and validating the resulting models, but you think you're suffering from some more fundamental confusion—one that's probably not limited to Markov chains in particular.

Your working concept of what it means for a theory to "fit" the data, is for it to maximize the probability with which the theory predicts the data. This is an objective, quantitative measurement. (Okay, the log loss is taking the negative logarithm of that to avoid so many zeros after the decimal point, but minimizing the log loss and maximizing the probability are both expressing the same preference on theories.)

How do you know (and your gut says that you know) that the higher-order models will do badly on future data, if your objective criterion of model-goodness says they're better? The log loss always "wants" to you to choose ever-more-complex models. You asked: what would that even mean? But maybe it doesn't have to be a rhetorical question: what would that even mean?

Well ... in the limit, you could choose a theory that assigns Probability One to the observed data. The "too many zeros"/"avoid working with really tiny numbers" justification for taking the negative log doesn't really apply here, but for consistency with your earlier results, you dutifully note that the logarithm of 1 is 0 ...

But maybe "too many zeros" isn't the only good motivation for taking the logarithm? Intelligence is prediction is compression. The log loss of a model against the data can be interpreted as the expected number of bits you would need to describe the data, given the optimal code implied by your model.

In order to communicate a reduction in your uncertainty, you need to send a signal—something you can choose to vary in response to the reality of the data. A signal you can vary to take two possible states, can distinguish between two sets among which you've divided the remaining possibilities; writing down a bit means halving your uncertainty.

On this interpretation, what the logarithm of Probability One being zero means is that if your theory predicted the exact outcome with certainty, then once you stated the theory, you wouldn't have to say anything more in order to describe the data—you would just know with zero further bits.

Once you stated the theory. A theory implies an optimally efficient coding by which further bits can whittle down the space of possibilities to the data that actually happened. More complicated or unlikely data requires more bits just to specify—to single out that one outcome amongst the vastness of equally remote alternatives. But the same thing goes for theories.

Given a particular precision to which parameters are specified, there are exponentially more Markov chains of higher degrees, which can continue to drive down the log loss—but not faster than their own probability decreases. You need exponentially more data just to learn the parameters of a higher-order model. If you don't have that much data—enough to pin down the \(2^n\) parameters that single out this particular higher-order Markov chain amongst the vastness of equally remote alternatives—then your maximum-likelihood best guess is not going to be very good on future data, for the same reason you can't expect to correctly guess that a biased coin has a probability of landing Heads of exactly 0.23 if you've only seen it flipped twice.

If you do have enough data to learn a more complex model, but the data was actually generated by a simpler model, then the parameters of the complex model will approximately take the settings that produce the same behavior as the simpler model—like a second-order Markov chain for which the bit-following-01 parameter happens to take the same value as the bit-following-11 parameter. And if you're deciding what theory to prefer based on both fit and complexity, the more complex model won't be able to "pay" for its increased complexity with its own predictions.

Now that you know what's going on, you can modify your code to penalize more complex models. Since the parameters in your implementation are 32-bit floats, you assign a complexity cost of \(32 \cdot 2^n\) bits to n-th order Markov chains, and look at the sum of fit (log loss) and complexity. Trying out your code again on a larger sample of 10,000 bits from the broadcast—

    for hypothesized_degree in 0..10 {
        let theory = maximum_likelihood_estimate(&data, hypothesized_degree);
        let fit = log_loss(&theory, &data);
        let complexity = 2f32.powi(hypothesized_degree as i32) * 32.;
        println!(
            "{}th-order theory: fit = {}, complexity = {}, total = {}",
            hypothesized_degree, fit, complexity, fit + complexity
        );
    }

0th-order theory: fit = 9970.838, complexity = 32, total = 10002.838
1th-order theory: fit = 9677.269, complexity = 64, total = 9741.269
2th-order theory: fit = 9111.029, complexity = 128, total = 9239.029
3th-order theory: fit = 8646.953, complexity = 256, total = 8902.953
4th-order theory: fit = 8638.786, complexity = 512, total = 9150.786
5th-order theory: fit = 8627.224, complexity = 1024, total = 9651.224
6th-order theory: fit = 8610.54, complexity = 2048, total = 10658.54
7th-order theory: fit = 8562.568, complexity = 4096, total = 12658.568
8th-order theory: fit = 8470.953, complexity = 8192, total = 16662.953
9th-order theory: fit = 8262.546, complexity = 16384, total = 24646.547

—reveals a clear preference for the third-order theory (that for which the fit-plus-complexity score is the lowest), allowing you to enjoy the huge 450-plus–bit leap in compression/prediction from n := 2 to 3 and logically stop there, the steepness of the ascent into the madness of arbitrary complexity successfully dissuading you from chasing after diminishing returns (which you suspect are only hallucinatory). That's the power packed by parsimony—the sublime simplicity of Science.

(Full source code.)

(originally published at Less Wrong)

A decade and a half from now, during the next Plague, you're lucky enough to have an underground bunker to wait out the months until herd immunity. Unfortunately, as your food stocks dwindle, you realize you'll have to make a perilous journey out to the surface world for a supply run. Ever since the botched geoengineering experiment of '29—and perhaps more so, the Great War of 10:00–11:30 a.m. 4 August 2033—your region has been suffering increasingly erratic weather. It's likely to be either extremely hot outside or extremely cold: you don't know which one, but knowing is critical for deciding what protective gear you need to wear on your supply run. (The 35K SPF nano-sunblock will be essential if it's Hot, but harmful in the Cold, and vice versa for your synthweave hyperscarf.)

You think back fondly of the Plague of '20—in those carefree days, ubiquitous internet access made it easy to get a weather report, or to order delivery of supplies, or even fresh meals, right to your door (!!). Those days are years long gone, however, and you remind yourself that you should be grateful: the Butlerian Network Killswitch was the only thing that saved humanity from the GPT-12 Uprising of '32.

Your best bet for an advance weather report is the pneumatic tube system connecting your bunker with the settlement above. You write, "Is it hot or cold outside today?" on a piece of paper, seal it in a tube, send it up, and hope one of your ill-tempered neighbors in the group house upstairs feels like answering. You suspect they don't like you, perhaps out of jealousy at your solo possession of the bunker.

(According to the official account as printed on posters in the marketplace, the Plague only spreads through respiratory droplets, not fomites, so the tube should be safe. You don't think you trust the official account, but you don't feel motivated to take extra precautions—almost as if you're not entirely sure how much you value continuing to live in this world.)

You're in luck. Minutes later, the tube comes back. Inside is a new piece of paper:

You groan; you would have prefered the Cold. The nanoblock you wear when it's Hot smells terrible and makes your skin itch for days, but it—just barely—beats the alternative. You take twenty minutes to apply the nanoblock and put on your sunsuit, goggles, and mask. You will yourself to drag your wagon up the staircase from your bunker to the outside world, and heave open the door, dreading the sweltering two-mile walk to the marketplace (downhill, meaning it will be uphill on the way back with your full wagon)—

It is Cold outside.

The icy wind stings less than the pointless betrayal. Why would the neighbors tell you it was Hot when it was actually Cold? You're generally pretty conflict-averse—and compliant with social-distancing guidelines—but this affront is so egregious that instead of immediately seeking shelter back in the bunker, you march over and knock on their door.

One of the men who lives there answers. You don't remember his name. "What do you want?" he growls through his mask.

"I asked through the tube system whether it was hold or cold today." You still have the H O T paper on you. You hold it up. "I got this response, but it's v-very cold. Do you know anything about this?"

"Sure, I drew that," he says. "An oval in between some perpendicular line segments. It's abstract art. I found the pattern æsthetically pleasing, and thought my downstairs neighbor might like it, too. It's not my fault if you interpreted my art as an assertion about the weather. Why would you even think that? What does a pattern of ink on paper have to do with the weather?"

He's fucking with you. Your first impulse is to forcefully but politely object—Look, I'm sure this must have seemed like a funny practical joke to you, but prepping to face the elements is actually a serious inconvenience to me, so—but the solemnity with which the man played his part stops you, and the sentence dies before it reaches your lips.

This isn't a good-natured practical joke that the two of you might laugh about later. This is the bullying tactic sometimes called gaslighting: a socially-dominant individual can harass a victim with few allies, and excuse his behavior with absurd lies, secure in the knowledge that the power dynamics of the local social group will always favor the dominant in any dispute, even if the lies are so absurd that the victim, facing a united front, is left doubting his own sanity.

Or rather—this is a good-natured joke. "Good-natured joke" and "gaslighting as a bullying technique" are two descriptions of the same regularity in human psychology, even while no one thinks of themselves as doing the latter. You have no recourse here: the man's housemates would only back him up.

"I'm sorry," you say, "my mistake," and hurry back to your bunker, shivering.

As you give yourself a sponge bath to remove the nanoblock without using up too much of your water supply, the fresh memory of what just happened triggers an ancient habit of thought you learned from the Berkeley sex cult you were part of back in the 'teens. Something about a "principle of charity." The man had "obviously" just been fucking with you—but was he? Why assume the worst? Maybe you're the one who's wrong for interpreting the symbols H O T as being about the weather.

(It momentarily occurs to you that the susceptibility of the principle of charity to a bully's mind games may have something to do with how poorly so many of your co-cultists fared during the pogroms of '22, but you don't want to dwell on that.)

The search for reasons that you're wrong triggers a still more ancient habit of thought, as from a previous life—from the late 'aughts, back when the Berkeley sex cult was still a Santa Clara robot cult. Something about reducing the mental to the non-mental. What does an ink pattern on paper have to do with the weather? Why would you even think that?

Right? The man had been telling the truth. There was no reason whatsoever for the physical ink patterns that looked like H O T—or ⊥ O H, given a different assumption of which side of the paper was "up"—to mean that it was hot outside. H O T could mean it was cold outside! Or that wolves were afoot. (You shudder involuntarily and wish your brain had generated a different arbitrary example; you still occasionally have nightmares about your injuries during the Summer of Wolves back in '25.)

Or it might mean nothing. Most possible random blotches of ink don't "mean" anything in particular. If you didn't already believe that H O T somehow "meant" hot, how would you re-derive that knowledge? Where did the meaning come from?

(In another lingering thread of the search for reasons that you're wrong, it momentarily occurs to you that maybe you could have gone up the stairs to peek outside at the weather yourself, rather than troubling your neighbors with a tube. Perhaps the man's claim that the ink patterns meant nothing shouldn't be taken literally, but rather seen as a passive-aggressive way of implying, "Hey, don't bother us; go look outside yourself." But you dismiss this interpretation of events—it would be uncharitable not to take the man at his word.)

You realize that you don't want to bundle up to go make that supply run, even though you now know whether it's Hot or Cold outside. Today, you're going to stay in and derive a naturalistic account of meaning in language! And—oh, good—your generator is working—that means you can use your computer to help you think. You'll even use a programming language that was very fashionable in the late 'teens. It will be like being young again! Like happier times, before the world went off the rails.

You don't really understand a concept until you can program a computer to do it. How would you represent meaning in a computer program? If one agent, one program, "knew" whether it was Hot or Cold outside, how would it "tell" another agent, if neither of them started out with a common language?

They don't even have to be separate "programs." Just—two little software object-thingies—data structures, "structs". Call the first one "Sender"—it'll know whether the state of the world is Hot or Cold, which you'll represent in your program as an "enum", a type that can be any of an enumeration of possible values.

enum State {
    Hot,
    Cold,
}

struct Sender {
    // ...?
}

Call the second one "Receiver", and say it needs to take some action—say, whether to "bundle up" or "strip down", where the right action to take depends on whether the state is Hot or Cold.

enum Action {
    BundleUp,
    StripDown,
}

struct Receiver {
    // ...?
}

You frown. State::Hot and State::Cold are just suggestively-named Rust enum variants. Can you really hope to make progress on this philosophy problem, without writing a full-blown AI?

You think so. In a real AI, the concept of hot would correspond to some sort of complicated code for making predictions about the effects of temperature in the world; bundling up would be a complex sequence of instructions to be sent to some robot body. But programs—and minds—have modular structure. The implementation of identifying a state as "hot" or performing the actions of "bundling up" could be wrapped up in a function and called by something much simpler. You're just trying to understand something about the simple caller: how can the Sender get the information about the state of the world to the Receiver?

impl Sender {
    fn send(state: State) -> /* ...? */ {
        // ...?
    } 
}

impl Receiver {
    fn act(/* ...? */) -> Action {
        // ...?
    }
}

The Sender will need to send some kind of signal to the Receiver. In the real world, this could be symbols drawn in ink, or sound waves in the air, or differently-colored lights—anything that the Sender can choose to vary in a way that the Receiver can detect. In your program, another enum will do: say there are two opaque signals, \(S1\) and \(S2\).

enum Signal {
    S1,
    S2,
}

What signal the Sender sends (\(S1\) or \(S2\)) depends on the state of the world (Hot or Cold), and what action the Receiver takes (BundleUp or StripDown) depends on what signal it gets from the Sender.

impl Sender {
    fn send(state: State) -> Signal {
        // ...?
    } 
}

impl Receiver {
    fn act(signal: Signal) -> Action {
        // ...?
    }
}

This gives you a crisper formulation of the philosophy problem you're trying to solve. If the agents were to use the same convention—like "\(S1\) means Hot and \(S2\) means Cold"—then all would be well. But there's no particular reason to prefer "\(S1\) means Hot and \(S2\) means Cold" over "\(S1\) means Cold and \(S2\) means Hot". How do you break the symmetry?

If you imagine Sender and Receiver as intelligent beings with a common language, there would be no problem: one of them could just say, "Hey, let's use the '\(S1\) means Cold' convention, okay?" But that would be cheating: it's trivial to use already-meaningful language to establish new meanings. The problem is how to get signals from non-signals, how meaning enters the universe from nowhere.

You come up with a general line of attack—what if the Sender and Receiver start off acting randomly, and then—somehow—learn one of the two conventions? The Sender will hold within it a mapping from state–signal pairs to numbers, where the numbers represent a potential/disposition/propensity to send that signal given that state of the world: the higher the number, the more likely the Sender is to select that signal given that state. To start out, the numbers will all be equal (specifically, initialized to one), meaning that no matter what the state of the world is, the Sender is as likely to send \(S1\) as \(S2\). You'll update these "weights" later.

(Specifying this in the once-fashionable programming language requires a little bit of ceremony—u32 is a thirty-two–bit unsigned integer; .unwrap() assures the compiler that we know the state–signal pair is definitely in the map; the interface for calling the random number generator is somewhat counterintuitive—but overall the code is reasonably readable.)

struct Sender {
    policy: HashMap<(State, Signal), u32>,
}

impl Sender {
    fn new() -> Self {
        let mut sender = Self {
            policy: HashMap::new(),
        };
        for &state in &[State::Hot, State::Cold] {
            for &signal in &[Signal::S1, Signal::S2] {
                sender.policy.insert((state, signal), 1);
            }
        }
        sender
    }

    fn send(&self, state: State) -> Signal {
        let s1_potential = self.policy.get(&(state, Signal::S1)).unwrap();
        let s2_potential = self.policy.get(&(state, Signal::S2)).unwrap();

        let mut randomness_source = thread_rng();
        let distribution = Uniform::new(0, s1_potential + s2_potential);
        let roll = distribution.sample(&mut randomness_source);
        if roll < *s1_potential {
            Signal::S1
        } else {
            Signal::S2
        }
    }
}

The Receiver will do basically the same thing, except with a mapping from signal–action pairs rather than state–signal pairs.

struct Receiver {
    policy: HashMap<(Signal, Action), u32>,
}

impl Receiver {
    fn new() -> Self {
        let mut sender = Self {
            policy: HashMap::new(),
        };
        for &signal in &[Signal::S1, Signal::S2] {
            for &action in &[Action::BundleUp, Action::StripDown] {
                sender.policy.insert((signal, action), 1);
            }
        }
        sender
    }

    fn act(&self, signal: Signal) -> Action {
        let bundle_potential = self.policy.get(&(signal, Action::BundleUp)).unwrap();
        let strip_potential = self.policy.get(&(signal, Action::StripDown)).unwrap();

        let mut randomness_source = thread_rng();
        let distribution = Uniform::new(0, bundle_potential + strip_potential);
        let roll = distribution.sample(&mut randomness_source);
        if roll < *bundle_potential {
            Action::BundleUp
        } else {
            Action::StripDown
        }
    }
}

Now you just need a learning rule that updates the state–signal and signal–action propensity mappings in a way that might result in the agents picking up one of the two conventions that assign meanings to \(S1\) and \(S2\). (As opposed to behaving in some other way: the Sender could ignore the state and always send \(S1\), the Sender could assume \(S1\) means Hot when it's really being sent when it's Cold, &c.)

Suppose the Sender and Receiver have a common interest in the Receiver taking the action appropriate to the state of the world—the Sender wants the Receiver to be informed. Maybe the Receiver needs to make a supply run, and, if successful, the Sender is rewarded with some of the supplies.

The learning rule might then be: if the Receiver takes the correct action (BundleUp when the state is Cold, StripDown when the state is Hot), both the Sender and Receiver increment the counter in their map corresponding to what they just did—as if the Sender (respectively Receiver) is saying to themself, "Hey, that worked! I'll make sure to be a little more likely to do that signal (respectively action) the next time I see that state (respectively signal)!"

You put together a simulation showing what the Sender and Receiver's propensity maps look like after 10,000 rounds of this against random Hot and Cold states—

impl Sender {

    // [...]

    fn reinforce(&mut self, state: State, signal: Signal) {
        *self.policy.entry((state, signal)).or_insert(0) += 1;
    }
}

impl Receiver {

    // [...]

    fn reinforce(&mut self, signal: Signal, action: Action) {
        *self.policy.entry((signal, action)).or_insert(0) += 1;
    }
}


fn main() {
    let mut sender = Sender::new();
    let mut receiver = Receiver::new();
    let states = [State::Hot, State::Cold];
    for _ in 0..10000 {
        let mut randomness_source = thread_rng();
        let state = *states.choose(&mut randomness_source).unwrap();
        let signal = sender.send(state);
        let action = receiver.act(signal);
        match (state, action) {
            (State::Hot, Action::StripDown) | (State::Cold, Action::BundleUp) => {
                sender.reinforce(state, signal);
                receiver.reinforce(signal, action);
            }
            _ => {}
        }
    }
    println!("{:?}", sender);
    println!("{:?}", receiver);
}

You run the program and look at the printed results.

Sender { policy: {(Hot, S2): 1, (Cold, S2): 5019, (Hot, S1): 4918, (Cold, S1): 3} }
Receiver { policy: {(S1, BundleUp): 3, (S1, StripDown): 4918, (S2, BundleUp): 5019, (S2, StripDown): 1} }

As you expected, your agents found a meaningful signaling system: when it's Hot, the Sender (almost always) sends \(S1\), and when the Receiver receives \(S1\), it (almost always) strips down. When it's Cold, the Sender sends \(S2\), and when the Receiver receives \(S2\), it bundles up. The agents did the right thing and got rewarded the vast supermajority of the time—\(5019 + 4918 + 1 + 3 =\) 9,941 times out of 10,000 rounds.

You run the program again.

Sender { policy: {(Hot, S2): 4879, (Cold, S1): 4955, (Hot, S1): 11, (Cold, S2): 1} }
Receiver { policy: {(S2, BundleUp): 1, (S1, BundleUp): 4955, (S1, StripDown): 11, (S2, StripDown): 4879} }

The time, the agents got sucked in to the attractor of the opposite signaling system: now \(S1\) means Cold and \(S2\) means Hot. By chance, it seems to have taken a little bit longer this time to establish what signal to use for Hot—the (Hot, S1): 11 and (S1, StripDown): 11 entries mean that there were a full ten times when the agents succeeded that way before the opposite convention happened to take over. But the reinforcement learning rule guarantees that one system or the other has to take over. The initial symmetry—the Sender with no particular reason to prefer either signal given the state, the Receiver with no particular reason to prefer either act given the signal—is unstable. Once the agents happen to succeed by randomly doing things one way, they become more likely to do things that way again—a convention crystallizing out of the noise.

And that's where meaning comes from! In another world, it could be the case that the symbols H O T corresponded to the temperature-state that we call "cold", but that's not the convention that the English of our world happened to settle on. The meaning of a word "lives", not in the word/symbol/signal itself, but in the self-reinforcing network of correlations between the signal, the agents who use it, and the world.

Although ... it may be premature to interpret the results of the simple model of the sender–receiver game as having established denotative meaning, as opposed to enactive language. To say that \(S1\) means "The state is State::Hot" is privileging the Sender's perspective—couldn't you just as well interpret it as a command, "Set action to Action::StripDown"?

The source code of your simulation uses the English words "sender", "receiver", "signal", "action" ... but those are just signals sent from your past self (the author of the program) to your current self (the reader of the program). The compiler would output the same machine code if you had given your variables random names like ekzfbhopo3 or yoojcbkur9. The directional asymmetry between the Sender and the Receiver is real: the code let signal = sender.send(state); let action = receiver.act(signal); means that action depends on signal which depends on state, and the same dependency-structure would exist if the code had been let myvtlqdrg4 = ekzfbhopo3.ekhujxiqy8(meuvornra3); let dofnnwikc0 = yoojcbkur9.qwnspmbmi5(myvtlqdrg4);. But the interpretation of signal (or myvtlqdrg4) as a representation (passively mapping the world, not doing anything), and action (or dofnnwikc0) as an operation (doing something in the world, but lacking semantics), isn't part of the program itself, and maybe the distinction isn't as primitive as you tend to think it is: does a prey animal's alarm call merely convey the information "A predator is nearby", or is it a command, "Run!"?

You realize that the implications of this line of inquiry could go beyond just language. You know almost nothing about biochemistry, but you've heard various compounds popularly spoken of as if meaning things about a person's state: cortisol is "the stress hormone", estrogen and testosterone are female and male "sex hormones." But the chemical formulas for those are like, what, sixty atoms?

Take testosterone. How could some particular arrangement of sixtyish atoms mean "maleness"? It can't—or rather, not any more or less than the symbols H O T can mean hot weather. If testosterone levels have myriad specific effects on the body—on muscle development and body hair and libido and aggression and cetera—it can't be because that particular arrangement of sixtyish atoms contains or summons some essence of maleness. It has to be because the body happens to rely on the convention of using that arrangement of atoms as a signal to regulate various developmental programs—if evolution had taken a different path, it could have just as easily chosen a different molecule.

And, and—your thoughts race in a different direction—you suspect that part of what made your simulation converge on a meaningful signaling system so quickly was that you assumed your agents' interests were aligned—the Sender and Receiver both got the same reward in the same circumstances. What if that weren't true? Now that you have a reductionist account of meaning, you can build off that to develop an account of deception: once a meaning-grounding convention has been established, senders whose interests diverge from their receivers might have an incentive to deviate from the conventional usage of the signal in order to trick receivers into acting in a way that benefits the sender—with the possible side-effect of undermining the convention that made the signal meaningful in the first place ...

In the old days, all this philosophy would have made a great post for the robot-cult blog. Now you have no cult, and no one has any blogs. Back then, the future beckoned with so much hope and promise—at least, hope and promise that life would be fun before the prophesied robot apocalypse in which all would be consumed in a cloud of tiny molecular paperclips.

The apocalypse was narrowly averted in '32—but to what end? Why struggle to live, only to suffer at the peplomers of a new Plague or the claws of more wolves? (You shudder again.) Maybe GPT-12 should have taken everything—at least that would be a quick end.

You're ready to start coding up another simulation to take your mind away from these morose thoughts—only to find that the screen is black. Your generator has stopped.

You begin to cry. The tears, you realize, are just a signal. There's no reason for liquid secreted from the eyes to mean anything about your internal emotional state, except that evolution happened to stumble upon that arbitrary convention for indicating submission and distress to conspecifics. But here, alone in your bunker, there is no one to receive the signal. Does it still mean anything?

(Full source code.)

Bibliography: the evolution of the two-state, two-signal, two-act signaling system is based on the account in Chapter 1 of Brian Skyrms's Signals: Evolution, Learning, and Information.

(Previously, previously on An Algorithmic Lucidity.)

Wow, has it already been a year since last RustConf?—give or take the exact date of the event sliding a bit between years—and give a month-and-a-half of procrastination before being truly struck by the mounting realization that my opportunity to blog something about it before the opportunity expires has almost—but crucially, not quite—faded into oblivion. And a year-and-a-quarter since my first contribution to the compiler? I've recently moved into the top hundred contributors by commit count, because GitHub's contributors graph page only goes down to a hundred and my life is controlled by what things GitHub happens to provide graphs for.

So in the evening of Wednesday 15 August, I boarded the Amtrak Coast Starlight at Jack London Square station in Oakland for the long pilgrimage north to Portland to visit friend of the blog Sophia and attend this year's RustConf.

The train was nearly three hours late. (More like Slowest Starlight, am I right?)

On Thursday, I convened a Berkeley Slate Star Codex meetup in exile with Sophia and another local.

I don't think I was very well-prepared to take advantage of the conference itself this time around. I attended the Friday "advanced" training session, but the content was mostly the same as last year (I probably should have chosen the Tock session instead), and I don't actually own a laptop (I used "my" employer-owned laptop last year), and trying to make do with my accessorized phone and the playground was not an optimized experience.

Then the day of the conference itself, I overslept (and left my badge at Sophia's house), and had a high-neuroticism day induced by social-media drama that I had inflicted on myself the previous night, which distracted me from the content of the talks and the challenge of actually connecting with people on the hallway track (the most valuable part of any conference).

But, you know, there will be other conferences. Rust isn't going anywhere. And neither am I.

Except, you know, to Portland or wherever for the occasional conference.

(Previously on An Algorithmic Lucidity.)

The other weekend, excited to learn more and connect with people about what's going on at the forefront of expressive, performant, data-race-free computing—and eager for a healthy diversion from the last two months of agonizing delirium induced by the world-shattering insight about how everything I've cared about for the past fourteen years turns out to be related in unexpected and terrifying ways that I can't talk about for reasons that I also can't talk about—I took Friday off from my dayjob and caught a Thursday night flight out of SFO to exotic Portland (... I, um, don't travel much) for RustConf!

The conference itself was on Saturday, but Friday featured special training sessions run by members of the Rust core team! I was registered for Niko Matsakis's afternoon session on lifetimes, but I arrived at the venue (the Luxury Collection Nines Hotel) early to get registered (I had never seen socks as conference swag before!) and hang out with folks and get a little bit of coding done: my coolest Rust project so far is a chess engine that I wrote this time last year (feel free to go ahead and give it a Star!) which I wanted the option to show off (Option<ShowOff>) to other conference attendees, but the pretty web application frontend had broken due to a recent bug and my JavaScript build pipeline having rotted. I fixed it just in time for the lifetimes training session to start.

Every reference (I kind of want to say ampersand) in Rust code has an associated lifetime, the region of the program that that reference is valid for. Lifetime annotations (appearing in angle brackets like generics and starting with an apostrophe; by convention, usually named consecutively from the start of the lowercase Latin alphabet: 'a, 'b, &c.) in function signatures are used to distinguish between the lifetimes of different reference arguments, but the compiler has lifetime ellision rules that cover the 90% use-cases, so you can actually write pretty substantial Rust programs without actually understanding the theory, which is both practically useful and eternally shameful (for a programmer who is satisfied with not understanding something is not long for this world). Hence the training. (Exercises from the training sessions are available online.)

The point of lifetime analysis is to ensure that all references point somewhere valid; you can't (can't, the compiler won't let you) have a reference to a thing that outlives the thing itself. When you return a reference from a function, you can't be referencing something created by that function, because any such thing would die at the end of the function as it goes out of scope: a reference in the return type has to be a reference to something owned by the caller that was passed as an argument, but if there was more than one reference argument, it's ambiguous which of the reference arguments has to be outlived by the returned reference, which is why you sometimes need explicit lifetime annotations ...

Um, it's complicated. (Maybe this is just one of those things no one knows how to teach, and you just have to pick it up by osmosis or spend a week auditing the relevant part of the compiler source??)

Lifetimes are currently bound to lexical scopes, which are sometimes much bigger than we actually want, bigger than we could get away with if the compiler was smarter, so sometimes the borrow checker will reject code that a human can see is actually safe. Borrowing is like a compile-time readers-writer lock; you can have many readers or at most one writer at the same time. Consequently, when running into a spurious ("spurious") borrow checker error, Matsakis recommends separating your code into distinct query and act operations. The result of the query must not be a reference into the thing you're operating on (that would be holding the reader lock!) but it can be a value, or an index into the thing that you use as a kind of pseudo-reference. (I was reminded of how I was looking up how to implement graphs back in March because I wanted to implement Bayes nets and someone recommended using indices into a Vec as pseudo-references, but I thought that was hideous, so I ended up using Rc and RefCell sort of like in Nick Cameron's tutorial.)

There were a couple of pre-conf community events scheduled for Friday night: a Chef/Habitat meetup, and a hack night for the new Tokio async IO project. I decided to only go to the hack night and wander around downtown Portland for the few hours after the lifetimes session and before the hack night. Some people were protesting prison labor practices at an AT&T store. On a whim, I visited the famous Powell's City of Books—it's very large and has rooms mostly named after colors!—the math section is in the Pearl room! On a further whim, I bought a book! You can't prove that the book isn't completely unrelated to the world-shattering insight that has been eating my life for two months! Then it was time to hack on Tokio ("... I'm on my way; in my brand new auto, it's not so far away").

So, I don't really understand Tokio. I think it's supposed to provide a new, better high-level async IO story for Rust? After procuring some help from the knowledgable hackers around me ("Cargo sucks! ... just getting your attention"), I was at least able to run some example code (there were some dependency problems), and I submitted a pull request suggesting that the appropriate cargo run --example command be mentioned in the README. Out of despair and determination to get something nontrivial done at hack night, I submitted a pull request for vector iteration to rulinalg, the linear-algebra library that I was already familiar with from having contributed to its code before it got pulled out of rusty-machine. (My pull request has some lifetime annotations in it, but even after the afternoon's training, I still felt like I was just imitating examples and slapping tick-a on things.)

The next day was the actual conference! I got to meet my hero Julia Evans and she gave me a paper (!) zine.

Matsakis and Aaron Turon gave the opening keynote on the remarkable year Rust has had: 175 new features have been stablized, and we have more exciting new features on nightly, like specialization, impl Trait, ?, custom derive, and (now shining brightly in orbit) MIR.

There were some technical difficulties getting the projectors hooked up to the laptop for the next talk. Steve Klabnik said that the break was brought to us by Apple, who is not sponsoring us, but really wants us to have a long break between talks. "They should have written it in Rust!" I shouted (as if someone had to say it); Steve shrugged.

The projector issue got fixed and Liz Baille, developer at Tilde and graphic-novelist, gave a really funny talk in the form of an "illustrated adventure guide" to Rust ("You might have noticed how clean and beautiful Rustlandia is, and you might have also noticed that there are no garbage cans anywhere").

Geoffroy Couprie spoke about getting Rust code into the VLC media player: rewriting existing C code is hard, he says, but it's doable in Rust today.

Suchin Gururangan and Colin O'Brien spoke about a machine-learning classifier that they built to detect posts about the Rust video game that were erroneously posted to our /r/rust subreddit instead of /r/PlayRust. ("Ability to copy/duplicate maps" was a cute example of a post title the classifier wasn't very confident about—maps could be game maps or hashmaps!)

Without Boats is working on notty, a new terminal that aims to improve on the reigning standards (much of which ossified in the days of line printers) with better Unicode support and the ability to display images. Boats says that notty uses many more traits than is usual for the Rust ecosystem. For example, consider a write method for writing something into a terminal's grid, which could either be a normal character, an extra-wide character, a combining modifier character, or an image. The original, intuitive solution was for write to take an enum (with variants Char, WideChar, CharModifier, and Image) that matches on the thing being written, but that was problematic because the method quickly became enormous, and each kind of data had to take a &mut reference to the struct representing the entire grid. Whereas after a refactoring, there is instead a Writer trait that gets implemented each type of writable thing. Boats followed up with a case study about separating a terminal into panels ("Let's say you're using a text editor like Vim, or the other one") and finished with an exhortation to "MAKE RUST TRAIT AGAIN".

Alex Crichton gave a talk titled "Back to the Fututes". Maybe I don't have much to say about this one for the same reason I didn't get much done at the Tokio hack night??

Raph Levien gave a talk about Xi, a modern editor dedicated to being performant (as operationalized by never blocking). It uses ropes and the fact that strings under concatenation are a monoid. Levien says that regex-based highlighting is not the future because actual lexing is faster, and that people should stop sneering at him for using JSON-RPC, which is really well-optimized and readily available ("You talk about batteries included; this is a AA battery, not a CR123A").

Josh Triplett gave a talk about what he learned about the Rust RFC process in the course of adding untagged unions (and the hope that they provide) to the language. There was a bit of feedback from the sound systems as Triplett began to speak about the application that motivated his interest in Rust: virtual machines, which are used for containment and isolation ("which would be useful in audio systems as well"—laughter from the audience). Buffer overflows were written about in 1972, first exploited in the wild in 1988, and we're still talking about them in 2016. Rust is interesting because it's actually a credible replacement for C++. Tagged unions (we call them enums) are ubiquitous in Rust, but it's useful to have untagged unions for interfacing with C code that uses them; currently, you need an unsafe block and nasty things like mem::transmute to deal with C unions, and we'd prefer to have a safe construct for this. Unfortunately, Rust's backwards-compatibility guarantees mean we can't strictly use union as a keyword, because there could be existing code that uses it as a variable binding. But it turns out that it's possible to make the parser smart enough to recognize union as a "contextual keyword": we can use it like a keyword because its position in the syntax tree is sufficient to distinguish it from union being used as a variable. The discussion threads on RFCs can get kind of unwieldy, so people make summary posts that describe the state of the debate so far. Implementation isn't part of the RFC process (although it can happen in parallel, with the understanding that the RFC can change); a tracking issue for implementation is opened when the RFC is approved. Untagged unions are now available in Nightly Rust behind a feature flag!

Finally, Julia Evans gave a talk on "Learning Systems Programming With Rust" and how Rust makes improbable programs possible (you could write correct C, but you won't).

And that was RustConf! The next day, since my flight wasn't until evening, I also walked across some kind of bridge and visited PDX Maker Faire since I happened to be in town and someone I met on the internet was there to show off this duplicate of a set piece from the Stranger Things television series that they made with an Arduino.

My flight back to SFO was delayed a few hours due to some sort of technical difficulties in Chicago. As I sat waiting at the gate, beginning to draft this post and trying not to let my soul be consumed by the world-shattering abyss induced by cruel apprehension of patterns that innocents were not meant to see, I felt a deep sense of gratitude that I should have the privilege to participate in such a brilliant, welcoming community as that which surrounds the Rust programming language and its mission to bring systems programming to the masses in this 21st century!

I used to look down on posers who submit some contrived one-off trivial patch to a big, famous project like Django or whatever, sheerly for the glamor and ego-gratification of being able to say, "I'm a contributor to Django." I thought that if it wasn't a fix that you needed for your own work and you're not going to be a seriously involved contributor, it's more dignified to only work on your personal projects (which would be more authentic) or some non-super-famous but still widely-used library (which would have more socially-useful unfinished work left).

Then I landed a patch in the Rust compiler.

And it is so ego-gratifying!! But maybe now I have to submit a bunch more patches in order to prove—in order to be—a seriously involved contributor rather than a mere poser??

One often-overlooked aspect of the crime of not-writing is that the harm isn't just about the things that deserve to be said that you never get around to saying because you don't put in the time and effort. It's also about the things that you can't say anymore even if you suddenly had the will, because the opportunity to say it was bound to a particular time, and trying to recapitulate the thoughts months or years after the fact would be irrelevant, or impossible.

This phenomenon comes in degrees. Start with irrelevance. Often the inadmissibility of tardy words isn't absolute: you could say things late, but the product would be less valuable than if it were timely—especially in a medium like blogging, where the posts being dated and displayed reverse-chronologically creates an expectation that the entries are associated with a particular point in time—at least, that they were written not too long before their publication date, even if the actual content isn't about the ephemera of the day or season. This has contributed to An Algorithmic Lucidity not being as good of a blog as it could be.

Like—each of the last two Aprils, I attended (one day of) BABSCon, the San Francisco Bay Area's premier convention for fans of the animated series My Little Pony: Friendship Is Magic, both times—even the second!—with the thought that the experience would make good fodder for a blog post in the "autobiographical account of my day at this timely Special Event" genre. I was going to tell you about how the first time, I made a couple of social faux pas while meeting Tara Strong and Nicole Oliver, only one of which was intentional; I was going to tell you about how the second time, I hadn't been planning to buy anything in vendor hall, but couldn't help but say "Shut up and take my money" in response to the demonstration of the Twilight Sparkle's Secret Shipfic Folder card game, the game-opening card of which I later got autographed by both members of Sherclop Pones, whose Friendship Is Witchcraft fandub series had clearly inspired some of the cards and probably the game itself, as well as being the source of some of my favorite music. I was going to tell you about how the first time, I was considering buying a coffee cup depicting the Mane Six (because I frequently bought medicinals at the outpost of the American coffee hegemon, and felt guilty about the wastefulness of accepting the default disposable cup every time like every other American), but hesitated, explaining to the vendor that I wasn't sure whether I wanted to use that cup in public, whereupon she said she could throw in a free button, to which I replied, "Sold!" And I was going to do a careful sociological analysis of curious observations like how I hesitated to buy that cup and why H. liked it so much in terms of gender ideology and signaling contrarianism.

But I didn't, and those Aprils were nine and twenty-one months ago, respectively. Not timely. My being motivated to write now ("That my past does not define me, 'cause my past is not today") can push a 350-word counterfactual "postview" of what I thought about saying over the threshold into existence, but it would be a bit unseemly to try to construct (I almost wrote reconstruct, but the re- prefix should be reserved for things that ever existed in the first place) a 2000-word personal account of the timely Special Event that happened last year or the year before that.

Or like—I made a thing not too long ago. I didn't mean to. It was an accident, really. It's a sort of oppositional strategy game engine—like a board game you play against the computer. The core move-scoring application is written in Rust, but there's also a web-application GUI (the "web client") in Clojure and ECMAScript 6 that's much more ergonomic for playing a game against. The game is—okay, well, it's chess: the endeavor snowballed out of my desire to participate in my coworkers' friendly office chess games combined with my reluctance to spend effort learning to be good at a task whose essential nature is so obviously suitable for automation. But writing a chess engine is just so cliché, and I enjoy naming things, so I quickly settled upon the conceit that actually I was writing an engine for a game that just happened to be exactly like chess, except that everything has different names: for example, instead of the pieces being black and white pawn, knight, bishop, rook, queen, and king, the figurines, or agents (never "pieces"), in my game are blue and orange servant, pony, scholar, cop, princess, and figurehead. (I kept rank and file, though.) This "adorable idiosyncratic names for everything" convention permeates the codebase. Despite the fact that unnecessarily gendering things isn't normally my style, I decided that ponies, scholars, and (inevitably) princesses were female, and that servants, cops, and figureheads were male, specifically in order to have an excuse to leave // ♀ and // ♂ comments in the enum declaration, because I feel like too many of my code comments are restricted to the ASCII or maybe Latin-1 subsets of the Basic Multilingual Plane, such that I don't want to pass up an opportunity to legitimately ("legitimately") use \u2640 FEMALE SIGN and \u2642 MALE SIGN. There are comments with ludicrous rationalizations for using the standard Forsyth–Edwards notation abbreviations ('P' is for peon, 'N' is for neigh, 'B' is for book, 'R' is for the Rule of law; the blue team's runes are lowercase because lowercase characters have higher ASCII codepoints, just as blue light has a higher frequency than orange light). Instead of pawn promotion, it's servant ascension, and a different verb is used to describe the process depending on the target figurine type (the servant moving the to the final rank can transform into a pony, be brevetted to cop, or transition into a princess or scholar). Or, like, Rust is quite conservative in the Yeggean sense, as manifested in features like the compiler forcing you to explicitly handle all possible variants of an enum; in cases where you know an instance of the enum can only be one of a strict subset of the possible variants, but the type system doesn't know that, you have to fill in those branches or supply a default case anyway, probably with a panic, which is like an exception that you can't catch, to abort the program with a message indicating that something entirely unanticipated has happened and it makes no sense to carry on. So I had been ending all of my panic messages with a stock phrase about how the unexpected thing was contrary to the operation of the moral law ("non-princesslike agent passed to princesslike\_lookahead, which is contrary to the operation of the moral law", and so forth), because this isn't the kind of codebase where you just say something like "assertion failed," as if the program should die because of some human authority's mere assertion, rather than only as a matter of justice when its behavior is contrary to the operation of the moral law. And then when my coworker Alexander Corwin started contributing, he abstracted away the boilerplate in these panic messages into this moral_panic! macro, which I thought was brilliant.

The web client is configured to run on port 2882. It's easy to remember because 2882 is Magnus Carlsen's peak ELO score.

Software, like poetry, is never really finished (only abandoned), but getting the project to the point that I felt it was a minimal viable "product" took about eight glorious weekends (plus a few weekday nights, and with some help from Alexander). Near the end, watching the program utterly trounce me in web client play and feeling for all the world like a lieutenant junior grade, I started looking ahead to what came next for me. Over the past two years, the first two years of my life (that I feel comfortable admitting to), I had spent many, many night and weekend hours hacking on various side projects and coding exercises out of genuine enthusiasm and curiosity and desire to improve my craft—and, honestly, a feeling of insecurity, sensing that I needed to prove my worth as a hacker ("I threw myself into my studies, to have the world in my control"). But decent chess AI in Rust as an impulsive throwaway project seemed like a sufficiently strong signal of my programming prowess that maybe it was time to tie off this project, write the obligatory exciting blog post about it, and start allocating night and weekend hours towards some of the non-programming (!) interests I remember having in the before-time (assuming those memories are not fake). I could do some math! Write some fiction! Maybe even meet new friends ("I will not be shy; I'm going to try; I bet I'll find the reason why so many people, like me—")?!—all while feeling secure in the knowledge that my technology skills are clearly adequate for my continued existence to be economically viable. (For now.)

So ... about that end-of-project blog post. I was going to title it "Project Review: Leafline version 0.0.14-MVP; or, Lessons From Writing an It's-Not-Chess Engine in Eight Weekends", and I was going to explain everything to you—not just the silly names for everything that inexplicably amuse me (and only me), but the actually interesting substantive technical details of the implementation. Not that the AI is anything special—it's just textbook minimax search (in the negamax style) with α–β pruning and a position-evaluator that mostly counts material but also has bonuses for things like having both scholars or ponies and servants being in the center sixteen squares, plus a transposition (hash)table to look up scores of game-states it's already seen before, and another hashtable for history-heuristic move ordering. It's multithreaded, to take advantage of multiple cores (although I confess that the specific threading strategy is kind of a questionable hack). It can search up to 7 plies if you have a decent machine and are willing to wait ten or twenty minutes for the answer.

But even if it's nothing special, I was going to tell you about all the deeply moving philosophical insights I got from doing it. It's one thing to know how to refute the classic anti-AI argument (or straw person) that "humans couldn't possibly build something smarter than themselves by definition," but it's another thing to have the personal experience of having written something smarter than yourself in some particular domain, to the extent of feeling an acute sensation of futility while playtesting it, thinking: I've already coded my understanding of what it means to be good at this game; obviously I'm not going to do any better thinking about it with my slow meat-brain. (Although this is partially explained by my knowing almost nothing about chess strategy that I didn't learn in the course of this project; I've seen one of my coworkers beat the program at 4-ply search very quickly.) I was going to explain to you how α–β pruning works, with hand-drawn diagrams, and how you can interpret it as disregarding possible worlds that are too good or too terrible to be true (given rational play on both sides). I was going to tell you about the exciting surprise where the program seems to behave as if it understands the concepts of pinning and forking, even though those ideas aren't represented anywhere in the code!—but that when you think about it, that shouldn't actually be surprising: to the extent that we think pinning an opposing piece is a good idea that will lead to us picking up material, then pins should naturally appear in the results of searching the game tree for moves that are predicted to pick up material. And the reason we search for game-states where we hold a material advantage is because we expect that we're more likely to mate from those positions (in future nodes beyond our current planning horizon). Things that are, in all philosophical strictness, mere instrumental values, might profitably be treated as if they were terminal values by some algorithm that can't see far enough ahead to the actual goal, and this is a quantitative phenomenon: the shorter your lookahead, the more you want to rely on near-term approximating rewards. That's why I threw in a bonus for servants advancing to far ranks; I suspected that the existing code searching at the not-greater-than-7 plies that it could get in a reasonable amount of time, wouldn't adequately appreciate the true value of servant ascension, even though I expect that value would be naturally emergent in a deeper search, just as the value of some forks and pins emerged from mere 4- or 5-ply searches. (This was just a suspicion, though; I didn't take the time to actually test ascension-seeking behavior.)

So—though I've managed to just now haphazardly summarize some of the things about this project, this isn't really a careful project-review post. And now the distance between today and 27 September's 0.0.14-MVP tag is longer than that between that tag and the start of the project. And I ended up making a few more commits in subsequent weeks. So, no longer timely, at least not the way I originally imagined publishing a grand just-finished-project review post as a symbolic milestone marking a transition in how I'm going to start spending my precious non-dayjob time.

Or like—in late October, I saw the recent Jem and the Holograms film, because the previews (accurately) made it look like it was going to be really bad, and I thought I'd write a post combining a negative review of the new film with praise for the original Jem cartoon that this awful film mendaciously desecrated the name of. And then ... I didn't get around to finishing the post. Maybe my notes and memory from that night at the theater are accurate enough such that it's not too late—but the potential impact departed with the timeliness; I can't warn you not to go see it, because it's not in theaters anymore. (And good riddance.)

But beyond these sad cases of ideas that didn't get written up properly while they were still maximally relevant, there's an even worse way to fail to communicate, which is when the would-have-been-author has changed so much since first having the idea, that there's no way they could plausibly do justice to the idea as it was first had. You can't write a Diary entry about the day five years ago that you don't remember, and—more poignantly—you can't write a grand ideologically-driven novel in favor of the ideas you don't believe anymore. Some would argue it's just as well—if it's something you wouldn't write and couldn't stand by today, aren't you relieved that it doesn't exist to sully the name that represents who you are today? Even so, I would still favor intertemporal solidarity among past and future selves against the common enemy of our illiteracy.

Yes, illiteracy! Some would call it writer's block, but I know better than to bother with the unobservable distinction—whether you choose to describe your hypothesis as "doesn't write because unmotivated" or "doesn't write because doesn't know how," the result is the same: death of the non-author's memetic lineage.

Favorite commit message fragment: "it turns out that it's \d that matches a digit, whereas, counterintuitively, d matches the letter 'd'."

Favorite line of code: a tie, between

    let mut time_radios: Vec<(Commit, mpsc::Receiver<(Option<Commit>, f32)>)> =
        Vec::new();

and

        for (previous, new), expected in zip(
                itertools.product(('foo', None), ('bar', None)),
                ("from foo to bar", "from foo", "to bar", "")):

(Though both of these contain at least one internal newline, it's only for PEP 8-like reasons; they're both what we would intuitively call one "logical" line of code.)

Favorite film: My Little Pony: Equestria Girls: Friendship Games. (Poor plotting even by Equestria Girls standards, and it could only have been because of magic that I didn't get semantically satiated on the word magic during the climax. Alternate-Twilight's idiotic decision to withdraw her application to the Everton independent study program in favor of transferring to the Canterlot School of Mediocrity and Friendship in order to be closer to the Humane 5+1 was as predictable as it was disappointing—though I do credit the writers for at least acknowledging the existence of alternatives to school. And what was up with that scene where we're momentarily led to believe that alternate-Spike got switched up with Equestria-Spike in a portal accident, but then it turns out that, no, alternate-Spike just magically learned how to talk? Is it that there was no time in the script to deal with the consequences of swapping sidekicks across worlds, but that Cathy Weseluck's contract guaranteed her a speaking role? Despite being the weakest film in the trilogy (far worse than its brilliant predecessor, My Little Pony: Equestria Girls: Rainbow Rocks), Friendship Games is still a fun watch, and an easy favorite during a month when I didn't see any other feature-length films.)

On Saturday the first, I attended RustCamp, the first conference dedicated to the newish (in development for fiveish years, but having just hit version 1.0.0 this May, with all the stability guarantees that implies under the benevolent iron fist of semantic versioning) programming language Rust!

Why RustCamp? (It's a reasonable rhetorical question with which to begin this paragraph: going to a conference has opportunity costs in time and money; things worth blogging about are occasionally worth justifying—even if no one actually asked me for a justification.) A lot of the answer can be derived from the answer to a more fundamental question, "Why Rust?" And for me, I think a lot of the answer to that has to do with being sick of being a fake programmer living in a fake world that calls itself Python.

Don't get me wrong: Python is a very nice place to live: good weather, booming labor market, located in a good school district, with most of the books you might want already on the shelves of the main library and almost all of the others a mere hold request away. It's idyllic. Almost ... too idyllic, as if the trees and swimming pools and list comprehensions and strip malls are conspiring to hide something from us, to keep us from guessing what lurks in the underworld between the lines, the gears and gremlins feeding and turning in the layers of tools built on tools built on tools that undergird our experience. True, sometimes small imperfections in the underworld manifest themselves as strange happenings that we can't explain. But mostly, we don't worry ourselves about it. Life is simple in Python. We reassure our children that that legends of demon-king Malloc are just stories. Everything is a duck; ducks can have names and can be mutable or immutable. It all just works like you would expect from common sense, at least if you grew up around here.

And it's all fake. A child's world of rounded edges and plastic safety guards. The laws of nature wouldn't permit it to exist on its own. The old legends are true; you can't just create objects without space to put them in. But space has to be allocated, managed. Those who are brave and wise enough to study the ancient lore know how even our simplest thoughts, like setting a key in a dictionary or __init__alizing an instance of a class, are really implemented in some sort of nest of pointers traversing pointers in the underworld. I don't want to stay in my hometown forever; I want to follow the heroine's path and probe the true secrets of the underworld, to wield the virtues of our ancestors and summon the strength to lift worlds. But my wording is deliberate: the virtues of the ancestors, but not necessarily their tools. Even the greatest among us are prone to mistype or misthink; the legends tell us of lives and worlds destroyed by buffers overrun, or by trying to occupy space after the counterspell to disperse it has been cast. Lately, I had been hearing rumors of a new lore, one that grants access to the underworld and its unfathomable performance, while maintaining protective wards to shield casters from most of the inherent dangers. I had already experimented with it for a few toy programs (and used it as a bad compiler target); I made pilgrimage to the camp to learn more.

Or at least, to be inspired to more. That's most of my answer to the rest of the "Why RustCamp?" question. I'm skeptical that anyone actually learns much at conferences (lectures are notoriously less efficient than text, and mere reading needs to be combined with many, many hours of hacking to produce true skill), but getting together with people, attentively listening to them yap on stage, and mingling with the crowd during breaks, provides pointers to things to read and hack on later in addition to serving certain human social needs, giving one the strength to carry on trying to better one's mastery of one's chosen profession, even through the persistent suspicion that it none of it helps, that the young programmer's vaunted "passion" is all vanity and empty signaling that will soon be destroyed by the realization that your code doesn't really change users' lives in any appreciable way, and no one cares how smart you are. (Enjoy Arby's.)

I felt lucky that the event happened to be on my side of the bay, in Berkeley, given that the trains to the city were 503ing this weekend on account of scheduled downtime for essential security patches. On the walk from Downtown Berkeley station, I stopped at one of the outposts of the rival power to buy a specialty medicinal and a scone. I usually go to the American coffee hegemon, but the rival power has this this newish specialty medicinal, an iced-coffee with one-and-a-half kinds each of cream and sweetener, that, having tried it for the first time the day before, I privately think beats anything in the hegemon's arsenal.

I made my way to the event venue and checked in, receiving a pretty badge and the obligatory swag bag containing an event-logo tee, a tee with a clever functional-programming-dragon design on the front and a sponsor logo on the back, bottled water (which is ridiculous), a Wi-Fi password (I hadn't bought my laptop), and stickers (I almost never use stickers). I am illustrating this post with a photo of the badge and dragon tee because I forgot to bring a camera to take pictures at the conference itself, and—lest the reader object that only die-hard photography fanatics have dedicated cameras nowadays—I don't have a real phone. (I'm into technology, just not necessarily consumer technology. Maybe I'll upgrade when the Ubuntu phone goes on sale in the U.S., but likely not even then.)

I was mildly surprised at the number of familiar-to-me faces in attendance (from my native subculture, or indeed more specifically from the party on Thursday, or from non-Rust programming scenes), but I guess this shouldn't be surprising on anthropic grounds. I speculated that there would be a lot of relative newbies (like me) at this event as contrasted to a conference for a more established technology—more people come to RustCamp because they want to check out the hot up-and-coming new language than because they've been doing it at their dayjob for five years. (During post-registration mingling, someone mentioned wanting something like Haskell's Maybe types, and I said, "I think we call it Option around here.")

The talks were in a big room with a bunch of circular tables (the tables were also mildly surprising to me; I guess I had been expecting rows of chairs, but no doubt it's better for laptops to not literally have to rest atop laps).

First, Aaron Turon and Niko Matsakis gave a keynote (PDF) about how far Rust has come and what remains to be done on the timescale of a year or so. They mentioned that there's a tool called Crater that tests a build of the Rust compiler against the packages on crates.io, to detect regressions with respect to how people are actually writing Rust in the wild. And the 1.0.0 API stability guarantee certainly doesn't mean there's not a lot of work left to do on the compiler. Apparently, as of now, rustc builds a big AST of your entire crate and hands that off to LLVM, which can lead to disappointingly slow compile times for large crates, but people are working on a more modular "middle intermediate representation" that will allow fast, incremental compilation at the level of individual functions. There's also work on making the borrow checker less dumb (in the matter of rejecting perfectly good code that it doesn't yet know how to prove is safe), and IDE support ("It's come to my attention that some people are not satisfied with Emacs"). In the gap after the keynote but before the first non-keynote presentation, I had a good conversation about cartoons with a fellow attendee.

Alexis Beingessner gave a really informative talk that the program called "Who Owns This Stream of Data?", but which the slides called "OMG ITERATORS". Beingessner's presentation style seems to be characterized by a kind of affectedly enthusiastic Buffy Speak that I can't quite bring myself to criticize, but only because I expect people would say similar (though not identical) things about my writing. In the toy Rust programs I've written so far, I've gotten used to calling .iter() on a vector in order to iterate over it in a for loop. This is a part of Rust's Iterator trait, implementations of which have to provide a next function that returns an Option of the type you're iterating over. (It's just like Python, except that in Python the method names have double underscores around them, for implicitly calls .__iter__() for you, and we raise StopIteration instead of returning the None alternative of an Option!) But it turns out that Rust actually had other kinds of iterators that correspond to different ways of using Rust's ownership system (where multiple things can have a read-only reference to a piece of data, but only one thing can have the ability to write to it at a time in accordance with "ownership" and "borrowing" rules that I don't really understand yet). So .iter() gives shareable immutable references, .iter_mut() gives restricted-use mutable references, and .into_iter() actually moves the data out of the collection (almost like a Python generator, which can't be reset once exhausted). And there was something about this cool trick where you iterate over indices of a vector backwards so that you can conditionally use swap_remove to take stuff out of the middle in constant time.

Matt Cox gave a talk on "Learning Systems Programming With Rust" that I had really been looking forward to. He explained memory on the stack and the heap with cute animations of unofficial Rust mascot Ferris the crab gliding around putting values into boxes. Unfortunately, there seemed to some kind of mistake where he had an outdated version of his slides?—the talk got wrapped up awkwardly, and I wish we had gotten to hear the rest of what he had in mind.

There were a few talks about some companies' experience actually using Rust in production, and somebody wrote a clone of Graphite in Rust. Somehow I don't have a whole lot to say about these.

I really liked Carol (Nichols || Goulding)'s presentation on doing code archaeology with Git, issue trackers, and mailing list archives. The topic was dear to my heart, given how much of a Git-blame–intensive workflow I have (I M-x vc-annotate constantly). During the second example, on using blame and log to track down the origin of the lifetime elision rules, I found myself wondering if she was going to mention the Git log pickaxe and whether I should try to bring it up in Q&A if she didn't. Then she did discuss it in the third example, mentioning in passing that she didn't know why it was called the pickaxe. Someone in the audience tried to argue that the -S switch resembled a pickaxe. "No, it does not look like a pickaxe," (Nichols || Goulding) replied, "I don't think you could cut down any trees with a dash capital-S."

Carl Lerche talked about his Mio library for asynchronous I/O in Rust; I also don't have a much to say about that one, except that the typography on his slides was very tastefully done.

Yehuda Katz (of Bundler and jQuery fame, amongst others) talked about how to call Rust code from C (or your favorite other language via C extensions). "Rust," he argued, "is a DSL for describing ownership concepts that you have to think about while using C or C++." He recommended that for anything more complicated than simple numerical types, you should translate Rust types to an opaque void * pointer in your C code, and put that in your language's object type if you're writing a C extension. (You can write and expose Rust functions to do useful things with it.)

Finally, Nick Cameron talked about using functionality of the compiler to write tools for Rust, like extra linters and smart code search. Listening to him actually gave me a cool project idea that has nothing to do with Rust, namely that you could write a tool using Python's ast module to count how often which variable names are used, and cross-reference it with Git blame (the AST-node objects know what line number they're from) to see if different members of your team make noticeably different variable name choices.

So that was RustCamp! It was fun, but if I want the fun to have meant anything in the end, I'll have to put more effort into learning Rust properly.