March 2009

In a previous post, I discuss my difficulties calling some Python modules from IronPython. In particular I wanted to call SciPy from IronPython and couldn’t. The discussion following that post brought up Ironclad as a possible solution. I wanted to learn more about Ironclad, and so I invited William Reade to write a guest post about the project. I want to thank William for responding to my request with a  very helpful article. — John

---

Hi! My name’s William Reade, and I’ve spent the last year or so working on Ironclad, an open-source project which helps IronPython to inter-operate better with CPython. Michael Foord recently introduced  me to our host John, who kindly offered me the opportunity to write a bit about  my work and, er, how well it works. So, here I am.

To give you a little bit of context, I’ve been working at Resolver Systems for several years now; our main product, Resolver  One, is a spreadsheet with very tight IronPython integration. We like to describe  it as a “Pythonic spreadsheet”, and that’s clearly a concept that people like.  However, when people think of a “Pythonic spreadsheet”, they apparently expect it  to work with popular Python libraries — such as NumPy and SciPy — and we found that IronPython’s incompatibility put us at a serious disadvantage. And, for some reason, nobody seemed very keen to  solve the problem for us, so we had to do it ourselves.

The purpose of Ironclad is to allow you to use Python C extensions (of which there are many) from inside IronPython without recompiling anything. The secret purpose  has always been to get NumPy working in Resolver One, and in release 1.4 we finally  achieved this goal. Although the integration is still alpha level, you can import  and use NumPy inside the spreadsheet grid and user code: you can see a screencast  about the integration here.

However, while Resolver One is a great tool, you aren’t required to use it to get the benefits: Ironclad has been developed completely separately, has no external  dependencies, and is available under an open source license. If you consider  yourself adequately teased, keep reading for a discussion of what Ironclad actually  does, what it enables you to do, and where it’s headed.

[click to continue...]

I stumbled across this quote from Mary Shaw.

Less than 10% of the code has to do with the ostensible purpose of the system; the rest deals with input-output, data validation, data structure maintenance, and other housekeeping.

I don’t know the context of her quote, but she could be talking about any software project.

When I began working as a professional programmer, I was surprised that I spent most of my time on work that wasn’t directly related to what I wanted to accomplish. Computer science classes and writing software for my own research had not prepared me for this. I kept thinking that as I got more experience, the proportion of my effort going directly toward what I wanted to accomplish would increase. It did, but very slowly, and never by very much. Only later did the reason occur to me: the vast majority of the work that needs to be done isn’t directly related to the purpose of the project.

People who know a little bit about programming can make difficult clients because they can imagine how they might write the core 10% (or maybe core 2%) of a large project.

Every once in a while someone will claim to have a solution that will change things. They’re selling a framework, a language,  etc. that will radically change things. The sales pitch is “You spend most of your time doing low-level stuff. Use my product and your programmers can focus on the value-added part and not do so much plumbing.” But plumbing is value-added work. (Call it “infrastructure” if you like; that sounds more important.) Sometimes plumbing work becomes repetitive and can be reduced by reusing code, but there’s always new plumbing to work on. Most of the work to be done is invisible and I don’t forsee this changing any time soon.

Update: See this list of non-functional requirements by Mike Griffiths. This list gives some specific examples of where development effort goes, things that must be done but are not obvious until you mention them.

A conversation at work this morning inspired a post on the Reproducible Ideas blog about preserving documents. Physically preserving documents may be the easy part. Keeping alive the memory that the documents exist can be much harder.

[The image above is a photograph of the Rosetta Disk, a disk preserving 13,000 pages of documentation about 1,500 human languages. The information is not encoded as bits; it is engraved. A thousand years from now, a scholar could read the disk using only a microscope. Click on the image for more information about the Rosetta Disk.]

There’s a new math blog, Numerical Recipes. The initial post says the blog will be understandable to anyone with a high school math background, will solve all problems in Python, and will not use any external libraries. The blog will also be available in Spanish.

The following story comes from Alton Brown’s book I’m Just Here for More Food, page 76.

Years ago Alton Brown ruined 50 pounds of dough by forgetting to add salt. By the time he remembered, it was too late. He threw the dough in dumpster behind the restaurant he was working in.

By noon, the temperature in the parking lot was edging toward 101°F. By 2:00 P. M. the lid of the dumpster started to rise. By 3:00 P.M. , grandson of the Blob was oozing out over the top of the dumpster and onto the pavement. … In the end, that 50-pound batch of dough completely filled the dumpster, and when the metal got hot enough, it baked onto the inside, making a real chore for those who had to clean it (meaning me).

He goes on to explain that throwing the dough out because he’d forgotten the salt made things worse: salt would have slowed down the fermentation in the dumpster. He concludes “So don’t forget the salt.”

Here are two complementary (but not entirely complimentary!) blog posts about C++.

Roshan James has a scathing article about C++. When asked to recommend books on C++, he replied that he doesn’t recommend C++. He explains how the best C++ books may be Scott Meyer’s series Effective C++ but argues that they should be called “Defective C++. ” He isn’t criticizing Scott Meyers, only the aspects of the C++ language that made it necessary for Scott Meyers to write such books. Effective C++ explains how to get around problems that don’t exist in more recent languages.

Bruce Eckel’s article The Positive Legacy of C++ and Java focused more on what C++ did well. C++ was designed to be backwardly compatible with C. Bjarne Stroustrup, original author  of C++, realized that the decision to be compatible with C would cause major difficulties, but he also thought (correctly) that without such compatibility no one would move over to the new language. Given this severe constraint, C++ has been remarkably well designed.

Update: Check out the C++ FQA site Alessandro Gentilini mentions in the comments. “FQA” is not a typo. It stands for Frequently Questioned Answers.

Sometimes when people say they want random points, that’s not what they really want. Random points clump more than most people expect. Quasi-random sequences are not random in any mathematical sense, but they might match popular expectations of randomness better than the real thing, especially for aesthetic applications. If by “random” someone means “scattered around without a clear pattern and not clumped together” then quasi-random sequences might do the trick.

Here are the first 50 points in a quasi-random sequence of points in the unit square.

By contrast, here are 50 points in a unit square whose coordinates are uniform random samples.

The truly random points clump together. Notice the cluster of three points in the top right corner. There are few other instances of pairs of points being very close together. Also, there are fairly large areas that don’t contain any random points. The quasi-random points by contrast are better spread out. They have a self-avoiding property that keeps them from clustering, and they fill the space more efficiently.

Quasi-random sequences could be confused with pseudo-random sequences. They’re not at all the same thing. Pseudo-random sequences are computer-generated sequences that in many ways behave as if they were truly random, even though they were produced by deterministic algorithms. For many practical purposes, including sensitive statistical tests, pseudo-random sequences are simply random sequences. (The “truly” random points above were technically “pseudo-random” points.)

The quasi-random points above were part of a Sobol sequence, a common quasi-random sequence. Other quasi-random sequences include the Halton sequence and the Hammersley sequence. Mathematically, these sequences are defined has having low-discrepancy. Roughly speaking, this means the “discrepancy” between the number of points that actually fall in a volume and the number of points you’d expect to fall in the same volume is small. See the Wikipedia article on quasi-random sequences for more mathematical details.

Besides being aesthetically useful, quasi-random sequences are useful in applied mathematics. Because these sequences explore a space more efficiently than random sequences, quasi-random sequences sometimes lead to more efficient high-dimensional integration algorithms than Monte Carlo integration. Quasi-Monte Carlo integration, i.e. integration based on quasi-random sequences rather than random sequences, is popular in financial applications. Art Owen has written insightful papers on Quasi-Monte Carlo integration (QMC). He has classified which integration problems can be efficiently computed via QMC methods and which cannot. In a nutshell, QMC works well when the effective dimension of a problem is significantly lower than the actual dimension. For example, a financial model might ostensibly depend on 1000 variables, but 50 of those variables contribute far more to the integrand than all the other variables. The integrand might essentially be a function of only 50 variables. In that case, QMC will work well. Note that it is not necessary to identify these 50 variables or do any change of variables. QMC just magically takes advantage of the situation.

One disadvantage of QMC integration is that it doesn’t naturally lead to an estimate of its own accuracy, unlike Monte Carlo integration. Several hybrid approaches have been proposed to combine QMC integration and Monte Carlo integration to get the efficiency of the former and the error estimates of the latter. For example, one could randomly jitter the quasi-random points or randomly permute their components. Some of these results are in Art Owen’s papers.

To read more about quasi-random sequences, see the book Random Number Generation and Quasi-Monte Carlo Methods.

Around 2000, some people believed that nearly all programming would be a matter of transporting and transforming XML. XML would be the universal data format, and all software would be a matter of transforming XML. If that were the case, then it would be very handy to use a language designed especially for transforming XML. That language was XSLT.

I’m sure some programmers write XSLT on a daily basis, and there’s probably a large amount of machine-generated XSLT out there. But it’s safe to say XSLT never became extremely popular. Maybe because the syntax is awkward. Not many developers like to write lots of angle brackets. Or maybe the declarative/functional style of the language isn’t as comfortable as a more imperative style of programming for most developers. I don’t really know. I thought XSLT sounded like a good idea, but I never learned it. My experience with XSLT consists of a few dozen lines I wrote six or seven years ago.

Along these lines, I ran across the following picture in a blog post entitled A picture is worth a thousand words: is XML dying? containing the following photo:

Apparently there’s no HTML entity for the flat symbol, ♭. In my previous post, I just spelled out B-flat because I thought that was safer; it’s possible not everyone would have the fonts installed to display B♭ correctly.

So how do you display music symbols for flat, sharp, and natural in HTML? You can insert any symbol if you know its Unicode value, though you run the risk that someone viewing the page may not have the necessary fonts installed to view the symbol. Here are the Unicode values for flat, natural, and sharp.

Since the flat sign has Unicode value U+266D, you could enter ♭ into HTML to display that symbol.

The sharp sign raises an interesting question. I’m sure most web pages referring to G-sharp would use the number sign # (U+0023) rather than the sharp sign ♯ (U+266F). And why not? The number sign is conveniently located on a standard keyboard and the sharp sign isn’t. It would be nice if people used sharp symbols rather than number signs. It would make it easier to search on specifically musical terms. But it’s not going to happen.

Related posts:

Entering Unicode characters in Linux
Three ways to enter Unicode characters in Windows
Greek letters and math symbols in (X)HTML

I tried typesetting music in LaTeX some time ago and gave up. The packages I found were hard to install, the examples didn’t work, etc. This weekend I decided to try again. I tried plowing through the MusiXTeX documentation and got no further than I did last time.

I posted a note on StackOverflow and got some good responses. Nikhil Chelliah suggested I look at LilyPond. I had looked at LilyPond before, and @jleedev explained how to integrate LaTeX and LilyPond.

Here’s some sheet music I included in my previous post, March in 7/4 time.

Here’s a full-sized PDF file version of the music above. And here’s the LilyPond source code used to create the music.

\relative c' {
\time 7/4
\key f \major
\clef treble
f g f \times 2/3{ c8 c c} f4 g a
g a8. bes16 a4 g f g c,
f g f \times 2/3{ c8 c c} f4 g a
g a8. bes16 a4 g f e f
}

The notation looks cryptic at first, but it makes sense after a few minutes. The command \relative c' means that the following pitches will be relative to middle C. For example, the first note, F, is the F closest to middle C. Each note is the same length as the previous note by default, and the first note is a quarter note by default. The notation c8 means that the C is an eighth note, except it’s in the context of a triplet (\times 2/3) and so it’s an eighth note triplet. The next F is denoted f4 to indicate that we’re back to quarter notes.

The notation a8. says that the A is a dotted eighth note. For the next note, bes16 means a B-flat sixteenth note. The suffix “es” stands for “flat” and “is” stands for “sharp.” (The documentation says it’s Dutch. I’ve never seen it before.) I don’t understand why I had to tell it that the B was flat. The code specified earlier that the key was F major, which implies B’s are flat. I suppose the code for individual notes is decoupled from the code to draw the key signature. That would make entering music painful in keys that have lots of sharps or flats. Maybe there’s a way to specify default sharps or flats.

The comma in c, gives the absolute pitch of the C. In relative mode, LilyPond assumes by default that each pitch name refers to the pitch closest to its predecessor. The C closest to the previous note, F, would have been the C up one fourth rather than down one fifth, so the comma was necessary to tell LilyPond to go down.

If I were to do a lot of music processing, I’d probably look at a commercial package such as Sibelius. But for now I’m just interested in producing small excerpts like that above, and it looks like LilyPond may be fine.

