Functional Programming for Everyone Else

Functional programming has become a hot topic in the last few years for programmers, but non-programmers might not understand what we’re talking about. I can imagine them wondering, “Did programs not work before? Why are they suddenly ‘functional’ now?”

Earlier today, I was tweeting a bit about the challenge of explaining to family or primary school students what the big deal is all about. Even we programmers take some time to cotton on to the notion. I know I’d have to pause for a moment if someone asked me what Haskell offers over Python.

If you’re not a programmer and have been wondering what the big deal is, here’s my attempt to lay it out.


First, consider the time just before computers existed. By the 1920s, a kind of math problem called a decision problem led various people to learn how to investigate the problem solving process itself. To do this, we had to invent an idea we call computability, meaning to automate problem solving using small, reusable pieces. A couple of mathematicians tackled this idea in two different ways (though they each came to the same conclusion), and today we have two ways to think about computability as a result.

I’m partial to Alan Turing’s approach because it’s very practical. He envisioned a process that’s quite mechanical. In fact, we now call it a Turing machine, even though his machine never actually existed. It was more of a mental exercise than something he intended to build.

To solve a problem with a Turing machine, he would break a problem into a sequence of steps which would pass through the machine on an endless tape. The machine itself knew how to understand the steps on the tape, and it knew how to store information in its memory. As the steps on the tape passed through, one at a time, the machine would consult the tape and its own memory to figure out what to do. This usually meant modifying something in its memory, which in turn could affect the following step, over and over until the steps ran out. By choosing the right set of steps, when you were done, the machine’s memory would end up with the answer you needed.

Since that time, most computers and programs are based on this concept of stringing together instructions which modify values in memory to arrive at a result. Learning to program means learning a vast number of details, but much of it boils down to understanding how to break a problem into instructions to accomplish the same thing. Programs made this way would not be considered “functional.”

At the same time, another mathematician, Alonzo Church, came up with another approach called lambda calculus. At its heart, it has a lot in common with Turing’s approach: lambda calculus breaks up a problem into small parts called functions. Instead of modifying things in memory, though, the key proposition of a function is that it takes input and calculates a result—nothing more. To solve a problem this way, little functions are written to calculate small parts of the problem, which are in turn fed to other functions which do something else, and so on until you get an answer.

Lambda calculus takes a much more abstract approach, so it took longer to work out how to make programs with it. When we did, we called these programs “functional programs” because functions were so fundamental to how they worked.


Putting all this together, I think of functional programs as ones which do their jobs without stopping to take notes along the way. As a practical consequence, this implies a few odd things. The little niceties that come first nature to procedural programs—like storing values, printing out text, or doing more than one thing at once—don’t come easy to functional programs. On the other hand, functional programs allow for understanding better what a program will do, since it will do the same thing every time if its input doesn’t change.

I think both approaches have something to offer, and in fact, most programs are made with a combination of these ideas. Turing proved neither approach was better than the other. They’re just two ways of ending up at the same result. Programmers each have to decide for themselves which approach suits best—and that decision problem can’t be solved by a program yet.

A Gentle Primer on Reverse Engineering

Over the weekend at Women Who Hack I gave a short demonstration on reverse engineering. I wanted to show how “cracking” works, to give a better understanding of how programs work once they’re compiled. It also serves my abiding interest in processors and other low-level stuff from the 80s.

My goal was to write a program which accepts a password and outputs whether the password is correct or not. Then I would compile the program to binary form (the way in which most programs are distributed) and attempt to alter the compiled program to accept any password. I did the demonstration on OS X, but the entire process uses open source tools from beginning to end, so you can easily do this on Windows (in an environment like Cygwin) or on Linux. If you want to follow along at home, I’m assuming an audience familiar with programming, in some form or another, but not much else.

Building a Program

I opened a terminal window and fired up my text editor (Vim) to create a new file called program.c. I wanted to write something that would be easy to understand, edit, and yet still could be compiled, so C seemed like a fine choice. My program wasn’t doing anything that would’ve been strange in the year 1982.

