Brandon S. Allbery KF8NH wrote:
You can define a set of valid transformations, have the interpreter log each transformation, and verify that all are correct (that is, that both the transformation and the logged result are correct.
This assumes the interpreter can be resolved down to a sufficiently simple set of transformations; if not, you're right back at having the tester being the interpreter itself. Note that you don't check if the transformation plan for the program matches a specified list, just that all transformations are correct. (Just remember that "logic is an organized way of going wrong with confidence.")
The amusing (?) part is that the interpretter itself is essentially quite simple. I've implemented it several times before now. But what I'm trying to do it make it print out elaborately formatted execution traces so that a human user can observe how execution proceeds. This transforms an essentially simple algorithm into something quite nausiatingly complex, with many subtle bugs and issues. Still, I guess it's not news to anybody that proof-of-concept programs are much easier that real-world implementations. One thing I could do is have QuickCheck build arbitrary expressions, run those through the pretty printer, and then run the result back through the parser and check that I get the same expression. Can anybody tell me how to get QuickCheck to build arbitrary expressions though? Let's say I had data Expression = Var String | Apply Expression Expression | Lambda String Expression How would you go about building random expression trees?