Older blog entries for Pseudonym (starting at number 13)

Long time no blog

Now working for Dot C. Just delivered a certain product which I'm not allowed to talk about (but it's no secret that it has something to do with Alias|Wavefront Maya).

BTW, ajv is right: working in Melbourne for US dollars kicks just about every appropriate part of the anatomy. You have the best of all worlds. I live in two blocks from Lygon St Carlton, too, so I never want for good coffee. It just doesn't get better than this.

slinc

This weekend, I officially threw away the throwaway copy of slinc. I'm now rewriting it in Haskell instead of C++. While I like C++ a lot for many applications, I've decided that compilers and C++ are not a good fit.

The obvious way to implement an abstract syntax tree in C++ is using the composite pattern, with the various passes implemented using virtual functions. Adding a pass means altering every object, even if the pass only needs to act on a small part of the tree. This encourages bigger passes which do more, which can make youre code quite unclear. A much better fit is algebraic types, so that's what I'm doing. That way, I'm not punished for wanting to implement lots of small passes.

Of course, any language with strong typing, algebraic types and pattern matching would probably be up to the job. I just happened to install ghc for an unrelated reason (I tutor first year CS students in Haskell), so I figured "why not".

New job

I will soon be leaving Monash University, working on graphics software full time. A certain company with a weird name is paying me to work from Australia for US dollars. Rather cool.

Not allowed to say what I'm doing. In fact, not allowed to know myself yet. (Now where did I put that nondisclosure agreement?)

Right now I'm trying to work out the best way to launder money. They need to put US dollars somewhere into the financial system and I need to get Australian dollars out of it, and it has to happen reasonably quickly and relatively cheaply. Does anyone have any experience with this sort of thing? Please let me know if you have any suggestions and I'll summarise.

Linux: the object-oriented kernel?

sh: Now all we need to do is remove the monolithic kernel baggage and we'll have a real object-oriented kernel!

Insert obligatory Hurd reference here.

Creationism et al

mrorganic: Betcha didn't expect you'd start a minor religious bunfight (not really big enough to be a "flamewar" yet) on Advogato, didja? :-)

You ask:

How can any reasonably intelligent person believe in this trash?

Until relatively recently in history (couple of hundred years ago at the most), pretty much every intelligent person in the West did. So don't be so surprised.

The current theories about the age of the earth and the origins of life are not obvious. Neither is the theory that the Earth revolves around the Sun, to an Earth-bound observer. Quantum mechanics certainly isn't obvious. Sure, these things are scientific facts, but they're not obvious and they're not trivial. Therefore there are going to be reasonably intelligent people who dissent from the popular wisdom. You shouldn't be surprised.

As a theist, I strongly agree with you about the whole "hell" thing, though. I'm yet to work out why anyone thinks they'll persuade people to follow a religion with promises about what happens after death. Now, I admit it, I'm as morbid as the next person, but this is just Wrong(tm). The man himself put it best: "I came that they may have life, and have it abundantly." People who are in their chosen religion because of perceived or real threat of punishment after death are in it for the wrong reasons. They just Don't Get It(tm).

As a parting shot to this rant, I must echo the words of Dr Peter Carnley, who noted that "God did not send the Son into the world to condemn the world" (John 3:17), but His followers have more than made up for that omission.

Capabilities

dan: For an OS, you get capabilites from the kernel, or some appropriately delegated authority (which from hereon in I will describe as "a security service"). It's most certainly not "we haven't thought about it yet": there are many operating systems in use which use capabilities for security (EROS and Amoeba come to mind).

There is more to it, namely, how are capabilities implemented?

One method is to use unbreakable abstractions. Implement the capability inside kernel or security service, and your normal memory protection system should make the abstraction unbreakable.

The other option (used in Amoeba, because it's a distributed OS) is to use cryptography. It's slow. Enough said.

Mathematics

To the Advogato amateur mathematicians: For those interested in a more "open" MathWorld replacement, I've registered a project on SourceForge under the working title Principia Mathematica. The first mailing list, "principia-discuss" should be up in a little while. Please add yourself if you support the idea of an open encyclopaedic dictionary of the mathematical sciences.

There will be some interesting social and technical challenges. The most difficult technical challenge, as I see it, will be how to handle mathematical and diagrammatic content with a web-based interface in a form that's convenient for mathematicians. I have some thoughts on this (which involve converting between LaTeX, Lout and MathML amongst other things), but I'd like to talk about it first.

ahosey: Actually, 3 is not the smallest coefficient.

The number of decimal digits required to represent the positive number x is floor(log10(x)) + 1. The largest unsigned integer which is N bytes long is 256^N (actually it's 256^N-1, but 256^N always has the same number of digits as 256^N-1, since 256^N is never a power of 10).

It follows that the number of digits required to represent an unsigned integer of N bytes is floor(N * log10(256)) + 1. So the actual smallest factor is more like 2.408, but don't forget the addition of one.

schoen: Never heard of one of those. Incidentally, a resource that's not as good as MathWorld but can help sometimes is The Math Forum. Good luck.

Open question: Do we need a more "open" MathWorld? Perhaps a Wiki-like system?

schoen: Well done! Your proof is much neater than mine.

Now I believe we're well on the way to proving the full challenge. That is to prove:

HM <= GM <= AM <= RMS

Harmonic mean is N / (1/x1 + 1/x2 + ... + 1/xN). RMS is of course the root mean squared, not that other RMS. Equality holds if and only if all numbers in the multiset are equal.

There might be some other means which fit into the chain of inequalities. If anyone knows of them, please let us know.

Does anyone else think there would be much call for some kind of web log devoted to hobby/recreational mathematics?

Long time no blog.

mwh, schoen: The GM/AM inequality can be proven inductively, but it's not easy.

Basically, you prove it for the case N=2. Then you prove that if it's true for N, it's also true for 2N. Then you prove that if it's true for N>2, it's true for N-1. I can sketch out the proof if anyone cares enough.

If you haven't seen the Netizen wake photos yet, please do. I'm the one up the back with the baby on his head.

A question to C++-heads out there: Has anyone found a use for the STL built-in predicates, arithmetic function objects, binders, adapters and/or negaters? Note that I'm not asking "are they potentially useful?" I'm asking "has anyone actually found a non-contrived use for them on a "real" project?" I've been playing around with sequence algorithms for slinc and I keep finding that the built-in function and combinator objects are pretty much useless for any "real" task that I typically want to do. Is it just me?

harrisj: Thanks for the bouquet. It's only because I happen to be good at remembering this esoteric excreta.

You mentioned verification in P-time, and I think it's worth exploring what that means. One technical definition of the class NP is:

NP is the class of decision problems (languages) L such that there is a polynomial time function f(x,c) where x is a string, c is another string whose size is polynomial in the size of x, and f(x, c)=True if and only if x is in L.
(taken from the comp.theory FAQ)

As an example, x might be a graph, c might be a path in that graph, and f(x, c) is the function "is c a Hamiltonian path in the graph x?"

There are at least three kinds of questions that you may want to ask about this problem, given x. They are:

• Is x in L, that is, does there exist c such that f(x, c)=True? That question corresponds to "does the graph have a Hamiltonian cycle"? Or "is the number composite"? This is called a "decision problem", and is not necessarily verifiable in P (unless P=NP, of course), because verifying an answer is identical to finding the answer.
• Given x, give me a c which proves that x is in L. This kind of problem is trivially certifiable in P, because all you need to do is take the certificate c and compute the value of f(x, c). This question corresponds to "find me a Hamiltonian cycle in this graph", or "find me factors of this number".
• Given x, find me the certificate c which minimises (or maximises) some cost function cost(c). This is called an "NP optimisation problem", and corresponds to something like "find me the Hamiltonian cycle of minimal distance" (i.e. the travelling salesman problem). I don't know whether this kind of problem is certifiable in P or not. Could someone please let me know?

Now to EXPTIME. EXPTIME-hard problems are not certifiable in P-time if the certificate is polynomial in the size of the input. If they were, you could construct a nondeterministic polynomial algorithm to solve them. (Nondeterministically guess the certificate in NP time then test it in P time.) So I guess EXPTIME-hard public-key systems and zero-knowledge proof systema aren't feasable. Darn.

If the certificate were not polynomial in the size of the input, that might be a different matter. That is, certifying EXPTIME-hard problems might be polynomial in the size of the certificate. I'm not sure about that one.

EXPTIME-hard problems often turn up when dealing with logic and theorem proving (e.g. constraint systems, conditional logic) or formal languages and the machines which generate/recognise them (e.g. tree automata). Here are some example EXPTIME-complete problems:

• Evaluation of datalog queries for single rule programs containing only a single clause.
• For tree automata, the intersection problem (i.e. given two tree automata, is the intersection of their languages empty) and equivalence problem (do two given tree automata accept the same language)
• Removing recursion from formulas in the mu calculus (i.e. given a recursive formula, give me a non-recursive equivalent if it exists)
• Satisfiability for definite set constraints
• Determining a winning strategy for chess generalised to an N*N board or go generalised to an N*N board. I'm not entirely sure how you generalise chess piece movement, but there you go.

And just for fun, here are a couple of NEXPTIME-complete problems:

• Satisfiability for two-variable first-order logic.
• Provability in first-order multiplicative additive linear logic

Naturally, NEXPTIME-complete problems are certifiable in EXPTIME.

Happy theory nerding.