Take a look here to get a feel of what rewrite rules are: https://downloads.haskell.org/~ghc/7.0.1/docs/html/users_gui...

Haskell has two very nice libraries, bytestring and vector which use rewrite rules to have performance comparable to C code.

Operations on dictionaries with default values implemented using inheritance from dictionary. This means that instead of just having conditional expression on the right side I have a call to virtual function and there is an expression on the right side of assignment or return statement.

Most of OO virtual machines can JIT things like these into efficient machine code, by specializing. The same is also quite possible with bytecode like in CPython - by optimization in the compiler or by introduction of rewrite rules like above for library implementors to specify rules that apply to any (transformed) user code.

So something like Cython or numba?

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!