Amateur Topologist

This is another song by Anberlin; it’s not as upbeat as the first one, and the lyrics are even downright emo if you pay attention to them. But I really like the beat of the chorus here, as well as some of the effects on the verses.

Popularity: 1% [?]

This was totally posted Tuesday I don’t know what you’re talking about.

This is another artist where I only listen to the one song; I should probably pick up the entire album sometime to see if I like it. Oh well.

Popularity: 1% [?]

In my previous post, I gave a basic explanation of optimality theory as it relates to the phenomenon of expletive infixation. At the end, I mentioned that the word laser is not infixable; I know of no speakers who would accept *la-fucking-ser. While we can state that ‘there are these rules that must be satisfied in order for infixation to be possible’, it’s better to continue to work within the optimality theory-based framework. So to do this, we introduce another rule, Infix, which corresponds to ‘there is an actual infix presented in the word.’ Right away, we see that the existence of pre-fucking-view implies that Infix is more important than Clash; in the notation of optimality theory, this is written as Infix >> Clash. Further, since we cannot have *pre-fucking-view, IP >> Clash.

But this doesn’t address the central problem: *la-fucking-ser, despite not violating any of these rules, is unattested. This, as it turns out, is because Clash is fundamentally the wrong rule. An even better illustration, that Clash cannot be the rule we’re looking for, lies in the word-pair unbelievable and irresponsible. They both have identical stress patters (a trochee followed by a dactyl). However, they don’t have the same infix patterns: un-fucking-believable, but not *ir-fucking-responsible. No rule based only on stress patterns can account for this difference. It helps to gather a table of prefixed words:

The fundamental common characteristic is that in the infixable words, the syllable boundary between the prefix and the root word is ’strong’ in some sense; it’s easy to state that the boundary in unbe- is between the /n/ and the /b/. On the other hand, in irre-, there’s confusion: is the boundary between the two /r/s? Is it between the second /r/ and the /e/? In more formal terms, the /ən.bə/ syllable juncture is considered strong, whereas the /ɪr.rə/ juncture is weak. This same pattern extends to all the other words, and so we delete Clash and create a new rule, Strong, which states that the infix must fall at a strong syllable juncture. So we see that the table for irreducible predicts infixation between /rə/ and /’duː/:

By contrast, for unbelievable, we have:

Much like the intuitive explanations for IP and RP, we can come up with an intuitive explanation for Strong: an infix inside a weak syllable boundary would be more like an infix inside a syllable, which is invalid; we can even see that Clash falls out as a special case when dominated by RP; a stressed-unstressed syllable juncture (as in /leɪ.sər/ vs. /leɪs.ər/) is typically a weak juncture; an infixation into stressed-stressed syllable junctures would violate Clash, but unstressing the former syllable would violate RP.

There is, however, one phenomenon we can’t account for: despite the fact that I pronounce undo undo, I only have un-fucking-do, not *un-fucking-do. There are two explanations for this, but one of them also predicts extraneous forms; giving the two explanations, as well as showing why one is wrong, will be the subject of the final part, which I’ll hopefully get around to posting sometime in the next week.

Popularity: 2% [?]

Chaostar does a bunch of weird opera-like, neoclassical stuff. This song is pretty representative of their work.

Popularity: 2% [?]

Most modern languages have some kind of printf analogue: a function that takes a format string, and a series of things to be inserted into that string, and formats them all accordingly. At first glance, Haskell’s strong type system would seem to preclude this. There’s no built-in system for writing functions that take variable numbers of arguments, and it seems like it would be difficult to write one. The standard approach is to take a list instead, but this fundamentally doesn’t work for printf, since you’re going to be wanting to print Integers, Strings, and Floats. It’s possible to just pre-apply show to everything, but that’s not really a good idea, because you might want to show them in a different way than the built-in show does. You can use an extension called existential types to create a list of PrintfWrappers which wrap integers/floats/strings (more on that below), but that requires your users to manually do the wrapping, which is, once again, not a good idea. Haskell’s Text.Printf module takes a third approach. Look at the following lines:

Here’s how to interpret this: PrintfType is the type of things that can be printed to. Printing to a String just gives you a string, much like sprintf in C or Perl, printing to an IO () will actually print it out (so you can use it like a normal printf in do blocks, a behavior which I personally find distasteful.). However, printf will return undefined when asked to return an IO r; the reason that you can nevertheless return one is that only declaring IO () as an instance of PrintfType is invalid according to Haskell 98.

PrintfArg, by comparison, are the elements that are valid arguments to printf; they basically consist of the various WordN/IntN types, Integer, Float, Char, and (IsChar c) => [c]. The point of the last instance is that, while you can’t have a specific version of a polymorphic type be an instance of a typeclass, you can restrict it to types whose parameters are themselves instance of another typeclass; the only instance of isChar is Char.
So now that we have that clarified, let’s suppose we want to call printf with “%s %d %f” “foo” 42 3.1, passing it the format string, String, an Integer, and a Float. This causes printf’s type to become

Does this match the pattern (PrintfType r) => String -> r? Let’s go in reverse. String is an instance of PrintfType, and Float is an instance of PrintfArg, so Float -> String is an instance of PrintfType. Therefore, Integer -> (Float -> String) is an instance of PrintfArg, and so is String -> (Integer -> (Float -> String)). Dropping parentheses, this becomes String -> Integer -> Float -> String. So the types all check out. If you pass an invalid type, then you’ll run into something that isn’t an instance of PrintfArg and so the types won’t check.

I mentioned above that if you use something called ‘existential types’, you can do something similar. The way it works is that you define a new type whose data constructor only requires that its argument be of a given typeclass. Look at the following example

When you run showBoxes boxes, you get 2 "f" 83, exactly as you’d expect. Note that, however, the function unbox (Box x) = x cannot be written; it would have to be of type (Show s) => Box -> s, and there’s just no real way to do that. So once you’ve wrapped something up in a Box, you can only get at it by showing it. From this, you can see how to pass a heterogeneous list to printf. The reason that this approach is suboptimal is that it would require Text.Printf to export a Printf data constructor which would wrap up everything to make it of the appropriate type, and that would be rather annoying, especially since it relies on show preserving enough information for you to format the number after reading it back in.

This pattern can obviously extended to any other variadic, heterogeneous function, as long as you can define a suitable typeclass that its arguments must all be instances of. And that’s not really a restriction at all; if you can’t specify a behavior that the instances must have, then you don’t really know what you can do with the arguments, and so you can’t do anything at all!

Popularity: 38% [?]

I’ve never been much of a big Bowie fan (I don’t listen to a lot of old music), but the more I listen to this song, the more I like it, especially with the music video. No embedded video cause fuck EMI.

Ashes to Ashes.

Popularity: 2% [?]

Expletive infixation (meaning the process by which you get words like ‘un-fucking-believable’, ‘irre-fucking-futable’, and yes, ‘opti-fucking-mality’) is traditionally explained based on a rule which involves the prosody (i.e., the lyrical structure) of the word. But the usual theory, which was first given by John McCarthy in his “Prosodic Structure and Expletive Infixation” is rather inadequate. It’s consistent with all of the data it provides, but it fails to give an explanation of one key phenomenon: when the word ‘destroy’ is infixed as ‘de-fucking-stroy’, the ‘de-’ becomes stressed, and the vowel lengthens from ‘deh’ into ‘dee’. Since the prosodic hypothesis states that the structure, so to speak, of the root word isn’t modified by the infix, this is hard to explain, especially since the change from ‘ih’ to ‘ee’, or [ɪ] to [iː] (see here for a chart of IPA tables) isn’t necessarily produced by stress. So another alternative is desirable.

Enter optimality theory. According to optimality theory (or OT), we can come up with a certain set of rules and a ranking for them; the valid infixation (or infixations) whose first rule violation is lower-ranked than any other infixed forms. Since some words, such as laser,cannot be infixed, the statement that ‘there must be an infixed word’ must also be a rule in and of itself, which can be violated. So let’s set up a few base rules:

• IP: The pronunciation of the infix word is preserved.
• RP: The pronunciation of the root word is preserved.
• Clash: There are no two adjacent stressed syllables.

I left out the Infix rule; we’ll come back to it later. Let’s take a look at a sample word, kindergarten (using bold for stress).

What this means is that only the first form, kinder-fucking-garten has no violatins of any rules. The other two violate one rule each; the ! indicates that each violation is the ‘first’, or highest-priority one. The two light-gray cells in the bottom row indicate that, for purposes of comparing fitness, those cells are irrelevant; in optimality theory, only the first violation is relevant.

Of course, this isn’t terribly useful for figuring out the actual rankings of constraints, and rankings are relevant; moreover, there are a few rules that haven’t been introduced yet that cannot be violated: as an example, *la-fucking-ser, despite not violating any of these rules, is not considered acceptable by the majority of English speakers. So what do we do?

Popularity: 9% [?]

The best description I heard of this song was from some review I read a while ago, and it went along the lines of: “If you went on a vacation and your appliances wrote electronic love songs while you were gone, this is what they would sound like.”

PS: expect actual content over the next few days!

Popularity: 4% [?]

Sorry, no video this time; all the good ones on Youtube have disabled embedding. Pet Shop Boys are a British electronic dance duo that’ve been making music for the past 18 years; I haven’t listened to a lot of their stuff, but I really, really likeOpportunities.

Popularity: 3% [?]

Part of the beauty of Haskell is that it allows you to simply write recursive functions. But part of the problem with recursive functions is that they tend to have absolutely horrible big-O run times. The usual solution to this problem is to use what’s known as memoization, which is memorization without the ‘r’, since programmers have to have special names for everything. Memoization is usually implemented as an associative array (or a plain array in the common case where the function takes a single non-negative integer as an argument); the function attempts to look up the return value for its arguments in an associative array. If it finds it, it can return without doing expensive computation; if it doesn’t, then it performs the computation, stores the result in its array, and then returns. In Python, a memoized Fibonacci function might be written as follows:

The speed savings gained by this are enormous; on my test machine, fib(35) takes 15 seconds to compute without memoization, whereas fib(1000) computes almost instantly with memoization. In terms of big-O running times, I believe that the memoized version takes time, whereas the unmemoized version takes , which is interesting since the Fibonacci numbers themselves are . In any case, the memoized version is clearly superior.

But how do you do this in a language such as Haskell? You can’t carry state between the various incarnations of the function, since that could potentially lead to the function’s values not solely depending on its arguments, violating referential transparency. You can’t carry the state around in a monad because then different calls to the function would each have separate caches, so you’d have to pull some kind of trick where the function returns itself and its value, then pass the function around and it would just be a huge mess. So instead what you do is you use Data.MemoCombinators, which is a package that lets you turn functions into other, memoized functions. So how do you use it? It’s not too hard, especially if you’re memoizing functions that only use builtin types. An example, straight from the Data.MemoCombinators page:

There are two things to note here: first, the memoized version, fib, is generated from the non-memoized by calling Memo.integral on it. This is how you create memoized versions of single-variable functions: you apply the appropriate combinator. Second, fib’ calls fib inside it. This is very important: if fib’ called fib’, then you couldn’t save time within the fib function, only outside of it. With fib’ calling fib, on the other hand, then the first time you call fib 1000, not only will it return before the heat death of the universe, but you’ll also get fib 999, fib 998, etc. cached.

But what if your function to be memoized isn’t one of the standard types? That’s why there’s Memo.wrap. You just have to define two mappings: one from your type to some combination of MemoCombinator types, and one that goes from that combination back. An example will make it clear:

So as you can see, first you build up a memoString type which can memoize Strings; since a String is just a list of Chars, you can just apply Memo.list to Memo.char. Then you define toFoo and fromFoo, which send you from the abstracted Foo type to a tuple of a String and an Int. Finally, you use Memo.wrap to ‘wrap’ the pair of a memoized String and a memoized Int (constructed using Memo.pair, naturally) up in an abstract memoFoo memoizer.

The other thing you can do with MemoCombinators is memoize functions of multiple variables. Take this sample of code from a project I’m working on:

The actual definition of *! isn’t important, I’m only including it for completeness. Nor are the definitions of toNimber and fromNimber. What is important is Memo.memo2: you use it to generate a memoized function of multiple arguments. You just pass it memoizers for each of its arguments (since * takes two Nimbers, I pass it memoNimber twice) and the unmemoized version, and it gives you a memoized version.

As for how Data.MemoCombinators works, I can’t really explain that. I know it has to do with the fact that expressions in function definitions are cached, but beyond that my knowledge fails. Maybe if I ever learn it I’ll return to this and explain it.

Edit: After I wrote this I realized that Data.MemoTrie exists; while it has cleaner syntax for memoizing functions (the memoizer doesn’t need to know the types of the arguments), it has a disadvantage in that it’s not immediately obvious how to memoize the types it doesn’t give you. But if you’re just memoizing functions of Ints or something, go ahead and use MemoTrie.

Popularity: 20% [?]