What if? What not? Testing … testing … testing

We continue our occasional series of posts on the Sun/FSF alliance and the release of Java as open-source by looking at the process of language definition and standardization, and the role of testing in enforcing conformance to a language specification.

Open-source is closely associated with open standards. For example, Linux implements the POSIX standards that were created around Unix, and the Apache HTTPD server implements the key standards associated with HTML.

Usually the implementor has some freedom of action, and one of the great appeals of open-source is the opportunity to affords to use that freedom to innovate on top of open-standards. For example, I use the Amarok program to play my digitally-encoded music on my SuSE box. There are many such players but I’ve found Amarok works the best for me. Amarok relies on code from others to play mp3 files as well asflac files . I prefer flac since it is based on an open-standard, while mp3 is encumbered by patents.

However, Java is much more precisely defined, in the form of the Java Language Specification (JLS) and the Java Virtual Machine Specificatinon (JMS). These are precisely written and are also available under a license that lets you implment the specifications.

This of course made the job of writing a Java compiler a well-defined task. Our compiler, Jikes, takes as input source programs written in Java and produces as output files in a precisely-defined format called “class files” that serves as the input to the Java virtual machine.

Philippe Charles and I were very careful from the start of our project to never exposed ourself to any of the source-code from Sun or to any of the tests that we new Sun had produced, and which were available to IBM under its license from Sun. Accordinly, we relied on such tests as we could put together, and were also one of the first users of the “Modena” test suite.

However, once word got out that we would be releasing Jikes in binary form at IBM’ alphaWorks site, we were instructed that IBM did not want to release any Java-based technology that did not conform to the applicable standards, and we were thus told we had to pass Sun’s tests before we could release the code, and were granted access to the test suite. In those days it was called the JCK (Java Compatability Kit).

We weren’t concerned with the virtual machine tests, only with the compiler tests. There were two key parts. The “b” tests tested for diagnosing errors; that is, each test had one or more errors and to pass the test was to recognize these errors. By the way, though Jikes is perhaps best known for its speed, I think its greatest strength is in the quality of the error messages. Philippe’s Ph.D. these was in the area of parsing, and his two major advances were (1) to advance the state of the art in compressing the tables that drove the parse, and (2) to provide code that, given the grammar as input, would automatically generated code that would detect and repair errors.

We used Philippe’s parser-generator as part of the Jikes work. It was released as part of the Jikes work, under the name JikesPG. It is also the parser-generator used by Eclipse’s Java parser. One indication of its quality is that JikesPG was able to accept the Java grammar exactly as it was written in the JLS. We noticed in a later release of the JLS that the grammar had been changed. The new grammar accepted the same language; the changes were made so Sun’s own parser-generator could process the grammar.

The “c” tests tests consists of correct programs and to pass the test was to compile the source, execute the resulting program, and produce the same results.

It took us a few weeks to pass the “c” tests. As I recall the tests uncovered about as many errors in Jikes as Jikes uncovered in the tests.

