There are at least two potential points of controversy:
I've made the cse_bind rule into a form that can be written in ksc syntax, namely:
(let (x rhs) (let (y rhs) body)) ===> (let (x rhs) (let (y x) body))
This leaves a pointless assignment, that can be cleaned up by subsequently applying "inline_let" (the variant that inlines all occurrences of a let-bound variable together, realized here, vs "inline_var" that inlines a single occurrence). It seems to me that it's good to have exactly one rule that does substitution inside an expression, and inline_let does that. (In RLO, the cse_bind rule included the trailing inline_let step.)
The PR includes a workaround for type-propagation within "lets" in the presence of Type.Any. It'd be good to keep all knowledge of how types propagate in one place (type_propagate.py), but given we do not want to repropagate the entire O(n) expression after rewriting only O(log n) of it, this would take some additional work, which I'm still considering. Since Type.Any only occurs within rules, maybe putting this logic in the rewriter is not so bad.
This one should be easy to resolve, but are we happy with RLO's names "new_bind" and "cse_bind" or should these be "new_let" and "cse_let" (or something else) ?
I've also made this PR follow #953, both as it adds new rules inside the rewrites_ast.py file created by that PR, and as this PR includes a test that a complete Common Subexp Elimination optimization can be performed (via a series of rewrites including said lifting rules).
(let (x rhs) (let (y rhs) body))===>(let (x rhs) (let (y x) body))This leaves a pointless assignment, that can be cleaned up by subsequently applying "inline_let" (the variant that inlines all occurrences of a let-bound variable together, realized here, vs "inline_var" that inlines a single occurrence). It seems to me that it's good to have exactly one rule that does substitution inside an expression, and inline_let does that. (In RLO, the cse_bind rule included the trailing inline_let step.)