US Patent 6,915,508

I continue my diatribe against Java patents with this...



US Patent 6,915,508 refers to a "Method and apparatus for eliminating C recursion from a Java™ bytecode."

First, some background:  Java is a programming language that was designed around a "bytecode" system.  This means that when you write a Java program the Java compiler does not generate native machine instructions but instead emits a series of generalized pseudo "bytecodes" which are like machine instructions but instead processed by a program.  The program, the Java interpreter, reads the bytecodes and processes them instead of the actual computer doing it.
For example, Java is a stack machine so you might have a series of bytecodes like this:

  PUSH 123 
  PUSH 1
  ADD

Where "PUSH" places 123 on the stack, the second "PUSH" places 1 on the stack and "ADD" adds the top to stack elements, removes them from the stack, and pushes the result 124.

PUSH may be implemented as a "byte" in memory, save with value 56.  ADD as a "byte" with the value 45.  So the series of bytecodes in memory would look like:

   56, 123, 56, 1, 45

Because Java is using a program to process the "instructions" like PUSH its possible for the Java interpreter to have a significant amount of control over what's going on - it can check for errors, like having too many things on the stack, and so on.  These things are more difficult to implement when hardware is directly executing instructions.  Java was designed to run in a number of different environments so this also eliminates the need to have a special hardware implementation of the Java interpreter.

Now let's suppose we want our bytecodes to call a method in a class called fred - say something like "fred.add(1, 2)".

In this case the Java interpreter has to do a lot of work - something like:

  PUSH 1
  PUSH 2
  LOAD "fred"
  INVOKE "add"

Here the "LOAD" operation has to go and find the class "fred" - this can involve it either already being in memory (which makes accessing it easy) or it can involve loading "fred" form outside the Java interpreter, e.g., a file, initializing the class (and any super class), and so on.  Finally "add" is called.

This patent addresses the issue where the bytecode interpreter is recursively invoked, for example as in the case where "fred" is loaded, where the interpreter would be reinvoked in the context of the class "fred" to initialize it. 

The "problem" is that the bytecode (Java) interpreter can run out of resources if there is too much "recursion" - for example running off the top of the stack in the interpreter.  Since this is hard to detect Sun is attempting to address this issue with this "solution".

The "solution" Sun patents involves replacing a recursive call to the bytecode (Java) interpreter with the invocation of some "replacement Java bytecodes" - basically converting the operations that the interpreter would have done into Java bytecode and thereby avoiding a recursive call to the interpreter.

However, in my view, this is simply a scheme to "flatten bytecode", for example as described in 1992 here (in this case the language is LISP, but the principles are the same) and to replace tail-recursive calls with continuations in the interpreter at an existing level albeit by generating additional bytecodes for the interpreter.

The real question for this patent is just how "unique" and "novel" are the concept espoused.

The LISP paper talks about replacing bytecodes to "flatten" execution - now in my view "flattening" is independent of whether an interpreter (as in the case of Java) is involved or whether raw machine instructions are involved.  Similarly "flattening" by using what amounts to effectively restarting the interpreter at the same level rather than a recursive call is the same as implementing a "tail recursion" optimization (something I used in Portable Standard Lisp in the 1980's).

Are we really talking about something novel and new here or is this a simple rehash of older ideas hidden by the words "Java" and "C"?

Certainly C is a programming language with roots in the 1970's.  From the perspective of a patent it predates this particular patent by decades.  Why use it?  Certainly a Java interpreter could be written without using C - the fact that its used in the patent title is deceiving I think.

Java is also not the first interpretive "bytecode" language - TinyBasic the first microprocessor Basic - used it in the 1970's (see this).  A lot of commercial work was done with Basic at that time as was a lot of research into optimization and performance.

This all boils down to this: Does this patent really talk about anything new and novel or is it just disguising a rehash of older work under the cloak of Java and C? 

Because computers have all processed instructions in roughly the same way for sixty or more years is it really new to put a different 'wrapper' around something old and claim it as new?

In this case I see a novel approach to two very old principles - "flattening" and replacing "tail recursion" with a "jump".  Again - like putting a new paint job on an old car and claiming that the old car is now in some way "unique".

Had this patent invented tail recursion elimination and flattening that would be one thing. 

But it doesn't.

It mere I think disguises them with new, and unnecessary, labels like "Java" and "C".