I came here to talk about SmallCheck, which was created to do exhaustive checking of inputs.
Yes! This is the same thing. There are lots of fun publications in this area, though Rudy Matela wins the trophy with his PhD thesis and many libraries.

Rudy wrote leancheck for intelligent enumerative testing, fitspec to find missing properties or overspecified properties, speculate to discover properties, and extrapolate for finding generalized counter-examples to a property.

But wait, there’s more! If you get as excited about property based testing as I do, you will enjoy this PhD thesis.

It’s related, but not in a fundamental way. Both the post and the paper are about exhaustively enumerating small cases. SmallCheck takes a type-driven approach, while Gen focuses on values (you don’t generate lists and then filter them to be permutations, you just directly generate permutations).

The other paper linked in the discussion, Capturing the Future by Replaying the Past, captures the fundamentals. Gen is essentially what is described in “WARM-UP: REPLAY-BASED NONDETERMINISM”.

(Aside: did you ever realise that the number of ways to pick two objects out of n is equal to the sum of first n natural numbers?)

Some proofs:

C(n, 2) = n / 2!(n-2)! = n(n-1)/2 = sum(0, n).

One algorithm to enumerate all ways of picking two objects out of n is to first pick one object from N, then pick a second from the remaining n-1. There’s n(n-1) ways to do this, but half of them are symmetric, so it’s n(n-1)/2.

Picking two objects is equivalent to picking an ordered pair of unequal coordinates from an n x n rectangle, which is equivalent to picking from the lower triangle. The first row of the triangle has 0 coordinates (since they have to be unequal), the next row has 1 coordinate (0, 1), the one after has 2… so there are 0 + 1 + 2 + ... = n(n-1)/2 possible coordinates.

C(n, 2) is index 2 (where the first element is index 0) of the nth row of Pascal’s triangle. Index 0 is always 1, index 1 is always n, index 2 is n + the previous row’s index 2, which will be n-1. Proceed inductively.

That’s a neat technique. At first I thought the list monad is where the article is going, but didn’t guess that right this time. It is nice that Haskell has its solution in the standard library, though…

Heh, I indeed didn’t see the connection, thanks! Though, even having seen the connection, I am not sure how to express what I want as a list monad exactly.

Let’s look at the allArrays n m function, which returns arrays with lengths 0..n of elements 0..m. For allArrays 2 3, the output would be

let mut g = Gen::new();
while !g.done() {
let l = g.gen(n) as usize;
let xs: Vec<_> = iter::repeat_with(|| g.gen(m)).take(l)
.collect::<_>();
}

The tricky bit I don’t quite know how to express in Haskell is that I first select the lenght of the array.

If I try to do it in Haskell, I get this

allArrays :: Int -> Int -> [[Int]]
allArrays n m = do
l <- [0..n]
f l m
where
f 0 _ = [[]]
f n m = do
x <- [0..m]
xs <- f (n - 1) m
return $ x:xs
main = print $ allArrays 2 3

That explicit recursion in f is bothering me. Is there some combinator I am missing which would allow me to write this as a single do block, sort-of how the Rust code look?

