[ARCH] Enforce Normalizer Invariance

[tqchen]

Previously we evaded the normalizer invariance so that we can get vertical working. In some cases when type cannot be deduced, the normalizer simply return Type(null). As we start to develop things further it is important to hammer on the base infra and enforce the following invariance:

• After Normalize: an Expr always have checked_type (with the exception of Op, which does not need to have checked_type for now)
• After Normalize: an Expr whose can have shape(of TensorType of Tuple of all Tensors) must have shape_(in worst case RuntimeDepShape)

This could mean that we need to add extra registrations to the code.

Action Items

• Add ICHECK to ensure the invariance hold in normalize function
• Fix the test cases and existing impl to ensure the invariance.
• WellForm check to ensure the invariance hold

[slyubomirsky]

Could we make a list of expressions for which we define shape_? Per the draft of the spec, I would be in favor of defining shape rules in more cases to make more information available at compile time and require fewer dynamic checks. For example, suppose we have a tuple where some members are tensors and others are not. I would prefer for that tuple to have a shape_ that describes the shapes of the tensor members so that we would not have to insert dynamic checks for those tensors if they're referenced.

It might be worth defining when shape inference is supposed to happen. For example, if we apply some transformations to the program (like constant folding or function inlining), we might be able to infer more specific shapes compared to running shape inference on the immediate input program. There would be a tradeoff between predictability and precision.

[tqchen]

thanks @slyubomirsky . the note mainly applies for Type , agree it is good to clarify shape as well.

[tqchen]

#287 thanks to @YuchenJin