Writings of a techie wizard
Thu, 15 Dec 2011
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.
Tue, 29 Nov 2011
Wed, 23 Nov 2011
Tue, 22 Nov 2011
Fri, 14 Oct 2011
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.
Sat, 08 Oct 2011
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.
Mon, 26 Sep 2011
Wed, 14 Sep 2011
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.
Sat, 10 Sep 2011
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.
Thu, 01 Sep 2011
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?
Open Source Projects
Old Open Source Projects
Copyright © 2011-2015
by Peter A. Donis
All Rights Reserved