quickcheck for compiler testing

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

quickcheck for compiler testing

Maurizio Vitale
I'm starting to work on my first real haskell program (I've only RWH exercises under my belt) and wondering whether people use quickcheck at all for compiler testing.

I've seen uses of quickcheck for testing parsers, but I'm interested in generating well-formed programs (e.g. random programs with all declarations in reasonable random places). This could be used to test passes other than parsing (or even parsing, for languages that needs to distinguish identifiers, like the 'typedef' problem in C/C++).

The only thing I can think of, is to use quickcheck for randomly generating statements, go over them and figure out free variables (incl. functions) and generate declarations in random places for them. But I'm not sure how this would play with test size reduction and doesn't look like a nice solution anyhow.

Any idea or pointers to examples? or should I give up on quickcheck for this and just do direct testing?

Thanks,

  Maurizio

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: quickcheck for compiler testing

Andrey Chudnov
I use QuichCheck for compiler testing where I generate random, but well-formed programs and check some high-level syntactic properties on results. The QuickCheck instance is open-source (see language-ecmascript), but the compiler-test code is closed-source at this time. Still, I found that it's not the ultimate answer: many properties are hard to formalize, so I have to resort to unit tests. I'm not sure what you mean by "how this would play with test size reduction". I think it's worth giving a try, but keep in mind that you might still need to use unit tests.

Let me know if you have any questions.

/Andrey

On 02/16/2015 11:53 AM, Maurizio Vitale wrote:
I'm starting to work on my first real haskell program (I've only RWH exercises under my belt) and wondering whether people use quickcheck at all for compiler testing.

I've seen uses of quickcheck for testing parsers, but I'm interested in generating well-formed programs (e.g. random programs with all declarations in reasonable random places). This could be used to test passes other than parsing (or even parsing, for languages that needs to distinguish identifiers, like the 'typedef' problem in C/C++).

The only thing I can think of, is to use quickcheck for randomly generating statements, go over them and figure out free variables (incl. functions) and generate declarations in random places for them. But I'm not sure how this would play with test size reduction and doesn't look like a nice solution anyhow.

Any idea or pointers to examples? or should I give up on quickcheck for this and just do direct testing?

Thanks,

  Maurizio


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: quickcheck for compiler testing

Maurizio Vitale
By 'test size reduction' I mean the 'shrink' function. It seems to me (as I said, first Haskell program and no experience with quickcheck) that it works nicely with a topdown generation of the test, but I don't see how to easily generate correct programs that way.

Even if you cannot release your tests, maybe you can help me with a very simple case. Consider a trivial AST. A program is a possibly nested block. Each block is a bunch of declarations of variables and some use of them

data Block = Block [Declaration] [Statement]

data Declaration = Var String String

data Statement = Statement Block | Use String

How one would generate things like:

Block [Var "a" "int"] [Use "a"] -- here a is declared in the same block

Block [] [Statement Block [Var "s" "int"] [Statement Block [] [Use "s"]]] -- here s is declared in some other visible scope

etc.

Or am I trying to approach the problem from the wrong angle?

 

On Mon, Feb 16, 2015 at 12:02 PM, Andrey Chudnov <[hidden email]> wrote:
I use QuichCheck for compiler testing where I generate random, but well-formed programs and check some high-level syntactic properties on results. The QuickCheck instance is open-source (see language-ecmascript), but the compiler-test code is closed-source at this time. Still, I found that it's not the ultimate answer: many properties are hard to formalize, so I have to resort to unit tests. I'm not sure what you mean by "how this would play with test size reduction". I think it's worth giving a try, but keep in mind that you might still need to use unit tests.

Let me know if you have any questions.

/Andrey


On 02/16/2015 11:53 AM, Maurizio Vitale wrote:
I'm starting to work on my first real haskell program (I've only RWH exercises under my belt) and wondering whether people use quickcheck at all for compiler testing.

I've seen uses of quickcheck for testing parsers, but I'm interested in generating well-formed programs (e.g. random programs with all declarations in reasonable random places). This could be used to test passes other than parsing (or even parsing, for languages that needs to distinguish identifiers, like the 'typedef' problem in C/C++).

