search

drym-org / qi

An embeddable flow-oriented language.
58 stars 12 forks source link

Review premature termination of multi-level optimization #154

Closed countvajhula closed 3 months ago

countvajhula commented 6 months ago

See this commented-out, failing test in normalize.rkt:

    ;; TODO: this test reveals a case that should be
    ;; rewritten but isn't. Currently, once there is a
    ;; match at one level during tree traversal
    ;; (in find-and-map), we do not traverse the expression
    ;; further.
    ;; (test-normalize "multiple levels of normalization"
    ;;                 #'(~> (>< (~> f)))
    ;;                 #'(>< f))
benknoble commented 6 months ago

Is this somehow related to the "repeat 'til fixed-point or not" discussion we had once? I remember a diff somewhere that affected fix-points but I can't recall what or where.

countvajhula commented 6 months ago

I think that would be more related to #161 , but may be relevant here as well. This one is more about the algorithm we use in traversing the input syntax to apply rewrite rules, i.e. find-and-map/qi. When it finds a match, it applies the rewrite rule (e.g. normalize, to a fixed point) and then proceeds to the next node in the tree. It doesn't continue to traverse the rewritten node. I'm not sure if this was intentional, or just a case we hadn't handled yet. In the example here, the toplevel thread is collapsed, and then it doesn't see that the innermost thread could also be collapsed since it doesn't enter the form.

Re: the diff, at one point, we changed it so that only the normalization pass rewrites to a fixed point, while deforestation just does a one-shot rewrite. That may be what you're thinking of.