Parallel Map

… in JavaScript.

A number of events and coincidences have reminded me about functional programming and parallelism lately, especially an example I saw of Clojure’s pmap:

pmap
function
Usage: (pmap f coll)
       (pmap f coll & colls)

Like map, except f is applied in parallel. Semi-lazy in that the parallel computation stays ahead of the consumption, but doesn’t realize the entire result unless required. Only useful for computationally intensive functions where the time of f dominates the coordination overhead.

I’ve heard, for a long time, the argument that functional programming offers a programming style better suited for parallelism. After all, MapReduce is perhaps the ultimate form of famous-brand massive parallelization. In a typical map operation, you don’t have to worry so much about all the nasty little parallelism problems since your code, by convention, is side-effect free.

parallelmap

So, as my contribution to the world of JavaScript hackery, here’s parallel map in JavaScript:

parallelmap(proc, tasks, callback)

where proc is a function that takes one argument, tasks is an array of things, and callback is a function that will be called with the results when processing has completed. The computation will occur in parallel and show dramatic speedups on processing-intensive tasks.

Continue reading Parallel Map

Ants on the brain

Google AI Challenge—Week 2:

I think my ants are losing faith in me, as I haven’t uploaded a new version of my AI to the official server for a couple days now. New things are still in the pipeline, but I’ve lost my last 3 matches (though my opponents were ranked higher than me and probably deserve it too).

IU now has more than 5 people with active submissions, but the upcoming CS Club Hackathon will change that! I’m excited to co-organize the hackathon, which will consist of an all-day coding party dedicated to writing an ants AI. Dustin and I, as organizers, will be running matches and generally running things, and since we already have entries in the competition, we’ll be helping other aspiring antlords to get their own AI up and running.

Thanks to the school, we should have a competition server up and running soon, as opposed to running an unofficial TCP server. Prizes will also be offered to our hackathon winners, so I hope to see some creative strategies. I expect that there will be somebody wanting to use Haskell or JavaScript, but we’ll see how far they get.

Of course, I’ve been thinking about people’s choices of languages in the competition. The top-ranking bots are mostly “industry” languages like C++, Java, and Python, but there are a couple bots written in Go, OCaml, and Pascal up there. There’s definitely a trade-off between compiled languages like C and C++ and higher-level languages like Java and Python. In this competition, time is becoming a sticking point on many bots—you simply can’t run A* on as many ants in Java as you can in C. On the other hand, the time I’ve spent debugging memory errors could have probably been spent on improving my AI strategies.

Language designers are working to pull together this gap between productivity and speed: Google’s Go combines garbage collection and better concurrency models with the spirit of C, and Rust is another interesting but young language out of Mozilla. In the meantime, Java bot writers in the competition are just making do with timers to keep track of when to stop their calculations.

Some interesting sorting algorithms

Walking back from Falafels today with CS majors, we somehow began discussing strange sorting algorithms.

A good sort to know (not really) is bead sort. Imagine you have a bunch of beads on rods, like an abacus, and cross-wise they represent numbers. If you simply tilt the whole thing over, then gravity will let them all fall and they’ll sort themselves. For example, we have the numbers 3, 2, 4, and 2 read horizontally. When they fall, we get 2, 2, 3, 4. Easy!

Another sort, “random sort,” “shuffle sort,” or the more common name “bogosort” was suggested as a good example of an O(∞) algorithm. But, as people have pointed out, if the quantum many-worlds theory holds, then you could sort in O(n) time: Use true quantum randomness to randomize the list and if the list is not sorted, then destroy the universe. The only universe that remains will have a sorted list.

Finally, Graham showed me the wonders of sleep sort. I’ll just leave the bash source code here:

seq="1 9 2 3 5 6 4 7"
for i in $seq; do
    (sleep $i;echo $i)&false;
done

git-dude, meet hg-dude

Git-dude is a cool little thing. Given a directory of git repos, it continually fetches updates and displays a popup if you get any new commits. When I first saw it on Google Plus, somebody inexplicably commented, “This is a neat thing and I dont [sic] think there is a mercurial equivalent.”

Given that Git and Mercurial are isometric for most intents and purposes, this baffled me. Clearly, this could not be some special Git-exclusive functionality. I dug into the git-dude source code and found out it was little more than a single bash script that pipes some git commands through sed and awk.

A few minutes later, I made hg-dude, which offers similar functionality for Mercurial. There’s a couple things that aren’t supported. Git-dude offered special notifications for tags and branches, and I didn’t translate them to Mercurial because the concepts, even though they have similar names, don’t quite match up. Regardless, it is still as useful as git-dude for commit notifications, which I expect is the primary usage.

Some may notice the irony of hosting a Mercurial tool on Github, but that was the easiest way to preserve its history from its git-dude days. Bitbucket fans can check out hg-dude’s Bitbucket repo.

Get hg-dude at Github or Bitbucket.

WordPress permissions on NearlyFreeSpeech.net

“To perform the requested action, connection information is required.”

My earlier post on WordPress with NearlyFreeSpeech.net was too hastily written. There are more issues than WP not wanting to use the direct upgrader, and editing WordPress code is not the right way to solve it either.

Problem 1: WordPress doesn’t want to use the direct upgrader. You can force it to use the direct upgrader by adding define('FS_METHOD', 'direct'); to /wp-config.php.

Problem 2: WordPress may not have write access to certain directories. The wp-content directory, for example, would need to be chgrp to web and chmod to 775 in order for WordPress to update the things within. Of course, there is the option of just doing that on all of your WordPress files.

Problem 3: WordPress will create files that you cannot edit. Files created by PHP will be owned by user ‘web’ and the permissions will be 644. That means you (“me”) cannot edit these files over SSH since you are not the owner. You can’t even delete, chown, or chmod the files. You’ll either have to get PHP to delete them or ask NFSN support to chown them for you. A workaround is to umask(002); to your wp-config.php, which makes files created by PHP group-writable. They will still be owned by web by default, but at least you can do something about it.

Problem 4: The default temp directory may not be accessible by PHP. NFSN’s FAQ for installing WordPress has instructions about this and a variant is given here. First, make a directory called ‘tmp’ in your WordPress root and give PHP permissions to write to it (chgrp to web and chmod to 775). Then, add define('WP_TEMP_DIR', dirname(__FILE__).'/tmp'); to your wp-config.php file.

Scheme in Javascript

Scheme’s power to simplicity ratio makes it a fun target for implementation. Today, I introduce a couple new ways of running Scheme powered by Javascript.

The first is an online Scheme interface that I’ve been working on sporadically for the last few months. Inspired by TryHaskell, it began as a series of patches to jquery-console, a jQuery terminal-ish plug-in. While my own Scheme-in-Javascript interpreter FoxScheme hasn’t yet reached a very featureful stage yet (macros are the next step), somebody else had created a similar system before me. It was a simple matter to replace FoxScheme with a different back-end system, in this case, Jason Orendorff’s Try Scheme.

Continue reading Scheme in Javascript

Convert PHP to static pages with GNU Make

I recently moved an old website to a new server. For performance reasons, the new server is running nginx instead of Apache, and didn’t have nginx set up to use PHP. (The optimal way, apparently, is to use PHP-FGM, which currently requires you to patch and build PHP yourself, at least until PHP 5.4).

That was fine, though, because this old site only really needed PHP for one little thing that we could do without. In fact, the primary reason for using PHP here was to essentially append the header and footer sections to each unique page. Basically, we had stuff like:

<?php include('../header.inc'); ?>
... page contents ...
<?php include('../footer.inc'); ?>

on every page. What I needed was an automated process to convert all of these PHP pages into static pages. GNU Make, of course, is the de facto standard for automating something like this. Let’s give it a go:

Continue reading Convert PHP to static pages with GNU Make

Android emulator temp directories

If you are using the Android SDK on a shared computer, you might run into the awesome “NAND: could not create temp file for system NAND” error. This is because “/tmp/android” is hardcoded into the emulator as the directory to start temporary files during emulation, and somebody else has likely claimed it first.

The easiest workaround is, if it won’t cause any problems, to delete or chown the /tmp/android directory, preventing anybody else from using it. If you must share, then you can set up the group so that multiple devs can access it.

But the best way, if you’re not the sysadmin, is to change the temp directory for yourself. You can modify the emulator and change the hardcoded values.

Run “vim -b tools/emulator” and search for “tmp/android” (which would be “/tmp\/android” in vim-speak). Overwrite the name android to something that doesn’t already exist, like “/tmp/anderic”, being careful not to change the length of the file.

Restart your emulator.

Our friend Scope

Scope is one of those things that is absolutely essential to understand as a programmer. If you don’t understand how a language handles scope, you are doomed to continue making difficult-to-understand mistakes and poor code design.

Scheme is a good platform for exploring how scope works for beginners, and the language features that it has distilled to the minimum form the basis of 99% of the cases you encounter from day to day.

Let’s look at one pattern that you’ll find in every jQuery plugin:

Continue reading Our friend Scope