Haskell and the World: Unicode and the Common Misuse of ByteString

Haskell's string handling is actually quite good overall. Strings are always encoded consistently, and as long as you don't leave the space of Haskell itself, you probably won't have (m)any problems. Sadly, this has caused some Haskell programmers (including myself) to become a little careless when handling strings of any kind, be they String, ByteString or Text.

So here's some basic minimum on what you need to get by with text in Haskell. Let's first get a grip on some basic terminology…

Charsets, Encodings and Codepoints

People tend to just throw these three together, but they shouldn't — they're all fundamentally different things!

• A character set is just that. It's a set, and it contains characters. Remember: a set is a bunch of stuff. All elements of a set are unique and a set is inherently unordered. That's it.

• An encoding defines a function that maps characters from the charset to byte strings.¹ Every encoding function needs to have a retraction, i.e. it needs to be reversible. Given f, an encoding function, C its domain (the character set,) and  * B_f its codomain (the set of valid byte strings for that encoding) an encoding should satisfy the following two properties: f ⋅ f^− 1 = 1_* Bf and f^− 1 ⋅ f = 1_C, making it an isomorphism.²

• Code points enumerate a character set by creating another isomorphism between the charset and numbers. It is very important to note that encodings and code points are distinct!

Why do we need code points when we already have encodings? The Unicode standard for example defines a pretty exhaustive character set that tries to capture all of the world's languages and various other stuff. The code points segment this set into planes and enumerate it sequentially in a well-defined manner.

This makes it possible to refer to a particular glyph via a single number, and without having to represent said glyph graphically (say, because you lack the font) and also without having to specify a particular encoding. Lastly, this makes for a portable representation of glyphs by mere integers.

Char in Haskell

Let U be the Unicode character set, and ü,я ∈ U (Latin small letter 'u' with diaresis, Cyrillic small letter ya.) Let u: U →  ℕ be the function assigning code points to elements of U. Then u(ü) = 252, and u(я) = 1103. This is what a Char value in GHC actually represents:

λ> 'ü'
'\252'
λ> 'я'
'\1103'

Another common way of representing code points is as 3-byte wide hexadecimal byte string values. The letters ü and я are rendered as U+0000FC and U+00044F, respectively, where the first byte stands for the plane this code point belongs to, and it is sometimes ommitted in the case the code point is settled in the BMP, or basic multilingual plane.³

So the Char data type in Haskell represents characters as Unicode code points, i.e. as numbers. When you print something in Haskell, you get back a decimal representation of its code point except for printable ASCII characters, which are represented as themselves. Non-printable ASCII characters are assigned special names:

λ> "\0\1\2\3\4\5"
"\NUL\SOH\STX\ETX\EOT\ENQ"

Encoding Functions

Let B be the set of bytes (numbers from 0 to 255) and  * B_utf8 to be the set of valid UTF-8 byte strings. Let f_utf8: U →  * B be the UTF-8 encoding function. Then f_utf8(ü) = 0xc3b6, f_utf8(я) = 0xd18f. Remember that an encoding function doesn't map characters to a number, but to byte strings. In the case of UTF-8, this is one or more bytes.

Let's also define f_utf16: U →  * B_utf16, the little endian UTF-16 encoding function. Then f_utf16(ü) = 0xfc00, and f_utf16(я) = 0x4F04. Do you notice how the byte strings representing the code points of the letters are different from these byte strings? It all comes down to the fact that we chose LE, since UTF-16, as opposed to UTF-8, depends on endianness.

… and why Char8.pack isn't one.

So far, the functions we've seen are isomorphisms, and encoding functions should always be structure preserving! But ByteString.Char8.pack does not fulfil that property, and, consequently, it doesn't form the identity on its domain when composed with its retraction (which an isomorphism does.) The supposed "retraction" of pack is unpack.

λ> import qualified Data.ByteString.Char8 as B
λ> (B.unpack . B.pack $ "я") == "я"
False
λ> (B.unpack . B.pack $ "я") == "O"
True

Earlier I said that a way of representing unicode code points was by rendering them as 3 byte wide byte strings. Unfortunately, this is not what ByteString.Char8.pack does. Let's look at the documentation of Data.ByteString.Char8:

Manipulate ByteStrings using Char operations. All Chars will be truncated to 8 bits.

The word truncate is a big red light. You lose information.

λ> B.pack $ [toEnum 255]
"\255"
λ> B.pack $ [toEnum 256]
"\NUL"

There is no legitimate use case for ByteString.Char8.pack in production code. It exists out of pure laziness, and in order to facilitate that laziness in developers. Even if you're sure you'll only ever process English, it's naïve to assume you're going to get by with ASCII, which is likely to be the only encoding you're not going to have any problems with when using Char8.pack.

Just to drive my point home, I'll use all caps:

WHEN YOU USE ByteString.Char8.pack YOU JUST TAKE A UNICODE CODE POINT AND TRUNCATE IT TO ITS FIRST BYTE AND ARE STILL PRETENDING IT'S TEXT!

Just stop it already.

Correct Text Handling in Haskell

In most cases, you should probably just use Data.Text.⁴ In the case of Data.Text, you can even use its IsString instance and add the OverloadedStrings pragma so you would never notice you're using Text and not String.⁵ Data.Text.Encoding supplies a couple of very nice encode and decode functions to marshal your Text values to and from ByteStrings.

λ> import qualified Data.Text as T
λ> import Data.Text.Encoding
λ> :set -XOverloadedStrings
λ> :t encodeUtf8
encodeUtf8 :: T.Text -> B.ByteString
λ> encodeUtf8 "ü"
"\195\188"
λ> encodeUtf16LE  "я"
"O\EOT"

The weird output we get back from this function is actually just a ByteString rendered by its Show instance. But in my opinion, ByteString's Show instance is broken and misleading!

Rendering octets as a String like that makes no sense, because a String makes a guarantee that it represents valid Unicode code points corresponding to the intended characters. Which this does not. It would be much more sensible to just render the hexadecimal values, without making any promise about representing textual data (because ByteStrings are NOT textual data.)

λ> import Data.Hex
λ> hex . encodeUtf8 $ "ü"
"C3BC"
λ> hex . encodeUtf16LE $ "я"
"4F04"

As a side note, you can also use text-icu, which allows for direct conversions of Strings and a more comprehensive treatment of encodings.⁶

tl;dr

• Don't use ByteString.Char8
• If you have textual data, you should be representing it as Data.Text
• ByteStrings have nothing to do with Strings — they're very different from one another.
• ByteStrings never should be used to represent textual data. As soon as you've encoded a particular piece of text into a ByteString, treat it as binary data, and do not render it via ByteString's Show instance, but only by using the appropriate decoding and encoding functions.

---

1. Technically, that's not true. An encoding can map characters to pretty much anything. Frequencies, Morse signals and other such things are all possible codomains of the encoding function, but we'll restrict ourselves to byte strings. ↩

2. This is a somewhat simplified view of an encoding, and in practise, it'll be desirable to break this property in order to establish certain equivalence relations; c.f. Unicode equivalence. We'll adopt this simplified view for the point of this discussion, though. Thanks to dmwit on reddit for pointing this out to me. ↩

3. If you ever happen run across funny U+XXXXXX sequences, DuckDuckGo allows you to decode them into their definitions and into decimal. ↩

4. Data.Text.pack is safe to use ;-) ↩

5. This extension has some problems of its own, but with Data.Text it should be safe to use. ↩

6. Thanks to yitz on reddit for recommending this library to me ↩

Re: Highbrow Java; Or: Java Generics and Why I Still Hate Them

• Type Safety and Type Polymorphism
  • Erasure
  • Reifcation
  • Generics Have Poor Support for Arrays
  • Inner Classes of Polymorphic Classes May Not Be Used as Array Component Types
  • No Polymorphism for Exceptions
  • Static Fields of Generic Types
  • Downcasting Towards a Polymorphic Type is Always Unsafe
• Theoretically…

This, well, rant, originated as a more elaborate answer to a comment on an article I left unanswered for over half a year. I wanted to apologise by coming up with a rather exhaustive answer. Turns out I got exhausted before I could finish complaining, so I'll just post what I have right now and will continue ranting at some later stages.

Because this is so long, I'll save everyone the trouble and give an abstract: I argue that, while generics were a neccessary and "good" addition to Java, this particular implementation of what is in essence second-order typed lambda calculus, is poor and severly limits the compiler's ability to guarantee run-time type safety. Turns out I'm focussing on arrays (again,) but that was the low hanging fruit. I'll get to the lack of expressive power in a later post.

Type Safety and Type Polymorphism

Why do we care about static type systems and type safety? I think one can discern two major points, quoting from Wikipedia:

• Static typing is a limited form of program verification
• Program execution may also be made more efficient by omitting runtime type checks and enabling other optimizations.

I actually only care about the first point: a good type system can catch mistakes in code paths rarely taken, which may have otherwise eluded testing. It may successfully shift some of the debugging effort from run-time to compile-time. The merit of any performance gain during run-time is debatable, and certainly not a really strong argument in my opinion.

What object-oriented programmers refer to as generic programming is parametric polymorphism (as opposed to ad-hoc or subtype polymorphism, both of which Java also supports.) Parametric polymorphism is also famously captured in System F, or polymorphic (or second-order typed) lambda calculus. It introduces universal quantification over types. There's a similar system developed by Mitchell & Plotkin (1988), which introduces existential quantification instead.

Prior to 1.5, Java lacked any kind of parametric polymorphism¹. The need for parametric polymorphism in a statically typed programming language should be obvious to any reader: it heightens the expressive power of the type system without compromising on type safety. Thus, generics were a step in the right direction.

An important mental note: in OOP terminology, polymorphism usually refers to subtype polymorphism. Sometimes polymorphic methods are mentioned, which correspond to ad-hoc polymorphism. When I refer to polymorphism in the rest of this text, I will mean the parametric kind, i.e. generics.

Erasure

In Java, generics are only used at compile-time. The JVM isn't even aware of the existence of generics. This is called erasure, and it exists purely for backwards compatibility reasons. It leads to several unfortunate problems with type safety.

When programming with generics in java, I'm always amazed by the amount of explicit casting one has to perform. Ideally, you'd never want to ever do that. Explicit casts can't generally be checked at compile time — we give up type safety by using them.

Reifcation

The opposite of erasure is reification — a very fancy name deriving from the latin word res (thing.) Naftalin and Wadler thus call it thingification. For us, it means that a type carries run-time information about itself. A Number knows it's a Number at run-time, and you can retrieve that information using the reflection API. A List<Number> only knows it's a List, but it has no idea about the fact that it's carrying Numbers.

The proposal for Reified Generics thus would either completely throw out type erasure, or allow some sort of explicitly reified generics syntax.

There currently are only a couple of non-reifiable types in Java:

• type variables
• instantiations of polymorphic types (such as List<String>)
• bounded instantiations of polymorphic types (such as List<? extends Number>)²

Generics Have Poor Support for Arrays

Arrays in Java feel like a wart nowadays, especially in the presence of generics. There is one cruicial constraint on array creation, which makes it utterly annoying to use them: the component type of an array must be reifiable.

