Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    anyway, I'm still trying to get some details on how ES is more than just some data structure concepts applied to a complete search-like process (e.g. the kind that miniKanren uses)
    for instance, if one saved the states produced by a stream of miniKanren rewrite goals would the result have the same "information content" as the data structures produced by the ES procedure under the same rewrites (and on the same graphs, of course)?
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    :point_up: Edit: anyway, I'm still trying to get some details on how ES is more than just some data structure concepts (I know it's more, but I'm talking about only one part of it) applied to a complete search-like process (e.g. the kind that miniKanren uses)
    remilouf
    @remilouf:matrix.org
    [m]
    Funny that the first example of Term Rewriting and all that is symbolic differentiation 😅
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    you know, we could start experimenting with optimization/rewrite paths right now
    it's fairly easy to construct a Rewriter that loops through all the Apply nodes and runs a set of rewrites on them
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    if you map each node to the results of each rewrite, you can select the "best" single-step rewrite for nodes according to some ordering
    once a "best" rewrite step is chosen for a node, the graph with that node changed comprises a new set of nodes to iterate upon
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    basically, many paths through the space of all possible graph rewrites are fairly easy to construct
    I still haven't finished reading through all of the Equality Saturation paper, but it sounds like this is what's overall being done (via the use of their specific IR and some similar maps)
    1 reply
    in other words, we can probably experiment with some greedy search approaches and get the same results, or better
    2 replies
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    the technical requirements for us involve some changes to how the rewriting is done
    specifically, we'll need to stop updating Apply nodes in-place (i.e. in FunctionGraph.replace)
    this is really just an efficiency concern, though
    because one could always clone the nodes before applying each rewrite, but that's a waste when a rewrite doesn't actually apply to a node
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    the idea is that one needs to efficiently produce new graphs representing the application of a single rewrite
    1 reply
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    if one pictures graphs as toposorted lists of Apply nodes, then we're just talking about walking through the space of single-element/node substitutions in a list
    just cache the results of each (rewrite, node) pair, and it should be pretty cheap to walk around these spaces (i.e. produce a bunch of different graphs to order/"weigh")
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    a specific thing to experiment with is an ordering that might produce canonical forms in fewer steps
    assuming confluence (which probably isn't reasonable under all of our current rewrites), one can take an "experimental" approach and try to find the best ordering of canonicalizing rewrites
    (i.e. all of our rewrites with the tag "canonicalize")
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    the test data could consist of randomly generated graphs
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    then simply devise a walk through the space of graph rewrites--as described above--that applies a reduction-like ordering (e.g. prioritize rewrites that reduce the number of nodes)
    perform each walk until the graph converges to its--hopefully unique--normal form (again, a strong assumption here)
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    looking at the orders of the rewrites resulting from many runs could reveal some things about a good single order to use by default in Aesara
    (FYI: all this gets fairly close to rewrite completion, which is essentially like a direct, non-experimental approach that works on the syntax of the rewrites themselves)
    anyway, the point is that we already have a suitable IR and the tooling necessary to perform higher-level optimizations/rewrites
    remilouf
    @remilouf:matrix.org
    [m]
    Is there a set of rules that we know are confluent to test our algorithm ?
    remilouf
    @remilouf:matrix.org
    [m]
    Actually I wouldn’t be surprised if we could find all possible rewrites and choose the best in most cases. Would need to read the Tensat paper more carefully.
    Btw I think adding the hypergraph structure needed to build egraphs from aesara graphs shouldn’t require too much work.
    remilouf
    @remilouf:matrix.org
    [m]
    This paper talks a bit about the trade-offs in a situation similar to aesara’s : https://arxiv.org/abs/2101.01332
    They benchmark greedy extraction vs ILP-based extraction. Also, they clearly need to set a max number of exploration cycles.
    remilouf
    @remilouf:matrix.org
    [m]
    How are graph optimizations performed in aesara right now? Sequentially?
    1 reply
    remilouf
    @remilouf:matrix.org
    [m]
    btw I was talking about NUTS sampler the other day because I have the vague intuition that a similar (albeit simpler) data structure can be used to build the "best" sampler out of multiple possibilities.
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    remilouf
    @remilouf:matrix.org
    [m]
    Oh wow Tim Gowers
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    in case anyone missed this: aesara-devs/aesara#938
    this is a really cool idea that could improve our interactive graph debugging situation
    zoj613
    @zoj613:matrix.org
    [m]
    Peridot: A functional language based on two-level type theory - https://github.com/eashanhatti/peridot
    Stumbled across this earlier.
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    you can do those kinds of things in a language like Haskell
    well, more easily perhaps
    Brandon T. Willard
    @brandonwillard
    @/all meeting in progress
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    here's an example of something we can do now: https://github.com/aesara-devs/aemcmc/issues/4#issuecomment-1124325830
    cool examples like this would make for some good showcase-able material
    also, if we get started on this general direction of work, it would start to explicitly motivate things like Equality Saturation
    remilouf
    @remilouf:matrix.org
    [m]
    We can work on this once #29 is merged !
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    Ricardo Vieira, after looking over those MergeFeature/MergeOptimizer updates, I'm brought back to a complete reassessment of the merging process in Aesara
    brandonwillard
    @brandonwillard:matrix.org
    [m]
    remilouf: you mentioned something about an AeHMC issue you discovered/fixed; is there a PR for that?