How would one go about testing an interpreter or a compiler?

Question

Hello all!

I've been experimenting with creating an interpreter for Brainfuck, and while quite simple to make and get up and running, part of me wants to be able to run tests against it. I can't seem to fathom how many tests one might have to write to test all the possible instruction combinations to ensure that the implementation is proper.

Obviously, with Brainfuck, the instruction set is small, but I can't help but think that as more instructions are added, your test code would grow exponentially. More so than your typical tests at any rate.

Now, I'm about as newbie as you can get in terms of writing compilers and interpreters, so my assumptions could very well be way off base.

Basically, where do you even begin with testing on something like this?

Answer 1

You can test with some already written apps.

Answer 2

I don't think there's anything 'special' about testing a compiler; in a sense it's almost easier than testing some programs, since a compiler has such a basic high-level summary - you hand in source, it gives you back (possibly) compiled code and (possibly) a set of diagnostic messages.

Like any complex software entity, there will be many code paths, but since it's all very data-oriented (text in, text and bytes out) it's straightforward to author tests.

Answer 3

In the case of brainfuck, I think testing it should be done with brainfuck scripts. I would test the following, though:

1: Are all the cells initialized to 0

2: What happens when you decrement the data pointer when it's currently pointing to the first cell? Does it wrap? Does it point to invalid memory?

3: What happens when you increment the data pointer when it's pointing at the last cell? Does it wrap? Does it point to invalid memory

4: Does output function correctly

5: Does input function correctly

6: Does the [ ] stuff work correctly

7: What happens when you increment a byte more than 255 times, does it wrap to 0 properly, or is it incorrectly treated as an integer or other value.

More tests are possible too, but this is probably where i'd start. I wrote a BF compiler a few years ago, and that had a few extra tests. Particularly I tested the [ ] stuff heavily, by having a lot of code inside the block, since an early version of my code generator had issues there (on x86 using a jxx I had issues when the block produced more than 128 bytes or so of code, resulting in invalid x86 asm).

Answer 4

Testing a compiler is a little different from testing some other kinds of apps, because it's OK for the compiler to produce different assembly-code versions of a program as long as they all do the right thing. However, if you're just testing an interpreter, it's pretty much the same as any other text-based application. Here is a Unix-centric view:

1. You will want to build up a regression test suite. Each test should have
   • Source code you will interpret, say test001.bf
   • Standard input to the program you will interpret, say test001.0
   • What you expect the interpreter to produce on standard output, say test001.1
   • What you expect the interpreter to produce on standard error, say test001.2 (you care about standard error because you want to test your interpreter's error messages)

2. You will need a "run test" script that does something like the following

   function fail {
     echo "Unexpected differences on $1:"
     diff $2 $3
     exit 1
   }
   
   
   for testname
   do
     tmp1=$(tempfile)
     tmp2=$(tempfile)
     brainfuck $testname.bf < $testname.0 > $tmp1 2> $tmp2
     [ cmp -s $testname.1 $tmp1 ] || fail "stdout" $testname.1 $tmp1
     [ cmp -s $testname.2 $tmp2 ] || fail "stderr" $testname.2 $tmp2
   done
   

3. You will find it helpful to have a "create test" script that does something like

   brainfuck $testname.bf < $testname.0 > $testname.1 2> $testname.2
   

   You run this only when you're totally confident that the interpreter works for that case.

4. You keep your test suite under source control.

5. It's convenient to embellish your test script so you can leave out files that are expected to be empty.

6. Any time anything changes, you re-run all the tests. You probably also re-run them all nightly via a cron job.

7. Finally, you want to add enough tests to get good test coverage of your compiler's source code. The quality of coverage tools varies widely, but GNU Gcov is an adequate coverage tool.

Good luck with your interpreter! If you want to see a lovingly crafted but not very well documented testing infrastructure, go look at the test2 directory for the Quick C-- compiler.

Answer 5

I’ve written an article on compiler testing, the original conclusion of which (slightly toned down for publication) was: It’s morally wrong to reinvent the wheel. Unless you already know all about the preexisting solutions and have a very good reason for ignoring them, you should start by looking at the tools that already exist. The easiest place to start is Gnu C Torture, but bear in mind that it’s based on Deja Gnu, which has, shall we say, issues. (It took me six attempts even to get the maintainer to allow a critical bug report about the Hello World example onto the mailing list.)

I’ll immodestly suggest that you look at the following as a starting place for tools to investigate:

1. Software: Practice and Experience April 2007. (Payware, not available to the general public---free preprint at http://pobox.com/~flash/Practical_Testing_of_C99.pdf.

2. http://en.wikipedia.org/wiki/Compiler_correctness#Testing (Largely written by me.)

3. Compiler testing bibliography (Please let me know of any updates I’ve missed.)

Answer 6

The secret is to:

• Separate the concerns
• Observe the law of Demeter
• Inject your dependencies

Well, software that is hard to test is a sign that the developer wrote it like it's 1985. Sorry to say that, but utilizing the three principles I presented here, even line numbered BASIC would be unit testable (it IS possible to inject dependencies into BASIC, because you can do "goto variable".