The only thing I can think of, is to use quickcheck for randomly generating statements, go over them and figure out free variables (incl. functions) and generate declarations in random places for them. But I'm not sure how this would play with test size reduction and doesn't look like a nice solution anyhow.

Any idea or pointers to examples? or should I give up on quickcheck for this and just do direct testing?

Thanks,

  Maurizio


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: quickcheck for compiler testing

Deyaaeldeen
Hi,

You will need to create instances of type Gen for your data types to specify how you can build expressions of your language. I have a simple interpreter for gradually-typed lambda calculus (still in development) and I am using quickcheck to verify it, here is the quickcheck code:
https://github.com/deyaaeldeen/GTLC/blob/master/interps/Testing.hs

Deyaa

On Mon, Feb 16, 2015 at 12:33 PM, Maurizio Vitale <[hidden email]> wrote:
By 'test size reduction' I mean the 'shrink' function. It seems to me (as I said, first Haskell program and no experience with quickcheck) that it works nicely with a topdown generation of the test, but I don't see how to easily generate correct programs that way.

Even if you cannot release your tests, maybe you can help me with a very simple case. Consider a trivial AST. A program is a possibly nested block. Each block is a bunch of declarations of variables and some use of them

data Block = Block [Declaration] [Statement]

data Declaration = Var String String

data Statement = Statement Block | Use String

How one would generate things like:

Block [Var "a" "int"] [Use "a"] -- here a is declared in the same block

Block [] [Statement Block [Var "s" "int"] [Statement Block [] [Use "s"]]] -- here s is declared in some other visible scope

etc.

Or am I trying to approach the problem from the wrong angle?

 

On Mon, Feb 16, 2015 at 12:02 PM, Andrey Chudnov <[hidden email]> wrote:
I use QuichCheck for compiler testing where I generate random, but well-formed programs and check some high-level syntactic properties on results. The QuickCheck instance is open-source (see language-ecmascript), but the compiler-test code is closed-source at this time. Still, I found that it's not the ultimate answer: many properties are hard to formalize, so I have to resort to unit tests. I'm not sure what you mean by "how this would play with test size reduction". I think it's worth giving a try, but keep in mind that you might still need to use unit tests.

Let me know if you have any questions.

/Andrey


On 02/16/2015 11:53 AM, Maurizio Vitale wrote:
I'm starting to work on my first real haskell program (I've only RWH exercises under my belt) and wondering whether people use quickcheck at all for compiler testing.

I've seen uses of quickcheck for testing parsers, but I'm interested in generating well-formed programs (e.g. random programs with all declarations in reasonable random places). This could be used to test passes other than parsing (or even parsing, for languages that needs to distinguish identifiers, like the 'typedef' problem in C/C++).

The only thing I can think of, is to use quickcheck for randomly generating statements, go over them and figure out free variables (incl. functions) and generate declarations in random places for them. But I'm not sure how this would play with test size reduction and doesn't look like a nice solution anyhow.

Any idea or pointers to examples? or should I give up on quickcheck for this and just do direct testing?

Thanks,

  Maurizio


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: quickcheck for compiler testing

David Feuer
In reply to this post by Maurizio Vitale

I was wondering the same thing about testing GHC itself. In particular, the test case for Trac #9964 (a subtle code generator crash) seems like it could conceivably be small enough for QuickCheck to have come up with. Although I can see why good properties would be hard to formulate (and some/many/most important ones are impossible to check in general), "does not quickly trigger a GHC panic" should be a very easy one.

On Feb 16, 2015 11:53 AM, "Maurizio Vitale" <[hidden email]> wrote:
I'm starting to work on my first real haskell program (I've only RWH exercises under my belt) and wondering whether people use quickcheck at all for compiler testing.

I've seen uses of quickcheck for testing parsers, but I'm interested in generating well-formed programs (e.g. random programs with all declarations in reasonable random places). This could be used to test passes other than parsing (or even parsing, for languages that needs to distinguish identifiers, like the 'typedef' problem in C/C++).

The only thing I can think of, is to use quickcheck for randomly generating statements, go over them and figure out free variables (incl. functions) and generate declarations in random places for them. But I'm not sure how this would play with test size reduction and doesn't look like a nice solution anyhow.

Any idea or pointers to examples? or should I give up on quickcheck for this and just do direct testing?