The standard way to present this style of exhaustive-enumeration code is to explicitly manipulate lists (or on-demand streams of some sort), either with explicit concatenation operations, or working in a non-determinism monad. That approach looks nice in languages have built-in support for non-determinism (Prolog and family), or languages that offer nice language constructs for user-defined effects (Haskell’s do-notation, F# computation expressions, effect handlers, etc.).

A less-standard way is to write the “direct-style” code where the gen function has exactly the same interface as usual (it just returns an integer below the bound), but then some magic happens under the hood to allow an exhaustive iteration. This is what is demonstrated in this post. I know of two ways to achieve this:

This can be done easily with languages that offer control operators (call/cc, delimited control) – in fact effect handlers are arguably also an example of this.

This can be implemented “by hand” by maintaining the control flow of the user-defined effect in some shared mutable state. Jimmy Koppel demonstrated that this is a general approach that can capture many user-defined effects, see our 2017 paper Capturing the Future by Replaying the Past. The implementation proposed in this blog post is a special case of this approach, for the non-determinism monad.

Oh fun! I was just thinking about test case generation. I haven’t grokked the bounds of this approach yet; I tried something similar once but I’m not sure it’s the same. My guess is, that this approach can’t (exhaustively and efficiently) generate all binary trees of size up to 5? Most approaches break down there.

Here’s another approach, which constructs a bijection between the values you want to generate and the natural numbers. So you ask if for “array number 347838299483”, and it quickly produces that array:
https://users.cs.northwestern.edu/~robby/pubs/papers/jfp2017-nfmf.pdf
(Importantly, the time it takes to produce “value number N” is polynomial in the number of bits of N.) This approach can’t generate binary trees fairly, though.

There’s another approach that can generate recursive data structures like binary trees. The API is that there’s a notion of “size” of the values you want to generate, and you can ask things like “tell me how many values of size 25 there are” or “give me an iterator over all values of size 25” or “give me a value of size 25 chosen uniformly at random”. For a tuple of natural numbers, the “size” would be the sum of the numbers. For a binary tree, it could be the number of nodes in the tree. Here’s a full-fledged Haskell library for this approach:
https://hackage.haskell.org/package/testing-feat
And my (independently discovered) prototype, which could be a good explanation just because it’s short:
https://github.com/justinpombrio/generators/blob/main/gen.hs

(Aside: did you ever realise that the number of ways to pick two objects out of n is equal to the sum of first n natural numbers?)

No! But I thought of an explanation. First of all, a correction: it’s the sum of the first n-1 numbers. For example, there are 10 ways to pick two things out of five, and 10 = 1 + 2 + 3 + 4. Now for the explanation: to pick two things out of five, put them in a line. How far apart are the two things you choose? There are 4 ways you could pick adjacent things (distance = 1), 3 ways to pick things with distance 2, 2 ways to pick with distance 3, or 1 way to pick with distance 4. 4 + 3 + 2 + 1 = 10.

Is this the same thing that Catalan numbers are counting? If it is, here’s the (exhaustive and efficient) equivalent code to generate all balanced parenthesis:

#[test]
fn gen_parenthesis() {
let n = 5;
let mut g = Gen::new();
while !g.done() {
let l = g.gen(n);
let mut s = String::new();
let mut t = 0;
let mut b = 0;
while t < l {
if b > 0 && g.gen(1) == 1 {
s.push(')');
b -= 1
} else {
s.push('(');
b += 1;
t += 1;
}
}
s.push_str(&")".repeat(b));
}
}

Though admittedly for a naturally recursive data a recursive solution would be nicer.

Yes, Catalan numbers count the number of binary trees of a given size. I think that’s related to but not quite the same as balanced parentheses, which are more like forests? Though there might be some bijection I’m not thinking of.

Anyhow, you’re right; your approach totally can generate all binary trees of a given size, exhaustively and efficiently and straightforwardly:

#[derive(Debug)]
enum Tree {
L,
B(Box<Tree>, Box<Tree>),
}
fn gen_tree(g: &mut Gen, size: u32) -> Tree {
if size == 0 {
return Tree::L;
}
let left_size = g.gen(size - 1);
let right_size = size - left_size - 1;
Tree::B(
Box::new(gen_tree(g, left_size)),
Box::new(gen_tree(g, right_size)),
)
}
fn main() {
let size = 3;
let mut g = Gen::new();
let mut trees = vec![];
while !g.done() {
trees.push(gen_tree(&mut g, size));
}
for tree in &trees {
println!("{:?}", tree);
}
println!("{}", trees.len());
}

What your approach can’t do is generate a uniformly random tree of a given size. For example, if you wanted to test something on all Json values of size up to 6 (which can reasonably be enumerated), plus a million uniformly random Json values of size 30 (of which there are too many to list).My approach / Haskell-feat can do that. The downside is that the code gets much more complex, and it requires bignums (because e.g. the number of Json values of size 30 might not fit in an int).

EDIT: you might immediately think it’s easy to generate a uniformly random tree. Just have each call to gen return a number uniformly random from its range. But this doesn’t work because the result of the first call to gen influences what future calls get made. For example in the line let left_size = g.gen(size - 1);, there are different numbers of trees for each possible left_size.

Nice. I’ve implemented a less generalized version of this in both Haskell and Rust fairly recently, for enumerating and testing all possible expressions in prototypes of Dawn. I’ll have to reference back to this if/when I go to expand or generalize that code.

Hm I don’t understand the motivation for doing it without recursion? Isn’t that code a lot shorter?

It’s an interesting topi,c but I found the blog post too dense with code and tests, without a clear explanation of the algorithm, at least not that I could see.

I think at least for imperative language, the code will be shorter:

#[test]
fn print_all_sets() {
let n = 3;
let mut g = Gen::new();
while !g.done() {
let s: Vec<bool> = (0..n).map(|_| g.gen(1) == 1).collect();
eprintln!("{:?}", s)
}
}
#[test]
fn print_all_sets_recursive() {
let n = 3;
let mut acc = Vec::new();
go(&mut acc, n);
fn go(acc: &mut Vec<bool>, n: usize) {
if n == 0 {
eprintln!("{:?}", acc);
} else {
acc.push(true);
go(acc, n - 1);
acc.pop();
acc.push(false);
go(acc, n - 1);
acc.pop();
}
}
}

But for me, the main benefit is the directness. I need to think how to write a recursive function which enumerates all the segments. The imperative version I can just type out.

Regarding the presentation, yeah, I know. At least for me this is still a new idea, so the genre is “presenting new material” rather than “teaching an established topic”, so the post assumes a fair amount of background and careful reading. Should’ve explicitly mentioned this at the start though.

Hm so I think the problem you are solving is not necessarily imperative vs. recursive, but abstracting the (combinatorial) iteration behind an API? Basically flattening it? The two examples don’t seem equivalent because the first uses a Gen object and the second doesn’t.

The reason I say that is because I think you can do this with Python generators and yield from recursively. I was going to try to write a demo today but I didn’t have time.

I think this is also related to “push vs. pull parsers”. In most language parsers you use the stack (recursive descent), which is analogous to the recursive case here. In other parsers, like the event-driven nginx and node.js HTTP parsers, the parser is “inverted” into a state machine, and doesn’t use the stack. So I think that is analogous to what you’re doing, although I didn’t read all the code.

Notably Go uses the stackful, “client pulls” style parser because it always starts a goroutine, which is basically like the the Python generator.

I think Rust has opposite style of iteration which is maybe why it’s harder to express. If you were willing to start a thread in Rust to generate permutations (which would probably be fine in tests), then you could just use the recursive style and hide it behind an API, no?

Both styles of code output the same thing, and both are recursive. I think the issue is more how to hide them behind an API, i.e. does the producer or the consumer “own the thread of control”?

Whether you can abstract it behind an API without threads depends on the language. Rust, Ruby, and JS favor the push style, while Python and Go favor the pull style.

It’s not too clear from this example, but for more complicated algorithms I think the pull style is nicer. The push style is more prone to bugs IMO, and for that reason I would avoid it in test code. (I think a lot of the blog post is testing the correctness of test code, which IMO is a bit of a smell.)

That reminds me of this good talk on changing the node.js parser from hand-written nginx style push to a pull style with code generation:

I guess I find it annoying that you have to “choose” and would like to just code all the algorithms one way, and have some “compiler” choose the right one. That is exactly what llparse does, and also re2c can generate both push and pull lexers, although one is more mature / favored. Some other parsing tools do it too.

edit: I neglected to mention the possibility of just generating the entire test matrix up front, i.e. putting it in a big vector. That is perfectly good for this testing use case, no need for any “concurrency” or coroutines. So you can write the generation in whatever style is easiest (no state machines) and then just hide it behind a vector.

Not sure – I’d say both your versions are a variation of print_all_sets_recursive. The way to see it is that all recursive versions use O(N) stack space, while the gen version uses O(1) stack space. Here’s the Python translation of gen: https://gist.github.com/matklad/77dd480b7b6e7d5eef93074b63b07391

I think if you mechanically replace recursion with iteration you’ll get some specialization of the Gen trick

OK but what I’m saying is: Why use the Gen style at all?

You can just write the “obvious” thing and materialize the entire output into a big vector. Then run your tests.

Or start a thread / coroutine if you really want it to be incremental.

I’m not convinced the Gen code is the “right” way to do it iteratively, it looks like it has a computational complexity problem with range(len(self.v)) in done(). In any case I find the Python is a lot clearer than Rust :) IMO Rust obscures the algorithm.

