Sind kombinatorische logische Begriffe immer größer?

9

Es gibt also einen Algorithmus zum Konvertieren von Lambda-Kalkül-Begriffen in kombinatorische Logik unter Verwendung von SK-Kombinatoren. Es produziert Dinge, die in der Größe explodieren . Ich würde gerne mehr über diese Explosion erfahren. Ich kann mir jedoch keinen besseren Algorithmus vorstellen. Ich habe von funktionalen Sprachen gehört, die praktisch zu Kombinatoren kompiliert wurden, so dass es den Anschein hat, dass ein besserer Algorithmus existieren muss. Ich habe David Turners Artikel zu diesem Thema nachgeschlagen und er sagt im Grunde nur, dass er einige Optimierungen anwenden soll und dass sie eine "erhebliche Verbesserung" bewirken.

Bedeutet "erhebliche Verbesserung", dass die Größe nur auf eine Polynomzunahme abfällt? Gibt es eine bekannte Möglichkeit, Lambda-Terme mit nur einer Polynomzunahme (oder weniger?) In kombinatorische Logik umzuwandeln? Wenn ein solcher Algorithmus existiert, ist er praktisch?

Jake
quelle
Das Papier stammt aus dem Jahr 1979. Es gibt viel modernere / neuere Überlegungen / Technologien zur Übersetzung von Code in Logik, z. B. mit FPGAs und GPUs, und würden im Allgemeinen nicht auf funktionalen Sprachen basieren ....
vzn
Kannst du mich auf sie hinweisen?
Jake
Die Forschung, die Sie zitieren, ist eher ein theoretischer "Beweis des Prinzips" ... es wäre besser, wenn Sie das Konzept / den Abschnitt über die "polynomielle Zunahme der Größe" zitieren, das im Mittelpunkt Ihrer Frage zu stehen scheint ... interessieren Sie sich für die allgemeine Theorie der Umwandlung von Code in Logik / Schaltkreise auf der theoretischen oder angewandten Seite oder die Theorie der effizienten Ausführung oder beides? Die Frage ist in ihren verschiedenen Aspekten sehr übergreifend ... vielleicht kann man mehr im Computer Science Chat
herausfinden
1) Gibt es eine Möglichkeit, dies in einen Chat zu importieren? Ich kann das nicht herausfinden. 2) Es gibt keinen Abschnitt über die Zunahme der Polynomgröße und das ist mein Problem. Es sagt eigentlich nichts Wesentliches aus (und ich kann auch keine solchen Referenzen finden), wie stark die Vergrößerung ist.
Jake
Die Kommentare können nach einem Schwellenwert für separate veröffentlichte Kommentare in den Chat importiert werden. Das ist nicht notwendig, um einen Chat zu starten. Bei einer Polynomzunahme könnte es sich um ein "Gerücht" - oder "Folklore" -Konzept über diese Forschungsrichtung handeln, nicht sicher. aber wo hast du was gehört wie "es produziert Dinge, die in der Größe explodieren "; es wäre hilfreich, genauer zu sein etc ...
vzn

Antworten:

4

Ich bin kein Experte in diesem Bereich, aber hier sind zwei historische Artikel, die für die Frage sehr relevant zu sein scheinen und möglicherweise ein halbaktives Forschungsgebiet sind. Turner schlug eine Reihe von Kombinatoren vor, die auf SK-Kombinatoren reduziert werden können. In diesem nächsten Artikel wird argumentiert, dass Turner-Kombinatoren, die nicht auf SK-Kombinatoren reduziert sind, zu einem exponentiellen Aufblasen führen (und dass die Reduktion auf SK-Terme vermutlich noch größer wäre). In der zweiten Veröffentlichung heißt es jedoch, dass es einen effizienten O (n log n) -Raumalgorithmus gibt, der auf Turner-Kombinatoren basiert. (Es scheint, dass Behauptungen über die Polynomeffizienz aufgestellt wurden, die als nicht vollständig demonstriert / unbewiesen angesehen werden und daher als Vermutungen angesehen werden ...

  • Was ist eine effiziente Implementierung des λ-Kalküls? / Frandsen, Sturtivant (1991) (siehe S.18)

    Darüber hinaus zeigen wir, dass Implementierungen, die auf Turner-Kombinatoren oder Hughes-Superkombinatoren basieren, Komplexitäten von , dh eine exponentielle Untergrenze. Es ist offen, ob eine Implementierung der Polynomkomplexität existiert, obwohl implizit behauptet wurde, dass einige Implementierungen diese Komplexität aufweisen.2Ω(ν)νO(1)

  • Übersetzung von Turner-Kombinatoren im O (n log n) -Raum / Noshita (1985)

    Es wird eine praktische Methode zur Darstellung von Turner-Kombinatoren vorgestellt, die im schlimmsten Fall nur O (n log n) Platz benötigt, um Lambda-Ausdrücke der Länge n zu übersetzen.

vzn
quelle
1
perfekt! Ich habe dieses Papier auch gefunden, nachdem ich nach diesen beiden Papieren gesucht hatte. sciencedirect.com/science/article/pii/002001908790161X Danke!
Jake