Thanks,

  Maurizio

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: quickcheck for compiler testing

Andrey Chudnov
In reply to this post by Maurizio Vitale
If you just need an example for generating and shrinking arbitrary ASTs, you can have a look here: https://github.com/jswebtools/language-ecmascript/blob/master/src/Language/ECMAScript3/Syntax/Arbitrary.hs . Note that I use the testing-feat package to generate Gen instances --- it tends to do better (explore interesting cases earlier) than handwritten code --- and then fix-up incorrect ASTs (another option is to simply discard them).

On 02/16/2015 12:33 PM, Maurizio Vitale wrote:
By 'test size reduction' I mean the 'shrink' function. It seems to me (as I said, first Haskell program and no experience with quickcheck) that it works nicely with a topdown generation of the test, but I don't see how to easily generate correct programs that way.

Even if you cannot release your tests, maybe you can help me with a very simple case. Consider a trivial AST. A program is a possibly nested block. Each block is a bunch of declarations of variables and some use of them

data Block = Block [Declaration] [Statement]

data Declaration = Var String String

data Statement = Statement Block | Use String

How one would generate things like:

Block [Var "a" "int"] [Use "a"] -- here a is declared in the same block

Block [] [Statement Block [Var "s" "int"] [Statement Block [] [Use "s"]]] -- here s is declared in some other visible scope

etc.

Or am I trying to approach the problem from the wrong angle?

 

On Mon, Feb 16, 2015 at 12:02 PM, Andrey Chudnov <[hidden email]> wrote:
I use QuichCheck for compiler testing where I generate random, but well-formed programs and check some high-level syntactic properties on results. The QuickCheck instance is open-source (see language-ecmascript), but the compiler-test code is closed-source at this time. Still, I found that it's not the ultimate answer: many properties are hard to formalize, so I have to resort to unit tests. I'm not sure what you mean by "how this would play with test size reduction". I think it's worth giving a try, but keep in mind that you might still need to use unit tests.

Let me know if you have any questions.

/Andrey


On 02/16/2015 11:53 AM, Maurizio Vitale wrote:
I'm starting to work on my first real haskell program (I've only RWH exercises under my belt) and wondering whether people use quickcheck at all for compiler testing.

I've seen uses of quickcheck for testing parsers, but I'm interested in generating well-formed programs (e.g. random programs with all declarations in reasonable random places). This could be used to test passes other than parsing (or even parsing, for languages that needs to distinguish identifiers, like the 'typedef' problem in C/C++).

The only thing I can think of, is to use quickcheck for randomly generating statements, go over them and figure out free variables (incl. functions) and generate declarations in random places for them. But I'm not sure how this would play with test size reduction and doesn't look like a nice solution anyhow.

Any idea or pointers to examples? or should I give up on quickcheck for this and just do direct testing?

Thanks,

  Maurizio


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: quickcheck for compiler testing

Paul Brauner-3

There's a recent paper by Jonas Duregård et al where they introduce a variant of feat that allows for efficient discarding of unwanted values, à la lazy Smallcheck. The motivating example of the paper is exactly what you're looking for: discarding ill-formed programs.


On Mon, Feb 16, 2015, 19:44 Andrey Chudnov <[hidden email]> wrote:
If you just need an example for generating and shrinking arbitrary ASTs, you can have a look here: https://github.com/jswebtools/language-ecmascript/blob/master/src/Language/ECMAScript3/Syntax/Arbitrary.hs . Note that I use the testing-feat package to generate Gen instances --- it tends to do better (explore interesting cases earlier) than handwritten code --- and then fix-up incorrect ASTs (another option is to simply discard them).


On 02/16/2015 12:33 PM, Maurizio Vitale wrote:
By 'test size reduction' I mean the 'shrink' function. It seems to me (as I said, first Haskell program and no experience with quickcheck) that it works nicely with a topdown generation of the test, but I don't see how to easily generate correct programs that way.

Even if you cannot release your tests, maybe you can help me with a very simple case. Consider a trivial AST. A program is a possibly nested block. Each block is a bunch of declarations of variables and some use of them

data Block = Block [Declaration] [Statement]

data Declaration = Var String String

data Statement = Statement Block | Use String

How one would generate things like:

Block [Var "a" "int"] [Use "a"] -- here a is declared in the same block