I actually thought about this type of problem a because shell has this construct:

It requires two instances of recursion to evaluate – one for the cross product and one for the “nesting”. So I was wondering how to do it without recursion. But I don’t think there’s any real problem of doing it with recursion even in production code. You can overflow the stack but that happens in every interpreted language.

I wonder if there is any relationship with this approach of something like smallcheck? They have a paper, “SmallCheck and Lazy SmallCheck: automatic exhaustive testing for small values” which might be of interest? I’m not very familiar with it though, so I could be off-the mark on this connection.

I came here to talk about SmallCheck, which was created to do exhaustive checking of inputs. Yes! This is the same thing. There are lots of fun publications in this area, though Rudy Matela wins the trophy with his PhD thesis and many libraries.

Rudy wrote leancheck for intelligent enumerative testing, fitspec to find missing properties or overspecified properties, speculate to discover properties, and extrapolate for finding

generalizedcounter-examples to a property.But wait, there’s more! If you get as excited about property based testing as I do, you will enjoy this PhD thesis.

Anyone know if there’s an equivalent library in Rust?

Let me google that for myself: https://github.com/blt/smallcheck

It’s related, but not in a fundamental way. Both the post and the paper are about exhaustively enumerating small cases. SmallCheck takes a type-driven approach, while Gen focuses on values (you don’t generate lists and then filter them to be permutations, you just directly generate permutations).

