Self-reproducing programs in Ruby

Self-reproducing programs, if you've never heard of them, are fascinating objects. This is Ken Thompson's description in his classic 1983 Turing Award address:

In college, before video games, we would amuse ourselves by posing programming exercises. One of the favorites was to write the shortest self-reproducing program. [...]

More precisely stated, the problem is to write a source program that, when compiled and executed, will produce as output an exact copy of its source. If you have never done this, I urge you to try it on your own. The discovery of how to do it is a revelation ...

Implementing the sieve of Eratosthenes using channels in Go

The Go language tutorial describes a concurrent prime number sieve, but also noted that it is not the most computationally efficient method. In fact, the algorithm is so bad that it is even slower than testing every natural numbers using trial division, which tries to divides each n by all primes p ≤ sqrt(n). In contrast, the described sieve trial-divides each n by all primes p ≤ n.

Understandably, the point of the language tutorial is to introduce Go's concurrency constructs and not the algorithmic efficiency of a particular example. But just right after seeing that example, I thought it ...

iPad haikus

Seeing this iPad haiku contest via twitter, I immediately fired up vim and wrote three entries:

iPad -- the fad
        whose rights to be tinkered must be bought!
Who would have thought.

On the margin
I tried to pad
my last theorem.
    'twas never written.

Computers that can't be programmed,
        be damned.
1 pad of paper,
        better!

Parallelized list-processing with stream.py

Version 0.8 of stream.py is out with a lot of goodies to make it easy to parallelize a pipeline. I have written previously that by expressing a list-processing task as a pipeline (or at least thinking of it as such), we can have parallelism for free. Well, at least as free as Python allows us to be. We can choose between threading and multiprocessing as our concurrency model: with first choice, we have shared-memory but no real concurrence of threads (thanks to the GIL), and with second choice, we have real multi-tasking but only under the tax of ...

Sugar-coating the App Engine remote_api

Since the 1.1.9 release, the Google App Engine SDK has come with a remote_api module which is a wonderful tool to interact with App Engine from your computer. However, using it involves a fair amount of boilerplate work which we can fortunately avoid.

Today, I will share with you a simple script – remote.py – which can do all the necessary staging in order for us to talk with our App Engine back-end at Google. remote.py provides a single function attach(host), which will configure the API to communicate with the specified host. This will allow us to ...

Using doctest.testmod() properly

The usual, library-recommended way of running all doctests in a Python module is:

if __name__ == '__main__':
    import doctest
    doctest.testmod()
This, however, has a flaw. __main__ always exits with status 0, which in Unix parlance signals that it has executed without errors where in fact some test cases might have failed. So instead, you should write:
if __name__ == '__main__':
    import doctest
    if doctest.testmod().failed:
        import sys
        sys.exit(1)
This way, it is possible to check if the doctests has succeeded programmatically from a shell script, which can be very useful when you have many test scripts to run. ■

Streamlined list processing aka. pipes in Python

One of the most widely admired contributions of Unix to the culture of operating systems and command languages is the pipe, as used in a pipeline of commands. — Dennis M. Ritchie [dmr]

If the pipe is so great; why, then, does your favorite modern, dynamic programming language not have pipes built-in?

If the idea is merely to direct the output of some computation to be the input of another, any programming languages with a procedure abstraction would let you do that simply by composition. Like this,

f(g(h(input)))

However, that is not a pipeline! The procedure f can ...

The art of stealing ideas

Good artists copy, great artists steal. — Pablo Picasso

The first time I learned about this quote, I was quite confused. It is considered immoral and unlawful to steal material goods, how could Picasso say that it is great to steal in the creative disciplines?

The answer I found lies in the subtle implication in the act of copying versus stealing. One can usually produce a replica of an original without wasting any brain power whatsoever; whereas stealing is much harder: it requires careful planning and deft execution. Most important of all, however, one steals only what is valuable and leaves ...