September Programmer's Challenge Addendums

ByteCode Interpreter

Mail solutions to: progchallenge@mactech.com

Due Date: 1 September 1996

(See original challenge)

>1. I have CW9 (no recent Symantec). I can compile java files and create
>class files, but is there a utility for creating dump files?

I haven't found one. Perhaps a reader from Metrowerks could answer.

With some trepidation, I'll make the following offer. If you send me your class files, I'll run them through the Symantec DumpClass utility and return the results to you. 12-hour turnaround except for 6am Thu - 11pm Fri, when I'll be UnPlugged.

>2. The 'swarm' example uses Math.Abs(), which is, of course, not in the
>swarm class. Should we gracefully handle this situation? Can you remove
>it?

Oops (again). I've corrected it in R2 of the sample code, available at: <ftp://ftp.mactech.com/mactech/CHALLENGE/12.09-Sep96/Testcode96.09R2.sit> and <ftp://ftp.ultranet.com/pub0/b/boonstra/Challenge/Testcode96.09R2.sit.hqx>

>3. There is no example of anewarray and multianewarray, and the latter's
>documentation is particularly vague. How about we just get rid of these
>two opcodes? If not, how will these objects be used? The doc hints at
>arrays of arrays, but what in order are the indices used?

I've added multianewarray and a few other opcodes to the MiscByteCodes example. I was unable to generate an anewarray opcode, so you can ignore that one.

>4. For the HelloWorld example, I'm not so sure that the result will be a
>pointer to a constants_pool entry. Doc says it is a reference to an
>object, which I interpret as an object in the heap, which would be in an
>implementation-defined format. In any case, it doesn't much matter since
>there's nothing our code can do with a string object. Anybody else read it
>this way?

Several people pointed out the fact that the format for an object reference is implementation defined. I've added the following comment to the test code.

// The Java VM specification states:
//    The specification does not require any particular internal structure for
//    objects.  In our implementation, an object reference is a handle,which is
//    a pair of pointers: one to a method table for the object, and the other
//    to the data allocated for the object.  Other implementations may use
//    inline caching, rather than method table dispatch ...
// Since the format of an object reference is implementation-defined, your
// solution should document the format that your miniVM uses for an object
// reference.
// The test code will use this information to access the data for that object
// and  compare it to the expected value.  Sample code to extract object data
// from  your implementation-defined object reference is welcome but not
// required.

<ftp://ftp.ultranet.com/~boonstra/Challenge/Testcode96.09R1.sit.hqx>

and

<ftp://ftp.mactech.com/mactech/CHALLENGE/12.09-Sep96/Testcode96.09R1.sit.hqx>

From the README:

- removed a call to a java/awt/Component method inadvertently left in the swarm example - corrected the Fib example so it does not require input parameters - added a few opcodes to the MiscByteCodes example (invokenonvirtual, tableswitch) - corrected the parsing logic for the constant pool so it correctly deals with 8 byte constants

NOTE: Your miniVM is expected to set up the execution frame for the class called by the test code. In a full VM implementation, this would involve allocating space for local variables and the operand stack, as well as running the default constructor for your class. In the Challenge, class variables will be initialized explicitly in code; you don't need to worry about a constructor. You _do_ need to create an object reference to your class before beginning execution. (See the first instruction, aload_0, in the swarm.myRun method.)

I also removed the spaces embedded in the file name to help those of you who had trouble downloading the original test code.

Test code for the ByteCode Interpreter Challenge is now available at: <ftp://ftp.ultranet.com/~boonstra/Challenge/Test%20code%2096.09.sit.hqx>

From the README:

Enclosed are 4 test cases for the September 1996 Programmer's Challenge

Three of the test cases are Applets created with Symantec Cafe. The fourth is an application created with Cafe.

The JavaMiniVM.µproject parses each of the class files, calls one of the methods, and compares the result to an expected value.

Each test case includes a .dmp file created by Symantec's DumpClass routine containing a disassembly of the class file.

Note that these are representative test cases only. The Challenge test code may stress your code in ways these cases do not. Feel free to write your own applets following these examples.

-- Programmer's Challenge        -- Bob Boonstra
   progchallenge@mactech.com        boonstra@ultranet.com
   <http://www.mactech.com/>        <http://www.ultranet.com/~boonstra>

Subject:     Sept Challenge Q&A; #1
Sent:        8/15/96 3:19 AM
Received:    8/15/96 10:39 AM
From:        Bob Boonstra, boonstra@ultranet.com
To:          challenge-a@listmail.xplain.com
 Q1 Eric Lengyel asks:
 >I would like to ask that we be allowed to use the MPW assembler for this
>challenge.  The reason being that Metrowerks does not let you subtract
>label addresses, making it impossible to build an entry point offset
>table.  (The Metrowerks assembler has several other deficiencies, but the
>above reason is the most significant.)
 A1: OK, I'll accept use of the MPW assembler.
 Q2 Peter Lewis asks:
 > Why not Pascal?
 A2: OK.  By way of explanation, when I originally put the Challenge
together, I was going to use the Symantec environment, which didn't support
Pascal.  MW CW9 came out with Java support in the interim, and I never
added Pascal back to the problem statement.
 Q: Andrew Robert Faulring asks:
 >And while I am at it I have one question about the challenge. Since our
>interpreter is only required to work with a single class, are we
>expected to support the creation of objects and the creation or
>manipulations of arrays. Specifically do we need to implement the
>following instructions:
>>    new, checkcast, instanceof, newarray, anewarray, multianewarray,
>arraylength, or any of the *aload or *astore (* = i, l, f, d, a, b, c,
>s),
 A3:  I want the interpreter to support all of the instructions that make
sense given the restriction to a single class file (with the exclusion
given in the problem statement: long, float, and double data types,
exceptions, breakpoints, monitored code regions, and the wide modifier for
load and store instructions).
 Given those constraints, I don't think new, checkcase, or instanceof make
sense.  At least, I haven't succeeded in generating them in an applet with
a single class file.
 It is possible to generate newarray, anewarray, multianewarray,
arraylength, and the *aload/*astore instructions, so you should support
those.
 Q4  Mark Day asks:
 >Can you document which opcodes your test classes actually use (so we know
>which ones we need to write additional tests for)?  There's a lot of
>opcodes to write and test (even without the long, float, double,
>exceptions, etc.)!
 A4: See A3.
 Q5  Mark Day asks:
 > [Quote from problem statement deleted]
 >From the above quote, I take it that returnStack is _only_ a pointer for
>the function result (i.e. we shouldn't treat it as a stack we can use),
>and that heapSpace is supplied for the runtime stack of the called
>routine.
 A5: Exactly.
 Q6  And one more from Mark:
 >From what I've been able to understand so far, some of the opcodes
>dynamically allocate structures that persist after the function exits
>(just like C++ "new" or malloc() or NewPtr()).  Do you intend for those
>objects to be allocated in memory outside the heapSpace area (such as via
>NewPtr or similar methods)?  If you intend for them to be allocated
>inside heapSpace, then I think we need to know how long that space is (so
>we can grow the stack from one end, and a heap from the other).
 A6: The intent was to use the heap space provided.  I'm not sure you need
to make assumptions about its size, but I'll guarantee at least a megabyte.
Please document any such assumption clearly and use a #define-like
construct so I can adjust it easily if necessary.
  -- Programmer's Challenge        -- Bob Boonstra
   progchallenge@mactech.com        boonstra@ultranet.com
   <http://www.mactech.com/>        <http://www.ultranet.com/~boonstra>   Subject:     Sept Challenge Q&A; #2
Sent:        8/15/96 12:05 PM
Received:    8/15/96 1:17 PM
From:        Bob Boonstra, boonstra@ultranet.com
To:          challenge-a@listmail.xplain.com
CC:          emunter@ibm.net
 Ernst Munter asks the following excellent questions:
 >Q1:
>The VM spec is fairly clear on simple op-codes, but less so on some
>others.  In
>particular, section 3.15 Method Invocation still leaves me scratching my head.
>It seems, the description is partly VM spec, partly a description of SUN's
>implementation which is based on an "object reference" being a handle to a
>2-pointer record to method tables and allocated data fields of a class
>instance.
>Which of these invokations (virtual, nonvirtual, static, interface) do I
>need to worry
>about? and is there a better description available than page 68/69 of SUNs
>spec?
 A1: The test code uses invokevirtual and invokestatic.  I think
invokeinterface is impossible given the single class file restriction.  I'm
not certain yet about invokenonvirtual - assume it will _not_ be included
unless I discover otherwise in the next few days.
 I don't have any better description of the VM than the documentation at the
java.sun.com web site.  Sorry.
 >Q2:
>In section 3.13 (Table Jumping) we are treated to a variable "byte pad"
>after the
>op-code.  Since everything else is byte oriented, where is the 32-byte base
>which allows me to determine how many pad bytes there are?
>(page 65)
 A2: The base is the start of the code array in the code attribute for the
given method.  That's what my experiments indicate anyway.
 >Q3:
>A "null" object reference is presumably a 32-bit 0.  If so, is there a
>difference
>between "aconst_null" and "iconst_0" ?, and why would I ever want to push
>a null object on the stack anyway?
>(page 29)
 A3: Afraid I don't know.  Maybe someone else on the list does.
 >Q4:
>In the challenge, everything will be in a single class file, i.e. 1 class.
>Does this mean, no need to find inherited fields or methods of the super
>class,
>no need to load additional files, etc?
 A4: Correct.
 >Q5:
>Will the call to the initial method have any parameters, and if so, how are
>these
>passed from the C-environment to the Java bytecode interpreter?
 A5: No parameters.
 >Q6:
>I have studied some of the example classes that came with the CW-9
>codewarrior.
>Since I have been unable to get "javap" to work (it cannot find the file, or
>claims the
>class is illegal), I wrote a disassembler to study the classes.  I can see
>how
>invocation via the constant pool might work, albeit slowly.  Hence, presumably
>the idea of "quick" variants for some opcodes (page 73 ff).
>Substituting "quick" variants for some codes amounts to modifying the class
>file in memory.  Is this allowed in the challenge?  Will it be of benefit,
>considering
>the number of times the same code will be executed in the test?
 A6: It is legal, but I cannot tell you whether it will be of benefit.  You
can assume I will create test cases that will run for statistically
significant amounts of time (seconds to minutes) but not unreasonably long
times (tens of minutes).
 >Q7:
>You say, no longs or doubles, but be aware of them.  What about this bizarre
>rule of longs and doubles taking up 2 spots in the constant_pool "array"
>(page 17),
>when every other item takes up 1 spot, regardless of length (nothing will be
>32-bit aligned anyway).  Do we have to worry about that also?
 A7: I'd like your code to be robust enough that I don't have to worry if
the applet puts a long or a double in the constant_pool, but I won't put
one there deliberately.
 RE bizarre: Interestingly enough, a chapter (chaper 4, The class File
Format) in an upcoming Addison-Wesly book, available at the java.sun.com
web site, has the following quote:
"In retrospect, making eight-byte constants take two constant pool entries
was a poor choice."  No kidding.
 >Q8:
>The way I see it, the only way to find the entry of an invoked method is
>to have
>parsed the complete constant_pool.  Presumably, there is enough memory
>available
>in "void *heapSpace" to make pointers or other structures to avoid having to
>re-parse half the file for every method or field reference?
 A8: You do need to parse the class file, including the constant_pool.  I've
previously guaranteed that heapSpace will be at least 1MB.  I'll now make
it at least 10MB to remove any doubt that it is large enough.
 >Q9:
>All examples I could find are extensions of library classes.  The challenge
>classes
>will be self-contained on the other hand.  Do you have some examples you could
>send me (.java source and .class)?  (binhex works fine with my e-mail setup)
 A9: The restriction to a single class does complicate creation of test
code.  Since you wrote, I've put some code at:
<ftp://ftp.ultranet.com/pub0/b/boonstra/Challenge/Test%20code%2096.09.sit.hqx> I also put it in the Challenge area at the MacTech ftp site.
 -- Programmer's Challenge        -- Bob Boonstra
   progchallenge@mactech.com        boonstra@ultranet.com
   <http://www.mactech.com/>        <http://www.ultranet.com/~boonstra>