Years ago, Doug McIlroy, the inventor of the Unix pipe, published a paper on techniques for computing the terms of power series. The paper talks about a number of key concepts in programming, such as "lazy" evaluation, that were not well supported by most programming languages at the time, which is why McIlroy spent a good portion of the paper describing an implementation of his techniques in a new language designed by Rob Pike.

I came across this paper recently and realized that Python's generators would be a perfect fit for representing power series. They support all the key techniques McIlroy described, particularly "lazy" evaluation (a generator doesn't compute any specific term of its series until it is asked for it in sequence). You can see the Python implementation I came up with on github here. A particularly neat feature is that you can recursively include a Python generator in itself; this allows the recursive nature of many power series to be directly represented in the code. For example, here's the exponential series:

def _exp():
    for term in integral(EXP, Fraction(1, 1)):
        yield term
EXP = PowerSeries(_exp)

No monkey business with factorials; just a generator that recursively integrates itself. This same trick also works for implementing operations on power series; for example, any series can be exponentiated by a method similar to the above. The reciprocal and inverse operations on series use similar tricks, which basically make the code look just like the mathematical descriptions of those operations in McIlroy's paper.

Once I got the Python implementation working smoothly, I began checking online to see what other recent implementations of these techniques existed, and found that McIlroy posted an implementation in Haskell on the web in 2007. All of the key operations are one-liners. This is possible because Haskell has built-in support for expressing these operations declaratively, instead of having to define functions and use for loops and so on. So in a sense, my Python implementation is a case of Greenspun's Tenth Rule. But it's still fun.

I thought I was done with this topic for now, but I can't help adding one more quick post, because it now appears that it isn't just media companies who want to put a stranglehold on the Internet. Chanel is getting in on the act.

Read more...

This is just a quick update to yesterday's post. According to Ars Technica,

Last Thursday, the European Parliament adopted a resolution ahead of a forthcoming summit between Europe and the United States. It included a section on "the need to protect the integrity of the global Internet and freedom of communication by refraining from unilateral measures to revoke IP addresses or domain names."

That provision was added at the urging of the civil liberties organization European Digital Rights (EDRi). In a presentation to the Parliament's Civil Liberties Committee, EDRi's Joe McNamee noted that "the United States has, up until recently, never sought to exploit its theoretical jurisdiction over the companies and infrastructure that are at the core of the Internet."

Read more...

I've posted twice now about the Protect IP Act, or SOPA (the former is the Senate version, the latter is the House version), which is the latest attempt on the part of big media companies to put a stranglehold on the Internet.

Read more...

Amidst all the news about Steve Jobs' passing, you may not have heard that Dennis Ritchie, creator of the C programming language and one of the original designers of Unix, also passed away this past weekend.

Read more...

Unusually for me, this post will be almost entirely links to and quotes from articles by others. But I should explain briefly why I'm linking to them and quoting them. It's not to set the stage for my own comments about Mac OS X, or about iPods and iPads and so forth. I made comments about OS X in an earlier post, and there's no need to rehash them here. Nor do I have any personal anecdotes to share. My reason for linking to these articles, and quoting briefly from them, is, quite simply, to draw attention to what they say.

Read more...

I've seen a number of online articles and blog posts recently with the common theme of being uncomfortable with Facebook. For instance, this at Slate, or this from a programmer, or this from a Facebook developer.

Read more...

This is a culture interlude, not a nerd interlude, although of course the kind of culture I'm about to focus on might well be called nerdish. A new production of Le Carre's classic spy novel, Tinker, Tailor, Soldier, Spy is out. A short video of the cast at the premiere in Britain is here.

Read more...

Having spent enough time using all three of the major OS's to have a decent understanding of their flaws, it's easy to explain why I use Linux whenever I have a choice: its flaws are much easier to manage.

Read more...

Unless you're a Linux nerd like me, you probably didn't hear that the kernel.org site, the "home" of the Linux kernel and the "official" place to get a copy of its source code, was recently cracked. As far as I can tell from the Internet oracle, this hasn't made the news outside of the Linux developer and distribution community. If you're a conspiracy theorist, you might be thinking that this not making the news is some kind of nefarious scheme to hide flaws in the security of Linux. When a bank's server gets cracked, everybody finds out in a New York minute. Why should Linux's kernel source be any different?

Read more...