research-article

Smallcheck and lazy smallcheck: automatic exhaustive testing for small values

Authors:

Colin Runciman,

Matthew Naylor,

Fredrik LindbladAuthors Info & Claims

Haskell '08: Proceedings of the first ACM SIGPLAN symposium on Haskell

Pages 37 - 48

https://doi.org/10.1145/1411286.1411292

Published: 25 September 2008 Publication History

Abstract

This paper describes two Haskell libraries for property-based testing. Following the lead of QuickCheck, these testing libraries SmallCheck and Lazy SmallCheck also use type-based generators to obtain test-sets of finite values for which properties are checked, and report any counter-examples found. But instead of using a sample of randomly generated values they test properties for all values up to some limiting depth, progressively increasing this limit. The paper explains the design and implementation of both libraries and evaluates them in comparison with each other and with QuickCheck.

Supplementary Material

JPG File (1411292.jpg)

Download
19.31 KB

index.html (index.html)

Slides from the presentation

Download
.95 KB

Audio only (1411292.mp3)

Download
11.58 MB

Video (1411292.mp4)

Download
159.74 MB

References

[1]

Sergio Antoy, Rachid Echahed, and Michael Hanus. A needed narrowing strategy. In POPL'94, pages 268--279, 1994.

Digital Library

[2]

Lennart Augustsson. Overloaded booleans. http://augustss.blogspot.com/, 2007.

[3]

Richard S. Bird. Introduction to Functional Programming Using Haskell. Prentice-Hall, 1998.

Digital Library

[4]

Jan Christiansen and Sebastian Fischer. Easycheck - test data for free. In FLOPS'08, pages 322--336. LNCS 4989, 2008.

Digital Library

[5]

K. Claessen, C. Runciman, O. Chitil, R. J. M. Hughes, and M. Wallace. Testing and tracing lazy functional programs using QuickCheck and Hat. In AFP'02, pages 59--99. Springer LNCS 2638, 2002.

[6]

Koen Claessen and John Hughes. QuickCheck: A lightweight tool for random testing of Haskell programs. In ICFP'00, pages 268--279. ACM SIGPLAN, 2000.

Digital Library

[7]

Andy Gill and Colin Runciman. Haskell program coverage. In Haskell'07, pages 1--12. ACM, 2007.

Digital Library

[8]

Michael Hanus. Curry: An Integrated Functional Logic Language. Language report, available online at http://www.informatik.uni-kiel.de/~curry,/report.html, March 2006.

[9]

Graham Hutton. The countdown problem. Journal of Functional Programming, 12(6):609--616, November 2002.

Digital Library

[10]

Daniel Jackson. Software abstractions: logic, language and analysis. The MIT Press, 2006.

Digital Library

[11]

Pieter W. M. Koopman, Artem Alimarine, Jan Tretmans, and Marinus J. Plasmeijer. Gast: Generic automated software testing. In IFL'02, pages 84--100. LNCS 2670, 2002.

Digital Library

[12]

Fredrik Lindblad. Property directed generation of first-order test data. In TFP'07, volume 8, pages 105--123. Intellect, 2008.

[13]

John W. Lloyd. Programming in an integrated functional and logic language. Journal of Functional and Logic Programming, 1999 (3).

[14]

Wolfgang Lux. The Munster Curry Compiler. http://danae.uni-muenster.de/~lux/curry/, 2003.

[15]

Neil Mitchell and Stefan O'Rear. Derive - project home page. http://www.cs.york.ac.uk/~ndm/derive/, March 2007.

[16]

Neil Mitchell and Colin Runciman. A static checker for safe pattern matching in Haskell. In TFP'05, volume 6, pages 15--30. Intellect, 2007.

[17]

Matthew Naylor and Colin Runciman. The Reduceron: Widening the von Neumann bottleneck for graph reduction using an FPGA. In IFL'07, page to appear. LNCS, 2008.

[18]

Matthew Naylor and Colin Runciman. Finding inputs that reach a target expression. In SCAM'07, pages 133--142. IEEE Computer Society, 2007.

Digital Library

[19]

Chris Okasaki. Red-black trees in a functional setting. Journal of Functional Programming, 9(4): 471--477, 1999.

Digital Library

[20]

Simon Peyton Jones. The Implementation of Functional Programming Languages. Computer Science. Prentice-Hall, 1987.

Digital Library

[21]

Simon Peyton Jones, Alastair Reid, Fergus Henderson, Tony Hoare, and Simon Marlow. A semantics for imprecise exceptions. In PLDI'99, pages 25--36. ACM, 1999.

Digital Library

[22]

D. A. Turner. A new implementation technique for applicative languages. Software - Practice and Experience, 9(1):31--49, 1979.

Cited By