Update: I double checked the rules about flats etc. Yes, I do have to specify explicitly that the B in this example is B-flat. If I just say b rather than bes, LilyPond will add a natural sign in front of the B! It’s strange. It is aware of the key signature: when I tell it the B is flat, it says “OK, then I don’t have to mark that specially since it’s implicit in the key signature.” And if I don’t tell it the B is flat, it says “Oh, that’s an exception to the key signature. Better mark it with a natural sign.”

After writing my post on music in 5/4 time, I remembered a march in 7/4 time that I played in band many years ago. Here’s an excerpt, about all I can remember.

In case the music above is too hard to read, here’s a full-sized PDF file version.

Marches are always in even meters: your left foot has to come down on the first beat of every measure when you’re marching. And yet this odd meter tune comes across as a convincing march. (It was a concert march. Actually marching to it would have been odd, pun intended.)

This march had a 4/4 + 3/4 feel, emphasis on the first and fifth beats of each 7/4 measure.

I’ve just started blogging about music recently, and I’ve got a lot to learn. I’m not set up to record audio clips. My next post will describe the software I used to post the sheet music above.

Update: Many thanks to Nikhil Chelliah for identifying the march. It’s the first movement from Third Suite by Robert Jager. The sheet music and a sound clip are available here.

Related post: Blue Rondo à la Turk

I’ve added a plug-in that I’ve found handy on other sites. Now when you post a comment on a post, you have the option of being notified by email of future comments on that post.

Updated list of books mentioned here with links to the posts where each was mentioned

Updated contact info

Greg Pattillo plays beatbox flute. It’s hard to imagine what that means until you hear it. Here’s a video of Pattillo playing the theme from Sesame Street.

And here’s a video of Pattillo playing Peter and the Wolf.

Is there a way to make sense of the n^th derivative of a function when n is not a positive integer?

The notation f⁽ⁿ⁾ is usually introduced in calculus classes in order to make Taylor’s theorem easier to state:

To make the above statement work, the 0^th derivative is defined to be the function itself, i.e. don’t take any derivatives. This makes a modest extension of the notation f⁽ⁿ⁾ from requiring n to be a positive integer to being a non-negative integer. Can we make sense of the case when n is negative or non-integer? Before answering that question, let’s think about what the fractional derivative might be in some special cases if we could define it.

When we take derivatives of powers of x, we get factorial-like coefficients. The first derivative of x^m is m x^m-1, the second derivative is m(m-1) x^m-2, the third derivative is m(m-1)(m-2) x^m-3, etc. We can use the gamma function to extend the factorial function to non-integer argument, so maybe we could do the same to compute non-integer derivatives. If m > -1, and n is a positive integer, the n^th derivative of x^m is (m!/(m-n)!) x^m-n. We could rewrite this as (Γ(m+1) / Γ(m-n+1)) x^m-n. The result holds for integer values of n, and so we could hope it holds for non-integer values of n.

If n is an integer and we take the n^th derivative of e^bx we get bⁿ e^bx. We might guess that for non-integer values of n the same formula holds.

It is indeed possible to define derivatives of order n for non-integer values of n, and the speculations above are correct, subject to some conditions. In fact there are several ways to define non-integer derivatives and the differences can be complicated.

What about negative derivatives? Well, it makes sense that these could be anti-derivatives, i.e. integrals. We could define, for example, the -3^rd derivative of f(x) to be a function whose third derivative is f(x). However, anti-derivatives are only determined up to a constant. We could use the Fundamental Theorem of Calculus to uniquely specify anti-derivatives if we agree on a lower limit of integration c, such as c = 0 or maybe c = -∞.

Here’s one way fractional derivatives could be defined. Suppose the Fourier transform of f(x) is g(ξ). Then for positive integer n, the n^th derivative of f(x) has Fourier transform (2π i ξ)ⁿ g(ξ). So you could take the n^th derivative of f(x) as follows: take the Fourier transform, multiply by (2π i ξ)ⁿ, and take the inverse Fourier transform. This suggests the same procedure could be used to define the n^th derivative when n is not an integer.

Fractional derivatives have practical uses. The book An Atlas of Functions makes frequent use of fractional derivatives, especially derivatives of order ¹/₂ and -¹/₂, to show connections between different classes of functions.

Related article: Generalizing binomial coefficients