dsp-dr / dsp-dr/guile-monkey-interpreter
Add Fuzzer and Property-Based Testing
- Dominant language
- Scheme
- Stars
- 0
- Forks
- 0
- Avg merge
- 19h 25m
- Merged PRs (30d)
- 1
Description
## Feature Request: Fuzzing and Property-Based Testing
### Overview
Implement fuzzing and property-based testing to discover edge cases and ensure interpreter robustness.
### Proposed Approaches
#### 1. Grammar-Based Fuzzer
Generate random but syntactically valid Monkey programs using the language grammar.
Features:
- Random token generation
- Grammar-aware program construction
- Mutation-based fuzzing
- Coverage-guided fuzzing
#### 2. Property-Based Testing (QuickCheck-style)
Port or implement a property-based testing library for Guile Scheme.
Properties to test:
- **Parsing invariants**: `parse(unparse(ast)) = ast`
- **Evaluation properties**: `eval(x + 0) = eval(x)`
- **Type safety**: No type errors in well-formed programs
- **Determinism**: Same input always produces same output
### Guile Libraries to Consider
#### Existing Options:
- **guile-quickcheck**: QuickCheck port for Guile (if available)
- **SRFI-194**: Random data generators
- **Custom implementation**: Build on SRFI-27 (random numbers)
### Implementation Plan
1. **Phase 1: Random Program Generation**
- Token generator
- AST generator with depth limits
- Expression generator by type
2. **Phase 2: Property Testing**
- Define language properties
- Implement generators for each AST node type
- Shrinking strategies for counterexamples
3. **Phase 3: Fuzzing Infrastructure**
- Mutation operators
- Coverage tracking
- Crash detection
- Corpus management
### Example Property Test
```scheme
(define-property "arithmetic-identity"
(for-all ([n integer-gen])
(equal? (eval-monkey (format "~a + 0" n))
(eval-monkey (format "~a" n)))))
```
### Example Fuzzer
```scheme
(define (fuzz-expression depth)
(if (zero? depth)
(generate-literal)
(random-choice
(generate-literal)
(generate-binary-op (- depth 1))
(generate-function-call (- depth 1)))))
```
### Benefits
- Discover parser edge cases
- Find evaluator bugs
- Test error handling
- Ensure robustness
- Generate test corpus
### Success Metrics
- No crashes on 1M random programs
- All properties hold for 10K test cases
- 100% code coverage achieved
- Performance regression detection
Contributor guide
Assessment
This issue has not been assessed yet.