[Haskell-cafe] Compiler's bane

[Andrew Coppin]

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?