normalization-optimization.md

Normalization & Optimization

First, normalization and optimization are two different things. Normalization, which has various sub-definitions, depending on the exact properties involves approaching some “normal form” that reduces the variety of the structure at hand. It can often pessimize a structure, but does so in a predictable way. A normalized structure is easier to apply other operations to, because it is restricted in its form.

Optimization, on the other hand, denormalizes in exchange for better performance. But an optimized structure is harder to reason about and make changes to.

So, the general approach is to normalize a structure, apply whatever transformations are appropriate, then optimize the structure. If you are converting between structures, usually only the final structure would have optimization applied, but normalization of each structure can be useful.

Defining Transformations

Often, many transformations need to be applied. There are various approaches of how to implement them (see Efficient Nanopass Compilers using Cats and Matryoshka for some examples). In the nanopass approach, they can be made extremely fine-grained, so what is a reasonable level of granularity?

I think we can let the types guide us.

Assuming we’re dealing with a coproduct of pattern functors, we’ll end up with types like the following:

|component| context needed              |
|  scope  |   no   |         yes        |
|---------|--------|--------------------|
|  within | F ~> F | F[T[G]] ~> F[T[G]] |
|  across | F ~> G | F[T[G]] ~> G[T[G]] |

“within” indicates transformations that operate within a single coproduct component, whereas “across” indicates transformations that may return a result in a different component. “context needed” indicates whether we need to look at the inputs in order to apply the transformation.

Transformations involving G should be partitioned by the exact context necessary. E.g., (implicit F: F :<: G, OC: OtherComponent :<: G) would be distinct from (implicit AC: AnotherComponent :<: G).[†]

In general, these transformations should also return the result in Option, to indicate an unchanged value. This allows repeated application until the result is in normal form.

[†]: This part is still in flux. When using a type class for a transformation, each instance can set its own constraints on the context, but there may be different options depending on exactly what coproduct it’s being applied to. To some extent, this may be solvable by ordered instances (i.e., when the contexts are strictly orderable, but not when they are overlapping).

I see a couple points to make regarding the order in which normalizations and optimizations are applied.

I see normalization not as a single transformation, but as many fine-grained transformations, each with some optimizations in mind. Meaning, we normalize in some particular way, because it makes it easier to run optimations X, Y, and Z. Because of that relationship, we necessarily need to run that particular normalization before its related optimizations.

Now, optimizations (and normalizations) may also need to be applied in certain orders. I would love to somehow encode these requirements in ordering in the types, but I'm not sure how to do that. Maybe we can have a single "within" normalization followed by the "within" optimizations for each component. And then maybe the ordering of the "within" blocks wouldn't matter. And it's only the ordering of the "across" blocks that matters? That would be nice!

Also, as we add more optimizations, I wouldn't be surprised if we hit more infinite loops like the one we saw recently, where we optimize recursively, oscillating forever between two different forms. So, a design with good debugging tools in mind will be important, which, at least for me, means the ability to easily print out the qscript at various stages in the transformation.

So, to be clear, with QScript, we should have some “normal form” that running all normalizations on repeatedly will eventually stabilize. I don’t doubt we’ll run into things where we’ll have a bug that causes reapplying the same case over and over again. But we should basically try to stay in normal form (i.e., all of our transformations should look something like .transCata(doTransformation >>> normalize), as mentioned in #qscript today). Optimizations are currently mixed in with our normalizations, but should be separated out, and only applied after we’re done doing any other QScript work (among other reasons, because the difference between normalization and optimization can lead to those infinite cycles).

Usually it doesn’t matter what order you run different normalization steps in (other than for performance, where we might be able to normalize with fewer passes if we think about how to order them). There are cases where certain normalizations must be applied before a more general normalization pass, and we can make that explicit if we run into any.

As far as debugging. I have resurrected Scalaz’s IdOps#<| as DebugOps#<|, and that allows us to do things like .transCata(someTransformation(_) <| println) that prints out each node as it goes. And we could also insert it into applyAll between the steps.

What I’ve had in mind to do for a while is something with Writer that we can give a List of transformations to and it returns (in the Writer) a list of the printed representations of each intermediate stage, even though we ran them all in one pass. We should be able to do this without actually decomposing something like applyAll into multiple passes.

BTW, I have simplified applyAll a bit, but even so, we do 8 distinct transformations there in a single pass, which I think is pretty neat.