There are only a few core instructions that would be neccessary to
build others :

- constantly : pop a value, push an instruction on the stack that
returns that value
- compose : pop two instructions, push a new instruction that
evaluates the first function, then the second.
- eval : pop an instruction and evaluate

This functionality would make it easier for me to compile functional
languages to the CIL, and make them much more efficient.

We have been discussing the topic on Lambda-the-Ultimate (
http://lambda-the-ultimate.org/node/2177 ). The first response from
many people is that they believe that this functionality has a huge
performance hit, and loses the effect of statically verifiable type
safety. This is untrue.

I've developed a type-system for stack-based languages with higher-
order functions and written a paper about it at : http://www.cat-language.com/paper.html.
I believe the work to be novel, and I would be interested in
discussing it further.

I'm rather sceptical about the approach -- at least, if taken as a candidate
for extending the expressiveness of the JVM.  (It does look interesting in and
of itself.)

The problems I see are "political" and practical, I'm willing to believe your
claim that there are no real killer problem in theory.

(Although I think you have a fair bit more work to do to support that claim.
Just for one example: how do you ensure that a constant-pool index pushed onto
the stack to form part of a generated invokevirtual instruction call sequence
is in range, let alone correctly "typed" ?).

The "political" problems (not really a very good term, but I can't think of a
better one off-hand) are boring and obvious.  The JVM is a standard (in the
sense of having a public specification independent of any one implementation),
and non-standard extensions are doomed to die in obscurity.  No one will use a
program which requires a non-standard JVM as an execution platform, and so any
JVM language will surely remain (to say the best of it) very much a niche
language unless it targets the /real/ JVM.  But if only very unimportant (in
numerical terms) languages require the non-standard extensions then there's not
a lot of chance of them making it into the standard.

The practical problems are more interesting ;-)

The best way I can put it is that the idea seem to assume, or require, an
approach to JVM implementation which is not used in practise.  If the JVM were
typically implemented as an interpreter with a classic "big-switch" on the
opcode, then the adding this feature would obviously be trivial.  If the
implementation approach were to translate bytecode into native code by doing a
table lookup to translate each opcode into a (stereotyped) native instruction
sequence, concatenating the results, then shoving everything through a peephole
optimiser, then adding this kind of feature would also be pretty trivial.  But
neither of those approaches are relevant (as far as I know no production JVM
for desktop class machines uses either of them, or has done since about JDK
1.0.2).

In fact the stack-based nature of the JVM bytecode language is a bit of a red
herring.  For one thing JVM bytecode isn't really that much of a stack-based
language[*].  More importantly the stack is only an incidental feature of the
intermediate language used to compress source code into a portable delivery
format.  It isn't necessarily a particularly well chosen format (though it is
reasonably compact, and does keep javac simple), since the JVM has to translate
code back from the stack-based expression into something suitable for input to
its optimising compiler (SSA or whatever).  I don't know the details of how the
current crop of JVMs generate native code, but it is at least a plausible
approach that the JITer never sees bytecode at all, nor ever thinks in terms of
a stack (except the stack of activation records, of course).

It may well be that there are ways of extending the analysis the JVM must do to
allow higher-order bytecodes in the context of a state of the art JITer, but I
don't see any reason to expect that to be simple at all -- nor any reason to
expect it even to fit into the current framework at all (it would be like
adding eval(char *) to an optimising C compiler -- how can the compiler
optimise code that is unknown until runtime ?)

But then, perhaps the overtly stack-based nature of your idea is itself a
red-herring.  It doesn't seem to me that much would change if you wanted to be
able to assemble sequences of executable bytecode in byte[] arrays, instead of
on the stack (the latter might significantly simplify the implementation of
languages like Cat, but it doesn't seem to me that it's similarly important for
languages outside that niche-within-niche).  But the techniques for doing that
are already well-understood, rather widely used, and do not require changes to
the semantics or implementation of the JVM.  So I suspect there's more mileage
to be gained in looking for ways to optimise that process (e.g. creating
lighter-weight classes) than in a wholesale reorganisation of the JVM
semantics.

    -- chris

[*] It is true that there is an explicit stack, with operations to manipulate
it, but that is only the expression stack and it isn't used in anything like
the way "the" stack is used in Forth or PostScript -- the character of the JVM
bytecode language would be essentially unchanged if it used, say, the
unbounded-number-of-named-registers-per-activation approach -- which it does,
anyway, for everything except expression evaluation.

Following the terms of my analogy, consider the following code:

    sum = 0;
    for (int i = 0; i < array.length; i++)
    {
        for (int j = i; j < array.length; j++)
        {
            eval("sum += array[i] * array[j]");
        }
    }
    return sum;

the problem is not that the input to eval() might specify unsafe operations, or
operations which wouldn't make sense, but that the compiler has no idea which,
if any, of the variables are used in the loop; what kinds of
loop-transformation operations are valid; or even whether there are any loops
at all there.  It can't compile code it hasn't seen.

     sum = 0;
     for (int i = 0; i < array.length; i++)
     {
         for (int j = i; j < array.length; j++)
         {
             eval(closure{sum += array[i] * array[j]});
         }
     }
     return sum;

There are plenty of well-known optimizations that can be done to the
above code using functional optimization techniques, including pre-
evaluation.

The next logical step after introducing higher order opcodes is the
introduction of array/list processing primitives based. Iterating over
an array for an example could also be done using higher order
functions like "map" or "fold", which can be easily parallelized by a
compiler.