See, given a type variable T, T[] is perfectly valid in Java. The Collection interface defines a method <T> T[] toArray(T[] a) after all! But there's something fishy about this method: why do I need to pass it an array? And isn't Collection defined as Collection<E>? T is only in scope for this one method, as can be gleaned from the type signature. T has nothing to do with E. The following code typechecks:

Collection<String> cs = new ArrayList<String>();
Number[] na = cs.toArray(new Number[10]);

There's an alternative method Object[] toArray(), which is more along the lines of what you'd expect such a method to do. It creates the array for you, (that's the point after all,) but it creates an array of the generic Object type which you'd have to cast into something more appropriate yourself.

The cause of this idiosyncracy is simple: you cannot write code that explictly creates arrays with non-reifiable component types. Recalling our earlier list, it means that type variables and (bounded) instantiations of polymorphic types cannot be used for arrays without casting explicitly.

<T> void f() {
    T[] a              = new T[1]; // error
    List<Integer>[] il = { Arrays.asList(1,2) }; // error
}

Both of these lines will fail with generic array creation (hooray for descriptive compiler error messages.)

But wait, how do the collection classes like ArrayList do it? Don't they have to use arrays with a polymorphic component type internally? Yes, they do. And you can create generic arrays:

T[] ta = (T[]) new Object[1]; // unchecked

Since the compiler cannot ensure the above line will actually work at runtime, it issues an "unchecked" warning for this line of code (see below.) The compiler is right, too. ta now has the run-time type Object not whatever T is! So if you instantiate T to, say String, and try to store it as a String[], you will receive a run-time error even though you didn't explicitly cast anything!

Naftalin & Wadler thus tell you to adhere to the The Principle of Truth in Advertising:

The reified type of an array must be a subtype of the erasure of its static type

That's quite a mouthful isn't it? I recommend reading the appropriate chapter 6.5 in Naftalin & Wadler (2006) for more information, but the gist is this: The run-time type of any array must be a the same as or a subtype of what is left of its compile-time type after erasure kicks in. If you don't adhere to this principle, you will get into trouble selling something as being of type a where it actually is of a completely different type b which can be anything. The compiler can't catch this, and it will result in an unchecked run-time exception most likely terminating your entire program. It's your responsibility (and it shouldn't be.)

This is the reason writing T[] toArray() is not advisable; you have to pass toArray a T[] parameter that you create yourself, and that you are responsible for. The compiler can't help you.

The solution to this is one of: a) don't mix arrays and generics³, it's bad for your mental health, or b) arcane magic aka reflection. I will leave it to the reader to figure out method b)⁴, since I'm tired of writing this at the moment. It's a pointless exercise anyway: the reality of the matter is, b) doesn't really exist in case you want to write a well-designed library. Why? Well…

I find the next example particularly devious (from N&W 2006, pp. 87)

List<Integer>[] ils =
    (List<Integer>[]) new List[] {Arrays.asList(1)}; // unchecked
List<? extends Number> nls = ils;
ils[0] = Arrays.asList(1.01) // storing a Double in an Integer list!
int n = ils[0].get(0); // class cast exception

You just need to inadvertently pass a reference of your array with a non-reifiable type to some devious method and it might put stuff in there that will make your program crash. And the compiler never saw it coming⁵. N&W thus call for adherence to the Principle of Indecent Exposure

Never Publicly expose an array where the components do not have a reifiable type

These two principles together mean that you should avoid non-reifible component types in both the source and run-time, which means, you should stick rule a) don't mix arrays and generics. At all. Of course the Java standard library doesn't have to follow these rules.

The way ArrayList et al. handle the issue internally is to not externally expose any generic array they do very much internally use, which is why you have to pass your own T[] to toArray. This also entails to tread lightly whenever using generic arrays internally, as well.

Inner Classes of Polymorphic Classes May Not Be Used as Array Component Types

Now that was a long subsection title. But it really is that silly:

public class C<E> {
    N[] ns = new N[10]; // *error*: Generic Array Creation
    private class N { int data; }
}

This will not compile. If you omit the parameter for C, it's no problem. If you put N into its own class file, it's fine again. I'm not exactly sure why that is, since the type parameter isn't even used, and N should be a reifiable type, since it's not parametric.

No Polymorphism for Exceptions

Type erasure also leads to the awkward consequence that anything deriving from Throwable cannot be a generic type, since the JVM couldn't distinguish different instantiations of that type, but it needs to in the case of exception handling.

Static Fields of Generic Types

It also makes it impossible to have any static fields of a class have the same type as a type parameter:

public class C<A> {
    static A a;
}

In order for this to work, the runtime would have to keep track of a value for a for each instantiation of type A, which is not possible, since it doesn't even know that A exists! It only ever knows about the raw type C.

Downcasting Towards a Polymorphic Type is Always Unsafe

And it can result in run-time failures with a ClassCastException that are far removed from the actual origin of the erroneous code. Consider the following snippet, loosely based on FAQ005:

void f() {
    List<Date> dl   = new ArrayList<Date>();
    List<String> sl = (List<String>) ((Object) dl); // unchecked warning
    g(sl);
}
void g(List<String> l) { String s = l.get(0); } // ClassCastException

The above code will always issue a warning, and we see why: the compiler cannot generally ensure that the code won't lead to a runtime error. The problem is: there are scenarios were doing this is actually useful, and legal: given Token, a subtype of Annotation, casting a List<Annotation> to a List<Token>, for example, which I have had to do in the context of UIMA very often will always result in a warning. The compiler cannot reason about whether the warning is justified or not.

