Tristan Dannenberg teryror

Crafting a Compiler from Scratch: Implementation Notes

For the past two weeks or so, I've been working on a little compiler project in C, mostly for educational purposes, i.e. to understand how a compiler really works. I'm not using any libraries, other than the C runtime library.

Introduction

I have a hand-written lexer and parser, and a simple code generator targetting

Unbiased Range Reduction of Pseudo-Random Numbers

Suppose you're working on a virtual board game and want to simulate the roll of a die. The first programming book I ever owned suggested the following:

int result = rand() % 6;

If you've spent any time reading about random numbers in computer science, you've probably heard that this is a bad idea. The reason that's usually given is that rand() (just like the standard RNGs of many other languages, such as

Random Sampling Without Replacement

Last time we talked about rolling unbiased virtural dice, now let's turn to opening virtual booster packs in a collectible card game. If you're a nerd like me, you may be interested in reading about the specifics of how cards are distributed in [Magic: The Gathering][2] and [Yu-Gi-Oh!][3], but our main concern here is to randomly select n items from an array of N options. I'm told that it's also useful in scientific computing or whatever.

Monte-Carlo Permutation Testing

Near the end of my first statistics class, I was introduced to the concept of a hypothesis test: given two sample sets, determine the probability that they were drawn from the same population. If this is less than your desired p-value (typically 5% or less, depending on your field), you can reject the [null-hypothesis][1] and accept the alternative hypothesis that the two samples are indeed from different populations.

This was presented to me in the context of social sciences, but it comes up in

Mulligans and Mana Bases

For my previous post on how many colored sources you should put in your mana bases, I adapted Frank Karsten's simulation code to the London Mulligan rules change, and to make recommendations based on how many lands you want to play. In doing so, I made two errors: first, the tables for Commander decks do not take into account the free mulligan, or the turn one draw. Second, I changed the assumed mulligan strategy to be more aggressive; the effect of this change dominated over the effect of the London Mulligan, invalidating my comment on the matter.

Redesigning `coca`'s Storage Abstraction

This post was written primarily to organize my thoughts during the design process. I'll explain the thought process that led me to each point in the design space we visit, then point out any issues, which will lead into the next iteration. Along the way, I made a few errors, which I'll try to rectify in the (Side Notes).

Here we go!

	// ...

	static int32_t*
	get_indentation_marks(Application_Links app, Partition part, Buffer_Summary *buffer, Cpp_Token_Array tokens, int32_t line_start, int32_t line_end, bool32 exact_align, int32_t tab_width){
	int32_t indent_mark_count = line_end - line_start;
	int32_t *indent_marks = push_array(part, int32_t, indent_mark_count);
	// Shift the array so line_index works correctly.
	indent_marks -= line_start;

	// NOTE: TLD modifications begin here

	/*******************************************************************************
	Author: Tristan Dannenberg
	Notice: No warranty is offered or implied; use this code at your own risk.
	********************************************************************************
	Approximate algorithm for generating length-limited prefix codes.

	I came up with this idea while working on an animation of Huffman's algorithm,
	and had a convincing informal argument for it being optimal.

	Comparison with Package/Merge shows this to be false for heavily skewed symbol

	/*

	Based on Frank Karsten's "How Many Colored Mana Sources" simulation code
	(see his article [1], original source code found at [2]).

	[1]: https://strategy.channelfireball.com/all-strategy/channelmagic/channelmagic-articles/how-many-colored-mana-sources-do-you-need-to-consistently-cast-your-spells-a-guilds-of-ravnica-update/
	[2]: https://pastebin.com/9P5kwqt1

	Updated to account for the London Mulligan rule change, and expanded to
	account for more restrictive casting costs and different land counts.

	use rand::prelude::*;
	use std::collections::HashMap;
	use std::fmt::Write;

	#[derive(Copy, Clone, PartialEq, Eq)]
	enum CardType {
	NonLand,
	Land,
	GoodLand,
	}