RFC: Visitor / subexr_children cleanup?

[awf]

AL: There is a function subexps_no_binds(e : Expr) -> List[Expr] that parallels the ExprWithPath method all_subexps(self) -> List[ExprWithPath. Both seem useful (and subexps_no_binds is defined in terms of the other), so it seems they should be named more consistently. Some possibilities to kick off discussion:

AF: I must admit I'm still kinda hoping these will go away. They currently save some duplication in AbstractMatcher, but I wonder if that might not be better as a visitor anyway?

Currently subexps_no_binds is used in:

• alpha-equivalence for Const, Call, If, Assert;
• hashing for Call, If, Assert
• find_template_subst for Const, Call, If, Assert

Originally posted by @acl33 in https://github.com/microsoft/knossos-ksc/issues/842#issuecomment-852852472

[awf]

So I think my proposal is something like this. Change existing code like this (from the hashing example).

I do see that it is more code, and that it means that hashing may have a different enumeration of e.g. the children of an "if" than matching, but actually I think it is reasonable for every traversal to ask itself "do I need to worry about the order of application of If"?

And if new nodes were to be added to the AST, I would much prefer to get a NotImplementedError than to ask "where are these children used? who needs to know about ordering?"

[acl33]

The "duplication" in the (single) example you give is annoying to have to write, but I'm more worried about the sheer number of places which depend upon knowledge of the Expr representation. I feel it would be good to minimise the number of places which would need to change were a new Expr type added. The idea of subexps_no_binds is not that everything has to use it; but that many callers would want to, and they might well change in the same way. If some new Expr-node makes the definition of "no_binds" unclear, then rename subexps_no_binds and every callsite fails...and many can be patched up by propagating said rename.

who needs to know about ordering?

I'm not sure whether you mean

• generally about the order of fields/members in each Expr subclass (where it seems in many cases any order is fine so long as its consistent; cases which really depend upon such should indeed implement their own, but most do not)
• specifically about If condition being executed before t_body / f_body - in which case it would be good for the Expr to encode this information in a universal language (say, Lam means it may not be executed eagerly) - but less drastically: we must be able to have utility functions/classes/somethings (maybe like ExprVisitor) that express different but common themes like:
  • "this analysis needs to treat binding specially" (but doesn't care about much/anything else, e.g. execution order)
  • "this analysis cares (only) about execution-order" (so special treatment for If, Lam, maybe even Calls with argument types involving Lam) but not about binding (say)
  • any others that may come up

subexps_no_binds is roughly aiming at the first of these; to me that seems reasonable, but I'm open to ways of restructuring. For example, one might write a variation on the present ExprVisitor/ExprTransformer framework:

T = TypeVar()
class ExprVisitorWithDefault(ABC, Generic[T]):
   ....
   @abstractmethod
   def visit_default(e : Expr, child_results: List[T], *args, **kwargs) -> T:
       """ Subclasses must override; or raise if all cases are overridden and no default is required """
   def visit_call(self, c: Call, *args, **kwargs) -> T:
      return self.visit_default(c, [self.visit(a, *args, **kwargs) for a in c.args], *args, **kwargs)
   def visit_if(self, if_node: If, *args, **kwargs) -> T:
      return self.visit_default(if_node, [self.visit(if_node.cond, *args, **kwargs), self.visit(if_node.t_body, *args, **kwargs), self.visit(if_node.f_body, *args, **kwargs)], *args, **kwargs)
   ....visit_lam, visit_let, visit_assert, visit_var, visit_const all calling visit_default similarly....

(And that visitor class could even have a flag as to whether to include binding occurrences, decl Vars, etc.)