Installing GHC 6.10 on Ubuntu Intrepid

Ubuntu Intrepid has GHC 6.8, and from the looks of it so will Jaunty when it releases next month. What if you want to install something that requires GHC 6.10?

Roll up your sleeves and do it yourself. Well, somewhat. Most of the hard work has already been done for you, but there’s still a bit of manual effort involved.

First, naturally, is installing GHC 6.10 itself. Luckily, there’s a PPA on Launchpad with GHC 6.10 packages for Intrepid. Just add the following to your package sources in Synaptic (or your package manager of choice):

deb http://ppa.launchpad.net/someone561/ppa/ubuntu intrepid main
deb-src http://ppa.launchpad.net/someone561/ppa/ubuntu intrepid main

Then upgrade or install ghc6, ghc6-prof, ghc6-doc, and haddock.

Unfortunately, all the Haskell modules in Intrepid proper only work with GHC 6.8, so they’ll all be removed from your system if you’ve installed them from there. There are a few modules in the aforementioned PPA that will work with GHC 6.10, but for the most part you’re going to be on your own.

Relatively speaking, of course. All the Haskell modules in Hackage (which is basically the Haskell equivalent to CPAN in the Perl world) can be automatically downloaded and installed for you using cabal-install. While installing Haskell packages manually is pretty simple, cabal-install also does all the work of tracking down dependencies and installing them for you as well.

The only catch is that cabal-install itself relies on a handful of modules that aren’t included with GHC 6.10 itself, so you get a little practice installing Haskell packages manually anyway. The bare minimum you need to install yourself is:

The manual install procedure basically works out to be this:

$ tar zxvf package-version.tar.gz
$ cd package-version
$ runghc Setup configure
$ runghc Setup build
$ sudo runghc Setup install

The only gotcha is that you’ll be tempted to install parsec-3.0.0 instead since, well, it’s newer and shinier, right? Alas, cabal-install requires a 2.x version of the parsec module, and if it doesn’t find it during bootstrap, it will just tell you to install parsec without mentioning that it’s picky about the version.

Luckily for you, you’re following these instructions and installed parsec-2.1.0.1, so you won’t run into this. Now you need to install cabal-install:

$ tar zxvf cabal-install-0.6.2.tar.gz
$ cd cabal-install-0.6.2
$ ./bootstrap.sh

The bootstrap script will automatically fetch the other modules it needs (which it can do, since you kindly installed network-2.2.0.1) and put the cabal tool itself in ~/.cabal/bin/cabal.

Now, add that program to your PATH and run the following to have cabal fetch the list of available packages:

$ cabal update

As a side effect, it will also create a configuration file at ~/.cabal/config. By default, cabal will install modules in a user-specific directory. To install them system-wide under /usr/local, add the following to the config file:

user-install: False

Now if you want to install package whatever, just do this:

$ cabal install whatever

cabal-install will download the package and install it for you, along with any other packages it depends on. Now you’re all set to go.

If for some reason cabal-install fails when it tries to install a package, it might be that it for some reason failed to install a dependency of it. When I tried to install happstack, cabal-install bombed out, complaining it couldn’t install happy. Yet telling cabal-install to install happy worked fine, so I’m not sure why it never bothered to try to install it as a dependency when its error message clearly identified it as a required module for happstack. That’s something to try if you run into problems with cabal-install.

Congratulations! You’re now the proud owner of GHC 6.10 on Intrepid, with ready access to all the modules you could ever want.

Today is Pi Day, but to hex with it

Did you know it’s possible to directly compute individual digits of pi? The Bailey-Borwein-Plouffe formula below can be used to compute the nth digit of pi… in hexadecimal:

Bailey–Borwein–Plouffe formula

The basic idea is that the nth term of the above summation corresponds to the nth digit of pi when written in hexadecimal — that’s what the (1/16)n essentially means. Of course, since the rest of the term is hardly guaranteed to be an integer between 0 and 15 inclusive, each term “spills over” into the following decimal hexadecimal places, so you can’t just pluck out the nth term and expect it to give you what you want.

The trick, explained in more detail on the Wikipedia article on the formula, is to evaluate only as many terms as you need to include all the ones that could affect the nth digit, which basically means terms 0 through n+1. But since we don’t care what comes before that digit, we can multiply everything by 16n, which shifts the decimal radix point to the position immediately before the digit we want, and use modular arithmetic to throw away the whole part, leaving just the fractional part we’re interested in.

Here’s some Haskell code that implements the basic idea:

{-
- Simple implementation of using the Bailey-Borwein-Plouffe formula
- for computing individual hexadecimal digits of pi.
-
- Copyright (C) 2009 Paul Kuliniewicz <paul@kuliniewicz.org>
-
- This program is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2, or (at your option)
- any later version.
-
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- GNU General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02111-1301, USA.
-}
 
import Data.Ratio
import Numeric
import System.Environment
 
{-
- Compute b^e mod m, using the method of exponentiation by squaring.
-}
mod_exp :: Integral a => a -> a -> a -> a
mod_exp modulus base = by_squaring 1 base
    where by_squaring acc mult 0    = acc
          by_squaring acc mult expo = let next_mult = mult * mult `mod` modulus
                                          next_expo = expo `div` 2
                                      in  if odd expo
                                             then by_squaring (acc * mult `mod` modulus) next_mult next_expo
                                             else by_squaring acc next_mult next_expo
 
{-
- Compute the "whole" part of one of the BBP subterms, where "b" is the
- particular constant used in the subterm being computed.
-
-     n   16^(n-k) mod (8k + b)
-     E  -----------------------
-    k=0         8k + b
-}
bbp_subterm_whole :: Integral a => a -> a -> Ratio a
bbp_subterm_whole n b = sum $ map kth_term [0 .. n]
    where kth_term k = let modulus = 8 * k + b
                       in  mod_exp modulus 16 (n - k) % modulus
 
{-
- Compute the "fractional" part of one of the BBP subterms, where "b" is
- the particular constant used in the subterm being computed.
-
-     oo   16^(n-k)
-     E   ----------
-   k=n+1   8k + b
-
- Actually, assume that only the first term is going to have any
- influence on the first fractional hex digit, so what's *really*
- computed is:
-
-   n+1   16^(n-k)          1
-    E   ---------- = -------------
-  k=n+1   8k + b      16 (8k + b)
-}
bbp_subterm_frac :: Integral a => a -> a -> Ratio a
bbp_subterm_frac n b = 1 % (16 * (8 * k + b))
    where k = n + 1
 
{-
- Compute one of the four BBP formula terms.  Since they only
- differ by one of the constants used, the same code can be used
- to compute each of them.  (They also have different coefficients
- in the BBP formula itself, but we don't worry about that here.)
-}
bbp_term :: Integral a => a -> a -> Ratio a
bbp_term n b = bbp_subterm_whole n b + bbp_subterm_frac n b
 
{-
- Given a fraction, remove the whole part and return the
- fractional part.
-}
frac_part :: Integral a => Ratio a -> Ratio a
frac_part r = (numerator r `mod` denominator r) % denominator r
 
{-
- Given a fraction, remove the fractional part and return
- the whole part.
-}
whole_part :: Integral a => Ratio a -> a
whole_part r = numerator r `div` denominator r
 
{-
- Compute the nth hex digit of pi, where digit 0 is the first
- digit *after* the radix point.  Uses the BBP digit-extraction
- algorithm; see the Wikipedia article for a description of what
- this means and why it works.
-}
nth_hex_digit_of_pi :: Integral a => a -> a
nth_hex_digit_of_pi n =
    let subsum =   4 * bbp_term n 1 - 2 * bbp_term n 4 - bbp_term n 5 - bbp_term n 6
        shifted = 16 * frac_part subsum
    in  whole_part shifted
 
{-
- Return a string containing hex digits "begin" through "end" of pi,
- where digit 0 is digit *before* the radix point.  Note how the
- digit indexes are adjusted before calling nth_hex_digit_of_pi.
-}
hex_substring_of_pi :: Integral a => a -> a -> String
hex_substring_of_pi begin end
    | begin == 0   =  "3." ++ hex_substring_of_pi 1 end
    | begin > end  =  ""
    | otherwise    =  concat $ map (hex . nth_hex_digit_of_pi) [begin - 1 .. end - 1]
 
{-
- Helper function to convert an integer into a hex string.
-}
hex :: Integral a => a -> String
hex value = showHex value ""
 
{-
- Get the range from the user and print it out.
-}
main :: IO ()
main = do argv <- getArgs
          case map read argv of
               [digit]      -> putStrLn $ hex_substring_of_pi digit digit
               [begin, end] -> putStrLn $ hex_substring_of_pi begin end
               _            -> mapM_ putStrLn ["usage: bbp digit",
                                               "       bbp first_digit last_digit"]

It will let you compute an individual digit:

$ ./bbp 15
d

Or a range of digits:

$ ./bbp 10 20
5a308d31319
$ ./bbp 0 50
3.243f6a8885a308d313198a2e03707344a4093822299f31d008

While the last example shows you can easily use the program to compute the first n digits of pi, calculating each digit individually is slower than other approximation techniques.

And since someone’s bound to be wondering:

$ ./bbp 700
6

So close. But given that nobody writes jokes in base 13, it shouldn’t be surprising that nobody writes songs about pi in base 16 either.

Archive of Fools: Sideline Sermon

Continuing our series of five-year-old Ship of Fools videos I found archived away, here’s a performance of Sideline Sermon:

Sideline Sermon – Two preachers are delivering Sunday’s sermon to the congregation. Problem is, they can’t quite remember what they’re supposed to be preaching about, so they wing it until a few helpful parishioners can discretely mime them some clues. Who will win? On the left: Jon Heffley sermonizes, aided by Scott Yost (mostly offscreen) and Wes Allen. On the right: Chandler Murch sermonizes, aided by Paul Kuliniewicz and Colin Reindl. Brazenly flouting congressionally-mandated conflict-of-interest regulations, Colin Reindl also emcees.

Sideline Sermon was one of my favorite games to do, but one we didn’t do often at shows. I’ve seen other groups mishandle it by letting it drag on and on indefinitely if for some reason the person just isn’t getting it. It doesn’t have Chain Murder Mystery’s escape valve of “I don’t know what you’re doing, but I’ll make something up and keep going anyway”; in fact, it’s arguably funnier when that happens. Sideline Sermon also requires the sermonizer to continue talking coherently — or at least reasonable grammatically — when dropping their guesses. Fail that, and you’ve just got charades, and nobody came to watch that.

Luckily, the above video contains neither of those problems.

Comments Off

Lobbying group FAIL

If I were a lobbyist working on behalf of the tobacco industry, I’d probably wouldn’t pick a name that suggests we’re trying to sell cigarettes to children.

Apparently that makes me overqualified:

Bruce Bereano, a lobbyist representing the Maryland Association of Tobacco and Candy Distributors, called the measure an “anti-smoking” bill and said he finds it “very troublesome.” [emphasis added]

Really?

Comments Off

Wallace Jr. Grows On Trees

I’ve updated Wallace Jr. to support actual genetic programming, instead of just genetic algorithms. That is, Wallace Jr. now generates programs that try to play video games, instead of just generating predefined controller input sequences.

Naturally, the language used by Wallace Jr. for its evolved programs is extremely limited. In fact, it’s really more of a language for writing expressions rather than what you’d typically consider a “program”: there’s no variables or subroutines or even loops. Here’s the entire (informal) specification of the language:

Expression Definition
0x00, 0x01, …, 0xff Constants in the range 0 – 255
(+ a b) Add a and b, modulo 256
(- a b) Subtract b from a, modulo 256
(* a b) Multiply a and b, modulo 256
(& a b) Bitwise AND a and b
(| a b) Bitwise OR a and b
(^ a b) Bitwise XOR a and b
(ifgt a b t f) If a > b, return t; otherwise, return f
(read a) Return the byte at address a in sprite RAM

That’s it. By combining those operations, you can read data from sprite RAM (which among other things, will tell you where each sprite on the screen is at), do computations on them, and ultimately return a one-byte value interpreted as the next controller input.

Here’s an example of what a program written in this language would look like:

(& (+ 0x1b (& (- (| 0x77 (^ 0x60 (read 0x81))) 0x23) (& 0x10 (& 0x28 (read 0xbe))))) (^ 0x56 (ifgt 0x62 (read (ifgt (| (read 0xa8) 0xfe) 0x93 0x30 0x34)) 0x23 (ifgt (+ 0xbd (read 0x70)) (^ 0xef (- (read 0x33) 0x4d)) (+ (& 0x27 (& 0x78 (ifgt (read 0x58) 0x41 0x76 0xb6))) (^ (read 0xe7) 0x9c)) (+ 0xb0 (read 0x08))))))

Strictly speaking, none of the parentheses are necessary. Since the language uses Polish notation and each operation has fixed arity, parsing an expression is unambiguous even without parentheses — an advantage not held by the more conventional (to the average person, anyway) use of infix notation for arithmetic operations.

In other words, the above mess means the same thing as the following mess, where parentheses have been removed to, um, change readability. Whether readability is improved or hindered is left as an exercise for the reader.

& + 0x1b & - | 0x77 ^ 0x60 read 0x81 0x23 & 0x10 & 0x28 read 0xbe ^ 0x56 ifgt 0x62 read ifgt | read 0xa8 0xfe 0x93 0x30 0x34 0x23 ifgt + 0xbd read 0x70 ^ 0xef - read 0x33 0x4d + & 0x27 & 0x78 ifgt read 0x58 0x41 0x76 0xb6 ^ read 0xe7 0x9c + 0xb0 read 0x08

Maybe just drawing it as an expression tree would help:

Generation 3 top performer, optimized version
(click for full version)

In the tree, each term appears as a node, with the arguments to that term shown as children of the node. Evaluation of the expression goes from the bottom up; as new subterms are evaluated, the results get passed up until you reach the root node at the top, at which time you have the value of the expression.

The above expression was one generated in a run of Wallace Jr. in the fourth generation using pretty much the same input as last time, only using trees instead of controller input sequences. This time, the configuration looked something like this:

mednafen        /home/paul/mednafen-eval/instdir/bin/mednafen
 
buttons         right left up down b a
rom             /home/paul/roms/nes/Mega Man 2 (U).nes
initial_state   /home/paul/.mednafen/mcs/Mega Man 2 (U).0527a0ee512f69e08b8db6dc97964632.nc0
organism_type   tree
organism_size   1000
organism_depth  7
subtree_depth   4
granularity     5
population_size 500
generations     30
parallelism    2
debug           no
export_tail    1200
 
metric          health    0x06c0 1
metric          enemy     0x06c1 1
functions       megaman2.py
 
tournament_size             50
homologous_crossover_rate   0
arbitrary_crossover_rate    80
point_mutation_rate         5
subtree_mutation_rate       5
reproduction_rate           10
 
point_mutation_probability  0.05
crossover_leaf_probability  0.20

Here, Wallace Jr. is starting off with 500 randomly generated expression trees of maximum depth 7 — i.e., each starting tree has one root and up to seven levels below it. Each new generation is produced through crossover (swapping one node [and its children] with a node [and its children] from another tree), point mutation (randomly changing the content of some nodes without changing its arity), subtree mutation (replacing one node and its children with a randomly generated subtree), and reproduction (copying unchanged from the previous generation).

The fitness graph over 30 generations looked like this:

Fitness over 30 generations

It’s interesting how quickly things plateaued at a maximum fitness of 12 so quickly and never improved from there. Something similar happened last time, but not nearly so quickly. I’m not entirely sure why there was no improvement past a fitness of 12, but I suspect it’s because doing better than that actually requires fairly precise play. A fitness of 12 is about what you wind up with if you consistently deal damage to Air Man but get hit by a couple tornadoes between his jumps.

A little manual play lends some support to this hypothesis: taking the controller myself, my own fitness ranged from 12-16 most of the time, with 20 being a personal best. That 20 was very hard to come by, requiring some very carefully timed jumps to avoid near-unavoidable tornadoes. In this scenario, a fitness of 12 could be the point of diminishing returns, where each incremental improvement in fitness starts being much harder to come by.

Actually, when I said the expression I showed earlier was one generated by Wallace Jr., I lied. It’s actually an optimized version of this mess, which was the top performer in the fourth generation (and the first to achieve a fitness of 12):

Top performer of generation 3
(click for full version)

It’s quite a bit larger than the optimized version, since it’s doing silly things like computing (& 0x19 0x4a) each time instead of just using a constant 0x08. That’s pretty much all the optimizer in Wallace Jr. does, mainly to make the trees it generates more readable, or at least less unreadable, by simplifying things as much as possible.

After the third generation, there wasn’t any improvement in peak fitness. However, the expressions being generated tended to get bigger and bigger. Here’s the top performer of the thirtieth generation (or really, one of the many many trees tied for top performer), optimized:

Generation 29 top performer, optimized
(click for full version)

And in its full, unoptimized glory:

Generation 29 top performer, unoptimized
(click for full version)

Interestingly, if you compare the optimized versions of the Generation 29 top performer with the Generation 3 top performer shown above, you’ll see that the top four levels of the tree are, with the exception of one node, identical. This suggests the Generation 29 winner is descended from the Generation 3 winner. It would be interesting to study the full scope of their similarities, and the similarities with the winners in the intervening generations, to what parts of the expression are so seemingly essential that they’ve been preserved from one generation to the next.

For the time being, doing so is also left as an exercise for the reader.

Another dimension to the economic crisis

I’ve heard a lot of doom-and-gloom predictions about the effects of the current economic, *ahem*, “downturn”, but even the most pessimistic Cassandras didn’t foresee the reality that we now face: the day itself has now dropped by over 4%.

Some are saying that the drop would be even greater had it not been for TARP, the Temporal Assets Relief Program, begun in the waning days of the previous administration to give insolvent financial institutions more time to recover from their gross incompetence. (Fun fact: at AIG headquarters, today is officially only Thursday, June 4, 1992.)

I’ve heard rumors that Congress will soon start work on a chronological stimulus package to give average Americans more time as well. Insiders are expecting any such bill to get bogged down in debate — Republicans are expected to insist it consist primarily of tax cuts, for example — so I wouldn’t advise holding your breath. My best guess is that we won’t see anything come out of it until early November.

To be sure, there have been some other proposals for how to deal with the temporal recession, but quite frankly our nation doesn’t have the resources to implement them. Everyone knows the auto industry is on the verge of total collapse, so even if the DeLorean Motor Company were still around, they probably wouldn’t be for much longer. And with the popularity of cell phones having driven public telephone booths to near extinction, both in America and in the UK, those are hardly viable options either.

And that’s not even getting into the really crazy ideas like using ionized dihydrogen monoxide.

So what can the average person do to make the most of what little time he or she still has? Simple: move in to your basement. From general relativity, we know that gravity causes time to pass more slowly, and gravity is stronger the farther down you are. (And here you thought general relativity didn’t have real-world applications!) The magnitude of the time dilation may be small, but it’s still going to give you a better rate of return than your retirement account.

Besides, it’s not like you can stash time under your mattress anyway. I mean, then were would you put your life’s savings?

Archive of Fools: Chain Murder Mystery

Here’s the next video from the set of clips from a April 2004 Ship of Fools performance at Tarkington Hall:

Chain Murder Mystery – A murder has taken place! Only Chuck Allen has witnessed the location of the murder (a desert), the occupation of the murderer (a stripper), and the murder weapon (a silent fart). He must convey these three things to Paul Kuliniewicz, using only mime and gibberish. Paul must then convey them to Colin Reindl, who must then in turn convey them to Jon Heffley. After watching this hybrid of Clue and Telephone, you will understand why real murder investigations don’t work like this. Scott Yost is the emcee.

Archive of Fools: Two Person Story

In the process of setting up my new backup hard drive, I came across a small cache of Ship of Fools videos dating back from April 2004. Here’s one of them; I’ll let the description I wrote for YouTube set it up:

Two Person Story – two performers tell a story based on suggestions from the audience. Like all good stories, it starts with “once upon a time” and ends with a moral. The catch: they can only speak one word at a time. Here, Scott Yost (left) and Paul Kuliniewicz (right) relate the timeless classic, “Charlotte’s Web of Fighting”. Colin Reindl is the emcee.

I think this was from a performance at Tarkington Hall, but I can’t tell from the background for sure which residence hall this was at.

There’s another four videos where this came from. Stay tuned.

The Perils of Pipes

In my last post, I mentioned this in regards to making Wallace Jr. and my hacked version of Mednafen:

It’s not insurmountable, but having programs talk back and forth to each other is always a bit tricky, especially to avoid deadlocks: A is waiting for B to say something, and B is waiting for A to say something. Especially when B was never intended to talk to A to begin with.

My prediction of running into difficulties proved to be all too accurate, even despite expecting problems to arise and being exceedingly careful to avoid them. Sadly, this hardly qualifies to win the JREF prize, any more than predicting that the sun will rise tomorrow would.

Recall what I’m trying to do here: have Wallace Jr. generate a sequence of controller inputs, have Mednafen execute them while playing a game, and have Wallace Jr. evaluate what happens in the game as a result. This means there has to be bidirectional communication: one channel from Wallace Jr. to Mednafen, and a second from Mednafen back to Wallace Jr.

In the original design, the path into Mednafen was pretty simple, since the input sequence was predetermined. Wallace Jr. generated an MCM file (a Mednafen movie file, consisting of an initial state and, well, a sequence of controller input), saved it to disk, and told Mednafen where to find it when it was launched. Mednafen, in turn, printed out status information, which Wallace Jr. read at its leisure.

For those of you not familiar with programming, allow me to elaborate on that last part a bit. Most languages provide three standard input/output streams to programs: one for input (stdin), one for normal output (stdout), and one for outputing error messages (stderr). By default, when you run a program from the command line, stdin comes from the keyboard, and stdout and stderr get printed out to the terminal window. To the program, these three streams look just like any other file; in fact, in C they’re even represented as FILE *, the same as you’d get if you called fopen to open a file.

Since I said by default the streams are connected to the keyboard and the terminal window, that obviously implies this isn’t always the case. When you create a new process, you’re free to connect its standard streams to whatever you want. That’s what Wallace Jr. did: when launching Mednafen, it attached its stdout stream to a pipe, so that whatever Mednafen writes to it, Wallace Jr. can read it.

The current version of Wallace Jr. goes one further, attaching pipes both to Mednafen’s stdout and stdin streams:

child = subprocess.Popen ([self.executable_path,
                                "-video", self.debug and "1" or "0",
                                "-sound", self.debug and "1" or "0",
                                "-nothrottle", "1",
                                "-movie", "/dev/stdin",
                                "-metrics", self.project_file,
                                self.rom_file],
                            stdin=subprocess.PIPE,
                            stdout=subprocess.PIPE,
                            close_fds=1)

But wait, you object, the arguments I’m passing to Mednafen still tell it to read its movie from a file — particularly, a file named /dev/stdin. What gives? /dev/stdin is just a symlink to /proc/self/fd/0, which is in turn a symlink to whatever the current process’s stdin stream is. So really, giving Medafen a file name of /dev/stdin is just telling it to read from its stdin.

(If that sounds like some kind of voodoo to you, keep in mind that on Unix-based systems, everything is a file. Files in the conventional sense of “a bunch of bytes with a name and stored on a disk” is just one type of file — files can also be pipes or devices or almost anything else. Everything in /proc is some type of information about the processes running on the system, exposed as a set of files. The underlying data is stored not on disk, but in the kernel‘s internal data structures.)

Anyway, the ultimate goal in sending Mednafen controller inputs via a pipe instead of a file is so that, in the future, Wallace Jr. will be able to generate programs that decide the next controller input based on the current state of the game. To do that, obviously, it needs to see the game state at time t before the controller input at time t+1 can be sent. Writing all the controller input to a file ahead of time is right out.

If everything’s working, what should happen is that Wallace Jr. does a little processing, sends controller input to Mednafen, waits for Mednafen to respond with the game state, and repeats. Meanwhile, Mednafen waits for Wallace Jr. to send it controller input, emulates the next frame of the game, sends the updated game state to Wallace Jr., and repeats. If these ever get out of sync — namely, if both Mednafen and Wallace Jr. are waiting for the other to send something, you hit deadlock and nothing happens.

It’s easy to get wrong. Here’s two examples of how things went wrong.

As a proof-of-concept, I initially tried having Wallace Jr. send everything at once through the pipe. Deadlock. However, I found that if I closed Wallace Jr.’s side of the pipe going to Mednafen, it worked! That was weird, since I was being careful to flush the pipe after writing, to make sure the data was actually getting sent instead of sitting around in a buffer.

After banging my head against it for a while, I ultimately figured out that gzip was the culprit. Normally, Mednafen movie files, which is ultimately what’s being sent to it via the pipe, are compressed with gzip, and I initially had Wallace Jr. do so as well. Apparently, however, the code on the Mednafen side of things that handles decompression was waiting to reach the end-of-file before actually decompressing the data. That’s why Mednafen did nothing until Wallace Jr. closed its side of the pipe, which would cause Mednafen to finally detect end-of-file.

Naturally, closing the pipe isn’t an option when sending controller input one frame at a time, since there’s no way to re-open a pipe once it’s closed. Luckily, however, Mednafen is happy with getting uncompressed movie data sent to it; taking gzip out of the equation entirely fixed the problem.

The second deadlock I ran into took even longer to diagnose. Here’s a simplified version of the code that triggered it. What it’s supposed to do is generate the next input, send it to Mednafen’s stdin, and then read from Mednafen’s stdout until it sees a line that starts with “metrics”. When it does, it processes it and decides whether to loop or not. What it actually does is deadlock immediately when it tries to read from Mednafen. Do you see why?

while should_continue:
    controller_input = compute_next_input ()
 
    child.stdin.write (controller_input)
    child.stdin.flush ()
 
    should_continue = False
    for line in child.stdout:
        if line.startswith ("metrics"):
            should_continue = process_metrics (line)
            break

Your first guess is that Mednafen isn’t actually writing any lines that start with “metrics”. That wasn’t the problem. Your second guess is that Mednafen isn’t flushing its output buffer, so the line isn’t getting sent through the pipe. Wrong again.

Give up? I’m not surprised — it’s very non-obvious.

The “for line in file” construct in Python iterates through the contents of a file, one line at a time. Internally, this happens by Python invoking file.next() each time through the loop to get the next line. Here’s what the Python manual says about the next() method for file objects (emphasis added):

A file object is its own iterator, for example iter(f) returns f (unless f is closed). When a file is used as an iterator, typically in a for loop (for example, for line in f: print line), the next() method is called repeatedly. This method returns the next input line, or raises StopIteration when EOF is hit when the file is open for reading (behavior is undefined when the file is open for writing). In order to make a for loop the most efficient way of looping over the lines of a file (a very common operation), the next() method uses a hidden read-ahead buffer. As a consequence of using a read-ahead buffer, combining next() with other file methods (like readline()) does not work right. However, using seek() to reposition the file to an absolute position will flush the read-ahead buffer.

A hidden read-ahead buffer! next() is trying to be clever and trying to read more than just the next line, so it can pad out its buffer. However, Mednafen stops and waits for more input from Wallace Jr. after outputting a line, so next() waits for input that isn’t going to come until Wallace Jr. gets back to work. But that won’t happen until next() returns, which it won’t until it sees more input from Mednafen, even though it already has the line Wallace Jr. is asking for! Deadlock.

The fix is simple enough: use readline() to get the next line of the file instead of the nice syntactic sugar of the for loop, in order to avoid next()‘s read-ahead buffer:

while should_continue:
    controller_input = compute_next_input ()
 
    child.stdin.write (controller_input)
    child.stdin.flush ()
 
    should_continue = False
    line = child.stdout.readline ()
    while line != "":
        if line.startswith ("metrics"):
            should_continue = process_metrics (line)
            break
        line = child.stdout.readline ()

I would actually call next()‘s behavior here a bug. It’s perfectly reasonable for it to read past the end-of-line and buffer the excess, if there’s data after the newline. What’s happening internally is that the data next() got from the pipe ended with a newline, and it’s going ahead and trying to read from the pipe again just for the sake of filling its buffer. This actually decreases efficiency, since if next() isn’t going to be called again, it’s doing a read unnecessarily, at the cost of another system call. And if next() is going to be called again immediately, well, waiting to do the read until then doesn’t cost anything.

Of course, you wouldn’t notice the difference in practice, unless there’s no more data after the newline, but the file/pipe/whatever isn’t closed yet either. Which is exactly what happens in Wallace Jr.’s case.

The moral is: even if you know how tricky bidirectional interprocess communication is, it’s still trickier than you expect.