Winterer DSu Z(2024)Validating SMT Solvers for Correctness and Performance via Grammar-Based EnumerationProceedings of the ACM on Programming Languages10.1145/36897958:OOPSLA2(2378-2401)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689795
Webbers Rvon Gleissenthall KJhala R(2024)Refinement Type RefutationsProceedings of the ACM on Programming Languages10.1145/36897458:OOPSLA2(962-987)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689745
Ballesteros IBenac-Earle CMariño JFredlund LHerranz Á(2024)Generation of Algebraic Data Type Values Using Evolutionary AlgorithmsJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2024.101022(101022)Online publication date: Nov-2024
https://doi.org/10.1016/j.jlamp.2024.101022
Show More Cited By

Index Terms

Smallcheck and lazy smallcheck: automatic exhaustive testing for small values
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
  2. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

Smallcheck and lazy smallcheck: automatic exhaustive testing for small values
HASKELL '08

This paper describes two Haskell libraries for property-based testing. Following the lead of QuickCheck, these testing libraries SmallCheck and Lazy SmallCheck also use type-based generators to obtain test-sets of finite values for which properties are ...
ArbitCheck: A Highly Automated Property-Based Testing Tool for Java
ICSTW '14: Proceedings of the 2014 IEEE International Conference on Software Testing, Verification, and Validation Workshops

Lightweight property-based testing tools are becoming popular these days. With property-based testing, developers can test properties of the system under test against large varieties of randomly generated inputs without writing test cases. Despite the ...
Automatic generation of test models and properties from UML models with OCL constraints
OCL '12: Proceedings of the 12th Workshop on OCL and Textual Modelling

Model-Based Testing and Property-Based Testing are two testing methodologies that usually facilitate the automation of the generation of test cases, using either models or properties as basis to derive complete test suites. In doing so, they also ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell '08: Proceedings of the first ACM SIGPLAN symposium on Haskell

September 2008

134 pages

ISBN:9781605580647

DOI:10.1145/1411286

Program Chair:
Andy Gill
University of Kansas, US

ACM SIGPLAN Notices Volume 44, Issue 2
HASKELL '08
February 2009
126 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1543134
Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 September 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP08

Sponsor:

ICFP08: ACM SIGPLAN International Conference on Functional Programming

September 25, 2008

BC, Victoria, Canada

Acceptance Rates

Haskell '08 Paper Acceptance Rate 13 of 28 submissions, 46%;

Overall Acceptance Rate 57 of 143 submissions, 40%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

156
Total Citations
View Citations
528
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)5

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Winterer DSu Z(2024)Validating SMT Solvers for Correctness and Performance via Grammar-Based EnumerationProceedings of the ACM on Programming Languages10.1145/36897958:OOPSLA2(2378-2401)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689795
Webbers Rvon Gleissenthall KJhala R(2024)Refinement Type RefutationsProceedings of the ACM on Programming Languages10.1145/36897458:OOPSLA2(962-987)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689745
Ballesteros IBenac-Earle CMariño JFredlund LHerranz Á(2024)Generation of Algebraic Data Type Values Using Evolutionary AlgorithmsJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2024.101022(101022)Online publication date: Nov-2024
https://doi.org/10.1016/j.jlamp.2024.101022
de Vries EMcDonell TVazou N(2023)falsify: Internal Shrinking Reimagined for HaskellProceedings of the 16th ACM SIGPLAN International Haskell Symposium10.1145/3609026.3609733(97-109)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3609026.3609733
Elazar Mittelman SResnick APerez IGoodloe ALampropoulos LMcDonell TVazou N(2023)Don’t Go Down the Rabbit Hole: Reprioritizing Enumeration for Property-Based TestingProceedings of the 16th ACM SIGPLAN International Haskell Symposium10.1145/3609026.3609730(59-71)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3609026.3609730
Mista ARusso A(2023)MUTAGEN: Reliable Coverage-Guided, Property-Based Testing using Exhaustive Mutations2023 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST57152.2023.00025(176-187)Online publication date: Apr-2023
https://doi.org/10.1109/ICST57152.2023.00025
Kappelmann KRädle JStevens L(2022)Engaging, Large-Scale Functional Programming Education in Physical and Virtual SpaceElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.363.6363(93-113)Online publication date: 26-Jul-2022
https://doi.org/10.4204/EPTCS.363.6
Chen ZRizkallah CO'Connor LSusarla PKlein GHeiser GKeller GFischer BBurgueño LCazzola W(2022)Property-Based Testing: Climbing the Stairway to VerificationProceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3567512.3567520(84-97)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3567512.3567520
van der Rest CSwierstra W(2022)A completely unique account of enumerationProceedings of the ACM on Programming Languages10.1145/35476366:ICFP(411-437)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547636
Cockx JMelkonian OEscot LChapman JNorell UPolikarpova N(2022)Reasonable Agda is correct Haskell: writing verified Haskell using agda2hsProceedings of the 15th ACM SIGPLAN International Haskell Symposium10.1145/3546189.3549920(108-122)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1145/3546189.3549920
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents