Thanks for bringing this feature to my attention, by the way. I'd be interested to see if you can use it to solve the next challenge, which was actually the one that inspired this challenge and arose from a real problem in Prolog programming: fairly generating a random permutation, given a source of random integers of arbitrary size. I don't immediately see a way of doing it, but perhaps you do.
Here's source code, in Python this time:
def random_permutation(len):
res = range(len)
for i in range(1, len):
j = random_int(i + 1)
res[i], res[j] = res[j], res[i]
return res
The magic is in the imperative part - the code depends on being able to randomly access an array updating it as it goes. But it seems that Haskell provides a special piece of magic to work around this sort of problem: an array creator which will initialise the array from a sequence of (index, value) pairs in arbitrary order. If that's what's going on (as it appears) and it works in linear time, then the challenge is answered.
I'd be curious to know how long Haskell has had this feature - I first proposed this problem in around 1992.
Interesting - have you timed it to make sure it's really linear time? Several solutions got proposed by experienced ML hackers last time I tried to do this, and I took the liberty of timing them; I found they were all quadratic time.
I don't have a Haskell implementation to hand, though, so I can't time it - let me know what you get. If you can do it to a million-element array almost immediately, it's linear time...
Here's a simple C function which finds the inverse of a permutation, in linear time.
void invert_permutation(
int in[],
int out[],
int len ) {
int i;
for (i = 0; i < len; i++)
out[in[i]] = i; }
Write the same function in Haskell, in linear time. Use whatever representation of a list seems natural for you.
I set this very simple problem to every pure functional programming enthusiast I meet, including several professors at a University known for that sort of thing. I've yet to hear a good answer...
If you think that's the foundation of Schneier's career you've not looked at his academic publications. He was a seriously high-powered cryptographer and cryptanalyst in his own right long before he got into writing for a popular audience.
And when he does write for a popular audience, he does an invaluable job getting home the ideas that people seem to miss when they're thinking about this stuff. Some of the ideas he promotes are far from truisms, such as for example his campaign to get insurance companies involved the computer security business in the hope that he can change the economics of the situation to favour better security.
Applied Cryptography was the right book at the right time; the most important thing about it was simply the message that this stuff was no longer secret and anyone could read about it. At the time it was written this stuff was not available on the Net; it was compiled from academic papers that weren't generally available for download.
(Disclosure/bona fides: I know him to talk to from crypto conferences and I once broke one of his ciphers (Solitaire))
There really should be a word or well-understood phrase for someone who repeats a joke because they don't realise the comment they're replying to was making the same joke first time around.
Wired has up a story about HP, as part of a larger drive to figure out how ideas ideas 'infect' large groups of people, scientifically proving what most people already knew: bloggers steal their ideas from other bloggers.
The existence of God isn't decided by a vote among physicists, of course, but for the record Einstein did not believe in God. "It was, of course, a lie what you read about my religious convictions, a lie which is being systematically repeated. I do not believe in a personal God and I have never denied this but have expressed it clearly. If something is in me which can be called religious then it is the unbounded admiration for the structure of the world so far as our science can reveal it."
XFree86 hashes to the same value as some search term they don't like? Remember, even "XFree86 XFree86" avoids the warning. And terms like "Linux", "AOL" and so forth are fine.
Or maybe the top hit on "XFree86" is a page where someone is really, *really* rude about the new licensing terms.
Your "obvious" impression is directly contrary to that of pretty much the entire computer security community. Read what Schneier has to say on the subject, for example - stealing a bunch of ballots is one thing, but silently altering the entire result of the election without having to expose yourself by moving a single physical ballot and while leaving absolutely no physical sign that anything might be amiss is quite another.
Under IRV, votes for minor parties are therefore symbolic at best, or dangerous at worst. [...] The only way a voter can be assured of not wasting his or her vote is to rank one of the two major parties as their first choice, which is precisely what happens now under plurality voting. [...] if IRV is ever actually adopted, we will likely remain stuck in the old two-party system, just as Australia still is, despite the fact that it has used IRV since around 1920. [...] In other words, IRV will not solve the classic "lesser of two evils" problem that plagues plurality voting. [...] IRV has other serious problems too, which are explained in more detail elsewhere at the website.
In summary, IRV is a deceptive and potentially dangerous non-reform masquerading as a reform. If adopted, the cure could be worse than the disease. Once the inadequacy of IRV becomes clear in actual practice, it could disillusion the public with electoral reform and thereby close the door to true reform. The stakes are way too high to get this one wrong. We can only hope that the well-intentioned and devoted advocates of IRV are still open-minded enough to recognize this reality. The battle for electoral reform will be difficult enough without insurmountable ignorance within the reform movement itself.
I think the case against IRV is overwhelmingly strong. I'd like to hear even a smidgeon of an argument as to why Condorcet wouldn't be in every way far better.
This is a useful insight, thanks. You discuss two relations between licenses: one of compatibility ("~"), which is symmetric and reflexive, and one you call "superset", which defines a partial ordering on licences ("]"). Now note that "X [ Y" implies "X ~ Y", since if in meeting the terms of X you automatically meet the terms of Y, then you can always distribute a combination under the terms of X. (In fact you can define "~" thus: "X ~ Y" <=> \exists Z st Z [ X and Z [ Y and Z permits free redistribution)
I used "compatibility" to refer to the latter property, but you're right that the former property is a better fit for the word. I was misled because the GPL has the property that "GPL ~ X" implies "GPL [ X" - the only licences that are compatible with the GPL are those which are strictly more permissive.
I think this property still means that the poster I replied to was wrong in substance - the GPL is not an "equal partner" with the MITL. They're only "getting along" because the MITL is prepared to do everything the GPL says. Some partnership!
But of course, in this topsy-turvy Universe, no-one can pay SCO to redistribute the Linux kernel; since they can't give the right to redistribute further to the recipients, they can't redistribute in a way compliant with the GPL, and thus any attempt to redistribute will violate about a million people's copyrights.
I've had zero success with CUPS under all-Debian environments, FWIW. At the moment I use BSD lpr and rlpr exclusively as the only thing that's easy to set up and works.
It's a consequence of Zooko's Triangle. See also Clay Shirky's Domain Names: Memorable, Global, Non-political? In summary, there are three properties you want from a naming scheme:
* memorable names * globally unique names * names free from centralized control
No, compatibility is generally one-way. The MIT license is GPL-compatible: that means you can combine code written under the MIT and GPL licences and release the combination under the GPL. However, you cannot release it under the MIT licence: in this sense, the GPL is not MIT licence compatible.
Not to let the facts get in the way of you spouting nonsense, or anything.
Slashdot Mirror
Thanks for bringing this feature to my attention, by the way. I'd be interested to see if you can use it to solve the next challenge, which was actually the one that inspired this challenge and arose from a real problem in Prolog programming: fairly generating a random permutation, given a source of random integers of arbitrary size. I don't immediately see a way of doing it, but perhaps you do.
Here's source code, in Python this time:
def random_permutation(len):
res = range(len)
for i in range(1, len):
j = random_int(i + 1)
res[i], res[j] = res[j], res[i]
return res
The magic is in the imperative part - the code depends on being able to randomly access an array updating it as it goes. But it seems that Haskell provides a special piece of magic to work around this sort of problem: an array creator which will initialise the array from a sequence of (index, value) pairs in arbitrary order. If that's what's going on (as it appears) and it works in linear time, then the challenge is answered.
I'd be curious to know how long Haskell has had this feature - I first proposed this problem in around 1992.
You can crash the code by passing a bogus "permutation", as well as various other nasties.
It would have been a fairer comparison in Python, which automatically bounds-checks arrays. I used C because it's more widely spoken.
Interesting - have you timed it to make sure it's really linear time? Several solutions got proposed by experienced ML hackers last time I tried to do this, and I took the liberty of timing them; I found they were all quadratic time.
I don't have a Haskell implementation to hand, though, so I can't time it - let me know what you get. If you can do it to a million-element array almost immediately, it's linear time...
Here's a simple C function which finds the inverse of a permutation, in linear time.
void invert_permutation(
int in[],
int out[],
int len
) {
int i;
for (i = 0; i < len; i++)
out[in[i]] = i;
}
Write the same function in Haskell, in linear time. Use whatever representation of a list seems natural for you.
I set this very simple problem to every pure functional programming enthusiast I meet, including several professors at a University known for that sort of thing. I've yet to hear a good answer...
If you think that's the foundation of Schneier's career you've not looked at his academic publications. He was a seriously high-powered cryptographer and cryptanalyst in his own right long before he got into writing for a popular audience.
And when he does write for a popular audience, he does an invaluable job getting home the ideas that people seem to miss when they're thinking about this stuff. Some of the ideas he promotes are far from truisms, such as for example his campaign to get insurance companies involved the computer security business in the hope that he can change the economics of the situation to favour better security.
Applied Cryptography was the right book at the right time; the most important thing about it was simply the message that this stuff was no longer secret and anyone could read about it. At the time it was written this stuff was not available on the Net; it was compiled from academic papers that weren't generally available for download.
(Disclosure/bona fides: I know him to talk to from crypto conferences and I once broke one of his ciphers (Solitaire))
I recall being able to buy 7200 RPM drives well over a year ago, and I don't follow these things very closely.
There really should be a word or well-understood phrase for someone who repeats a joke because they don't realise the comment they're replying to was making the same joke first time around.
I have seen severe mental illness close up, and I think that if it could be banished from our society forever we would be very much the richer for it.
That's nothing, I downloaded xqzyk_K32-287634-m452Z-ZZ92ZA.e987.DNA.fqz three months ago!
And another thing:
Wired has up a story about HP, as part of a larger drive to figure out how ideas ideas 'infect' large groups of people, scientifically proving what most people already knew: bloggers steal their ideas from other bloggers.
The existence of God isn't decided by a vote among physicists, of course, but for the record Einstein did not believe in God. "It was, of course, a lie what you read about my religious convictions, a lie which is being systematically repeated. I do not believe in a personal God and I have never denied this but have expressed it clearly. If something is in me which can be called religious then it is the unbounded admiration for the structure of the world so far as our science can reveal it."
XFree86 hashes to the same value as some search term they don't like? Remember, even "XFree86 XFree86" avoids the warning. And terms like "Linux", "AOL" and so forth are fine.
Or maybe the top hit on "XFree86" is a page where someone is really, *really* rude about the new licensing terms.
Your "obvious" impression is directly contrary to that of pretty much the entire computer security community. Read what Schneier has to say on the subject, for example - stealing a bunch of ballots is one thing, but silently altering the entire result of the election without having to expose yourself by moving a single physical ballot and while leaving absolutely no physical sign that anything might be amiss is quite another.
Getting someone marked as a vexatious litigant is almost impossible. And if course, if you try, they'll sue you...
The full phrase is something like "It's a fair cop, guvnor! You've got me bang to rights and no mistake!" See for example, this usage in a debate in the House of Commons on 31 March 1995.
This is a useful insight, thanks. You discuss two relations between licenses: one of compatibility ("~"), which is symmetric and reflexive, and one you call "superset", which defines a partial ordering on licences ("]"). Now note that "X [ Y" implies "X ~ Y", since if in meeting the terms of X you automatically meet the terms of Y, then you can always distribute a combination under the terms of X. (In fact you can define "~" thus: "X ~ Y" <=> \exists Z st Z [ X and Z [ Y and Z permits free redistribution)
I used "compatibility" to refer to the latter property, but you're right that the former property is a better fit for the word. I was misled because the GPL has the property that "GPL ~ X" implies "GPL [ X" - the only licences that are compatible with the GPL are those which are strictly more permissive.
I think this property still means that the poster I replied to was wrong in substance - the GPL is not an "equal partner" with the MITL. They're only "getting along" because the MITL is prepared to do everything the GPL says. Some partnership!
But of course, in this topsy-turvy Universe, no-one can pay SCO to redistribute the Linux kernel; since they can't give the right to redistribute further to the recipients, they can't redistribute in a way compliant with the GPL, and thus any attempt to redistribute will violate about a million people's copyrights.
I've had zero success with CUPS under all-Debian environments, FWIW. At the moment I use BSD lpr and rlpr exclusively as the only thing that's easy to set up and works.
It's a consequence of Zooko's Triangle. See also Clay Shirky's
Domain Names: Memorable, Global, Non-political? In summary, there are three properties you want from a naming scheme:
* memorable names
* globally unique names
* names free from centralized control
Of these properties, you can have any two.
No, compatibility is generally one-way. The MIT license is GPL-compatible: that means you can combine code written under the MIT and GPL licences and release the combination under the GPL. However, you cannot release it under the MIT licence: in this sense, the GPL is not MIT licence compatible.
Not to let the facts get in the way of you spouting nonsense, or anything.
No
And who should be the PKG, the third party in whom we trust all authentication of everybody and to be holder of all private keys, if we use IBE?
Remember that in practice it would be Verisign.
IBE is *not* a good solution to this. Actually it is very rarely appropriate.
Thanks. Just noticed that it linked to an old version of the page; I've updated the link.
I particularly like the comments on the "truth is in the middle" attitude. I've updated my bio with something to that effect.