252: Property Testing

by Antero Mejr

Status

For editor's use only. Please do not edit this section.

??? the draft/final/withdrawn status of the SRFI, information on how to subscribe to its mailing list, and important dates in its history. The editor will add this section.

Abstract

This defines an extension of the SRFI 64 test suite API to support property testing. It uses SRFI 158 generators to generate test inputs, which allows for the creation of custom input generators. It uses SRFI 194 as the source of random data, so that the generation of random test inputs can be made deterministic. For convenience, it also provides helper procedures to create test input generators for the types specified in R7RS-small. The interface to run property tests is similar to SRFI 64, and a property testing-specific test runner is specified in order to display the results of the propertized tests.

Issues

char-generator does not use an SRFI 14 char-set. This means, for implementations that use Unicode, char-generator may generate characters that are not valid Unicode code points. I think this is the correct behavior, since invalid code points fulfill the char? predicate.

I wanted to use the test-name attribute in test-assert to store the iteration number as a string. But the test-assert macro only evaluates test-name once, so I abandoned that idea. The iteration number is made available inside the test runner's test-result-alist instead.

Some procedures being tested may accept an eof-object as an argument. But generators use eof-object to indicate if they are exhausted. The user might naively create an eof-object generator, not knowing that it is equivalent to an empty generator. This shouldn't cause an error but may cause confusion.

I would like to propose (scheme property-test) as an R7RS large alias name.

Rationale

Property testing is a software testing method where the programmer defines a property for a piece of code. A property is a predicate procedure that accepts one or more input arguments and returns True if the code under test exhibits correct behavior for the given inputs. Then, the property testing library generates pseudorandom ranges of inputs of the correct types, and applies them to the property. After running many tests, if application of inputs to the property ever returns False, then it can be assumed there a bug in the code, provided that the property itself is correct.

Property testing can expose bugs that would not be found using a small number of hand-written test cases. In addition to generating random inputs, property testing libraries may also generate inputs that commonly cause incorrect behavior, such as 0 or NaN.

Property testing provides a more rigorous alternative to traditional unit testing. In terms of the learning and effort required for use, it serves as a "middle ground" between unit tests and formal verification methods. Properties can be written as stricter specifiers of program behavior than individual test cases.

Property testing was popularized by the QuickCheck library for Haskell, and has since spread to other languages. The following libraries were referenced in the creation of this document, in order of influence:

Hypothesis, QuickCheck, Scheme-Check, and QuickCheck for Racket.

Property testing requires a testing environment, generators, and random sources of data. These dependencies are provided by SRFI 64, 158, and 194, respectively. Users of those SRFIs will note the familiar interfaces presented here. SRFI 64 is chosen to provide the testing environment over the simpler SRFI 78. This is because property testing is often more complex than unit testing, so a more extensive testing environment is required.

The Scheme-Check library provided an implementation of property testing for a limited set of Scheme implementations. However, it has been unmaintained for many years, and is not compatible with R7RS. Introducing a flexible property testing system as an SRFI will standardize a stable interface that can be used in multiple implementations.

Property testing is also known as generative testing or property-based testing. This document uses the short name in order to have shorter identifiers.

Specification

Testing procedures

(test-property property generator-list [runs])

Run a property test.

The property argument is a predicate procedure with an arity equal to the length of the generator-list argument. The generator-list argument must be a proper list containing SRFI 158 generators. The generator-list must be applied to the property procedure such that the value generated by the car position of the generator-list will be the first argument to property, and so on.

The runs argument, if provided, must be a non-negative integer. This argument specifies how many times the property will be tested with newly generated inputs. If not provided, the implementation may choose how many times to run the test.

The generators in generator-list must be infinite. It is an error for any of the generators to be exhausted.

This procedure must be called inside a SRFI 64 test group.

(define (my-square z) (square z))
(define (my-square-property z) (= (sqrt (my-square z)) z))

;; Test the property ten times.
(test-property my-square-property (list (integer-generator)) 10)

(test-property-expect-fail property generator-list [runs])

Run a property test that is expected to fail for all inputs. This only affects test reporting, not test execution.

(define (my-square z) (* z 2)) ; WRONG
(define (my-square-property z) (= (sqrt (my-square z)) z))

(test-property-expect-fail my-square-property (list (integer-generator)))

(test-property-skip property generator-list [runs])

Do not run a property test. The active test-runner will skip the test, and no runs will be performed.