The other paper linked in the discussion, Capturing the Future by Replaying the Past, captures the fundamentals. Gen is essentially what is described in “WARM-UP: REPLAY-BASED NONDETERMINISM”.

Some proofs:

`C(n, 2)`

=`n / 2!(n-2)!`

=`n(n-1)/2`

=`sum(0, n)`

.`n(n-1)`

ways to do this, but half of them are symmetric, so it’s`n(n-1)/2`

.`n`

x`n`

rectangle, which is equivalent to picking from the lower triangle. The first row of the triangle has 0 coordinates (since they have to be unequal), the next row has 1 coordinate`(0, 1)`

, the one after has 2… so there are`0 + 1 + 2 + ...`

=`n(n-1)/2`

possible coordinates.`C(n, 2)`

is index 2 (where the first element is index 0) of the nth row of Pascal’s triangle. Index 0 is always`1`

, index 1 is always`n`

, index 2 is`n`

+ the previous row’s index 2, which will be`n-1`

. Proceed inductively.Combinatorics is fun!

That’s a neat technique. At first I thought the list monad is where the article is going, but didn’t guess that right this time. It is nice that Haskell has its solution in the standard library, though…

Heh, I indeed didn’t see the connection, thanks! Though, even having seen the connection, I am not sure how to express what I want as a list monad exactly.

Let’s look at the

`allArrays n m`

function, which returns arrays with lengths 0..n of elements 0..m. For`allArrays 2 3`

, the output would beMy version of it looks like this:

The tricky bit I don’t quite know how to express in Haskell is that I first select the

lenghtof the array.If I try to do it in Haskell, I get this

That explicit recursion in

`f`

is bothering me. Is there some combinator I am missing which would allow me to write this as a single`do`

block, sort-of how the Rust code look?I would write this as

With

`replicate : Int -> a -> [a]`

(`replicate len m`

creates a list`[m, m, m...]`

of size`len`

) and`mapM : (a -> m b) -> [a] -> m [b]`

.Right,

`mapM`

is what I was missing, thanks!You could also use

`replicateM`

:The standard way to present this style of exhaustive-enumeration code is to explicitly manipulate lists (or on-demand streams of some sort), either with explicit concatenation operations, or working in a non-determinism monad. That approach looks nice in languages have built-in support for non-determinism (Prolog and family), or languages that offer nice language constructs for user-defined effects (Haskell’s do-notation, F# computation expressions, effect handlers, etc.).

A less-standard way is to write the “direct-style” code where the

`gen`

function has exactly the same interface as usual (it just returns an integer below the bound), but then some magic happens under the hood to allow an exhaustive iteration. This is what is demonstrated in this post. I know of two ways to achieve this:Oh fun! I was just thinking about test case generation. I haven’t grokked the bounds of this approach yet; I tried something similar once but I’m not sure it’s the same. My guess is, that this approach can’t (exhaustively and efficiently) generate all binary trees of size up to 5? Most approaches break down there.

Here’s another approach, which constructs a bijection between the values you want to generate and the natural numbers. So you ask if for “array number 347838299483”, and it quickly produces that array: https://users.cs.northwestern.edu/~robby/pubs/papers/jfp2017-nfmf.pdf (Importantly, the time it takes to produce “value number N” is polynomial in the number of

bitsof N.) This approach can’t generate binary trees fairly, though.There’s another approach that can generate recursive data structures like binary trees. The API is that there’s a notion of “size” of the values you want to generate, and you can ask things like “tell me how many values of size 25 there are” or “give me an iterator over all values of size 25” or “give me a value of size 25 chosen uniformly at random”. For a tuple of natural numbers, the “size” would be the sum of the numbers. For a binary tree, it could be the number of nodes in the tree. Here’s a full-fledged Haskell library for this approach: https://hackage.haskell.org/package/testing-feat And my (independently discovered) prototype, which could be a good explanation just because it’s short: https://github.com/justinpombrio/generators/blob/main/gen.hs

No! But I thought of an explanation. First of all, a correction: it’s the sum of the first n-1 numbers. For example, there are 10 ways to pick two things out of five, and 10 = 1 + 2 + 3 + 4. Now for the explanation: to pick two things out of five, put them in a line. How far apart are the two things you choose? There are 4 ways you could pick adjacent things (distance = 1), 3 ways to pick things with distance 2, 2 ways to pick with distance 3, or 1 way to pick with distance 4. 4 + 3 + 2 + 1 = 10.

Is this the same thing that Catalan numbers are counting? If it is, here’s the (exhaustive and efficient) equivalent code to generate all balanced parenthesis:

Though admittedly for a naturally recursive data a recursive solution would be nicer.

Yes, Catalan numbers count the number of binary trees of a given size. I think that’s related to but not quite the same as balanced parentheses, which are more like forests? Though there might be some bijection I’m not thinking of.

Anyhow, you’re right; your approach totally can generate all binary trees of a given size, exhaustively and efficiently and straightforwardly:

What your approach can’t do is generate a uniformly random tree of a given size. For example, if you wanted to test something on all Json values of size up to 6 (which can reasonably be enumerated), plus a million uniformly random Json values of size 30 (of which there are too many to list).My approach / Haskell-feat can do that. The downside is that the code gets much more complex, and it requires bignums (because e.g. the number of Json values of size 30 might not fit in an int).

EDIT: you might immediately think it’s easy to generate a uniformly random tree. Just have each call to

`gen`

return a number uniformly random from its range. But this doesn’t work because the result of the first call to`gen`

influences what future calls get made. For example in the line`let left_size = g.gen(size - 1);`

, there are different numbers of trees for each possible`left_size`

.Nice. I’ve implemented a less generalized version of this in both Haskell and Rust fairly recently, for enumerating and testing all possible expressions in prototypes of Dawn. I’ll have to reference back to this if/when I go to expand or generalize that code.

https://pkg.go.dev/github.com/muesli/combinator is a similar library for Go. Strongly recommended if you want both shorter tests and better test coverage.

Hm I don’t understand the motivation for doing it without recursion? Isn’t that code a lot shorter?

It’s an interesting topi,c but I found the blog post too dense with code and tests, without a clear explanation of the algorithm, at least not that I could see.

I think at least for imperative language, the code will be shorter:

But for me, the main benefit is the

directness. I need to think how to write a recursive function which enumerates all the segments. The imperative version I can just type out.Regarding the presentation, yeah, I know. At least for me this is still a new idea, so the genre is “presenting new material” rather than “teaching an established topic”, so the post assumes a fair amount of background and careful reading. Should’ve explicitly mentioned this at the start though.

Hm so I think the problem you are solving is not necessarily imperative vs. recursive, but abstracting the (combinatorial) iteration behind an API? Basically flattening it? The two examples don’t seem equivalent because the first uses a Gen object and the second doesn’t.

The reason I say that is because I think you can do this with Python generators and

`yield from`

recursively. I was going to try to write a demo today but I didn’t have time.I think this is also related to “push vs. pull parsers”. In most language parsers you use the stack (recursive descent), which is analogous to the recursive case here. In other parsers, like the event-driven nginx and node.js HTTP parsers, the parser is “inverted” into a state machine, and doesn’t use the stack. So I think that is analogous to what you’re doing, although I didn’t read all the code.

Notably Go uses the stackful, “client pulls” style parser because it always starts a goroutine, which is basically like the the Python generator.

I think Rust has opposite style of iteration which is maybe why it’s harder to express. If you were willing to start a thread in Rust to generate permutations (which would probably be fine in tests), then you could just use the recursive style and hide it behind an API, no?

OK I transcribed the code in this comment and I think it illustrates what I’m getting at:

https://github.com/oilshell/blog-code/blob/master/push-pull/powerset.py

Both styles of code output the same thing, and both are recursive. I think the issue is more how to hide them behind an API, i.e. does the producer or the consumer “own the thread of control”?

Whether you can abstract it behind an API without threads depends on the language. Rust, Ruby, and JS favor the push style, while Python and Go favor the pull style.

Bob Nystrom calls it “internal vs external iterators”: https://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/

Also related: https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

It’s not too clear from this example, but for more complicated algorithms I think the pull style is nicer. The push style is more prone to bugs IMO, and for that reason I would avoid it in test code. (I think a lot of the blog post is testing the correctness of test code, which IMO is a bit of a smell.)

That reminds me of this good talk on changing the node.js parser from hand-written nginx style push to a pull style with code generation:

https://lobste.rs/s/76akkn/llhttp_http_1_1_parser_for_node_js_by_fedor

my comment mentioning it: https://lobste.rs/s/rzhxyk/plain_text_protocols#c_gnp4fm

Also reminds me of the discussion we had about whether Pratt Parsing and Shunting Yard are the same algorithm :) https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html

I guess I find it annoying that you have to “choose” and would like to just code all the algorithms one way, and have some “compiler” choose the right one. That is exactly what llparse does, and also re2c can generate both push and pull lexers, although one is more mature / favored. Some other parsing tools do it too.

edit: I neglected to mention the possibility of just generating the entire test matrix up front, i.e. putting it in a big vector. That is perfectly good for this testing use case, no need for any “concurrency” or coroutines. So you can write the generation in whatever style is easiest (no state machines) and then just hide it behind a vector.

Not sure – I’d say both your versions are a variation of

`print_all_sets_recursive`

. The way to see it is that all recursive versions use O(N) stack space, while the gen version uses O(1) stack space. Here’s the Python translation of gen: https://gist.github.com/matklad/77dd480b7b6e7d5eef93074b63b07391I think if you mechanically replace recursion with iteration you’ll get some specialization of the

`Gen`

trickOK but what I’m saying is: Why use the

`Gen`

style at all?You can just write the “obvious” thing and materialize the entire output into a big vector. Then run your tests.

Or start a thread / coroutine if you really want it to be incremental.

I’m not convinced the

`Gen`

code is the “right” way to do it iteratively, it looks like it has a computational complexity problem with`range(len(self.v))`

in`done()`

. In any case I find the Python is a lot clearer than Rust :) IMO Rust obscures the algorithm.I actually thought about this type of problem a because shell has this construct:

It requires two instances of recursion to evaluate – one for the cross product and one for the “nesting”. So I was wondering how to do it without recursion. But I don’t think there’s any real problem of doing it with recursion even in production code. You can overflow the stack but that happens in every interpreted language.