How to test nanopass-based compilers?

[Amirouche Boubekki]

I am cycling back to my Scheme->JavaScript compiler and figured that there is a problem about my testing method.

At the time of writing, what I do is compose all the pass starting from parse-and-rename Lsrc language, until somekind of Ltarget language, at which point a procedure takes the control and prints JavaScript code.

To test the whole thing, I created small snippets of scheme code, compile, execute it with nodejs redirect output to a file, at which point I verify the output of the file and commit that file as expected result.

That is to say, I test the output of the whole compiler based on controlled input.  This is usually what I do when testing other projects, that is, I only test the public interface (and in rare cases difficult implementation details).

The thing, even if my compiler is simple so far, sometime I struggle to find the source of bugs because they are in the middle of the nanopass pipeline. I think I hit the "difficult implementation detail that requires testing".

That is why, I was thinking about something like the following:

(define minipass0 (make-minipass parser0 pass0 unparse0 eval0 write0))

(define pipeline (minipass-compose minipass0 minipass1 ....))

Mind `eval0` should be a meta-evaluator, in the ideal case it should be plain eval.

Imagine there is several minipass.

Then the tests will be specified as a file system tree as follow:

./tests/entry-pass/output-pass/program.scm

./tests/entry-pass/output-pass/expected.txt

where entry-pass and output-pass are minipassn. And expected.txt contains the verified result.

Does it makes sense?

I guess what I want to ask is how do you test your compiler?

[Jens Axel Søgaard]

Den søn. 3. maj 2020 kl. 10.29 skrev Amirouche Boubekki <amirouche...@gmail.com>:

I am cycling back to my Scheme->JavaScript compiler and figured that there is a problem about my testing method.

At the time of writing, what I do is compose all the pass starting from parse-and-rename Lsrc language, 

until somekind of Ltarget language, at which point a procedure takes the control and prints JavaScript code.

To test the whole thing, I created small snippets of scheme code, compile, execute it with nodejs redirect 

output to a file, at which point I verify the output of the file and commit that file as expected result.

That is to say, I test the output of the whole compiler based on controlled input.  This is usually what I do 

when testing other projects, that is, I only test the public interface (and in rare cases difficult implementation details).

The thing, even if my compiler is simple so far, sometime I struggle to find the source of bugs 

because they are in the middle of the nanopass pipeline. I think I hit the "difficult implementation detail that requires testing".

... 

I guess what I want to ask is how do you test your compiler?

The approach I use is basically the same as yours.
Compile and run expressions and comparing the results with the expected values.
If the error is in the middle of a pipeline, I first try to find a minimal example.
Then I look at the programs generated by the various phases and try to see where
the error is introduced.

Your idea to write an evaluator for each intermediary language - or at least some of them - 
would make it is easier to find where an error is introduced. I believe it is for the same reason
that some compilers attempt to stick with Scheme forms as longs as possible before
introducing lower level operations.

Some details of how I tried to make testing reasonably convenient in Urlang.

I have a form `urlang` that always

   1) compiles a "module" to JavaScript, 

and optionally (controlled by a parameter) 

   2) executes it using nodejs,
   3) returns the output of the program as a string

The form is convenient to use both for testing and in the repl.

A parameter `current-urlang-console.log-module-level-expr?` controls
whether the results of module level expressions are printed. For tests this is set to true.

This makes it possible to write tests using `rackunit`:

/Jens Axel

Racket Stories
https://racket-stories.com

[Matt Jadud]

To add to Jens's note... or, repeat/expand on some bits... when we used this framework in the compilers class at IU (before the papers were even written... mercy)... the following framework had been developed:

At each language transformation (e.g. going from L0 -> L1, and L1->L2), there would be a pass called "verify-lang0" or similar. This pass would make sure that anything removed/added from/to L0 was no longer present in L1, and that L1 conformed to the new grammar. The nanopass framework has tooling, I think, baked in at this point to do this kind of boilerplate work. (If it doesn't, my brain's memory cells think it does. We had to write those passes by hand at the time.) This just made sure you were fully in the grammar of the language, though, and wasn't "testing" per se.

To test interim passes, you essentially need an interpreter, or a macro system, or some kind of language interface that lets you execute a test suite every step of the way. That is, if you want to test code in L1, you need code in L1 that can execute. It might be easiest to keep everything Rackety until the every last pass. I recall that there were test suites sprinkled throughout the compiler we were developing, and they would allow you to test at each major language transformation point. (I wonder if this is true... it was a long time ago. I remember it, though, and therefore perhaps remembering something makes it true.) The result was that you could test in a subset of Scheme as you progressed, all the way down to the assembly level... because, at that point, the Scheme-y bits had become simple operations on a memory vector. (I may be conflating the IU compiler with another language project I worked on, where I did exactly that... the assembly-pass was able to be tested in a "VM" of sorts, before generating the actual assembly and having to execute on bare metal. The debugging was easier in the VM. I'm thinking this particular part of the story was a project of my own, but still... same difference.)

It may be that you don't test every step of the way, but only in language levels that you know significant/complex transforms are taking place. Testing early in the pipeline might be easier because the language is still similar to the host language... testing later in the pipeline probably requires more work to "lift" the partially-compiled language back up into the host language for testing. But, either way, those are the strategies we used (and I've used since in language transformation projects).

Cheers,

Matt

--
You received this message because you are subscribed to the Google Groups "nanopass-framework" group.
To unsubscribe from this group and stop receiving emails from it, send an email to nanopass-framew...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/nanopass-framework/CABefVgyhxB8EPqrZZpT%2BtW539CBtXZsCmRetZVbpz3P0VGi3AA%40mail.gmail.com.