Freeing Algorithms

[Stefan Ram]

If you possess the knowedge to narrow down to within a specific
year when the sun will implode

The following article from 2002 says »in less than 6 years«.

http://web.archive.org/web/20021015123543/http://tv.yahoo.com/news/wwn/20020918/103236120009.html

So, it might be 2006, 2007 or 2008 - indeed we do not know yet
/exactly/ which year.

(In order to help to avoid panic, please do /not/ spread the
information of this article. This information is intended for
the eyes of readers of »comp.lang.java.programmer« only.)

 

[Tony Morris]

To me, this is a prime example of inappropriate extension.

Before extending a method to a wider domain, it is essential to consider
any underlying assumptions, and decide whether they remain valid over
the new domain. There is often far more to widening the domain than just
picking bigger data types.

In this case, the underlying assumption is the Gregorian calendar, and
its approximation to the relationship between day and year length. Leap
seconds are coming in about one a year, and most of them are in the same
direction. At one second per year, it would only take 86,400 years to
accumulate a day of leap seconds. Obviously, something is going to have
to change in time management well within the next hundred thousand years.

Sometimes generality is free, sometimes it costs, in programming and
testing time, and in runtime efficiency. In this case, the generality
gain from using int rather than short is effectively free, and there is
some risk short would not be wide enough.

On the other hand, int is simple, efficient, and handles very
effectively the entire domain over which the algorithm makes any sense.
It is a fine data type for this job. BigInteger, or even long, would be
overkill.

Patricia

By the very same reasoning, int, and in fact, Java, is a poor choice.
The data type int falls somewhere before the (assumed) requirement of
the user. To paraphrase the requirement (since requirements cannot be
accurately expressed in English (or a programming language for the Mr.
TDD!)), a data type that extended between negative and positive infinity
is required to express the arrow of time. Of course, this cannot be
achieved - quantum mechanics not withstanding - since it comes down to
things like physical hardware limitations, etc.

The question now is, why is the user of the programming language
restricted to express his/her implementation of requirements using a
tool - the programming language - that falls short of the target? Why is
the restriction not put in place by other physical limitations? And more
importantly, why does the programming language even care about such a
restriction? More often than not, I see an exceeding of requirements,
and here we are observing a not-so-common case, so it makes things a
little more difficult to argue. That is, it is much more easy to argue
on the premise of excess requirements since it is much more common, and
subsequently digress to this case, so I'm going out on a limb.

Assuming Java provided a data type that permitted an extension to
infinity (this excludes BigInteger for other reasons that I have omitted
and hope are not picked up on - for brevity), then it would certainly
make int look like hitherto "overkill". Since int could be viewed as
"being exactly the same as the infinite data type with the addition of a
restriction of finite bounds". One could then go on to say that this
restriction is indeed "addition" and since this addition "exceeds
requirement", it is therefore, "overkill".

The moral of the story is, formally express your requirements, even if
it is in your own head (admittedly, this is extremely difficult to do in
the face of the prolific "propaganda"). Unfortunately, Java contradicts
this ability in more ways than one, so we end up with some contrived and
blurred understanding of "what the hell it is we are doing" - to state
it loosely but not to undermine its importance. Nevertheless, I concede
to the immense power that marketers/evangelists/proclaimed
"experts"/etc. have...

In the meantime, I continue to document (though not publicly for now -
my recent resignation from IBM (i.e. The Filth) now permits me to) what
I, and a select few others, believe is a sound refutation and logical
proof of the invalidity of many of the tools (including Java itself)
that so many assume to exist legitimately within our common axioms.

 

[Lasse Reichstein Nielsen]

That's why, within my source tree, this is placed into the
package »gregorian«. This was not visibly from my post.

If I keow it's gregorian, I would just use the GregorianCalendar:

public boolean isLeapYear(int year) {
GregorianCalendar c = new GregorianCalendar();
c.setLenient(true);
c.set(year, GregorianCalendar.FEBRUARY, 29);
boolean isLeapYear =
(c.get(GregorianCalendar.MONTH) == GregorianCalendar.FEBRUARY);
return isLeapYear;
}

This doesn't help you with the "int" limit on years, but it does remove
the burden of understanding the leap year calculations from you. Should
it change, e.g., by adding a 4000-year rule, an update of the standard
library would fix it for your application without you needing to concern
yourself about it.

Also, unless you plan to implement your own date methods for all
purposes, having some of them support dates outside the domain of
the standard methods will not help greatly.

/L

 

[Rob Skedgell]

Roedy Green wrote:

[...]

there are an surprisingly large number of definitions of leap year
besides the Gregorian one we are familiar with. See
http://mindprod.com/jgloss/leap.html

Shouldn't that be <http://mindprod.com/jgloss/leapyear.html>?

 

[Chris Uppal]

So there is no need to bind it to the special type »int« that
has many more features which are not needed here. The
following untested draft shows how the algorithm can be freed
from this binding.

I can see what you are getting at, but I think there are several problems.

The first is purely practical: it's hellishly verbose.

The seconds is more theoretical: it requires the designer of the objects that
the algorithm is applied to, to have considered these kinds of uses in advance.
That means they have to decide what are sensible "bundles" of methods for
algorithms to use, and to separate each bundle out into an interface. That way
lies analysis paralysis. It's also a helluva lot of work for little gain.

The third is also theoretical: it exposes a great deal of detail about how the
algorithm works, to the client code. In your example it exposes the fact that
it uses modular arithmetic (which is probably acceptable), but it /also/
exposes the fact that it does /not/ use other arithmetic operations. That
increased coupling is (IMO) a very bad thing. For instance, it restricts
future improvements to the algorithm. Note that this is a kind of dual to my
second objection, in that the coarser the bundles of methods "published" by the
Year objects, the less closely coupled the algorithm is to the Years, but on
the other hand, the greater the constraints on the design of the Year class.

I think what's really going wrong here, is that you are trying to do this stuff
/by hand/. I don't see anything wrong with trying to make a very fine-grained
evaluation of the features that algorithm X requires of the objects to which it
is applied, but in languages where that is feasible, it is always[*] managed
automatically. For instance, ML, C++ (templates), and Smalltalk, all achieve
this desirable end -- in very different ways but in each case automatically. I
think that if you want to do this, then Java is the wrong language to use. If
you want to do this sort of thing /and/ run on a JVM then you'll have to either
define your own language (or possibly an automation layer as a front-end to
javac), or switch to, say, Nice or Scala[**].

([*] As far as I am aware).

([**] I'm not actually certain that either Nice or Scala /does/ support this,
but either might...)

-- chris

 

[Alan Krueger]

So helping someone to improve his articles is regarded
as a »battle« by you.

That's usually a figure of speech not intended to be interpreted literally.

 

[Alan Krueger]

Do you really think the average Java programmer will ever care whether the
year 23456543215678908765432124354667 is a leap year?

I would hope the average Java programmer would first notice that it
wasn't a multiple of four.

 

[Dimitri Maziuk]

Stefan Ram sez:
Actually, your T must implement operator % as well.

So, how can this be achieved in Java?

interface IsCongruentModulo<S,T>
{ boolean isCongruentModulo( S comparand, T modulus ); }

The drawback is that you'll have to wrap your ints in
Integer.

Dima

 

[Stefan Ram]

The third is also theoretical: it exposes a great deal of
detail about how the algorithm works, to the client code.

This is true. But this exposure possibly can not be avoided.

Software engineers often take hardware as a role model.
Hardware devices have interfaces (connectors).

So a device having a power-supply connector and a loudspeaker
connector exposes that it needs power and possibly a
loudspeaker. But hiding this might be impossible.

It could add additional connectors in order to hide
the information that it only needs a power-supply and
a loudspeaker. The client then would have to connect
to all the connections but would not know which of them
really are used and which not.

But in the case of a hardware device one would see
little use of this over-hiding.

In your example it exposes the fact that it uses modular
arithmetic (which is probably acceptable), but it /also/
exposes the fact that it does /not/ use other arithmetic
operations. That increased coupling is (IMO) a very bad thing.
For instance, it restricts future improvements to the
algorithm.

Within my paradigm, in this case, I will not /change/
the existing algorithm, but /add/ another algorithm
with the new interface.

I think what's really going wrong here, is that you are trying
to do this stuff /by hand/.

On one hand, C++ templates are great for such algorithms.
I still use Java, because I like the fact that Java has a GUI
(Swing) as part of its standard edition and that there are
JVM-implementations for several platforms. And C++ is really
a mess with all thos legacies and complicated rules.

 

[Chris Smith]

I'm afraid I have been getting lax about snipping lately. I've had people
"yelling" at me for snipping;