Don't just ignore those unchecked warnings, it can end badly, and it will confuse you.

Theoretically…

I would recommend to anybody further interested in exploring the theory behind (and above!) Java's Generics, to have a look at Wadler's page on them. A lot of very interesting papers are linked there, as well as the authoritative O'Reilly book on Java Generics.

---

1. Well, that's not exactly true. Technically, the array type does count for a polymorphic type ↩

2. Curiously, wildcards are reified, so List<?> has full run-time type information, but List<? extends Object>, which is equivalent, does not. ↩

3. Did I mention that varargs are actually just arrays? Yes, don't mix generics and varargs either; same restrictions apply. Some methods in the standard library use varargs, among them Arrays.asList. And this does mean that creating a List<T> or List<List<Integer>> with said method shouldn't be attempted… ↩

4. Hint, it involves Arrays.asList and can't avoid unchecked casts either. ↩

5. Well, it did issue a warning alright, but as we know, there is no way around that in case you're dealing with arrays anyway. ↩

Vegetarian Lasagna with Black Beans

Nothing tastes quite as good as lasagna Bolognese, one of the very few meat dishes I used to eat when I actually did eat a little meat. Since I'm thoroughly grossed out by any form of allegedly 'edible' animal now, I've been looking for a lasagna that could compare to 'the real deal.' Recently, I found a delectable recipe over at epicurious.

The lasagna requires quite a bit of effort. Due to the different cheeses in it, the cost is also relatively high. I tried to make it both as easy as possible, and as cheap as possible.

Ingredients

• 200g black beans (usually available in any Asia shop.)
• 250g Ricotta (Italian cottage cheese. You can substitute it with pretty much any kind of cottage cheese that doesn't have too strong a taste.)
• 3 balls of mozzarella, around 250 to 300g; (it isn't worth it to buy good buffalo Mozzarella, but don't buy the cheapest stuff either.)

• Parmesan (or, if you want to save money, Grana Padano is equally good.)
• 1 egg
• 1 onion, some 3 cloves of garlic
• 150g of black olives
• olive oil
• some 2-2½ cans of tomatoes in various aggregate states: puréed, skinned and diced, or just cut up.
• 2-3 tsp. ground dried cilantro
• basil
• a bay leaf
• lasagna noodles
• jalapeños to taste
• oregano, thyme, ground dried basil
• salt, pepper, asafoetida, chili powder, sweet pepper powder, dried pomegranate powder

	preheat the oven to 180°C						layer: (top to bottom) parmesan 1/3 béchamel noodles parmesan 1/3 mozzarella 1/3 tomato sauce 1/3 béchamel noodles parmesan 1/3 mozzarella 1/3 tomato sauce bean cream noodles parmesan 1/3 mozzarella 1/3 tomato sauce 1/3 béchamel noodles bake for 30-35min
	oil in a lasagna dish
250 g ricotta	mix				whisk until creamy
1 egg
25g grated Parmesan
2-3 tsp. cilantro powder
2 tbsp. olive oil					mix and blend until creamy
250g black beans	cook			separate 1 cup
				rest of beans	fold, cook until oil separates
onion	dice	mix	fry until onions are soft	mix, fry 2-3 min
salt, pepper
bay leaf
spices
chili powder to taste
3-4 cloves of garlic	press
2 spoons olive oil	heat in frying pan
jalapeños (to taste)	remove stems and seeds, dice
150g olives	remove kernels if necessary
2 cans of assorted tomatoes	dice purée
3 balls of mozzarella
grated Parmesan
lasagna noodles

The Perfect Prompt

Long ago I switched to zsh from bash for my hacking needs. I think at the time I just needed a new toy. However, over the years, zsh has proven to be a very good shell, with excellent flexibility, a healthy "Do what I Mean" attitude, and overall much more powerful globbing, auto-complete, keybinding and scripting capabilities than bash.

Part of the usual appeal of zsh are the ridiculously fancy prompts you can make it display. I was never a fan of those. My prompts have to be simple, since I'm staring at them all the time. Don't show me anything I don't need, to know! I find it hard to concentrate on something anyway, without my shell telling me how many emails I have left in my Inbox. So I created the perfect minimalist prompt that does exactly what I need it to do:

• Display whether I'm root or not
• How many jobs are there running in the background (if any?)
• Did the last command finish successfully, or did the damn thing just die silently?
• Since I'm using vi keybindings, am I in insert mode or in normal mode?
• What machine is this shell on?
• What directory is this shell in?

Almost all of these have defaults I don't expect to be mentioned. Usually, I have nothing running in the background, I'm on my local machine, and the last command finished successfully. At that point, I don't need to be reminded that all is well. Hide it! So here's a picture: Let's go over the features one-by one:

I don't like directories to be on the left-hand side prompt, since that'll move your prompt all the way to the right when you're in a deeply nested directory. So they're on the right, where they don't bother me, but I can still look them up easily (the blue string on the right will disappear if the cursor gets too close.)

Named directories are zsh's handy way to provide directory shortnames. Instead of going to the lengthy ~/Documents/src I can just go to ~src. I can define similar hashes for projects I'm working on, say ~myproject for ~/Documents/src/java/myproject.

Whenever there's a background job (like sleep in this example) I get a yellow number before my prompt mark. This is a counter for the background jobs. It disappears if there aren't any.

The shell checks the variable SSH_CLIENT to see if it's on a remote or local machine. On a local machine, nothing happens, but on a remote machine (i.e. a machine I'm accessing via SSH — the client always sets SSH_CLIENT when connecting) it displays the leftmost part of the machine's subdomain. I don't need to know I'm on a local machine when I'm sitting in front of it! But I do want to know if a shell doesn't belong to the machine I'm currently working on.

Similarly to the background job display, I don't want to always know every program's return code. I'm interested in the ones that failed. If a program returns non-zero, I see a big fat red number signalizing error.

Finally I like to know which mode I'm in. The blue > indicates insert mode, and a yellow ∙ indicates normal mode. Like this:

Since it's tracked by version control, I'll link you to my .zshrc. My shell config changes periodically, and no doubt even this "perfect prompt" will experience revisions. Use the commit log to find commits to .zshrc that look like this one.

Finally, since my config's rather big, maybe someone will find something else useful there :-)

The Catsters YouTube Channel: Lectures on Category Theory

Just quickly posting to mention my finding a neat little YouTube channel with lectures on Category Theory: The Catsters.

The folks on the channel giving the lectures are enthusiastic nerds (what else?) and their lectures are actually really well done. One can even read what they scribble on the board. Usually.

The quality of the videos is pretty poor though, and the buzzing of the sound and poor balance of voice and ambient noises, as well as the amplification problems (sometimes, especially on the Monads video, the voice just blows out the mic amp's range) make it a little hard to follow the lectures. It won't, of course, prevent a real enthusiast from watching them. The explanations' quality is good (as far as I could tell.)

I increasingly find the lecture format of Internet videos a little nicer than your average run-of-the-mill lecture, where you sit with some 100 folks in one room. Granted, my own course of studies usually put me into rooms of no more than 20 people, but I still find it quite useful to be able to view lectures on demand. There's something to be said for both formats.

Go check it out! And I'll try to find some original content to post again :-P

Generalised Algebraic Data Types in Haskell

I will just ignore the fact that I haven't posted anything here in more than 1.5 years. It's still my blog :-) Maybe there's gonna be a follow-up on how/what I was doing, but right now, I'll skip right over it.

Heinrich Apfelmus has posted an absolutely enlightening video explanation of Haskell's generalised algebraic data type system on his blog. It gives a newcomer quite a nice perspective on why GADTs are so powerful, and how one can use them. There's a couple of caveats: first, if you're totally new to Haskell this won't make too much sense to you. You'll have to understand at least data type declarations, type constructors and maybe the infix function notation (and the fact that every type constructor is a function!)

The example he chose (algebraic expressions) is quite nice & simple, but it's also a toy example. It would be nice to see GADTs used in an example that is still intuitive but maybe a little more... engaging. I'm thinking of 2-sorted Typed logic, and/or typed lambda-calculus with embedded FOPL. I'm currently implementing something along those lines and hope to release the code soon :-)

EDIT: I just discovered a newer post of his about the fixed point combinator; and it even taught me some new and interesting things! I really like the style of his videos... and his cute accent ^^.

The Good the Bad and the Funny

Credit where credit is due. Vladimir Putin may be a despisable person, but, damn, he's so Russian, he sweats Vodka:

French media had quoted Putin as saying in a heated conversation with French President Nicolas Sarkozy in Moscow on August 12 that Saakashvili should be "hung by his balls" for starting the war which was roundly condemned by the West.
Source: Reuters

The Russian soul is an intrepid one. They like their unbashed, dauntlessly honest attitude, they sell it as a feature, where some might consider it outright rude. Can't say I blame them for that. Hearing one of the most "important" persons on the world talking like that does find favor with me. That's probably my Slavic side, or maybe even the faint Mongolic or Thrakian genes, so I don't expect you westerners to understand that. It's great, because it's stupid, but it's manly, which is even more stupid, and that in turn, makes it great again.

He goes on:

"Seriously speaking, both me and you know about tragic events in another region of the world, in Iraq, invaded by American troops due to a concocted pretext of searching for weapons of mass destruction," said Putin.

"They found no weapons, but hanged the head of state, albeit on other charges ... " said Putin, referring to the 2006 execution of former Iraqi President Saddam Hussein.

"I believe it is up to Georgia's people to decide what kind of responsibility must be borne by those politicians who led to these harshest and tragic consequences," he said.
ibid

No matter what you may think about Mr. Putin, it does take quite some self-confidence to accuse the Americans so openly of wrongdoing. Demanding to hang the Georgian president by his balls for attacking another country under "false" premises is indirectly asking to do the same thing to George. Bush. Jr. Not that I would mind.

And I'd like to take that as an opportunity to remind everybody that, despite these brutish words, Putin is a man of extreme subtlety, and no doubt even those words were duly prepared and carefully placed (…or maybe I overestimate him?) I still think he's one of the most dangerous people on this planet (known to me, anyway) and I'm watching the current political "developments" in Russia with great unease.

Tough Questions

Apparently, it's been "Philosopher Day" recently. Not that I noticed. BBC took it as an excuse to feature an article on "Four Philosophical Questions that will Make Your Brain Hurt." So far, my brain feels fine, and I'm only slightly amused. Let's consider them in turn.

Should we kill healthy people for their organs?

I first misread that as "Should we kill wealthy people for their organs" and thought to myself: "My, what a good idea! that's no hard question at all." Unfortunately, on second glance, the question turns out to be the same old utilitarian vs. moralistic clash. And mind you, that's not strict philosophy, it's more like ethics.

You cannot justify utilitarian reasoning with moral doctrine. But you can doubt the utilitarian thought on other grounds: Since there is no way of predicting the future, utilitarian maximes will always be based on assumptions and guesswork. See the world as a system of interdependent states. Killing someone is quite an action on this system, and can have unpredictable consequences. Letting someone die of natural cause might be seen as part of the system, and will have the usual consequences.

Trying to answer this question without having a look at the big picture isn't sensible, but that's what they're doing here. And that's stupid. The big picture doesn't care about one person or five. WWII eradicated the same amount in Millions, per year. Humanity recovered. The human race is such that it can compensate for the loss of individuals. The current human (Western) society is such that it cannot (easily) compensate for the (open) loss of individual values. On the other hand, doing such things implicitly, is perfectly valid, even in the most "civilized" of nations. Or when did you last flush your fecal matter down the toilet, while children in other parts of the world die because of the lack of (clean) water.

Are you the same person who started reading this article?

Ugh. Not again that ol' "Who am I?" question. Heraklit (sortof) says: "You cannot go into the same river twice, since the river always changes." The question is the definition of "same." Ergo, the definition of individuality. If you like to think of time as nothing more than another dimension, you'll just say, it's me, over there. A state change does not indicate a change in kind. Or does it? Anyway, this doesn't make my brain hurt, it merely provides a nice distraction best discussed with friends over some pints of beer.

Is that really a computer screen in front of you?

Solipsism. How boring. For all I know, yes it is. It is safe to assume it is. If I'm mistaken, so be it. Conventionalism is the keyword here. Yes, senses can be fooled, but, what isn't perceived isn't there. What isn't perceived by me, isn't there for me. Since I call it a computer screen, and you call it a computer screen, it is a computer screen. If it turns out to be a sentient life form, disguising itself as something useful, I'd probably still call it a computer screen, at least until I find a better name and use for it.

Did you really choose to read this article?

Quoth the article:

Suppose that Fred existed shortly after the Big Bang. He had unlimited intelligence and memory, and knew all the scientific laws governing the universe and all the properties of every particle that then existed. Thus equipped, billions of years ago, he could have worked out that, eventually, planet Earth would come to exist, that you would too, and that right now you would be reading this article.

Ever heard of quantum physics? This scenario is as absurd as it is impossible, because there is no way of knowing all state in the universe. Even if you did, there is no way of predicting how that state would evolve.
But I like the idea of calling god 'Fred.'

TeX on Blogger

It's done! After about an hour of desperately trying to set it up using various approaches, I finally came across Yourequations.com. Sounds very Web2.0, but it works!

\mathbf{Proof.\mbox{ }}\mathrm{ By\mbox{ }example:} \sum_{n\in\mathbm{N}} p. \mbox{ }\Box

Now that was one one-liner! Two problems remain: in-line (in-text) LaTeX symbols (this script requires the use of <pre> tags, which, by definition, open a new line) and the fact that I have to first publish the post, before I see the results.

I had hoped to take Blogspot's lacking LaTeX support as an excuse to roll out my own server and CMS. Meh, now I'll have to find another reason.

Like, nicer fonts in the equations, using my favorite font package. Yes, that's it!

Update:

Reading the source code, it may be possible to do in-line \LaTeX{} after all. Yeah. Just use the <code> tags instead.

Now you can expect to see several posts that have been rotting in my drafts section for a while due to lack of formula support. Let's just hope I don't promis you too much.

Overheard in Tübingen

"Ja, es gibt ja halt Zahlen."
"Ja."
"Und mit denen kannst Du dann rechnen."
"Jaaa."
"Und damit kannst Du dann halt so Daten verschlüsseln."
"Aha."

(defun perspective (person) ( … ))

Dan Bikel has written a nice statistical CYK parser for Java, and it reads and writes Lisp syntax, namely Sexps. While I was coding on a project today, I was being watched and supported by a colleague. When I used Dan Bikel's Sexp class, hilarity ensued.
I countered her chuckles with an explanation of basic Lisp syntax. This prompted a curious reply of hers:

The inventors must have been lonely people.

Well, contracting 'symbolic expressions' to a word reminiscent of what computer freaks stereotypically lack may seem an awkward coincidence to some, but drawing a connection may seem like a stretch to others. Sadly, there probably is a grain of truth in such… assumptions.
Upon demonstrating to her some real world examples of Lisp code, and after the inevitable "all those parens!", she uttered

The inventors really must have been lonely people. And bored ones at that.

Poor Lisp. Is that what people think of you today?
Lisp is old. Very old. But just as Prolog, it is still around, and that alone justifies its use. In fact, most of what people use XML for nowadays should rather be done in Lisp syntax.

Thou Shalt not Forget Those Who Are Afraid of Upgrades

I don't know how often I will have to curse about type erasure in the Java HotSpot VM. It is a pain in the… EVERYTHING. And the only reason for it is, of course, our sacred backward compatibility.
Some core library functionalities are utterly broken. How can a parameterized ArrayList's .toArray() return Object[]?
WHY??*
All because of type erasure. class Foo {{T[] = new T[42]; }} is illegal, because the runtime would have no clue as to what constructor to call for the array (it doesn't know its type). It boils down to: you cannot instantiate Generics. OK, you say, it wouldn't make too much of a sense anyway, but you see, it has side effects. Ever bothered to read the code of ArrayList and other parameterized standard collection types that use an array as a back end? Don't, if you want to retain your sanity. The heart of it is a lot of dirty casting, made necessary because of the way Generics are implemented (oh, the irony.)
One of the proposed features for Java 7 are Reified Generics, but somehow I doubt they'll make it into the language anytime soon. There's just still too many people around using a 1.4 VM (YES, Apple, we're looking at YOU) and introducing another substantial change to the way Generics work would make them even more complex than they already are (Yes, that PDF has more than 500 pages. Yes, it's mostly about Generics.) So, probably we'll have to just keep up with that crap. Microsoft did it right in .NET. Pity it's a closed platform.

</rant> [1] You have to first create an Array of your Type T (a literal type, not a Generic one) and then pass it to the overloaded .toArray(T[]).

Luv Github

You gotta love github at least for their error messages: I know whom I have to blame that I can't but think about tentacle rape porn now...

What Do You Want To Live For?

There he is, the mid-twen, contemplating the meaning of life. Take care of your career, or go farming the fields? Why not do both? Why live at all?
You're not asking yourself these questions?

You should.
And then some more.
It seems MediaStorm is an invaluable resource of doubt. Doubt every breath you dare to take, every word you write. Doubt them as being privileges you haven't done jack for.

"What are you complaining about? That's the best system we have, and don't tell me it's not working fine!" Being equally ignorant as the feudal ruling class, people fail to see what's happening outside their parks, castles and palaces.
Only the dimensions have shifted. It's a global village now, The West being an enormous castle of nescience, feeding on everybody else.

But what do I do for it? Nothing. Yet?

The Power of ASP.NET

To all you web admins and coders of web servers: please make sure to fail gracefully. What does that mean? Well, you shouldn't present your potential readers with such hilarious demonstrations of your own incompetence:

HTTP/1.1 404 Connection: close Date: Sat, 26 Jul 2008 13:35:29 GMT 
    Server: Microsoft-IIS/6.0 X-Powered-By: ASP.NET 

What's that? A decent 404 message? No! A decent 404 message should include at least an excuse, a clear description of the problem, (not everyone knows how to make sense of something like HTTP/1.1 404 Connection: closed.) and probably a sitemap or search resource to find the content the user came to your web page for in the first place!

Safer startx

Many people claim one should be using a display manager for starting one's X session. One oft cited reason to do so is that when you use startx to fire it up, a malicious person could just circumvent any lock you may have put on your X-session by [ctrl]-[alt]-[←]'ing the server and then being dropped to the console.
However, you can just use the following command:

 startx;exit 

This will exit your session once startx exits. Since X traps all signals, switching to the tty and trying to suspend it won't work.
There's one catch though: my default shell (zsh) will warn you about programs you may still have running in the same shell before exiting and thus prevent the exit command from actually doing its job. So you should be careful about this, or just alias startx so that it first turns off the offending shell option.
This is, of course, also handy for safely giving away restricted prompts to other users (su someuser comes to my mind).

If someone knows a reason this is not safe, please tell me :-)

Edit: I initially thought the pun in this post's title would work only in German, but it appears to be OK for English, too. Thanks to ke for pointing this out.

Update:

I'm such a jerk. Just use the shell's built-in exec. Sheesh.

About the Inertia of Programmers

The Adoption Formula

Over at the Arc Language Blog, there's a nice post trying to give a reason why cool new technologies like Haskell don't catch on nowadays - and why cool old technologies like Lisp didn't catch on some years ago. I'd toss in some Prolog, too - although one reason for Prolog not to be adopted was surely that it was a pain to run on olden days machines.

What they say, basically, is that languages like Lisp or Haskell (or Prolog) are solutions in search of a problem. Not that they're not cool. They are. But who needs higher order functions in programming?
The basic problem is a relation between a certain user's crisis (set of problems, if you so prefer) and the pain of adoption. Let's face it: programmers are a lazy bunch. We'll try not to deviate from the known path any more than we absolutely have to. We remember what a pain it was getting here in the first place. So we have to have a big crisis and some solution that can easily solve this crisis by offering us a way to approach our problems that feels similar to what we already know. Since Haskell, Lisp and Prolog all offer solutions to a set of problems most programmers are not even aware they have (and therefore probably don't really have in the first place), not many people bother picking them up. If they offered solutions to problems programmers know they have, they would see a wider range of adoption.

To make it a bit more clear, take Linux as an example. When Linux saw the light of day, there was an operating system crisis of some sort: Windows dominated the markets and UNIX-based solutions for home PCs weren't cheap or viable (or at all available). BSD was closed source, the HURD was the same vapor it's today. Linux offered UNIX-geeks an easy way out: an operating system that's the same in many aspects, except for those that weren't good about the old one. So that's why Linux got big in geek-world.
But on the desktop market, where grandma and all those pathetic stereotypical example PEBKACs can't tell the difference between a browser and a mail application, Linux is still largely unheard of. Why? Well, Linux solves problems grandma doesn't even know how to spell, nevermind realise having them. Free software? DRM? Hardware support? Stability? Security? Who cares?
Spinning 3D cube? Oooooh, shiny!

That's All Folks... is it?

I'd argue that there is one more aspect to it: if technologies like Lisp or Prolog didn't get adopted, why are they not forgotten? Heck, even COBOL is still around and COBOL is everything but cool. There's an easy answer: those languages found a niche. Lisp has always been big in AI development. COBOL, who knows. Prolog has always had a nice and warm room in the basement of universities - and is now catching on in NLP. In those niches, people come from a different background. They have a different notion of pain. For me, managing pointers, malloc() calls and machine code are a pain. I can deal with the first, don't really understand much about the second and have an allergy to the third. But higher order functions? I've had dreams which happened in intensional logic (that was after reading a paper by Groenendijk & Stokhof, I think)! That was a weird feeling waking up, I can tell you.

Also, our crises are different: we need to interface with inferencing tools, and translate logic and mathematical formulae directly into machine instructions. Doing this in C is a pain. I have nothing but admiration for the people behind prover9/mace4, but I'd argue that Haskell is more suitable for that task. A solution that is less of a pain for us is Prolog. You can program almost the same way you write things down in theory (and quickly see where your theory is failing. Damn). You can then go on debugging your theory and back again to punching it in. To a person doing work in IT business, Prolog will look like a complete disaster. What, no unit tests?. Well, no. But you have guitracer/0 :-).

