5 ms·

That's super fascinating! I have been studying the graph isomorphism problem for a while now since I actually needed it for a real-world use case, so I'm really

That's super fascinating! I have been studying the graph isomorphism problem for a while now since I actually needed it for a real-world use case, so I'm really psyched to hear that there is a good solution now. About our use case: We developed an algorithm for creating "semantic diffs" between two source code trees. Starting from a graphical (AST) representation of the source code of an entire software project, such a diff would basically tell you how you can transform one tree into the other using a range of edit operations (e.g. insert, delete, copy, paste, modify). The advantage compared to line-by-line diffs is that the latter work only on the text-level (i.e. "this line has been removed, this other line has been added"), whereas the former can actually tell you what changed on a semantic level (i.e. "this argument was inserted into this function and this variable name was changed"). For big projects, this is quite a computational challenge and can (could) only be solved using approximations and shortcuts. Having a polynomial-time algorithm for this would therefore be a huge deal. I hope that the proof will soon lead to practical implementations of the algorithm.

deleted 11y ago
[deleted]
espes 11y ago
Why is general graph isomorphism needed for that?
- ThePhysicist 11y ago
  Probably it isn't, but if there was a general-purpose algorithm that I could just use without doing any hand-crafted optimizations that would be a huge win. As you said, finding a good solution is usually possible but it requires applying a lot of (reasonable) approximations and shortcuts.
  - espes 11y ago
    But it sounds like your model isn't a general graph? DAG and tree isomorphism is in P (and pretty straightforward), and so is tree edit distance...
    - ThePhysicist 11y ago
      ASTs are DAGs indeed, but as soon as you add semantic information to the mix the graph usually becomes cyclic.
Ar-Curunir 11y ago
Most real life instances of Graph Isomorphism are easily solved in polynomial time though...
- johncolanduoni 11y ago
  Yes, they discussed in the comment section of the post that when theoretical computer science researchers have tried to find actual graphs which existing algorithms do not handle well, they had difficulties finding them outside of some very specific (and vanishingly small) classes.
bmh100 11y ago
Is this the sort of technology that could theoretically enable reasonably good, automated conversion between programming languages?
- ThePhysicist 11y ago
  I would say it's part of it but by far the only thing that you'd need to solve for this, in my opinion.
- obastani 11y ago
  Not really, it's not hard to write a compiler to convert between different programming languages. The challenge is translating between the different semantics of different programming languages (e.g., object-oriented vs. functional, dynamically typed vs. statically typed, etc.).
est 11y ago
reminds me of this https://github.com/yinwang0/ydiff https://github.com/yinwang0/ydiff
- ThePhysicist 11y ago
  That's interesting, thanks for sharing! Lisp is probably a natural fit for this kind of diffing since it is literally written as a syntax tree, so it is kind of a natural representation of the language.
mafribe 11y ago
Have you seen the paper "Editing Functional Programs Without Breaking Them" by Amsden et al. [1]? It does something similar. It allows you to transform any program (in an idealised typed programming languages) into any other using a small collection of transformation operations. The highlight is that this is possible without compormising typability. This is also related to patch theory [2, 3, 4, 5, 6], a theory that seeks mathematise version control systems like, and to provide provably correct merging algorithms. Patch theory arose in the context of the DARCS system. [7] connects patch theory with homotopy type theory. [1] https://ifl2014.github.io/submissions/ifl2014_submission_32.pdf https://ifl2014.github.io/submissions/ifl2014_submission_32.... [2] J. Dagit, Type-Correct Changes - A Safe Approach to Version Control Implementation. [3] G. Sittampalam, Some properties of darcs patch theory. [4] I. Lynagh, Camp Patch Theory. [5] D. Roundy, Implementing the darcs patch formalism ... and verifying it. [6] J. Jacobson, A Formalization Of Darcs Patch Theory Using Inverse Semigroups. [7] C. Angiuli, E. Morehouse, D. R. Licata, R. Harper, Homotopical Patch Theory.
caf 11y ago
Tree Isomorphism is a much easier problem than general Graph Isomorphism.
deleted 11y ago
[deleted]

deleted 11y ago

[deleted]

espes 11y ago

Why is general graph isomorphism needed for that?

ThePhysicist 11y ago
Probably it isn't, but if there was a general-purpose algorithm that I could just use without doing any hand-crafted optimizations that would be a huge win. As you said, finding a good solution is usually possible but it requires applying a lot of (reasonable) approximations and shortcuts.
- espes 11y ago
  But it sounds like your model isn't a general graph? DAG and tree isomorphism is in P (and pretty straightforward), and so is tree edit distance...
  - ThePhysicist 11y ago
    ASTs are DAGs indeed, but as soon as you add semantic information to the mix the graph usually becomes cyclic.

Ar-Curunir 11y ago

Most real life instances of Graph Isomorphism are easily solved in polynomial time though...

johncolanduoni 11y ago
Yes, they discussed in the comment section of the post that when theoretical computer science researchers have tried to find actual graphs which existing algorithms do not handle well, they had difficulties finding them outside of some very specific (and vanishingly small) classes.

bmh100 11y ago

Is this the sort of technology that could theoretically enable reasonably good, automated conversion between programming languages?

ThePhysicist 11y ago
I would say it's part of it but by far the only thing that you'd need to solve for this, in my opinion.
obastani 11y ago
Not really, it's not hard to write a compiler to convert between different programming languages. The challenge is translating between the different semantics of different programming languages (e.g., object-oriented vs. functional, dynamically typed vs. statically typed, etc.).

est 11y ago

reminds me of this https://github.com/yinwang0/ydiff https://github.com/yinwang0/ydiff

ThePhysicist 11y ago
That's interesting, thanks for sharing! Lisp is probably a natural fit for this kind of diffing since it is literally written as a syntax tree, so it is kind of a natural representation of the language.

mafribe 11y ago

Have you seen the paper "Editing Functional Programs Without Breaking Them" by Amsden et al. [1]? It does something similar. It allows you to transform any program (in an idealised typed programming languages) into any other using a small collection of transformation operations. The highlight is that this is possible without compormising typability. This is also related to patch theory [2, 3, 4, 5, 6], a theory that seeks mathematise version control systems like, and to provide provably correct merging algorithms. Patch theory arose in the context of the DARCS system. [7] connects patch theory with homotopy type theory. [1] https://ifl2014.github.io/submissions/ifl2014_submission_32.pdf https://ifl2014.github.io/submissions/ifl2014_submission_32.... [2] J. Dagit, Type-Correct Changes - A Safe Approach to Version Control Implementation. [3] G. Sittampalam, Some properties of darcs patch theory. [4] I. Lynagh, Camp Patch Theory. [5] D. Roundy, Implementing the darcs patch formalism ... and verifying it. [6] J. Jacobson, A Formalization Of Darcs Patch Theory Using Inverse Semigroups. [7] C. Angiuli, E. Morehouse, D. R. Licata, R. Harper, Homotopical Patch Theory.

caf 11y ago

Tree Isomorphism is a much easier problem than general Graph Isomorphism.

deleted 11y ago

[deleted]