dsp-dr / dsp-dr/guile-monkey-interpreter

Add Fuzzer and Property-Based Testing

Open
#2 0 comments 0 reactions 1 assignee Claimed by @jwalsh View on GitHub
enhancement feature-request 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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.