We also uncovered an error in one the vendor run-times, I think it was in Microsoft’s C++ compiler. To compile Java you need to able to evaluate expressions involving constants at compile-time, and the language is so precisely defined that every bit in the result is known. As a result we had to include our own code (or it might have been code written by someone else at IBM) to do 64-bit arithmetic. (The only other code in Jikes that we didn’t write ourselves was some of the info-zip code we used to unpack Java “jar” files. (By the way, this is one of the reasons Jikes makes such a good example for a compiler course — it was written from the ground up, bit-by-bit, byte-by-byte.)

I did all the testing thereafter , and I spent thousands of hours from early 1997 to the end of 1999 running the “c” tests. It was fortunate that Jikes was so fast, as it routinely compiled the tests about 10 times faster than Sun’s own compiler, javac. Indeed, the standard demo I spent when showing Jikes at conferences during 1999 was to have two windows open, one compiling the tests using Jikes, the other using Javac, as the difference in speed was easy to see.

That test suites tend to mimic the behavior of what is being tested is a well-known phenomenon in the world of testing. For example, perhaps the best book ever written about the C programming language is the classic C: A Reference Manual by Samuel Harbison and Guy Steele (the same Steele who is also one of the authors of the JLS). It reflects the work they back in the 1980’s while at Tartan Labs. I recall an anecdote about their experience; perhaps it can be found in the book or perhaps I heard it elsewhere. Their first version attempted to reflect the language spec as precisely as possible. However, they started getting complaints from users who were getting different results using the standard Unix C compiler. They tracked the problems down, and realized the differences were due to a number of bugs in the Unix compiler, so they then modified their compiler to have precisely the same bugs so compiler programs would exhibit the same behavior.

We had similar experiences in the early days of Jikes. Here’s an excerpt from the Jikese FAQ:


Why does Jikes reject a program that another compiler accepts, or accept one that it rejects?

You may find that Jikes accepts a program that another compiler rejects (or can’t compile), or rejects programs that another compiler accepts.

Each version of Jikes represents our best effort at the proper interpretation of the language specification. Although Jikes is designed to work with all but the earliest versions of the JDK, we make no claim that any particular version supports precisely the same language as any particular version of the JDK. Since some products are designed to work with specific versions of the JDK, the compilers associated with them may not always recognize the same programs as Jikes.

This section contains some examples of issues related to interpreting the specification.

Extraneous Semicolons

Your program may contain extraneous semicolons that are silently ignored by many compilers. For example, given

public class Test {
   void f() {};          // first extra semicolon
};                       // second extra semicolon

Jikes accepts the program but issues:

     2.       void f() {};       // first extra semicolon
*** Warning: An EmptyDeclaration is a deprecated feature that 
             should not be used - ";" ignored

     3.    };                   // second extra semicolon
            ^
*** Warning: An EmptyDeclaration is a deprecated feature that
             should not be used - ";" ignored

The first extra semicolon is erroneous, the second is allowed by section 7.6. Jikes treats each as cause to issue a warning. You can use the -nowarn option to suppress this (and other) warnings, or, even better, you can use your editor to delete those extra semicolons.
Unreachable Statements

It is a compile-time error if a statement cannot be executed because it is unreachable (section 14.19). When Jikes first appeared, some other compilers didn’t properly detect unreachable statements, and accepted programs such as the following:

class Test {
   void method(boolean b) {
      if (b) return;
      else return;
      b = !b;
   }
}

Jikes rejected this program:

        b = !b;

*** Semantic Error: This statement is unreachable

(This is the example referrred to in PC Week (April 14, 1997): IBM, Netscape Up Web Ante.)

Another example, and one that confused many users, is shown by the following program:

class Test {
   public static void main(String[] args) {
      try {
      }
      catch (Exception e) {
         System.out.println("caught"); 
      }
   }
}

Jikes accepts this program but issues the warning:

        catch (Exception e) {
               
*** Caution: This catch block is unreachable: there is no
             exception whose type is assignable to
             "java/lang/Exception" that can be thrown during
             execution of the body of the try block

This was the most frequently reported problem when Jikes first appeared. It took several months to confirm that Jikes was right all along. See Query #2 to Sun for the full story.


By the way, “Query to Sun” refers to a series of posts we made to Sun about the language spec. These and many other documents were once available on the web, but are no longer so. However, the Notes database containing them is still around and I will endeavor to have the documents made web-accessible.

The best example I have ever seen in the design and implementation of a programming language is Ada. The effort began in the mid 1970’s when the U.S. Department of Defense (DOD)realized that their vendors were using scores of different programming languages, and, thanks mainly to some visionary leadership, DOD undertake an effort to create a new programming language that would meet their needs.

First, they enlisted experts to draft a series of requirement documents, known as “Strawman,” “Ironman,” and I think the last one was “Steelman.” Then they funded two teams and charged them with the task of designing a language that met the requirements. The winner was the “Green Team,” led by Jean Ichbiah of Alsys. (This is why so many Ada books have green covers.)

DOD then funded two efforts, one at NYU to produce an executable form of the specification, another at Softech to create a set of tests to test conformance to the specification. I was part of the NYU team (as was Philippe); the tests were written by Softech, under the leadership of John Goodenough (a ferociously skilled test-writer.)

Ada was unveiled to the public in 1982 in the form of a joint announcement that the compiler was available, as were the tests, and the compiler had passed all the tests.

DOD then set up a group to supervise the language standard going forward. I believe it was called the ARB (Ada Review Board). It was the final arbiter on language specification as well as any proposed language changes.

My last job at NYU was to translate the original Ada compiler from SETL, a programming language developed at NYU, into C, with the goal — that was met — of being able to compile and pass the tests on an IBM PC/AT. [1]

The key people from the NYU team went on to found a company called ACT (Advanced Compiler Technologies). They translated the compiler into Ada and it has become the industry standard. It is licensed under the GPL.

But is one until now untold story from the Jikes day that really brought home to me the importance of testing in maintaining an implementation’s conformance to a specification.

Sometime well after Jikes had been released in open-source form I was approached by a group at IBM. They had been approached by a vendor. The vendor said they were acting on behalf of a client, and that the client wanted a commercial license to the Jikes source code, as it stood just before the release as open-source.

I pointed out this didn’t make much sense, since the code was freely available, but the vendor persisted, as they wanted to be able to build a commercial offering on top of the Jikes code. I then pointed out that even if they did get code in its state when it was released then they would be unable to make use any of the bug fixes that had been received from our contributors, since those fixes came to us via the open-source process.

They persisted, and there were a few more calls. Finally, the senior IBMer involved said they were welcome to the code, so long as they agreed to make no changes that would cause their product to fail any of the compatability tests.

We never heard from them again — that was the last call.

Now I am well aware of the Sun/FSF alliance and the recent announcements of Java as open-source –though I think they prefer to call it “free software.” But I don’t know all the details. I think some code has been released, some more has been promised.

However, here is my own view, based on my experience designing and implementing programing languages:

Any release by Sun of all or part of the Java source-code is of value if and only if Sun also releases ANY and ALL of the associated tests they have developed to test that code.,

For example, supposed you get the code and compile it on Linux. How will you know you got it right without testing? Perhaps you have some secret sauce, but the only way I know to find out is to run tests.

I’m hoping in my ignorance that Sun has already vowed to release all these tests. If so, I congratulate them.

If not, we shall see if Sun is up to the test.

Advertisements

3 Comments

  1. Posted November 29, 2006 at 19:44 | Permalink | Reply

    Jikes has great error messages, I wish more projects did that. And I wish the test suites were free as well. It’s not decided yet, though, afaik.

    Meanwhile, I’d like to push the more important practical test projects, like Apache Gump.

  2. Posted November 30, 2006 at 01:40 | Permalink | Reply

    I love jikes, but as far as I know it’s practically been abandoned. It hasn’t been touched in over two years and doesn’t handle JDK5 language features yet. Maybe I just haven’t been paying attention?

  3. Posted November 30, 2006 at 09:08 | Permalink | Reply

    Jikes is in a dormant state. I’m the project owner once again, but no longer have the skills, time or interest to keep Jikes up to date.

    Jikes still averages over 100 downloads/day.

    If you need a fast Java compiler, use the one in Eclipse. I understand it’s quite good. And if you don’t want the overhead of using an IDE then I understand Eclipse can run in what is called “headless” mode, though I don’t know the details.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

  • Pages

  • November 2006
    M T W T F S S
    « Oct   Dec »
     12345
    6789101112
    13141516171819
    20212223242526
    27282930  
  • RSS The Wayward Word Press

  • Recent Comments

    mrrdev on On being the maintainer, sole…
    daveshields on On being the maintainer, sole…
    James Murray on On being the maintainer, sole…
    russurquhart1 on SPITBOL for OSX is now av…
    dave porter on On being the maintainer, sole…
  • Archives

  • Blog Stats

  • Top Posts

  • Top Rated

  • Recent Posts

  • Archives

  • Top Rated

  • %d bloggers like this: