Kann die Homotopietypentheorie verwendet werden, um effizientere Algorithmen für effizientere Datendarstellungen von weniger effizienten abzuleiten?

Question

Ich habe gelesen hier dass Compiler in HoTT weniger effiziente Darstellungen von Daten gegen effizientere austauschen könnten und ich mich frage, ob meine Interpretation dieser Aussage richtig ist.

Angenommen, wir haben zwei verschiedene Möglichkeiten, die natürlichen Zahlen darzustellen, unär (Null und Nachfolger) und binär.Hier ist eine Funktion, die die Ebenheit der früheren Darstellung überprüft:

even : UnaryNat -> Bool
even zero = true
even (succ zero) = false
even (succ (succ n)) = even n

Wenn wir dann einen Isomorphismus zwischen der unären und der binären Darstellung haben, erhalten wir trivialerweise eine Gleichheitsfunktion für die binäre Darstellung "kostenlos", indem wir einfach eine gegebene binäre natürliche Zahl in eine unäre umwandeln, indem wir die anwenden even funktion und konvertiert das Ergebnis zurück in die Binärdarstellung.Offensichtlich ist das nicht sehr effizient, und wir brauchen dafür auch kein HoTT.

Eine bessere Möglichkeit zu überprüfen, ob eine binäre natürliche Zahl gerade ist, besteht darin, zu überprüfen, ob ihre niedrigstwertige Ziffer eine Null ist.Meine Frage ist:Könnten wir diesen effizienteren Algorithmus für binäre natürliche Zahlen aus unserer Definition der Gleichmäßigkeit für unäre natürliche Zahlen mit HoTT ableiten?Wenn ja, wäre dies auch für andere Datentypen möglich?Ich habe noch kein HoTT studiert und da es ein ziemlich komplexes Thema zu sein scheint, würde ich gerne herausfinden, ob es so aufregend ist, wie ich es denke.Danke!

Answer 1

Sie fragen, ob wir könnte eine effizientere Art der Berechnung ableiten even?Ja, das könnten wir natürlich.Der Punkt ist jedoch, dass Compiler konnte nicht.

Es ist ein schwieriges Problem, wenn ein Compiler automatisch sehr ausgefallene Optimierungstechniken ausführt.Tatsächlich kann das Problem, wenn Sie zu viel verlangen, unentscheidbar und für fast alle interessanten Fälle zumindest extrem schwierig werden.Auch nur zu fragen, ob zwei einfache Typen sind isomorph führt schnell zu offenen Forschungsfragen.

Was wir von HoTT gewonnen haben, ist kein Zauberstab, sondern ein Formalismus, der einen sehr guten und strukturierten Weg bietet denken und Argumentation über Isomorphismus, Äquivalenz und Gleichheit im Allgemeinen.Man kann leicht genug über den Begriff der Äquivalenz im "kleinen Maßstab" nachdenken, zum Beispiel wenn wir uns nur auf eine bestimmte Datenstruktur konzentrieren, wie zum Beispiel ein Wörterbuch, aber es ist eine ganz andere Sache, darüber sprechen zu können aller Äquivalenzbegriffe gleichzeitig.

In Ihrem speziellen Fall ist leicht zu erkennen, was es bedeuten würde, eine Äquivalenz zwischen zwei Implementierungen natürlicher Zahlen zu haben.Aber wie sieht es mit der Äquivalenz großer Softwarekomponenten aus?Oder Äquivalenz von Implementierungen von partiellen Differentialgleichungslösern?Wie sollen wir überhaupt darüber nachdenken?HoTT hat eine Antwort.