(test-property-skip (lambda (x) #t) (list (integer-generator)))

(test-property-error property generator-list [runs])

Run a property test that is expected to raise an exception for all inputs. The exception raised may be of any type.

(define (my-square z) (* z "foo")) ; will cause an error
(define (my-square-property z) (= (sqrt (my-square z)) z))

(test-property-error my-square-property (list (integer-generator)))

(test-property-error-type error-type property generator-list [runs])

Run a property test that is expected to raise a specific type of exception for all inputs. In order for the test to pass, the exception raised must match the error type specified by the error-type argument. The error type may be implementation-specific, or one specified in SRFI 36.

(define (cause-read-error str)
  (read (open-input-string (string-append ")" str))))

(define (cause-read-error-property str)
  (symbol? (cause-read-error str)))

(test-property-error-type
  &read-error cause-read-error-property (list (string-generator)))

Generator procedures

The generator and special generator procedures in this SRFI must be implemented using SRFI 194. That way, the current-random-source parameter can be configured to facilitate deterministic generation of property test inputs.

(boolean-generator)

Create an infinite generator that returns #t and #f. The generator should return the sequence (#t #f) first, then a uniformly random distribution of #t and #f.

(define bool-gen (boolean-generator))

(bool-gen) ; => #t
(bool-gen) ; => #f
(bool-gen) ; => #t or #f

(bytevector-generator)

Create an infinite generator that returns objects that fulfill the bytevector? predicate. The generator should return an empty bytevector first, then a series of bytevectors with uniformly randomly distributed contents and sizes.

(define bytevector-gen (bytevector-generator))

(bytevector-gen) ; => #u8()
(bytevector-gen) ; => #u8(...)

(char-generator)

Create an infinite generator that returns objects that fulfill the char? predicate. The generator should return the character #\null first, then a uniformly random distribution of characters.

(define char-gen (char-generator))

(char-gen) ; => #\null
(char-gen) ; => #\something

(complex-generator)

Create an infinite generator that returns objects that fulfill the complex? predicate. The real and imaginary parts of the complex numbers may be exact or inexact. The generator should return the sequence

(0.0+0.0i 0+0i -0.0-0.0i -0-0i 1+1i 1.1+1.1i -1-1i -1.1-1.1i
 +inf.0+inf.0i -inf.0-inf.0i +nan.0+nan.0i -nan.0-nan.0i)

first, then a uniformly random distribution of complex numbers. Elements of the above sequence may be omitted if they are not distinguished in the implementation.

(define complex-gen (complex-generator))

(complex-gen) ; => 0.0+0.0i

(exact-generator)

Create an infinite generator that returns objects that fulfill the exact? predicate. The generator should return the sequence (0 -0 1 -1) first, then a uniformly random distribution of exact numbers. Elements of the above sequence may be omitted if they are not distinguished in the implementation.

(define exact-gen (exact-generator))

(exact-gen) ; => 0

(exact-complex-generator)

Create an infinite generator that returns objects that fulfill the complex? predicate. The real and imaginary parts of the complex numbers must be exact. The generator should return the sequence (0+0i -0-0i 1+1i -1-1i) first, then a uniformly random distribution of exact complex numbers. Elements of the above sequence may be omitted if they are not distinguished in the implementation.

(define exact-complex-gen (exact-complex-generator))

(exact-complex-gen) ; => 0+0i

(inexact-complex-generator)

Create an infinite generator that returns objects that fulfill the complex? predicate. The real and imaginary parts of the complex numbers must be inexact. The generator should return the sequence

(0.0+0.0i -0.0-0.0i 1.1+1.1i -1.1-1.1i +inf.0+inf.0i -inf.0-inf.0i
 +nan.0+nan.0i -nan.0-nan.0i)

first, then a uniformly random distribution of inexact complex numbers. Elements of the above sequence may be omitted if they are not distinguished in the implementation.

(define inexact-complex-gen (inexact-complex-generator))

(inexact-complex-gen) ; => 0.0+0.0i

(inexact-generator)

Create an infinite generator that returns objects that fulfill the inexact? predicate. The generator should return the sequence

(0.0 -0.0 1.1 -1.1 +inf.0 -inf.0 +nan.0 -nan.0)

first, then a uniformly random distribution of inexact complex numbers. Elements of the above sequence may be omitted if they are not distinguished in the implementation.

(define inexact-gen (inexact-generator))

(inexact-gen) ; => 0.0

(integer-generator)

Create an infinite generator that returns objects that fulfill the integer? predicate. The generator should return the sequence (0 -0 1 -1) first, then a uniformly random distribution of integers. Elements of the above sequence may be omitted if they are not distinguished in the implementation.

(define integer-gen (integer-generator))

(integer-gen) ; => 0

(number-generator)

Create an infinite generator that returns objects that fulfill the number? predicate. The generator should return the sequence

(0.0 -0.0 0 -0 1 -1 1.1 -1.1 +inf.0 -inf.0 +nan.0 -nan.0)

first, then a uniformly random distribution of numbers. Elements of the above sequence may be omitted if they are not distinguished in the implementation.

(define number-gen (number-generator))

(number-gen) ; => 0

(rational-generator)

Create an infinite generator that returns objects that fulfill the rational? predicate. The generator should return the sequence

(0 -0 0.0 -0.0 -1.1 1.1 -1 1)

first, then a uniformly random distribution of rational numbers. Elements of the above sequence may be omitted if they are not distinguished in the implementation.

(define rational-gen (rational-generator))

(rational-gen) ; => 0

(real-generator)

Create an infinite generator that returns objects that fulfill the real? predicate. The generator should return the sequence

(0.0 -0.0 0 -0 1 -1 1.1 -1.1 +inf.0 -inf.0 +nan.0 -nan.0)

first, then a uniformly random distribution of real numbers. Elements of the above sequence may be omitted if they are not distinguished in the implementation.

(define real-gen (real-generator))

(real-gen) ; => 0

(string-generator)

Create an infinite generator that returns strings. The generator should return the sequence ("" "\0") first, then a series of strings with uniformly randomly distributed contents and sizes.

(define string-gen (string-generator))

(string-gen) ; => ""
(string-gen) ; => "\0"
(string-gen) ; => "..."

(symbol-generator)

Create an infinite generator that returns symbols.

(define symbol-gen (symbol-generator))

(symbol-gen) ; => 'something

Special generator procedures

(list-generator-of subgenerator [max-length])

Create an infinite generator that returns homogeneous lists. The contents of the list are values generated by subgenerator. The generator should return the empty list first. Then it should return lists containing values generated by subgenerator, with a length uniformly randomly distributed between 1 and max-length, if specified. If the max-length argument is not specified, the implementation may select the size range.

(define list-gen (list-generator-of (integer-generator)))

(list-gen) ; => '()
(list-gen) ; => '(0 -0 1 -1 ...)

(pair-generator-of subgenerator [subgenerator2])

Create an infinite generator that returns pairs. The contents of the pairs are values generated by the subgenerator, and if specified, subgenerator2 arguments. If both subgenerator arguments are specified, subgenerator will populate the car, while subgenerator2 will populate the cdr.

(define pair-gen (pair-generator-of (integer-generator boolean-generator)))

(pair-gen) ; => '(0 . #t)

(procedure-generator-of subgenerator)

Create an infinite generator that returns procedures. The returns of those procedures are values generated by the subgenerator argument. The procedures generated should be variadic.

(define proc-gen (procedure-generator-of (boolean-generator)))

((proc-gen) 1)           ; => #t
((proc-gen) 'foo 'bar)   ; => #f
((proc-gen) "x" "y" "z") ; => #t or #f

(vector-generator-of subgenerator [max-length])

Create an infinite generator that returns homogeneous vectors. The contents of the vector are values generated by subgenerator. The generator should return the empty vector first. Then it should return vectors containing values generated by subgenerator, with a length uniformly randomly distributed between 1 and max-length, if specified. If the max-length argument is not specified, the implementation may select the size range.

(define vector-gen (vector-generator-of (boolean-generator)))

(vector-gen) ; => #()
(vector-gen) ; => #(#t #f ...)

Test runner

(property-test-runner)

Creates a SRFI 64 test-runner. The test runner should be able to display or write the results of all the runs of a property-based test.

Implementation

A conformant sample implementation is provided. It depends on R7RS-small, SRFI 1, SRFI 64, SRFI 158, and SRFI 194. However, there are values in the implementation that may need to be adjusted. The size of the generated test inputs, and the number of cases to run, should be tuned depending on the performance characteristics of the implementation. These tunable values are denoted by comments in the code.

The property-test-runner provided by the sample implementation is the same as the test-runner-simple from SRFI 64. However, implementations should define a property testing-specific runner that displays results in a well-organized way.

The sample implementation is available here.

Acknowledgements

Thank you to Shiro Kawai for the initial review of the implementation.

Copyright

© 2024 Antero Mejr.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.