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

Note: This post was updated on 14 April 2018 to clarify misconceptions that were written early in its composition. These corrections were addressed back in 2014 in a footnote, but I have incorporated these corrections into the main post now, along with a note describing where the update was made and the initial misconception.

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 Bros. and Duck Hunt in one. We picked up others along the way, but Super Mario Bros. 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 Bros. 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 Bros. ROM file. 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 blank space, and then the game goes on to use that blank space as the destination world when you warp. Why a space? That’s because of the way the NES games store numbers, letters, and other symbols.

I said above that the game cartridges get dumped to data in a ROM 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 (like Mario’s lives) are stored simply as the numbers from zero to nine. Numbers ten through thirty-five represent the letters of the alphabet and get displayed as such on screen. Finally, the very next number, thirty-six, gets displayed as a space, or blank tile. (Other numbers represent punctuation, or tiles of background terrain, buildings, and so on.)

Knowing this, we know that the game ROM file stores a world’s number with a typical number, such as using a five for world 5. When we go to the Minus World, somehow we’re actually going to world 36, and the game displays this as a blank space. When Mario pops out at his destination, the top of the screen shows  -1, which looks like a negative one, hence the name for this glitch—the Minus World.

How does Mario end up at world 36? First, it’s important to know that Mario contains a lot of creative code reuse. 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 likely guided the decision for the program code to reuse the the labels above the pipes as the actual destinations as well. In other words, when Mario descended down a pipe which the game knew to be a warp zone pipe, Mario‘s code would check out what number was above the pipe and plug that number directly into the world to which it sent you.

Second, it’s important to know that Mario had essentially no error-checking. The original programmers had no room for extraneous error-checking and simply avoided, to the best of their ability, creating erroneous or nonsensical situations in the code. When an error does happen, the game just carries on as best it can until it breaks completely. This allows parts of the game to fragment and coalesce like free radicals, creating new, unintended things.

Those two factors make the Minus World possible, and a bug in the collision detection enables players to access it. Here’s what actually happens in the code to trigger the glitch from within the game.

  • First, Mario reaches the exit pipe near the end of world 1–2, but he doesn’t go through it.
  • By knocking out a brick above the pipe and jumping in a precise way, the player triggers a bug in Mario’s collision detection which allows Mario to move through the pipe and bricks to the right.
  • Mario emerges at the left edge of the warp zone clearing, near the leftmost pipe there.
    • Note at this point that no label appears above the pipe. The code for Super Mario Bros. does not load the labels for the warp zone until it has fully scrolled into view—try it out sometime when playing normally. So this glitch has essentially allowed us to prevent loading the labels for the warp zone. In other words, we’ve taken a shortcut preventing us from running all the way to the right before dropping into the clearing. That’s the critical part.
  • Mario descends into the leftmost pipe.
    • The code dutifully checks what number is above the pipe. However, that memory is a blank space. Mario reuses the same memory for both what’s on the screen and what destination the pipe goes to. A blank space is represented by a thirty-six, so Mario heads to world 36–1, which the game displays as  –1 at the top of the screen.
  • Mario appears in the Minus World.

I’m unclear about what happens on the level of the code to create the Minus World, but the experience, as many have learned, is an improbable one: 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! 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 Bros. ROM, an emulator (I recommend OpenEmu on OS X), and a hex editor. Go hack!