Why is dynamic polymorphism so useful?

[Patricia Shanahan]

It depends on how sneaky the compiler wants to be. If it notices that
this code is only called once, couldn't it generate the random number at
compile time, and then just compile the appropriate branch?

No, because the result of Math.random() depends on the time of the first
call, and the number of prior calls to it anywhere in the program,
including in code that is not available at compile time. I assume
Math.random() was used in the example to represent any method whose
result depends on run time data, and varies from call to call.

In any case, the compiler needs a strategy that will work for multiple
calls.

Patricia

 

[Lew]

No, because the result of Math.random() depends on the time of the first
call, and the number of prior calls to it anywhere in the program,
including in code that is not available at compile time. I assume
Math.random() was used in the example to represent any method whose
result depends on run time data, and varies from call to call.

In any case, the compiler needs a strategy that will work for multiple
calls.

Even conceptually the idea of pre-compiling a random result is repugnant.
What would that do to cryptography?

In fact, random() is supposed to depend on unknowable, future extrinsic
events, like the output of your system's entropy generator. We should
understand its role as close to being truly random. The "pseudo" in
"pseudorandom" isn't supposed to mean, "deterministic, decided before we even
deploy the program". It's like the old math joke - any time I need a random
number I pick 17.

 

[Lasse Reichstein Nielsen]

It depends on how sneaky the compiler wants to be. If it notices that
this code is only called once, couldn't it generate the random number at
compile time, and then just compile the appropriate branch?

It cannot tell that it is only called once. Apart from the undecidability
of the general problem, the compiler doesn't know how many times the
program will be run.

Also, Java is a dynamically linked language where the compiler doesn't
necessarily have the entire program at compile time. The class compiled
at one time might be combined with classes compiled at another time and
place, and the entire program should still work correctly.


/L

 

[Arne Vajhøj]

Even conceptually the idea of pre-compiling a random result is
repugnant. What would that do to cryptography?

In fact, random() is supposed to depend on unknowable, future extrinsic
events, like the output of your system's entropy generator. We should
understand its role as close to being truly random. The "pseudo" in
"pseudorandom" isn't supposed to mean, "deterministic, decided before we
even deploy the program". It's like the old math joke - any time I need
a random number I pick 17.

You are not supposed to use Math.random or java.util.Random.* in
cryptography - java.security.SecureRandom exist to handle those
cases.

Arne

 

[Tim Smith]

It cannot tell that it is only called once. Apart from the undecidability
of the general problem, the compiler doesn't know how many times the
program will be run.

Why would it matter how many times the program is run? I don't see
anything (although I didn't do a deep search) in the documentation of
Math.random() that says the first value returned across different runs
of the programs must satisfy any particular distribution requirements.

 

[Tim Smith]

In fact, random() is supposed to depend on unknowable, future extrinsic
events, like the output of your system's entropy generator. We should
understand its role as close to being truly random. The "pseudo" in
"pseudorandom" isn't supposed to mean, "deterministic, decided before we even
deploy the program". It's like the old math joke - any time I need a random
number I pick 17.

You've confused java.util.Random with java.util.SecureRandom. The
former, which is what Math.random() uses, is a linear congruential
generator. It is deterministic and completely predicatable from the
current state. No external events affect it.

(And if you don't know the current state, observing consecutive output
of the generator allows the state to be recovered. That's why such
generators are completely unsuitable for cryptographic work. They were
broken a very long time ago--I believe it is even mentioned in the first
edition of Knuth volume 3, to give an idea of how long ago they were
broken).

Linear contruential generators are OK where you care about are the
statistical properties of the output, and do not care about the
predictability of it.

 

[Patricia Shanahan]

Why would it matter how many times the program is run? I don't see
anything (although I didn't do a deep search) in the documentation of
Math.random() that says the first value returned across different runs
of the programs must satisfy any particular distribution requirements.

The Math.random() documentation says "When this method is first called,
it creates a single new pseudorandom-number generator, exactly as if by
the expression

new java.util.Random

This new pseudorandom-number generator is used thereafter for all calls
to this method and is used nowhere else."

The java.util.Random documentation says that the parameterless
constructor "sets the seed of the random number generator to a value
very likely to be distinct from any other invocation of this
constructor." The algorithms for generating the streams of numbers from
the seed are fully documented.

I don't see how a compile-time selection could conform to that contract,
because it would act as though seed were the same for every invokation
of the java.util.Random constructor.

Patricia

 

[Lew]

You've confused java.util.Random with java.util.SecureRandom. The
former, which is what Math.random() uses, is a linear congruential
generator. It is deterministic and completely predicatable from the
current state. No external events affect it.

(And if you don't know the current state, observing consecutive output
of the generator allows the state to be recovered. That's why such
generators are completely unsuitable for cryptographic work. They were
broken a very long time ago--I believe it is even mentioned in the first
edition of Knuth volume 3, to give an idea of how long ago they were
broken).

Linear contruential generators are OK where you care about are the
statistical properties of the output, and do not care about the
predictability of it.

Yes, well, now two people have corrected my statement here. What I was
driving for and missed was that even regular random() or Random should have
those statistical properties. Just returning "17" probably won't.

 

[Lew]

As Patricia Shanahan's post pointed out, there is some dependence on
something, in the choice of seed for the no-arg constructor. It's not the
same every time and one might not know the seed.

For the purposes of this thread, also as Patricia pointed out, the fact that
the seed is (likely) different each time obviates a compiler's ability to
predict it, or to turn it into a constant. It might be cryptographically
hackable, but not in service of a compiler optimization.

 

[Tim Smith]

The Math.random() documentation says "When this method is first called,
it creates a single new pseudorandom-number generator, exactly as if by
the expression

new java.util.Random

This new pseudorandom-number generator is used thereafter for all calls
to this method and is used nowhere else."

The java.util.Random documentation says that the parameterless
constructor "sets the seed of the random number generator to a value
very likely to be distinct from any other invocation of this
constructor." The algorithms for generating the streams of numbers from
the seed are fully documented.

I don't see how a compile-time selection could conform to that contract,
because it would act as though seed were the same for every invokation
of the java.util.Random constructor.

Is that talking about different invocations within a program, or across
all programs? I see they've changed the documentation since 1.4. In
1.4, it used the millisecond time as the seed, so two separate programs
starting at the same time could get the same seed. The later
documentation just says very likely to be distinct and doesn't give
details.

Given that it is a 48 bit seed, if they do it at random, then about
every 16 million times, there would be a duplicate seed (birthday
paradox argument on 2^48). If they initialize partially with random and
partly with something derived from time, collisions from programs
launched apart in time would be less likely, but among all being
launched near in time, they would be more likely.

Given a 48 bit seed, I'd be a bit surprised if they mean that it is is
very likely to be globally distinct. I'd expect the problem they were
trying to address with a new seeding procedure was the problem of
invocations from within the same program getting the same seed. Imagine
an adventure game, say, that wants to give each computer-controlled
character its own random generator (that makes debugging easier, as you
can reproduce the sequence) rather than have them all share one, and it
happens to initialize them all within the same millisecond. That could
be a problem, so I can see that they'd want to fix that.

Anyway, it's a fun problem to think about.

 

[Patricia Shanahan]

Is that talking about different invocations within a program, or across
all programs? I see they've changed the documentation since 1.4. In
1.4, it used the millisecond time as the seed, so two separate programs
starting at the same time could get the same seed. The later
documentation just says very likely to be distinct and doesn't give
details.

Given that it is a 48 bit seed, if they do it at random, then about
every 16 million times, there would be a duplicate seed (birthday
paradox argument on 2^48). If they initialize partially with random and
partly with something derived from time, collisions from programs
launched apart in time would be less likely, but among all being
launched near in time, they would be more likely.

The new initialization uses the sum of a long counter and
System.nanoTime(). I think it would be practically impossible to get
duplication within a single JVM.

I would accept something happening once in 2^48 times as "very
unlikely", but not something happening every time. Indeed, the use of
time seems pointless if the intent of the Random API is to allow it to
produce the same sequence for each run.

Patricia

 

[twerpinator]

Java has basically three ways to accomplish this: classloaders, reflection and
the debugger API.

And one method that is relatively "nice", using a fairly simple subset
of reflection, is serialization.

Say you have a plugin architecture with, say, pluggable codecs. You
employ the strategy pattern and create a Codec interface that has
encode() and decode() methods, among others, and supply some
implementations. But you also provide code that runs at startup or
when a user picks "Scan for plugins" from a menu that looks in a /
plugins directory someplace looking for ".codec" files, which are
actually serialized instances of Codec objects. It reads these one by
one with an ObjectInputStream and casts each to Codec; if a
ClassCastException is thrown, it's ignored and so is the object that
was loaded; same if any of the various serialization exceptions or
IOExceptions are thrown. NoClassDefFound? Discard.
ObjectStreamException? Discard. The surviving objects are added to the
collection of Codec objects the program maintains. Perhaps there's an
initialize() method on these, and the ones that are newly added (using
a Set allows detecting which are really new) get this run, adding
particular "Save As" options that go through their respective encode()
methods. Perhaps the program tries to decode files opened with "Open"
by invoking each one's "decode()" in turn until one of them returns
something other than null (or doesn't throw some exception); the new
ones now get a crack at decoding any opened file.

This requires, on the programmer's part, no nastier reflection code
than code to deserialize objects (and, in some SDK somewhere, to
serialize them so plugins can be made). A plugin's installation
requires only that some .class files (perhaps wrapped in a .jar) go
into the application's classpath and a .codec file go in the
application's plugins directory. Likely that plugins directory is on
the app's class path and contains the plugin classes as well.

A .codec missing a needed .class will result in some sort of
deserialization exception; that particular one should probably trigger
a warning to the user, since it likely resulted from a sloppy
installation. A user adding a plugin and getting a silent failure of
anything new to appear in the program's menus will be much less able
to diagnose and fix the problem than one told that they forgot to
install one of the plugin's files (or the plugin's installer did).

It shouldn't be hard to generalize the above far beyond codecs to all
sorts of other plugin architectures.

The dynamic polymorphism here is of course in any of the instance
method calls through the Codec interface, and here can call code added
while the program is already running.

 

[Owen Jacobson]

And one method that is relatively "nice", using a fairly simple subset
of reflection, is serialization.

Say you have a plugin architecture with, say, pluggable codecs. You
employ the strategy pattern and create a Codec interface that has
encode() and decode() methods, among others, and supply some
implementations. But you also provide code that runs at startup or
when a user picks "Scan for plugins" from a menu that looks in a /
plugins directory someplace looking for ".codec" files, which are
actually serialized instances of Codec objects. It reads these one by
one with an ObjectInputStream and casts each to Codec; if a
ClassCastException is thrown, it's ignored and so is the object that
was loaded; same if any of the various serialization exceptions or
IOExceptions are thrown. NoClassDefFound? Discard.
ObjectStreamException? Discard. The surviving objects are added to the
collection of Codec objects the program maintains. Perhaps there's an
initialize() method on these, and the ones that are newly added (using
a Set allows detecting which are really new) get this run, adding
particular "Save As" options that go through their respective encode()
methods. Perhaps the program tries to decode files opened with "Open"
by invoking each one's "decode()" in turn until one of them returns
something other than null (or doesn't throw some exception); the new
ones now get a crack at decoding any opened file.

This requires, on the programmer's part, no nastier reflection code
than code to deserialize objects (and, in some SDK somewhere, to
serialize them so plugins can be made). A plugin's installation
requires only that some .class files (perhaps wrapped in a .jar) go
into the application's classpath and a .codec file go in the
application's plugins directory. Likely that plugins directory is on
the app's class path and contains the plugin classes as well.

The Java Beans specification uses the extension ".ser" for this and
provides some hooks in the .jar format and java.beans API for finding
and loading serialized bean instances. See sections 10.3 and 11.8 of
the spec:
<http://java.sun.com/products/javabeans/docs/spec.html>

and the related API docs:
<http://java.sun.com/javase/6/docs/api/java/beans/
Beans.html#instantiate(java.lang.ClassLoader,%20java.lang.String)>

and the Java-Bean MANIFEST.MF entry described in:
<http://java.sun.com/javase/6/docs/technotes/guides/jar/jar.html>

-o

 

[nebulous99]

The Java Beans specification uses the extension ".ser" for this and
provides some hooks in the .jar format and java.beans API for finding
and loading serialized bean instances. See sections 10.3 and 11.8 of
the spec:
<http://java.sun.com/products/javabeans/docs/spec.html>

and the related API docs:
<http://java.sun.com/javase/6/docs/api/java/beans/
Beans.html#instantiate(java.lang.ClassLoader,%20java.lang.String)>

Haven't bothered with Beans much, but it sounds similar. Perhaps a bit
more complex to do/use but perhaps a bit more powerful in exchange; it
looks like you need to muck about explicitly with classloaders.