teorth / equational_theories

A project to map out the relations between different equational theories of Magmas.
https://teorth.github.io/equational_theories/
Apache License 2.0
212 stars 51 forks source link

[DO NOT MERGE] Deep-embed graph #45

Open alxest opened 1 month ago

alxest commented 1 month ago

Hi all! Thank you for initiating this extremely exciting project. This PR is my attempt to simplify & give more principled approach to maintain the implication graph.

[Syntactic data] Each axiom (equation) is now has a concrete, syntactic term, named Equation type. A graph, Graph type, is defined as Equation -> Equation -> Status where Status denotes the current state for the corresponding edge. For example, a concrete instance for the subgraph of our interest is given as a term subgraph: Graph.

[Semantic interpretation] The validity of this graph object is enforced with Graph.valid definition - e.g., subgraph_valid would be the final theorem for the subgraph. The Graph.valid requires corresponding semantic proof for each syntactic edges. Notably, Edge is defined with typeclass and has few benefits below.

Benefits are as follows:

One caveat would be performance scalability issue, especially for the final theorem (like subgraph_valid). If typeclass resolution mechanism takes O(n) (where n is the number of instances), it would take prohibitively long. If it takes O(log n), it should (I think) compile in time.

If you find this useful, I can make it a mergeable state quickly.

teorth commented 1 month ago

I like this idea but it needs to be coordinated with #36 , perhaps one can discuss it on the Lean Zulip thread https://leanprover.zulipchat.com/#narrow/stream/458659-Equational/topic/Syntax ?