So, I don't think that Prolog has to catch on. It's good enough if it stays around. Haskell is more suitable for an even wider range of tasks (basically everything), but probably even more of a pain to get started with. But it seems that recently many people got interested in Haskell. The Programming Reddit is full of Haskell lately. And there is now a haskell-beginners list and it seems that introductory CS courses at Tübingen University are being taught in Scheme. Functional programming has received a lot of attention lately - let's see what comes out of it.

Meanwhile, I don't care. As long as Haskell and Prolog continue to be developed and used by a certain niche population, I'm happy. I'll be using them happily. They solve some crises I have, they are not a big pain to adopt if you come with a strong background in logics and sorted type theory. And every time I cuss at Prolog, I have to remember: would it be any better doing this in Java? Probably not.

Oh, and by the way: if you happen to wonder what good books there are on learning logic: Read Gamut's Introduction to Logic and also Volume 2, Introduction to Intensional Logic. Some of the best books I've ever had the pleasure to read. Somewhere next to Camus' Stranger, Dostojewski's Idiot and Nietzsche's Zarathustra.

Advertent Curt

Wohoo, I handed in my BA thesis topic today:

From Questions to Queries

Enhancing the Curt System by a Theory and Implementation of Embedded WH-Questions

The Curt System is implemented in Prolog and presented in the last chapter of Blackurn & Bos (2005), a brilliant book about Vincent, who loves Mia, every owner of a hash bar and foot massages. Oh, and computational semantics. And boxers.

Curt is short for Clever use of reasoning tools. Blackburn & Bos use external inferencing tools, a DCG grammar and an emulation of λ-Calculus in Prolog to put together a nice system that is able to parse sentences according to a toy grammar, construct (discourse) models and logic representations of the discourse. They use inferencing to check the discourse for satisfiability and validity.

They develop several variants of the Curt System throughout that chapter, gradually introducing external inferencing, satisfiability checks, validity checks, model building, world and situational knowledge, ontologies and, last but not least, a way to interpret questions in their framework. The last version of the system is codenamed "Helpful Curt" - it can answer basic direct WH-questions by substituting the WH-phrase for an existential quantification over an uninstantiated variable and running a bit of inferencing magic on it in order to find a result.

Advertent Curt

But I found that a bit ad-hoc. Basically, all of the system is a tad ad-hoc (they use Keller Storage for it still!) and it could use some work in order to become really awesome (although it's already quite awesome!). I'd like to show in my thesis that it's possible to introduce a formal account of question semantics into the system. I'll be following Groenendijk & Stokhof's analyses for the most part, also arguing about Karttunen's earlier approach. The main reason for me choosing G&K over Karttunen was that the former use Ty2 to describe their system, whereas Karttunen stays in traditional Montague IL, which would be harder to transfer into the Prolog world.

Ideally, the system should be able to handle the following types of questions:

(1) Vincent knows whether Mia loves Marcellus
(2) Marcellus believes Mia loves Vincent
(3) Every owner of a hash bar knows who likes hash

But why embedded questions?

Almost all accounts of formal question semantics (I know of) treat direct questions as a subtype of embedded questions (Well, except Hamblin, but that's obvious[ly not adequate here]). Once we solve embedded questions, implementing a few transformation steps to translate (4a) into (4b) should pose no problem.

(4 a.) Tell me who owns a hash bar.
(4 b.) Who owns a hash bar?

In this regard I'm taking the very opposite of the more pragmatic approach by Blackburn & Bos, which explicitly handles direct questions only.

I will try to keep the blog up-to-date with progress and ideas :-)

Anachronism isn't what it Used to Be...

I'm not an English native speaker - and sometimes I find myself in a situation where I need to look up a word from the dictionary in order to find more graceful-sounding synonyms, et cetera. But the dictionary is not always very helpful. Consider the following query in a thesaurus:

Synonyms for begin: … inaugurate …

Well - using to inaugurate right away would lead to strange results, because it's not really used for anything besides politics nowadays.

Concordance and Collocation

This means that sometimes you'll have to not only search for the translation or synonyms of a word, but also for usage examples. A good Dictionary typically provides you with some, but is also usually limited in the amount of examples it can display. This is why looking at occurrances of a word in real text together with their immidiate context is sometimes unaviodable (and in fact the way dictionaries are made). Linguists call that concordance, for grammatical agreement (e.g. using the right temporal form or aspect or the right preposition) and collocation for statistic relatedness (two or more words that form a phrase or a certain reoccurring pattern in language). What linguists now do to find out how a word is used, is, they search for the word in corpora and then classify its context - and patterns thereof.

A Poor Man's Corpus-engine: Google

But such corpora are usually hard to get or expensive, since virtually every accumulation of a non-trivial amount of text will contain copyrighted material (and it's often not easy (read: expensive) to enhance the signal-to-noise ratio). So, as a poor man, one has to resort to Google or equivalent search machines. Searching for a particular word or phrase in Google will often give satisfactory results for its most typical usage patterns. Phrase queries often help to narrow the scope of possible collocations.

… and while doing a bit of research I discovered the following: A word is archaic if the first two pages of Google hits for it return only results from dictionaries. Try searching for advertent (heck, it's not even in vim's default word file on Debian anymore…) as an example...

At Night, Alone with the Computer...

My favorite Prolog dialog

?- true. true.

A lonesome bungalow in the forest; a man; his computer. A conversation arises.