I didn't see the specific discussion you're talking about, but that is a
common USENET flame/"discussion" tactic. Rest assured that had you not
snipped that person's comments, he/she would almost certainly have found
something else to yell at you over.

one guy even _killfiled_ me because I had
snipped a previous poster's _sig_,

That's a new one for me.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Chris Uppal]

Stefan Ram wrote:

[me:]

This is true. But this exposure possibly can not be avoided.

Software engineers often take hardware as a role model.
Hardware devices have interfaces (connectors).

I think the hardware analogy is often pushed beyond its limits....

So a device having a power-supply connector and a loudspeaker
connector exposes that it needs power and possibly a
loudspeaker. But hiding this might be impossible.

It could add additional connectors in order to hide
the information that it only needs a power-supply and
a loudspeaker.

I suspect this is a rather misleading analogy. Well-designed and universal
hardware interfaces /do/ hide a lot of information. For instance, a mains plug
is the same shape whatever the power requirements (within limits) of the
appliance, so the mains "interface" is hiding a great deal of information.
That seems to me to be similar to the case where the interfaces used to define
requirements of an algorithm, or properties of an object, are defined very
broadly.

OTOH, if the hardware interface were as specific as in your example with Years,
then we would have something more like the mess with power adaptors for
laptops, phones, etc -- all of which seem to take malicious delight in strongly
coupling the laptop to the adaptor (you can't mix-and-match)

And there's the same tension in the design of hardware interfaces. The more
universal the interface (mains power) the more work the things that /use/ it
have to do. They have to convert the generic main power to their own specific
requirements, rather than just "assuming" that they'll get, say, 1.3 v
stabilised DC.

Within my paradigm, in this case, I will not /change/
the existing algorithm, but /add/ another algorithm
with the new interface.

But then you are pushing extra work onto the designers of the client objects.
They have to anticipate the interface required by the next algorithm, and
declare it. (That's assuming that the objects already have the necessary
abilities, but those are not exposed as an interface).

-- chris

 

[Stefan Ram]

But then you are pushing extra work onto the designers of the
client objects. They have to anticipate the interface required
by the next algorithm, and declare it.

This is assuming that an algorithm was /replaced/ by a
successor. My original paradigm was that algorithms and
interfaces do not change. So I thought about /adding/ an
/additional/ interface and algorithm that can be ignored by
clients (like Sun has added StringBuilder instead of changing
StringBuffer).

However, you might be right that in real live I /will/ change
interfaces and algorithms.

 

[Oliver Wong]

I can see what you are getting at, but I think there are several problems.

The first is purely practical: it's hellishly verbose.

The seconds is more theoretical: it requires the designer of the objects
that
the algorithm is applied to, to have considered these kinds of uses in
advance.
That means they have to decide what are sensible "bundles" of methods for
algorithms to use, and to separate each bundle out into an interface.
That way
lies analysis paralysis. It's also a helluva lot of work for little gain.

The third is also theoretical: it exposes a great deal of detail about how
the
algorithm works, to the client code. In your example it exposes the fact
that
it uses modular arithmetic (which is probably acceptable), but it /also/
exposes the fact that it does /not/ use other arithmetic operations. That
increased coupling is (IMO) a very bad thing. For instance, it restricts
future improvements to the algorithm. Note that this is a kind of dual to
my
second objection, in that the coarser the bundles of methods "published"
by the
Year objects, the less closely coupled the algorithm is to the Years, but
on
the other hand, the greater the constraints on the design of the Year
class.

On the topic of good OO design, the concept of a "year" and the concept
of an "integer" are not nescessarily interchangeable. Rather than passing in
some arbitrary integer into a method, and having that method answer the
query "If you take this integer, and interpret it as a Gregorian year
number, would this be a leap year in the Gregorian calendar?" it might be
better to have a type which defines a "point in time" (for simplicity, let's
assuming newtonian physics, and i.e. a globally agreed progression of time),
and then query that "point in time" object, does this point occur within a
leap year under the gregorian calendar?

The "point in time" might implement its state using ints representing
seconds since the unix epoch (and thus could represent points prior to the
epoch via negative numbers), or it might use BigInteger to represent
nanoseconds since the the Big Bang, or something else. It doesn't matter,
and you shouldn't need to know how it internally keeps track of its time.

Alternatively, you might have various Calendar objects, which take as
input a "point in time" object, and then could answer questions about that
point in time (e.g. there might exists calendars for which the concept of a
"leap year" is meaningless).

- Oliver