Generate random Tensor (and Boolean and Integral) programs

[Mikolaj]

@tomsmeding said:

I wonder if what you need here is generating random programs :p

And indeed I need it. Dimensions only 1, 2 or 3, ranks up to 5, I guess. Maybe 7. Not too high so that the programs don't take forever to vectorize and forever to AD.

Probably just QuickCheck generators? We already have them for orthotope tensors. I guess it's enough to generate Ast programs, which are terms, not Tensor programs, which can desugar and instantiate to terms.

The difficulty I can see at this point is generating correctly ranked and correctly shaped programs. E.g., in tfromList [t, u], t and u should have the same shape.

We could go top-down and first generate a shape and then a constructor that can have that shape, e.g., AstIndex and then, recursively, that would partially determine the shapes of subterms and sometimes we'd have to generate more shapes, within constraints of the outer shape. This sounds complex. We'd surely need unification. Probably a fully fledges shape reconstruction for Ast terms with holes (not the current simplistic shape-checking of concrete Ast terms).

Another top-down methods is to generate a constructor and only then a shape that the constructor can possibly have, etc. Similarly complex.

A bottom-up methods seems hopless: we generate t and u, they have totally different shapes, none of the constructors can take t and u at once, we give up.

Is it know that randomly generating well-typed expressions is as hard as reconstruction of the most general type (or something close) for the expressions?