First, I wrote a function for validating a password.

int is_valid(const char* password)
{
    if (strcmp(password, "poop") == 0) {
        return 1;
    } else {
        return 0;
    }
}

This function accepts a string and returns a 1 if the string is “poop” and 0 otherwise. I’ve chosen to call it is_valid to make it easier to find later. You’ll understand what I mean a few sections down.

Now we need a bit of code to accept a string as input and call is_valid on it.

int main()
{
    char* input = NULL;
    input = malloc(256);
    printf("Please input a word: ");
    scanf("%s", input);

    if (is_valid(input)) {
        printf("That's correct!\n");
    } else {
        printf("That's not correct!\n");
    }

    free(input);
    return 0;
}

This source code is likewise pretty standard. It prompts the user to type in a string and reads it in to a variable called input. Once that’s done, it calls is_valid with that string. Depending on the result, it either prints “That’s correct!” or “That’s not correct!” and exits, returning control to the operating system. With a couple of “include” directives at the top, this is a fully functioning program.

Let’s build it! I saved the file program.c and used the command gcc program.c -o program to build it.

This outputs a file in the current directory called program which can be executed directly. Let’s run our program by typing ./program. It’ll ask us to put in a word to check. We already know what to put in (“poop”), so let’s do that and make sure we see the result we expect.

Please input a word: poop
That's correct!

And if we run it again and type in the wrong word, we get the other possible result.

Please input a word: butts
That's not correct!

So far, so good.

A Deeper Look

There’s nothing special about this program that makes it different than your web browser or photo editor; it’s just a lot simpler. I can demonstrate this on my system with the file command. Trying it first on the program I just built, with the command file program, I see:

program: Mach-O 64-bit executable x86_64

This is the file format OS X uses to store programs. If this kind of file seems unfamiliar, the reason is that most applications are distributed as app bundles which are essentially folders holding the executable program itself and some ancillary resources. Again, with file, we can see this directly by running file /Applications/Safari.app/Contents/MacOS/Safari:

/Applications/Safari.app/Contents/MacOS/Safari: Mach-O 64-bit executable x86_64

Let’s learn a little more about the binary we just built. We can’t open it in a text editor, or else we get garbage. Using a program called hexdump we can see the raw binary information (translated to hexadecimal) contained in the file. Let’s get a glimpse with hexdump -C program | head -n 20.

