Month: May 2014

On Explaining Monads

Something about learning what a monad is renders you utterly unable to say what a monad is. It’s a self-enforcing Fight Club.

Let’s assume you’re a programmer, and you’ve heard your coworkers toss around the term “monad” a few times. They suffer from a deplorable inarticulateness when you ask about “monads”. So you go to Wikipedia, thinking you’ll find a primer. You won’t. As of the time of this writing, you’ll actually find something more like this.

In functional programming, a monad is a structure that represents computations defined as sequences of steps. A type with a monad structure defines what it means to chain operations, or nest functions of that type together. This allows the programmer to build pipelines that process data in steps, in which each action is decorated with additional processing rules provided by the monad.

Okay, then.

And, I mean, that explanation really does say it all! If only you can understand what it means. I read the first sentence a few times, and I thought, Okay, well, isn’t that what a program is? A sequence of steps which defines a computation? You find yourself reading many words you’ve seen before, but filled with different meanings. You’ve set out to learn a new word, and now you find you’ve lost words you thought you already knew.

Like I said, though, it’s really all there. I’m not going to explain monads, but I’m going to supply a bit of context missing from every single discussion, tutorial, or other edifying material I’ve seen online and offline, and maybe this will help someone besides me out. The key there is really the first three words: in functional programming.

What they mean is a pure functional programming language, which is essentially just lambda calculus. Setting aside what lambda calculus is and why you might ever want to type it into a computer, the upshot of this purity concept is that things we take for granted while programming—assignment, exceptions, input/output, continuations, and so on—are no longer possible! They’re not pure.

Monads therefore exist to give a “pure” way to do all these things. It’s just a word for a tactic that solves all these problems in similar ways that don’t cause the language to become “impure.” Using this tactic, we can laboriously reconstruct many of the computational bits we’re accustomed to. While the concept dates from the early 90s, it’s found new life as we realize the advantages of stateless functional computations in concurrency programming contexts.

For the nuts and bolts of how this tactic works, I found the best explanation were the earliest ones. I didn’t get any of the above until I read this whitepaper on the subject from 1992. Or this one by the same guy from around the same time. Seriously. Give it a shot if you’re struggling with this concept.

On Being Brushed Aside

While writing about the warp zone hacking in my last post, I mentioned offhandedly how I lost interest in video games in the 90s. I wanted to talk a little more about that because I’ve noticed this pattern in a lot of women.

I had never considered a pattern might exist until I discovered my friend Shawna’s story matched mine very similarly. I asked around and heard similar things—girls seem to have plenty of interest in video games, and then at some age or another, while still young, the interest peters out.

It’s not a universal trait by any means, but it’s a noticeable pattern. Someone pointed me to a nice list of points of privilege that lead to becoming a geek, and my attention focused on the fifth bullet point in particular (emphasis mine):

If we were girls, no brothers. (A study in the early 90s showed that in households with both boy and girl children, a computer or video game console was likely to end up in the boy’s room, with all the usual sibling territoriality that entails. My straw poll in a women’s meetup at the Game Developer’s Conference some years back showed only about a third of the women in the room had brothers….)

Shawna and I both had younger brothers, and more especially I had older cousins I spent time with. I haven’t conducted any studies, so I can only relate my personal experiences on the subject. It seems like several things happened right around the same time which caused me to become an outsider to video games early on. From my point of view, I saw the following trends push me out as the 90s wore on and became the 2000s.

  • Game consoles became more varied, competitive, and expensive. As a member of a family having trouble making ends meet as it was, Nintendo’s waning dominance meant other consoles competed for the market, and in turn, competed for our own dollar. After the Super Nintendo, we didn’t buy a new console for perhaps a decade.
  • Games themselves introduced game play styles requiring more dedication in terms of time. As the id Software–style first-person shooter proliferated, along with fighting games with extensive “move lists” and 3D games requiring more elaborate controls, games began to demand new and more challenging skills. This led them to become less accessible to inexperienced or new players, favoring those who had time to practice and develop those specific skills. Without the same amount of practice, I could never hope to provide meaningful competition or cooperation in Goldeneye or Halo later on.
  • At the same time, games could further evolve their graphics, character development, game play mechanics (competitive versus cooperative, for example), and so on, which allowed the games to target ever more specific demographics. Violence grew to be a salient trend. Protagonists could become more distinctively male. I imagine these trends tracked closely with the type of person making this generation of game. To me, this meant it was harder to find games that held my attention, and it was hard to find people with whom to play.
  • The shift in demographic manifested itself in the result of the study mentioned above: Boys came to dominate console time. If the boy said, “You can play when my turn is over,” his turn would last far longer than yours. That fed into a feedback cycle where girls got less play time altogether, fell behind in terms of ability, lost interest in waiting, and found other things to do. This particular issue didn’t affect me quite as much, given the first point affecting me more, but I’ve heard it in multiple anecdotes from friends who were better off.

I imagine age plays a major role in what I experienced. Some girls grew up among first-person shooters and may have developed a fluency with them that I can’t imagine. “Casual games” have made something a resurgence, as making games for tablets, phones, and computers have become more accessible. So this problem might not even be a problem anymore, but I imagine it’s still left a troubling gap, and it’s definitely affected me (and probably a wider generation of disaffected women out there).

Through the Warp Zone

Did you ever play Nintendo? I mean the original thing, the Nintendo Entertainment System that made its way to North America in 1985. It was the first kind of video game I ever had experience with, and I still play it today. It’s really rare that I pull out the actual hardware my family got back in the 80s to use, though that happens from time to time. So I use an emulator.

The first game we had, which came with the system, was the combination cartridge with Super Mario Brothers and Duck Hunt in one. We picked up others along the way, but Super Mario Brothers was first for me and always felt like the default game, the Platonic ideal of games. I played it enough to etch every one of its nooks and secrets indelibly into my memory, and I can play it with muscle memory today. After the early 90s, I stopped forming any sort of attachment to video games and mostly stopped bothering, but before that, I played Mario with dedication, enough that it feels like every part of the game is carved in stone. Super Mario Brothers is the same everywhere and will never change—or so it seemed when I was younger.

I also heard rumors of glitches, ways to make the game do unintended things, which came built into every copy. The most famous one that I know of is the Minus World. There are warp zones throughout the game which allow you to skip from an earlier world to a later one by going down a pipe. The Minus World glitch required you to get near the first warp zone and then do some weird maneuver that lands you in a glitched version of that warp zone, such that two of the pipes can take you to a world labeled  –1, a bizarre Mario hinterland which doesn’t ordinarily exist.

I tried and tried, but I never could get that damn glitch to work. Several years ago, though, I figured out a way to get to the Minus World so that I wouldn’t have to bother with the glitch. I did it by directly manipulating the contents of the Super Mario Brothers ROM. In fact, I was able to tell that warp zone to take me anywhere I liked, including existing and nonexistent worlds apart from the Minus World altogether. I’ll explain in a moment, but first I want to explain the Minus World glitch.

In the course of the glitch, the game ends up showing the warp pipe, as you’d expect, and instead of the familiar number above it, instead, it puts a space, and then the game goes on to use that space as the destination world when you warp. Why a space? That’s because of the way the NES games store numbers and letters.

I said above that the game cartridges get dumped to data in a file, and like any other file, that data is just made up of numbers. Some of those numbers are instructions, and others represent data, such as words, or what Mario and his world look like. Literal numbers you’d see on screen are stored simply as the numbers from zero to nine. Numbers ten through thirty-five represent the letters of the alphabet. Finally, the very next number, thirty-six, is a space, or blank tile. (Other numbers represent tiles of background terrain, buildings, and so on.)

How does it choose the number thirty-six? This is conjecture on my part, but the telling aspect of the original glitch is that either of the side pipes take you to the Minus World while the middle pipe takes you to world 5–1. This tells me that the glitch somehow mistakes the game into thinking you’re at the warp zone you’d otherwise encounter in world 4–2. In that warp zone, there is only a single pipe which takes you to world 5–1. Mario uses the same code instructions to display three numbers above the pipes in every warp zone, but for the sake of those warp zones with only a single pipe, the game designers used blank tiles (number thirty-six) so that you wouldn’t see useless numbers hanging above pipes that aren’t there. This allowed them to reuse the same bit of code for each warp zone to show the destinations, and where they only needed one destination, they just hid the others.

There is a lot of creative code reuse in Mario. This served to keep the game very, very small—as all early NES games were. I see that my ROM, in fact, is only 40,976 bytes. That’s smaller than most webpages. Code reuse probably also guided the decision to use the labels above the pipes as the actual destinations as well. Mario would check out what number was above the pipe in a warp zone and plug that number directly into the world to which it sent you.

Returning to the glitch, you’d see the three warp pipes built into world 1–2, but with the labels from warp zone you’d see in world 4–2, which included two blanks. Given the thrifty assembly code with which Mario was made, it didn’t bother checking you were doing something which made sense. It simply tried to make sense of the situation in which the player found itself, so when you went down a pipe there, it’d look at the label, see a thirty-six, and blissfully send you to world 36–1, which looked like  –1.

At this point, I’m unclear about what happens on the level of the code, but the experience, as many have learned, is that of the Minus World: you find yourself swimming through a glitched version of world 7–2 which never ends. Probably, Mario tries to look up which data corresponds to world 36–1 in order to build it and somehow ends up with the wrong one. I’m guessing that the code takes the number thirty-six and tries to count up through a table to look up the world it wants, overflowing and wrapping back around as it goes. (It’s interesting, if maybe irrelevant, to observe that thirty-six divides by seven with a remainder of one.) Whatever the case, those are the details I know about how the Minus World works.

Like I said, I never managed to get that glitch to work. I wasn’t dextrous enough, I guess. You can find videos of it online, but back when I was attempting it, I never managed it. I did get curious about how it all worked, enough to figure out what I said above.

I realized then that within the ROM, there must be a kind of table, with three-number combinations describing the possible destinations for each warp zone. The Mario ROM being itty-bitty, as I said, I just opened it up in a hex editor (a program that lets you edit the data in a file directly in numerical form) and searched for the sequence of numbers representing the first warp zone: four, three, and two, in that order read from left to right in the actual game.

Hex editor screenshot showing the warp tableIt didn’t take too long to find such a sequence, and luckily, this three-number sequence only recurs a few times. Look at the screenshot up above. It’s in hexadecimal, but the number sequence looks pretty straightforward. For those who can’t see the screenshot, the line of numbers reads FF 15 1E 10 12 04 03 02 00 24 05 24 00. Among the seeming garbage, the sequence 04 03 02 is easy to spot.

But look, there’s another clue! Right after the numbers I wanted, there’s a zero, and after that, a thirty-six, a five, and another thirty-six. Does that sound familiar? It’s the next warp zone! In fact, it’s the one we get if we trigger the glitch. So we’re definitely on the right track. But if we want to be sure, there’s only one real way to know. I changed 04 03 02 to 08 03 02 and ran the game. Sure enough, I saw what I was looking for!

Screenshot of Super Mario Brothers with edited warp table leading to world 8

And just to make sure the hack did indeed work, I had to go down the pipe, of course.

Screenshot of Super Mario Brothers in world 8-1

Success! I can hack the warp table and go to any world I want from the first warp zone. This has possibilities!

Screenshot of Super Mario Brothers with hacked warp zone to world nineI realized I could then edit 08 03 02 to be anything I wanted, including the Minus World (24 03 02). But even more, I can put in numbers to worlds nobody has ever seen. I wanted to see world nine and play it, so I put in 09 03 02.

Screen Shot 2014-05-05 at 11.41.38Haha, world nine, as it turns out, is ridiculous. You can actually swim through the world all the way to the end. It’s kind of wild. I tried several other worlds, most of which were alphabetical. Each one is different and broken in its own way.

Some strongly resemble existing worlds with little twists (weird gray blocks all over, gray spits from the castles in random places). Some are like world nine, something which should never have seen the light of day and which only barely work (I note that my emulator I used for making screenshots actually froze up). Some are blank and don’t work at all.

I won’t spoil these other worlds with screenshots. You know enough to see these worlds for yourself now. All you need is a Super Mario Brothers ROM, an emulator (I recommend OpenEmu on OS X), and a hex editor. Go hack!

© 2017 Emily St*

Theme by Anders NorenUp ↑