Oct 31 2005
In thinking about it more, I’m back to declaring the equals(Object) method completely screwed. The this.getClass().equals(them.getClass()) || them.equals(this) causes an infinite recursion if you have an instance of one subclass call it on an instance of a different subclass, neither of which override equals(Object).
Popularity: 2% [?]
Oct 28 2005
Java has a universal “equals” method, as well as a “Comparable” interface that defines “natural comparison”. I always had a distaste for that design decision, and that distaste has just been further validated.
So, I have a class which looks like this:
public class TwoDeePoint implements Comparable {
public int x = 0;
public int y = 0;
public boolean equals(final Object obj) {
if(obj == null || !(obj instanceof TwoDeePoint)) {
return false;
} else {
TwoDeePoint them = (TwoDeePoint)obj;
return them.x == this.x && them.y == this.y;
}
}
public int compareTo(final Object o) {
if(o == null) {
throw new NullPointerException();
} else if(!(o instanceof TwoDeePoint)) {
throw new ClassCastException();
} else {
final TwoDeePoint them = (TwoDeePoint)o;
final int xCmp = new Integer(this.x).compareTo(new Integer(them.x));
final int yCmp = new Integer(this.y).compareTo(new Integer(them.y));
return xCmp != 0 ? xCmp : yCmp;
}
}
}
Even ignoring certain religious/performance fights (like whether the trinary operator is evil, why I declare so much crap “final” and whether the “x” member variable should be “X“, or even visible at all…), there is a major error to this code. Specifically, consider this class:
public class ThreeDeePoint extends TwoDeePoint implements Comparable {
public int z = 0;
public boolean equals(final Object obj) {
if(obj == null || !(obj instanceof ThreeDeePoint)) {
return false;
} else {
final ThreeDeePoint them = (ThreeDeePoint)obj;
return super.equals(obj) && them.z == this.z;
}
}
public int compareTo(final Object o) {
if(o == null) {
throw new NullPointerException();
} else if(!(o instanceof ThreeDeePoint)) {
throw new ClassCastException();
} else {
final ThreeDeePoint them = (ThreeDeePoint)o;
final int supCmp = super.compareTo(them);
final int zCmp = new Integer(this.z).compareTo(new Integer(them.z));
return supCmp != 0 ? supCmp : zCmp;
}
}
}
See the problem yet? Guess the result of the following snippet of code:
final TwoDeePoint a = new TwoDeePoint();
a.x = 1;
a.y = 2;
final ThreeDeePoint b = new ThreeDeePoint();
b.x = a.x;
b.y = a.y;
c.z = 3;
System.out.println(a.equals(b));
System.out.println(b.equals(a));
The answer is that the snippet will print out:
true
false
And there’s the problem: the equality operator, which is designed into all classes and is so critical to the operation of so many standard collections, has a very common and glaring issue. Given this implementation, a Set of TwoDeePoint and ThreeDeePoint objects may or may not insert a new ThreeDeePoint if its x and y are the same as an existant TwoDeePoint, and the deciding issue which equals method the programmer decided to call. Since the equals method is reflexive by definition, it shouldn’t make a difference…but it does.
The kludge that all Java programmers need to burn permenently into their brain can be modelled after the following change to the TwoDeePoint class:
public boolean equals(final Object obj) {
if(obj == null || !(obj instanceof TwoDeePoint)) {
return false;
} else {
TwoDeePoint them = (TwoDeePoint)obj;
if(them.x == this.x && them.y == this.y) {
if(them.getClass() == this.getClass()) {
return true;
} else {
return them.equals(this);
}
}
}
}
At the point when we do the class check, we know that they are an instance of our class. If they are not precisely our class, then they are an instance of a child class, and we should make sure that they are equal to us. A similar change also needs to be made to compareTo.
Of course, if I’ve got a Collection of arbitrary TwoDeePoint objects, I now know that two of them may not be equal even though their x and y values are equal, so if I only care about the x and y values, I need to write my own method to compare them which is external to the TwoDeePoint class, which really begs the question of whether that equals method is worth anything at all…
EDIT: I just realized that my code has a possible infinite recursion case. Specifically, if two ThreeDeePoint objects compare to eachother, they’ll end up spinning infinitely into the abyss. Crap…I don’t know if there is a solution to this problem without breaking its object-oriented nature (e.g.: explicitly checking x and y in ThreeDeePoint)…
Popularity: 7% [?]
Oct 20 2005
Every couple of months I dig out “Cosmos” and watch Carl Sagan again. One nice thing about DVDs is that they die a lot slower with this sort of abuse than the VHS tapes of Cosmos did.
Anyways, one interesting thought went through my head. OK, assume we receive the signal from alien intelligences in some distant start, an in proper Sagan style, it’s a sequence of prime numbers: 2, 3, 5, 7, 11, etc. But no richer message has been found yet, just a short sequence of prime numbers. What can the prime numbers tell us about the alien civilization? That it’s an intelligent species trying to be blatant about it’s intelligence, is the standard Sagan reply. No natural phenomenon could produce such a highly artificial sequence. But is that all we can tell about the alien species, given that clue? I’d argue no.
The first, and by far the most interesting thing, is that the aliens have the same sort of math we do. This is by no means a given, there may be ways to understand the universe that do not involve integers. It’s the only way we know how to understand the universe- counting integers seems to be bound up in our perspective of the universe. Even chimpanzees have the concept of “an apple” as a distinct entity, this apple as being distinct from that apple over there, and thus the concept of “two apples” is natural to us- giving rise (eventually) to the abstract concept of “two-ness”. Early human tribes had different number words for two rocks vr.s two apples, it took us a bit to get the idea of the abstract two concept. But it was the inevitable next step for us humans, I can’t think of any other way it could have gone. But that doesn’t mean an alien species, with a radically different form of intelligence, couldn’t understand the universe without integers. We have only the one sample of an intelligent species (humans)- we can’t begin to even say it’s improbable.
But if they’re sending us a list of primes, they have integers. And integers are really the key into our whole system of mathematics. Even if you just start with the counting integers, the positive integers, you very rapidly start running into problems like what is the number X such that X + 1 = 1? Given the question of what is X given X + 1 = 2, I can solve easily- X = 1. But what is X given X + 1 = 1? Solving this requires me to invent a zero. Then I ask, what is X given that X + 2 = 1? This forces me to invent negative numbers. Note that the questions I am asking all only contain positive integers! So then I ask, what is X given X*3 = 2? This forces me to invent the rationals, so I can say that the answer is X = 2/3. But then I ask what is X given that X*X = 2? This forces me to invent the irrationals. Then I ask what is X given that X*X + 2 = 1? This forces me to invent the imaginary numbes. The imaginary numbers gives me geometery (if I don’t already have it), systems of linear equations gets me linear algebra and geometery in multiple dimensions, and so on. They almost certainly have more math than we do, and may have different math than we do. Integer-based mathematics may be this weird sub-field only taught to a handfull of graduate students, while the undergrads and grade school children are taught some wildly different sort of mathematics, but they have our sort of mathematics.
The other interesting thing is where the sequence stops. Why did it stop there, and not somewhere else? Say the sequence is:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Why stop at 97? Why not go on an include the next prime in the sequence, 101? The reason has to be that there is some “natural stopping point” for the aliens between 97 and 101- there is something different about 97 vr.s 101 which is relevent, “natural” in some sense, to the aliens. We humans are immediately drawn to the answer of 100 being the natural stopping point. For people using base-10 arithemetic, the above list of primes are all the one and two digit primes. What’s different about 97 vr.s 101 is that 97 is two digits, while 101 is 3 digits. If that is the sequence of primes being sent, it’s reasonable to assume that the aliens do their arithmetic in base 10, just like we do. But if the sequence is instead:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167
we might note that 169=13*13 is between 167, the largest prime in the sequence, and 173, the smallest prime not in the sequence. At that point, by exactly the same logic we used above, we can assume that the aliens do their arithmetic in base-13.
One trick to this is that the aliens may be using weird arithmetic forms. We naturally think of representing numbers as a series of digits in base B, where each digit can assume any value in the range 0 to B-1, and a number is represented by the sequence d0 + d1B + d2B2 etc., where di is the ith digit. But there are other forms of arithmetic. For example, there is a form where the digits have values in the range of 1 to B, instead of 0 to B-1. Keep B=10 in this system, and using A as the 10th1 + 10), 21 would be 21 still (2*101 + 1), 30 would be 2A, 100 would be 9A, 101 would be A1, and 110 would be AA. If the aliens used this sort of number system, they’d probably send us the prime sequence:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109
This prime sequence would initially deeply confuse us, because if they used base-10, they wouldn’t have included the primes 101, 103, 107, and 109, but if they used base-11, they wouldn’t have stopped at 109, but included the prime 113 (A3 in base-11) as well. It’d be like us stopping at 89. It wouldn’t be until we thought of the zeroless base representation that we’d figure it out.
Unfortunately, in many cases there are multiple different possbilities. We could rule many arithmetics out, but still be left with more than one possibility. For example, say the sequence goes to 29. We might be tempted to conclude that the aliens use a zero-less base-5 arithmetic, as 30 (55 in zero-less base-5) is more than 29 but less than 31- until some joker points out that 29 is also the 10th prime, and is another sensible stopping point if you use base-10 (zero-less or not). We may not be able to tell if they use a zero-less base 5 or a base 10 (zero-less or not) number system, but we can pretty sure they don’t use a base-7 system.
And some bases tell us less than others. If the aliens come out using base-11, that tells me something about them. But what if they use base-16? There are good reasons that arise out of physics why our computers use base-2 (and powers of two, and powers of powers of two, etc)- reasons that would apply to the aliens as well as us. We’ve only been using computers for a few decades. They have not yet had time to have major impacts on our society. But what of a society that that has been using computers for millions of years? I could see them having migrated over onto binary, or some easy to convert to/from binary system, like base-16. If you hand the problem over to a long time programmer, they are already likely to have the series end at 251, i.e. generate all primes less than 28, or in programmer terms, all primes that fit into a single byte. Finding out the aliens use base-16 tells me that they have more or less the same computer technology we do, but isn’t nearly as interesting as if we figured out they use a zero-less base-11 system.
And some sequences don’t mean anything. In the movie “Contact”, for instance, the aliens terminate their sequence at 101. Other than being the 26th prime, there is no reason I can think of to stop there. It’s not a natural stopping point for any base I can think of, other than base-26.
Popularity: 2% [?]
Oct 19 2005
I recently started a bit of a ruckus on the Minneapolis PerlMongers list by suggesting that Perl prototypes are Good, not Evil. This is going up against the saints of Perl, particularly Tom Christiansen, and so the position was pretty much dismissed out of hand.
I’d like to take this opportunity to say that, after serious consideration, I stand by my position. I will unequivicably state that I think Perl prototypes (with minor reservations) are a Good Thing, and that all new code should use them. After considering his complaints, I will furthermore assert that I think Tom secretly hates Perl, and that he’s blaming prototypes for his fundamental disappointments with the language.
The fundamental issue is whether it is better to allow PI - 1 to secretly and silently become PI(-1), or to allow people to pass arguments as a list — as far as I’m concerned, the issue with the first is bigger than the advantage of the second, and therefore I support prototypes. I believe that if you’re talking about scalars, you should use $, so if you want to pass scalar parameters into a function, you should have to draw scalars out of your array somehow — it’s broken to automagically draw for you.
Now, before continuing I’d want to state that I certainly would agree that there are bugs in prototypes. Here’s the start of a list, although I reserve the right to append onto it:
scalar function, it should be used. It should be a warning (at least) to do this in code with the warnings and/or strict pragma in play.@ prototype symbol is a bug. Since the @ prototype symbol consumes all remaining elements, the concept of arguments “after” the @ is nonsensical.% prototype symbol is also a bug. The concept of a \% prototype symbol is legitimate (there are hash references), but the concept of a % prototype symbol is nonsense (there is no “hash context”). Perl prototypes force context and silently reference variables, and that’s it.* and & prototypes need to be made more clear, because they’re awkward and buggy.Once you get past these (fixable) issues, though, the rest of Tom’s complaints are actually complaints about the Perl language as a whole, in that I can find equivalent problems in the core Perl functions.
Now let’s address Tom’s complaints directly.
The first surprise is that when Perl programmers see “$”, “@”, and “%”, they usually think “scalar”, “array”, and “hash” respectively. This isn’t completely accurate in all cases, but it is, nevertheless, what they often think.
So, in short, Tom is saying that since people haven’t taken the time to really understand what prototypes are, we shouldn’t use them. If you understand that prototypes ONLY force context and magically take references, you’re not going to think “scalar” when you see the “$” prototype: you’re going to think “scalar context”. Assuming that we can make that minor adjustment to the way people think, we gain the major advantage of actually being able to write rand 10, rand 10, rand 10 without it becoming rand(10, rand(10, rand(10))) or something equally nonsensical.
So when the user sees a “prototype” of “$”, the primrose programming path leads them to believe, lamentably, that the compiler will complain if they pass something in that’s not a scalar. Nothing could be further from the truth!
Granted. As stated above, this is a bug: it’s a fixable problem, not built into the design of Perl prototypes. If Tom really doesn’t like it so much, he should hack the Perl code to fix it. Still, even without it being implemented, all that means is that people who use your code wrong are going to get garbage results: GIGO. This problem is also not unique to prototypes (remember Tom hating Perl?): the code length(@arr) will silently and cleanly succeed, which means the issue exists in the core of the language.
@array = (1 .. 10);print length(@array);You might think that would be an error, but it’s not, because there exists an implicit coercion rule for arrays taken in scalar context: it’s the number of elements in that array.
In the particular example of length(@array), non-prototyped code would also gleefully and secretly succeed, returning the length of the first element of the code. Since the same class of problem exists whether or not prototypes are there, it’s not prototypes that are the problem. The problem is the intuitive behavior, but that problem is really with the length function’s name being misleading. Even more, without prototypes, the calls length(), length($a, $b, $c), and length(@arr1, @arr2) would all silently succeed.
There’s more similar arguments laid out, so I’m going to skip over them unless there’s some real insistance. The upshot is that the problems are with Perl’s insistance on trying to do the right thing even when it doesn’t always make sense: the , operator that evaluates expressions and returns the value of the last one, the implicit coercion of lists into scalars, etc., etc. So Tom’s problem isn’t with prototypes, but with Perl’s behavior in those cases. The prototypes are doing precisely what they’re supposed to be doing by forcing context, and when you pass garbage into them, they get you garbage out — the fact that the compiler doesn’t whine is a bug which should be fixed, but not sufficient cause to be rid of them completely.
Let’s examine the “@” “prototype”. What’s that? Is it an array? No, it’s not. It just looks like that. It’s merely a list. Is it a required list? Why no, it’s not. You’re welcome to supply a list of no elements; that is, omit it altogether.
Granted. You need to keep in mind that “@” means “all remaining arguments, possibly zero”. Once you know that’s the case, though, you can code with it. Perl happilly has zero-length lists everywhere else: why does Tom expect prototypes to be different?
Finally, he has this complaint:
To see how this works when you use “\@” in the “prototype”, you haven’t declared a function as taking a reference to an array. Rather, you’ve declared one that takes an array, which the compiler will pass by (implicit) reference to you.
Granted. Perl will take implicit references for you all over the place: for instance, push(@arr1, @arr2), which Tom acknowledges. The fact that you can’t tell that the first is being treated as a reference and the second is being treated as a list isn’t a problem with prototypes, it is a decisison explicitly made to Do The Right Thing while keeping the number of \ characters to a minimum. If you don’t like it, you don’t like that aspect of Perl’s nature, so the problem is much larger than prototypes. Blaming prototypes for them is like blaming a carpenter’s hammer because you don’t like the architecture of your house.
Think of how often you’ve been forced to do something like
push @{ $hash{$string} }, $value;Why can’t you just do this:
push $hash{$string}, $value;It’s because of the “prototype”.
Actually, it’s because Larry Wall didn’t want to have to type push \@arr1, @arr2 every time the push function was used, and because he made the decision that Perl did NOT do implicit dereferencing so that $hash{$string} = $arrref didn’t get silently dereferenced. Again, the problem isn’t the prototype, it’s other aspects of the language that happen to involve calling subroutines.
Given those considerations, I’ve got to say that I just think Tom’s railing against prototypes really exposes a very superficial consideration for how the langauge actually works and how prototypes fit in there — he aggrandizes them to blame them for things that aren’t their fault (the compiler not issuing warnings), and then is annoyed when they don’t do things the language explicitly is designed not to do (implicit dereferencing). It’s not prototypes that Tom has a problem with, it’s Perl.
Popularity: 4% [?]
Oct 16 2005
Went out to a wedding reception last night: congrats to the lovely couple, and I’m glad to be a part of that extended family.
Popularity: 1% [?]