00000000  cf fa ed fe 07 00 00 01  03 00 00 80 02 00 00 00  |................|
00000010  10 00 00 00 10 05 00 00  85 00 20 00 00 00 00 00  |.......... .....|
00000020  19 00 00 00 48 00 00 00  5f 5f 50 41 47 45 5a 45  |....H...__PAGEZE|
00000030  52 4f 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |RO..............|
00000040  00 00 00 00 01 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000060  00 00 00 00 00 00 00 00  19 00 00 00 28 02 00 00  |............(...|
00000070  5f 5f 54 45 58 54 00 00  00 00 00 00 00 00 00 00  |__TEXT..........|
00000080  00 00 00 00 01 00 00 00  00 10 00 00 00 00 00 00  |................|
00000090  00 00 00 00 00 00 00 00  00 10 00 00 00 00 00 00  |................|
000000a0  07 00 00 00 05 00 00 00  06 00 00 00 00 00 00 00  |................|
000000b0  5f 5f 74 65 78 74 00 00  00 00 00 00 00 00 00 00  |__text..........|
000000c0  5f 5f 54 45 58 54 00 00  00 00 00 00 00 00 00 00  |__TEXT..........|
000000d0  10 0e 00 00 01 00 00 00  e7 00 00 00 00 00 00 00  |................|
000000e0  10 0e 00 00 04 00 00 00  00 00 00 00 00 00 00 00  |................|
000000f0  00 04 00 80 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000100  5f 5f 73 74 75 62 73 00  00 00 00 00 00 00 00 00  |__stubs.........|
00000110  5f 5f 54 45 58 54 00 00  00 00 00 00 00 00 00 00  |__TEXT..........|
00000120  f8 0e 00 00 01 00 00 00  1e 00 00 00 00 00 00 00  |................|
00000130  f8 0e 00 00 01 00 00 00  00 00 00 00 00 00 00 00  |................|

The left column is the “offset,” in hexadecimal (like line numbering, it tells us how many bytes into the file we are on a particular line). The middle two columns are the actual contents of the file itself, again in hexadecimal. The right column shows an ASCII equivalent for the file’s contents, where possible. If you pipe the file’s contents to less you can scan through and see mostly a lot of garbage and also a few familiar strings. If you’re interested in knowing what pieces of text are embedded in a file, the program strings speeds this process up a great deal. In our case, it tells us:

poop
Please input a word:
That's correct!
That's not correct!

So clearly those strings are still floating around in the file. What’s the rest of this stuff? Volumes of documentation exist out there on the Mach-O file format, but I don’t want to bog down in the details. I have to level with you here—I honestly don’t actually know much about it. Analogizing from other executable formats I’ve seen before, I know there’s probably a header of some kind that helps the operating system know what kind of file this is and points out how the rest of the file is laid out. The rest of the file, incidentally, is made up of sections which may contain any of a number of things, including data (the strings in this case) built into the program; information on how to find code called from elsewhere in the system (imports, like our printf and strcmp functions, among others); and executable machine code.

Disassembling the Program

It’s the machine code we’re interested in now. This is the interesting part! Machine code is binary data, a long string of numbers which correspond to instructions the processor understands. When we run our program, the operating system looks at the file, lays it out in memory, finds the entry point, and starts feeding those instructions directly to the processor.

If you’re used to scripted programming languages, this concept might seem a little odd, but it bears on what we’re about to do to our binary. There’s no interpreter going over things, checking stuff, making sure it makes sense, throwing exceptions for errors and ensuring they get handled. These instructions go right into the processor, and being a physical machine, it has no choice but to accept them and execute each one. This knowledge is very empowering because we have the final say over what these instructions are.

As you may know, the compiler gcc translated my source code I wrote earlier into machine language (and packaged it nicely in an executable file). This allows the operating system to execute it directly, but as another important consequence of this process, we also no longer need the source code. Most of the programs you run likely came as binary executables without source code at all. Others may have source code available, but they’re distributed in binary form.

Whatever the case, let’s imagine I lost the source code to program up above and can’t remember it. Let’s also imagine I can’t even remember the password, and now my program holds hostage important secrets.

You might think I could run the binary through the strings utility, hoping the password gets printed out, and in this case, you’d be on the right track. Imagine if the program didn’t have a single password built in and only accepted passwords whose letters were in alphabetical order or added up (in binary) a specific way. Without the source code, I couldn’t scan to see which strings seem interesting, and I wouldn’t have a clue what to type in.

But we don’t need to lose heart because we already know that the program contains machine code, and since this machine code is meant to be fed directly to the processor, there’s no chance it’s been obfuscated or otherwise hidden. It’s there, and it can’t hide. If we knew how to read the machine code, there would be no need for the source code.

Machine code is hard for a human to read. There’s a nice GNU utility called objdump which helps enormously in this respect. We’ll use it to disassemble the binary. This process is called “disassembly” instead of “decompilation” because we can’t get back the original source code; instead we can recover the names of the instructions encoded in machine code. It’s not ideal, but we’ll have to do our best. (Many people use a debugger to do this job, and there’s a ton of benefits to doing so, like being able to watch instructions execute step by step, inspect values in memory, and so on, but a disassembly listing is simpler and less abstract.)

I looked up the documentation for gobjdump (as it’s called on my system) and picked out some options that made sense for my purposes. I ended up running gobjdump -S -l -C -F -t -w program | less to get the disassembly. This is probably more than we’d care to know about our program’s binary, much of it mysterious to me, but there’s some very useful information here too.

The Disassembly

I’ll share at least what I can make of the disassembly. At the top of the listing is some general information. This symbol table is interesting. We can see the names of the functions I defined. If I had truly never seen the source code, I would at this point take an especial amount of interest in a function called is_valid, wouldn’t I?

Immediately below this is a “Disassembly of section .text”. I happen to know from past experience that the “.text” bit is a bit misleading for historical reasons; a “.text” section actually contains machine code! The leftmost column contains offsets (the place in the file where each instruction begins). The next column is the binary instructions themselves, represented in hexadecimal. After that are the names and parameters of each instruction (sometimes with a helpful little annotation left by objdump).

Of course, the very first thing I see is the instructions of the is_valid function.

Disassembly of section .text:

0000000100000e10  (File Offset: 0xe10):
   100000e10:   55                      push   %rbp
   100000e11:   48 89 e5                mov    %rsp,%rbp
   100000e14:   48 83 ec 10             sub    $0x10,%rsp
   100000e18:   48 89 7d f0             mov    %rdi,-0x10(%rbp)
   100000e1c:   48 8b 7d f0             mov    -0x10(%rbp),%rdi
   100000e20:   48 8d 35 33 01 00 00    lea    0x133(%rip),%rsi        # 100000f5a <strcmp$stub+0x4a> (File Offset: 0xf5a)
   100000e27:   e8 e4 00 00 00          callq  100000f10 <strcmp$stub> (File Offset: 0xf10)
   100000e2c:   3d 00 00 00 00          cmp    $0x0,%eax
   100000e31:   0f 85 0c 00 00 00       jne    100000e43 <is_valid+0x33> (File Offset: 0xe43)
   100000e37:   c7 45 fc 01 00 00 00    movl   $0x1,-0x4(%rbp)
   100000e3e:   e9 07 00 00 00          jmpq   100000e4a <is_valid+0x3a> (File Offset: 0xe4a)
   100000e43:   c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%rbp)
   100000e4a:   8b 45 fc                mov    -0x4(%rbp),%eax
   100000e4d:   48 83 c4 10             add    $0x10,%rsp
   100000e51:   5d                      pop    %rbp
   100000e52:   c3                      retq   
   100000e53:   66 66 66 66 2e 0f 1f 84 00 00 00 00 00  data16 data16 data16 nopw %cs:0x0(%rax,%rax,1)

This is super exciting because we’re about to read assembly language. There are lots of books and sites on this subject, and my own understanding of assembly language is a bit rusty from years of disuse, but I know enough to get the gist. Let’s break it down.

  • The first three instructions (the first three lines, starting with 100000e10) are a preamble that begin most functions in assembly language generated by a compiler. They’re not important for us. (It saves the old frame pointer, gets a new frame pointer, and clears space on the stack for locals.)
  • The next two instructions set up for our strcmp function. This looks a bit odd in assembly language compared to what we’re used to. The mov instructions are shifting data from a location in memory to a register and vice versa. Because registers are involved, the disassembly wasn’t able to hint very well what these values may be, but we can guess it’s moving the strings to compare into place. I know this because of the calling convention for the function call (basically, set up the data and then make the call, which will know where to find the data); because the %rbp is the base register, which usually points to data; and because -0x10(%rbp) is a way of saying “look sixteen bytes earlier in memory than the address in the %rbp register.”
  • The lea and callq instructions load and call the strcmp function using the parameters we just moved in place. That function lives elsewhere in the system, so some magic happens here to transfer control of our program to that function.
  • By the time we reach the cmp instruction, strcmp has done its thing and stored its result in the accumulator register %eax. By convention, return values usually live in %eax, so given that we’re using a cmp (“compare”), and it’s acting on %eax and $0x0 (a zero), it’s a safe bet we’re checking to make sure strcmp returned zero. This instruction has the side effect of setting a flag in the processor called ZF to either 1 or 0, depending on if the comparison is true or not.
  • The next instruction is jne which is short for “jump if not equal.” It checks the ZF flag, and if it’s zero, skips ahead twelve bytes (bypassing any instructions in the intervening space).
  • That’s followed by a movl and a jmpq. These instructions move a 1 into a location in memory and skip ahead another seven bytes. Look at the two-digit hexadecimal numbers to the left of these two instructions. They add up to twelve!
  • Likewise, after these instructions, one other instruction moves the value 0 into the same location of memory and continues ahead. This instruction is exactly seven bytes long. So these jumps accomplish one of either two things: either the memory location -0x4(%rbp) is going to hold a 1 or a 0 by the time we get to the final mov. This is how assembly language does an if—a very interesting detail we’ll return to.
  • That last mov puts the value at -0x4(%rbp) (we just saw it’s either a 1 or a 0) into %eax, which we know is going to be the return value.
  • Finally, the function undoes the work from the preamble and returns. (After that is some junk that’s never executed.)

That was a lengthy explanation, so to sum up, we learned that the binary executable has a function called is_valid, and this function calls strcmp with some values and returns either a 1 or a 0 based on its return value. That’s a pretty accurate picture based on what we know of the source code, so I’m pleased as punch!

Directly below the definition for this function is the main function. It’s longer, but it’s no more complex. It does the same basic tasks of moving values around, calling functions, inspecting the values, and branching based on this. Again, the values are difficult to get insight into because many registers are used, and there’s a bit more setup. For the sake of brevity, I’ll leave analyzing this function as an exercise for the reader (I promise it won’t be on the test).

Breaking the Program

Remember, we don’t have the slightest idea what the password is, and there’s no good indication from the disassembly what it might be. Now that we have a good understanding of how the program works, we stand a good chance of modifying the program so that it believes any password is correct, which is the next best thing.

We can’t modify this disassembly listing itself. It’s output from objdump meant to help us understand the machine code (the stuff in the second column). We have to modify the program file itself by finding and changing those hexadecimal numbers somewhere in the file.

After looking over how both is_valid and main work, there are lots of opportunities to change the flow of the program to get the result we want, but we have to stay within a few rules. Notice how a lot of the instructions specify where other parts of the program are in terms of relative counts of bytes? That means that we can’t change the number of bytes anywhere, or else we’d break all the symbol references, section locations, jumps, offsets, and so on. We also need to put in numbers which are valid processor instructions so that the program doesn’t crash.

If this were your first program, I’d be forced to assume you wouldn’t know what numbers mean what to the processor. Luckily, the disassembly gives us hints on how to attack it. Let’s confine our possibilities (such as changing jump logic or overwriting instructions with dummy instructions) to only those we can exploit by using looking at this disassembly itself. There isn’t a lot of variety here.

To me, one neat thing about is_valid stands out. Two of the lines are extremely similar: movl $0x0,-0x4(%rbp) and movl $0x1,-0x4(%rbp). They do complementing things with the same memory location, use the same number of bytes (seven), involve the same setup, are near one another, and directly set up the return value for is_valid. This says to me the machine code for each instruction would be interchangeable, and by changing one or the other, we can directly change the return value for is_valid to whatever we want. It’s a safe bet, with a function named that, we want it to return a 1, but if we weren’t sure, I could look ahead to the main function and see how its return value gets used later on.

In other words, we want to change movl $0x0,-0x4(%rbp) to be movl $0x1,-0x4(%rbp) so that no matter what, is_valid returns a one. The machine code for the instruction we have is c7 45 fc 00 00 00 00. Conveniently, the machine code for that precise instruction we want is just two lines above: c7 45 fc 01 00 00 00. The last challenge ahead is to find these bytes in the actual file and change them.

Where in the file are these bytes? Note that the listing says “File Offset: 0xe10” for the function is_valid. That’s actually the count of bytes into the file we’d find the first instruction for this function (3648 bytes, in decimal), and the offset in the left column for the first instruction is “100000e10”, so those offsets in the left column look like they tell where in the file each instruction’s machine code is. The instruction we care about is at “100000e43”, so it must be 3651 bytes into the file. We only need to change the fourth byte of the instruction, so we can add four to that count to get 3655 bytes.