Block [] [Statement Block [Var "s" "int"] [Statement Block [] [Use "s"]]] -- here s is declared in some other visible scope

etc.

Or am I trying to approach the problem from the wrong angle?

 

On Mon, Feb 16, 2015 at 12:02 PM, Andrey Chudnov <[hidden email]> wrote:
I use QuichCheck for compiler testing where I generate random, but well-formed programs and check some high-level syntactic properties on results. The QuickCheck instance is open-source (see language-ecmascript), but the compiler-test code is closed-source at this time. Still, I found that it's not the ultimate answer: many properties are hard to formalize, so I have to resort to unit tests. I'm not sure what you mean by "how this would play with test size reduction". I think it's worth giving a try, but keep in mind that you might still need to use unit tests.

Let me know if you have any questions.

/Andrey


On 02/16/2015 11:53 AM, Maurizio Vitale wrote:
I'm starting to work on my first real haskell program (I've only RWH exercises under my belt) and wondering whether people use quickcheck at all for compiler testing.

I've seen uses of quickcheck for testing parsers, but I'm interested in generating well-formed programs (e.g. random programs with all declarations in reasonable random places). This could be used to test passes other than parsing (or even parsing, for languages that needs to distinguish identifiers, like the 'typedef' problem in C/C++).

The only thing I can think of, is to use quickcheck for randomly generating statements, go over them and figure out free variables (incl. functions) and generate declarations in random places for them. But I'm not sure how this would play with test size reduction and doesn't look like a nice solution anyhow.

Any idea or pointers to examples? or should I give up on quickcheck for this and just do direct testing?

Thanks,

  Maurizio


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: quickcheck for compiler testing

Andrey Chudnov
Do you know if there is an implementation?

On 02/17/2015 03:15 AM, Paul Brauner wrote:

There's a recent paper by Jonas Duregård et al where they introduce a variant of feat that allows for efficient discarding of unwanted values, à la lazy Smallcheck. The motivating example of the paper is exactly what you're looking for: discarding ill-formed programs.


On Mon, Feb 16, 2015, 19:44 Andrey Chudnov <[hidden email]> wrote:
If you just need an example for generating and shrinking arbitrary ASTs, you can have a look here: https://github.com/jswebtools/language-ecmascript/blob/master/src/Language/ECMAScript3/Syntax/Arbitrary.hs . Note that I use the testing-feat package to generate Gen instances --- it tends to do better (explore interesting cases earlier) than handwritten code --- and then fix-up incorrect ASTs (another option is to simply discard them).


On 02/16/2015 12:33 PM, Maurizio Vitale wrote:
By 'test size reduction' I mean the 'shrink' function. It seems to me (as I said, first Haskell program and no experience with quickcheck) that it works nicely with a topdown generation of the test, but I don't see how to easily generate correct programs that way.

Even if you cannot release your tests, maybe you can help me with a very simple case. Consider a trivial AST. A program is a possibly nested block. Each block is a bunch of declarations of variables and some use of them

data Block = Block [Declaration] [Statement]

data Declaration = Var String String

data Statement = Statement Block | Use String

How one would generate things like:

Block [Var "a" "int"] [Use "a"] -- here a is declared in the same block

Block [] [Statement Block [Var "s" "int"] [Statement Block [] [Use "s"]]] -- here s is declared in some other visible scope

etc.

Or am I trying to approach the problem from the wrong angle?

 

On Mon, Feb 16, 2015 at 12:02 PM, Andrey Chudnov <[hidden email]> wrote:
I use QuichCheck for compiler testing where I generate random, but well-formed programs and check some high-level syntactic properties on results. The QuickCheck instance is open-source (see language-ecmascript), but the compiler-test code is closed-source at this time. Still, I found that it's not the ultimate answer: many properties are hard to formalize, so I have to resort to unit tests. I'm not sure what you mean by "how this would play with test size reduction". I think it's worth giving a try, but keep in mind that you might still need to use unit tests.

Let me know if you have any questions.

/Andrey


On 02/16/2015 11:53 AM, Maurizio Vitale wrote:
I'm starting to work on my first real haskell program (I've only RWH exercises under my belt) and wondering whether people use quickcheck at all for compiler testing.

I've seen uses of quickcheck for testing parsers, but I'm interested in generating well-formed programs (e.g. random programs with all declarations in reasonable random places). This could be used to test passes other than parsing (or even parsing, for languages that needs to distinguish identifiers, like the 'typedef' problem in C/C++).

The only thing I can think of, is to use quickcheck for randomly generating statements, go over them and figure out free variables (incl. functions) and generate declarations in random places for them. But I'm not sure how this would play with test size reduction and doesn't look like a nice solution anyhow.

Any idea or pointers to examples? or should I give up on quickcheck for this and just do direct testing?

Thanks,

  Maurizio


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: quickcheck for compiler testing

Paul Brauner-3
According to the paper there is, but it's not on Hackage as far as I know. If you ever ping the authors about the implementation I'd be interested in their answer too.

Paul

On Tue Feb 17 2015 at 1:54:52 PM Andrey Chudnov <[hidden email]> wrote:
Do you know if there is an implementation?


On 02/17/2015 03:15 AM, Paul Brauner wrote:

There's a recent paper by Jonas Duregård et al where they introduce a variant of feat that allows for efficient discarding of unwanted values, à la lazy Smallcheck. The motivating example of the paper is exactly what you're looking for: discarding ill-formed programs.


On Mon, Feb 16, 2015, 19:44 Andrey Chudnov <[hidden email]> wrote:
If you just need an example for generating and shrinking arbitrary ASTs, you can have a look here: https://github.com/jswebtools/language-ecmascript/blob/master/src/Language/ECMAScript3/Syntax/Arbitrary.hs . Note that I use the testing-feat package to generate Gen instances --- it tends to do better (explore interesting cases earlier) than handwritten code --- and then fix-up incorrect ASTs (another option is to simply discard them).


On 02/16/2015 12:33 PM, Maurizio Vitale wrote:
By 'test size reduction' I mean the 'shrink' function. It seems to me (as I said, first Haskell program and no experience with quickcheck) that it works nicely with a topdown generation of the test, but I don't see how to easily generate correct programs that way.

Even if you cannot release your tests, maybe you can help me with a very simple case. Consider a trivial AST. A program is a possibly nested block. Each block is a bunch of declarations of variables and some use of them

data Block = Block [Declaration] [Statement]

data Declaration = Var String String

data Statement = Statement Block | Use String

How one would generate things like:

Block [Var "a" "int"] [Use "a"] -- here a is declared in the same block

Block [] [Statement Block [Var "s" "int"] [Statement Block [] [Use "s"]]] -- here s is declared in some other visible scope

etc.

Or am I trying to approach the problem from the wrong angle?

 

On Mon, Feb 16, 2015 at 12:02 PM, Andrey Chudnov <[hidden email]> wrote:
I use QuichCheck for compiler testing where I generate random, but well-formed programs and check some high-level syntactic properties on results. The QuickCheck instance is open-source (see language-ecmascript), but the compiler-test code is closed-source at this time. Still, I found that it's not the ultimate answer: many properties are hard to formalize, so I have to resort to unit tests. I'm not sure what you mean by "how this would play with test size reduction". I think it's worth giving a try, but keep in mind that you might still need to use unit tests.

Let me know if you have any questions.

/Andrey


On 02/16/2015 11:53 AM, Maurizio Vitale wrote:
I'm starting to work on my first real haskell program (I've only RWH exercises under my belt) and wondering whether people use quickcheck at all for compiler testing.

I've seen uses of quickcheck for testing parsers, but I'm interested in generating well-formed programs (e.g. random programs with all declarations in reasonable random places). This could be used to test passes other than parsing (or even parsing, for languages that needs to distinguish identifiers, like the 'typedef' problem in C/C++).

The only thing I can think of, is to use quickcheck for randomly generating statements, go over them and figure out free variables (incl. functions) and generate declarations in random places for them. But I'm not sure how this would play with test size reduction and doesn't look like a nice solution anyhow.

Any idea or pointers to examples? or should I give up on quickcheck for this and just do direct testing?

Thanks,

  Maurizio


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: quickcheck for compiler testing

Maurizio Vitale
In reply to this post by Paul Brauner-3
also a longer thesis (which I believe is the backtracking optimization they refer to in the paper)  is at http://publications.lib.chalmers.se/records/fulltext/157525.pdf
I'll have to play with a very small language and see where I get.
Thanks to everybody, and if there're other examples around I'll be glad to know about them.

On Tue, Feb 17, 2015 at 3:15 AM, Paul Brauner <[hidden email]> wrote:

There's a recent paper by Jonas Duregård et al where they introduce a variant of feat that allows for efficient discarding of unwanted values, à la lazy Smallcheck. The motivating example of the paper is exactly what you're looking for: discarding ill-formed programs.


On Mon, Feb 16, 2015, 19:44 Andrey Chudnov <[hidden email]> wrote:
If you just need an example for generating and shrinking arbitrary ASTs, you can have a look here: https://github.com/jswebtools/language-ecmascript/blob/master/src/Language/ECMAScript3/Syntax/Arbitrary.hs . Note that I use the testing-feat package to generate Gen instances --- it tends to do better (explore interesting cases earlier) than handwritten code --- and then fix-up incorrect ASTs (another option is to simply discard them).


On 02/16/2015 12:33 PM, Maurizio Vitale wrote:
By 'test size reduction' I mean the 'shrink' function. It seems to me (as I said, first Haskell program and no experience with quickcheck) that it works nicely with a topdown generation of the test, but I don't see how to easily generate correct programs that way.

Even if you cannot release your tests, maybe you can help me with a very simple case. Consider a trivial AST. A program is a possibly nested block. Each block is a bunch of declarations of variables and some use of them

data Block = Block [Declaration] [Statement]

data Declaration = Var String String

data Statement = Statement Block | Use String

How one would generate things like:

Block [Var "a" "int"] [Use "a"] -- here a is declared in the same block

Block [] [Statement Block [Var "s" "int"] [Statement Block [] [Use "s"]]] -- here s is declared in some other visible scope

etc.

Or am I trying to approach the problem from the wrong angle?

 

On Mon, Feb 16, 2015 at 12:02 PM, Andrey Chudnov <[hidden email]> wrote:
I use QuichCheck for compiler testing where I generate random, but well-formed programs and check some high-level syntactic properties on results. The QuickCheck instance is open-source (see language-ecmascript), but the compiler-test code is closed-source at this time. Still, I found that it's not the ultimate answer: many properties are hard to formalize, so I have to resort to unit tests. I'm not sure what you mean by "how this would play with test size reduction". I think it's worth giving a try, but keep in mind that you might still need to use unit tests.

Let me know if you have any questions.

/Andrey


On 02/16/2015 11:53 AM, Maurizio Vitale wrote:
I'm starting to work on my first real haskell program (I've only RWH exercises under my belt) and wondering whether people use quickcheck at all for compiler testing.

I've seen uses of quickcheck for testing parsers, but I'm interested in generating well-formed programs (e.g. random programs with all declarations in reasonable random places). This could be used to test passes other than parsing (or even parsing, for languages that needs to distinguish identifiers, like the 'typedef' problem in C/C++).

The only thing I can think of, is to use quickcheck for randomly generating statements, go over them and figure out free variables (incl. functions) and generate declarations in random places for them. But I'm not sure how this would play with test size reduction and doesn't look like a nice solution anyhow.

Any idea or pointers to examples? or should I give up on quickcheck for this and just do direct testing?

Thanks,

  Maurizio


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: quickcheck for compiler testing

Doug McIlroy
In reply to this post by Maurizio Vitale
>> I'm ...  wondering whether people use quickcheck at all for
>> compiler testing.

> it's worth giving a try, but keep in mind that you might still
> need to use unit tests

If your compiler is for a widely used language, you might consider
a hybrid approach due to Bill McKeeman: generate random code
and check it by automated crowd-sourcing. The crowd is a jury
of other compilers, not necessarily even for the same hardware.
The check is to compare compilability, compile time, run time
and run results against those of the jury.

McKeeman used a generative grammar whose productions were
adjustably weighted to influence the characteristics of the
generated code. Over the course of several months of overnight
runs torturing a production C compiler, he turned up something
like one anomaly per day, excluding jury errors and extra
reports from a common root cause.  (One amusing find was that
the compiler took Omega(INT_MAX) time to evaluate the constant
expression 1<<INT_MAX.)

Doug
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe