CSE 401, Winter 2014

Robert R. Henry

Assignment 2

Test Programs

Due via dropbox Friday January 17th 2014

Goals

In this assignment you will be writing a number of Mini Java programs designed to test your Mini Java compiler.  The goal is to have you think about what is in Mini Java, and become familiar with the Mini Java coding straight-jacket, and understand what each feature of the language does, and how it might be implemented.  You’ll also learn how to run the makefile and the ant build mechanisms.

When writing the Mini Java compiler, we’ll be adding many small things to the pre-existing “bones” of the compiler.  These bones are primarily the AST data structure, but include the lexer specification and the parser specification.

By writing test programs now, you are engaged in a slowed-down version of a process called “Test Driven Development” (aka TDD) http://en.wikipedia.org/wiki/Test_driven_development.  You write the tests now, and then write the code in the Mini Java compiler needed to make the tests work.  Eventually your tests will all work. You will have to rewrite or extend your tests as you go along, based on new information about the language, the compiler, or the way in which you are staging your extensions.  I fully expect that you will have to rewrite some or all of these tests in the course of the quarter.

Our compiler is simple enough that there’s very little interaction between most of the extensions, and there is no cleverness or trickiness.  Consequently, you can write a simple test for one extension more or less in isolation from tests for other extensions.  Simple is good! If it works in a simple way, then we’ve built the compiler and runtime so that concatenation of simple things yields overall correct results.  It may not be efficient, but that’s a non-goal. You can probably test many related things in the same test file, such as a single test file that tests all integer arithmetic operations.

Suggestions

Your tests should test things and output something that tells you what test was run, and whether or not the test passed or failed.  Since our Mini Java program can only print integers (and eventually doubles), you’ll have to encode the test results in some stream of integers or doubles.  Remember, since Mini Java is a subset of Java, you can rely on Java to give you the “known-good” expected answers.

Keep in mind some of the common coding errors you might make, or coding errors common when writing this kind of a compiler:

1. cut and paste errors (example: implement != just like ==)
2. reversal errors (example: caller transmits arguments, but callee reverses them)
3. interchange errors (example: doubles used instead of instead of integers)
4. nesting errors (example: right recursive division or nested function calls)
5. resource limitation errors (argument count, failure of new)

Pragmatics

Together with your project partner, write about 20 small test programs, where a “small” program is 50 lines or (much) less long. The value of “20” is somewhat arbitrary.

You will write two kinds of test programs: one kind should compile and execute without errors.  The second kind should contain compile-time or run-time error(s).

Most of these programs should compile and execute without errors.  Here’s some examples:

1. Your first test program should be really simple:  can I print an integer constant?
2. Your second test program can be more complex: can I do integer arithmetic operations on integer constants?
3. Your third test program should be even more complex: can I execute an if/then/else statement, which implies can I compare two integers together and branch?
4. Your fourth test program should be more complicated yet: can I execute a while statement?
5. ...etc…
6. Test objects and inheritance and function dispatch.
7. Your last few test program(s) should exercise doubles.

The remainder of the test programs should contain semantic errors that your compiler or runtime should catch.  (Lexical and syntactic errors are not that interesting for us.) Since your compiler and runtime will have neither error repair nor error recovery, only test one kind of thing in each of these “broken” programs. Some examples might be:

1. use of an undefined identifier;
2. mixing up operand types in expressions or arguments;
3. array indexing problems;
4. etc…

Write your test programs using the following file (and class) naming conventions:

• The root file name should start with your group name.
• An underscore
• The root file name should then have “correct” if the test should compile and run fully, or “ctfail” if the test should fail at compile time, or “rtfail” if the test should fail at runtime.
• An underscore
• The root file name should end with a 2 digit serial number, such as “00”, “01”, etc.

For example, I might have a file named “cs401admin_correct_24.java”.

With this naming scheme we can combine all test files into a single massive test repository without fear of file naming collision.

Effectiveness Guesstimate

Make an estimate (you will not be graded on you estimate!) now of what fraction of the lines of code in your compiler your test suite will execute.  We’ll hopefully show you later in the quarter how to get this information from the Java RunTime, or from the C-runtime (eg, the Mini Java Runtime).

Running the tests using make

There is a top level Makefile that has rules to compile and run a Mini Java program in one of two different ways.  Compiling with the regular Java system produces the “expect” output.  Compiling with your Mini Java compiler produces the “actual” output.  The goal is to have the “expect” output eventually match the “actual” output.

Suppose you put your tests into a subdirectory named “tests”.  Suppose you have a test program named “cs401admin_correct_00.java”.  The following invocation of “make” would run the Mini Java tool chain on this program:

 make SAMPLEDIR=tests tests/cs401admin_correct_00.actual

would produce interesting files:

1. tests/cs401admin_correct_00.s  (assembly code output from your mini java compiler
2. tests/cs401admin_correct_00.x  (executable file suitable for use with gdb)
3. tests/cs401admin_correct_00.actual (actual program output)

Alternatively, running:

  make SAMPLEDIR=tests tests/cs401admin_correct_00.expect

would produce these interesting files, plus others (take a look!):

1. tests/cs401admin_correct_00.expect (expected program output)

Running:

  make SAMPLEDIR=tests tests/cs401admin_correct_00.diff

would difference the expected and actual output.  Ultimately, there should be none.

Since you don’t yet have a Mini Java compiler that implements a true subset of Java, you’ll have to wait a bit before you can difference the output of the two compilers.

Other Test Cases

The Mini Java project code you start with already has a number of test cases already in the directory SamplePrograms/SampleMiniJavaPrograms. There are programs to do:

• some simple classical algorithms;
• one program that uses inheritance;
• several programs that use double precision numerics, including computation of asin.
• a truly wondrous piece of code that with hardly any effort at all churns out the first 1000 digits of Pi; see www.mathpropress.com/stan/bibliography/spigot.pdf‎

But all of these “real” programs require that many small things already work.