Using hexdump -C program | less and scrolling ahead a bit, I find a line like this one:

00000e40  00 00 00 c7 45 fc 00 00  00 00 8b 45 fc 48 83 c4  |....E......E.H..|

Sure enough, there’s the instruction, and the seventh byte on this line is the one we want to change. Patching a binary file from the command line is sort of difficult, but this command should do the trick:

printf '\x01' | dd of=program bs=1 seek=3654 count=1 conv=notrunc

dd is writing to the file program (of=program), seeking by one byte at a time (bs=1), skipping ahead 3654 bytes past the first one to land on 3655 (seek=3654), changing only one byte (count=1), and not truncating the rest of the file (conv=notrunc).

Now I’ll run the program the same way we did before (./program) and see if this worked.

Please input a word: butts
That's correct!

Success!

Conclusions

That’s about it. It’s a contrived example, and I knew it would work out before the end, but this is a great way to start learning how programs are compiled, how processors work, and how software cracking happens. The concepts here also apply themselves to understanding how many security exploits work on a mechanistic level.

Clarity Through Static Typing

I can’t seem to find much discussion online contrasting dynamic and static typing as teaching tools. Others have covered the technical merits up and down, but I wanted to make a case for static typing for teaching new programmers.

It’s true that it’s easier, even necessary, to elide abstract concepts like types when first starting out. Dynamically typed programming languages (like Python, Ruby, or JavaScript) allow learners to get started quickly and see results right away. It’s important not to underestimate the importance of that quick, tight feedback loop! While getting started, students don’t need to know that “Hello World” is skating on layers of abstractions on the way to the screen.

At the risk of veering into criticizing dynamic typing itself (which isn’t my intention!) languages like Ruby and Python unfortunately also lengthen the feedback cycle between making certain kinds of mistakes and seeing an error produced from them. In the worst cases, the error becomes much more difficult to understand when it occurs. Testing becomes crucial to ferret out these kinds of errors.

That’s a relatively minor concern of mine, though. I’m more concerned about what happens when a student turns into a new programmer interacting with a non-trivial system. It’s inevitable that a new programmer will have to learn an existing complex system—if not on the job, then at the least while learning a web framework. At this point, she will have to use or modify some part of the system before understanding the whole. In other words, a new programmer will have to point at a symbol or word on the screen and ask, “What is that?”

In a language like Ruby or Python, it literally takes longer to figure out what a variable on the screen represents, and it sometimes requires searching through many files and holding many abstractions in your head to understand any non-trivial piece of source code. Using or modifying a complex system requires deeper and more expert knowledge of the system. It’s for this reason that I feel static typing helps peel away abstractions. It also makes information about the system more explicit, closer at hand, and more readily searchable.

I find it ironic in the case of Python especially. “Explicit is better than implicit,” say the Pythonistas—except when it comes to types?

Most of the Mistakes

When I interviewed at Simple, I wanted to get across one very important thing—if I got hired, I would begin by making every possible mistake, but I would only make each mistake once.

I think enough time has passed that I’ve managed to make most of the mistakes I needed to get past feeling stuck. Five months in, and I’m finally feeling like I’m contributing steadily. My world at work has also widened, putting me in contact with other teams.

One of the major shortcomings of my last job was that I found I spent so much time helping with maintenance that I never got to create things. Programming actually became a rare part of my job. I spend almost every day at Simple actually programming, and I’m really thankful for that. Not necessarily because I enjoy programming in and of itself (that comes and goes) but because I get to have a say in how things work, and I get to help drive us forward.

Greater Evils, or, Where My Code Lives Now

I’m going to tear down my GitLab instance and just host my programming things on GitHub. It comes down to the ready-made community, the well-worn functionality (everything will always just work), and the ease of not having to host a complex web app.

