What are these? Do they support rewrite rules on programs?

I meant them in the context of your last paragraph; they are tools that optimize Python for performance. Cython is a compiled superset of Python, while numba is a JIT compiler that works on a subset of Python.

I must admit I don't quite understand what rewrite rules actually are; are they akin to macros?

Macros have local scope. They are evaluated to program text only once, probably, lazily.

Rewrite rules fire when compiler encounters a chance for them to fire, at any point of (optimizing) program transformation.

Due to this fact, rewrite rules are not local - compiler can transform the inner structure of a program changing the locality of program statements.

    bs = map g xs
    ... many other lines of program text not reassigning bs
    as = map f bs

still can be transformed into "as = map (f . g) xs" by rule "map f (map g xs) => map (f . g) xs" due to substitution.

So they -- like macros -- rewrite the source code into something different before the compilation, but -- unlike macros -- only do that under certain circumstances. Would this be a sensible approximation? I'm just trying to understand what they're doing, not why or how. Thank you!