Less soul searching went into this decision than usual, and I know I’m making the wrong decision. It’s wrong on its face, to me, but I make wrong decisions like this all the time. I’m still using Twitter, for example, even knowing my content is monetized on my behalf. I think the only thing that’s changed is my drained wherewithal to fight back quotidian evils.

If you find my blog where before you found my GitLab site, now you know why. I haven’t moved absolutely everything, so let me know if something’s missing you’d like to look at.

What I Need from a Notes App

Here’s what I want from an ideal note-taking application.

  • Runs on every conceivable platform. May or may not include a degenerate web app. This is the one thing Evernote nails.
  • Uses keyboard input intelligently. For example, a quick, judicious asterisk creates a list on the fly. A tab can easily kick off a table. Quick calculations are performed inline. This is something OneNote has done well.
  • Allows completely free-form control over what’s already input. I can select and cordon off something and pull it aside somewhere else. Whitespace expands infinitely in any direction to accommodate. Items (be they drawings, text, or whatever else) can be moved around, side by side or similar.
  • As a corollary, input with structure can be restructured. Lists are dynamic outlines that can be rearranged, re-nested, and so on. Tables’ rows and columns can be dragged around. Grippy handles on things abound to accommodate this.
  • Accepts any manner of input and handles it intelligently: audio recordings; drawing with mouse, finger, or stylus; dragged-and-dropped files, which can be inlined as images or rendered as documents if applicable.
    • Bonus points if the app can index all these things (handwriting analysis, image OCR, audio speech recognition).
  • Organizational scheme with at least two tiers above the note level. OneNote had/has notebooks, sections, and pages (notes).
  • Extremely configurable appearance of notes, easily templated. Organizational scheme is easy to configure (names, colors).
  • Preferably professionally designed.
  • Rock-solid brain-dead sync between devices, preferably with encryption on the client side.

I can sum up the above by saying that I want a large, free-form space that accepts anything from anywhere and tries to do something smart with it. I realize this is a tall order. I’m surprised to hear that this doesn’t exist, though, not even for an exorbitant price (which I’d pay for something which came close). If someone comes across something like this, let me know.

The Discomfort of Being New

It’s sort of incredible after all this time that I get so uncomfortable with not knowing all the answers. Setting aside my personal and spiritual development (“What is the stars, what is the stars?”), I also stumble over this issue professionally.

I finished my fifteenth week at the Simple last Friday, and during my short tenure, we experienced one of the most trying times in our short history. It has been a difficult time to ramp up, and I’m still pretty new to having a programming job at all. The first of August marks three years since I started at the first one. I learned a lot at my last place, but I’m probably still a little too green to hit the ground running the way I’d like.

Now in my second programming job, I’ve identified a pattern that may have more to do with me than with the jobs I find myself in. I get frustrated very quickly when I’m unsure what to do. I haven’t always dealt with it very well. I expect to sail forward without bumps. Instead, I quickly blame setbacks on lack of process, documentation, opaque code, bad tests, unfamiliar culture, and a number of other externalities. The truth has a lot to do with just being new. I can’t speed past it, avoid it, or outsmart it. There’s no other way to become a veteran than by the pain of experience.

It’s like I’m so used to being able to hand in my test first in science class, and now in calculus I’m squirming while watching the others looking breezy. I figure it’s the teacher’s fault, curse the awful textbook, and complain how uncomfortable my chair is.

If I get to a point where I can internalize the discomfort, I start beating myself up with it instead. I finally reached that point a couple of weeks ago. I began questioning myself. I don’t have any good coping tactics for this stress. I’ve found I end up swinging to the other extreme; it’s not everything around me being awful and wrong, it’s just me. I feel like a new firefighter losing control of the hose, watching the fire burn out of control and screaming apologies.

It’s neither of those extremes. It’s just being new, and it’s uncomfortable. I’m in the same boat everyone’s spent time in. Whatever I do, as long as I hold faith with the process, it’ll pass.

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!