Was ist der Unterschied zwischen dem Umschreiben von Begriffen und dem Anpassen von Mustern?

Da es bei Lambda the Ultimate keine Antwort gab, versuche ich es hier noch einmal: Term Rewriting-Systeme werden beispielsweise in automatisierten Theoremen verwendet, um eine symbolische Berechnung zu beweisen und natürlich formale Grammatiken zu definieren. Es gibt einige Programmiersprachen, die auf dem Umschreiben von Begriffen basieren, aber nach meinem Verständnis ist das Konzept eher als Pattern Matching bekannt . Pattern Matching wird häufig in funktionalen Sprachen verwendet. Barry Jay hat eine ganze Theorie entwickelt, die Musterrechnung genannt wird , aber er erwähnt das Umschreiben von Begriffen nur kurz. Ich habe das Gefühl, dass sie sich alle auf die gleiche Grundidee beziehen. Können Sie also das Umschreiben von Begriffen und den Mustervergleich synonym verwenden?

Eine Möglichkeit, diese beiden Konzepte zu betrachten, besteht darin, zu sagen, dass Pattern Matching ein Merkmal von Programmiersprachen ist, um Diskriminierung nach Konstruktoren zu kombinieren und Begriffe zu zerstören (während Termfragmente sicher, kompakt und effizient ausgewählt und lokal benannt werden). Die Forschung zum Pattern Matching konzentriert sich typischerweise auf die Implementierungseffizienz, z. B. darauf, wie die Anzahl der Vergleiche, die der Matching-Mechanismus durchführen muss, minimiert werden kann.

Im Gegensatz dazu ist das Umschreiben von Begriffen ein allgemeines Berechnungsmodell , das eine breite Palette von (möglicherweise nicht deterministischen) Methoden untersucht, um syntaktische Ausdrücke (genauer gesagt ein Element einer Termalgebra über eine Reihe von Variablen) durch andere Begriffe zu ersetzen. Bei der Erforschung von Term Rewriting-Systemen geht es normalerweise um abstrakte Eigenschaften von Rewriting-Systemen wie Zusammenfluss, Determinismus und Terminierung und insbesondere darum, wie solche Eigenschaften durch algebraische Operationen auf Rewrite-Systemen erhalten werden oder nicht, dh inwieweit diese Eigenschaften kompositorisch sind.

Natürlich gibt es konzeptionelle Überschneidungen zwischen beiden, und die Unterscheidung ist eher traditionell als technisch. Ein technischer Unterschied besteht darin, dass das Umschreiben von Begriffen in beliebigen Kontexten erfolgt (dh eine Regel induziert das Umschreiben von für beliebige Kontexte Und Substitutionen ), während Pattern Matching in modernen Sprachen wie Haskell, OCaml oder Scala ermöglicht nur das Umschreiben "am Anfang" eines Begriffs. Ich denke, diese Einschränkung wird auch in Jays Musterkalkül auferlegt. Lassen Sie mich erklären, was ich mit dieser Einschränkung meine. Mit Pattern Matching im Sinne von OCaml, Haskell, Scala kann man so etwas nicht sagenC [ l σ ] → C [ r σ ] C [ . ] $(l, r)$$C[l\sigma] \rightarrow C[r\sigma]$$C[.]$$\sigma$

match M with
   | C[ x :: _ ]  -> printf "%i ...\n" x
   | C[ [] ] -> printf "[]"

Was ist C[.]hier Es soll eine Variable sein, die sich über einlöchrige Kontexte erstreckt. Sprachen wie OCaml, Haskell oder Scala geben Programmierern jedoch keine Variablen, die sich über beliebige (Ein-Loch-) Kontexte erstrecken, sondern nur Variablen, die sich über Werte erstrecken. Mit anderen Worten, in solchen Sprachen können Sie keine Musterübereinstimmung an einer beliebigen Position in einem Begriff durchführen. Sie müssen immer den Pfad von der Wurzel des Musters zu den Teilen angeben, an denen Sie interessiert sind. Ich denke, der Hauptgrund für diese Einschränkung ist, dass der Mustervergleich ansonsten nicht deterministisch wäre, da ein Begriff möglicherweise mit einem Muster in übereinstimmt mehr als eine möglichkeit. Beispielsweise (true, [9,7,4], "hello", 7)stimmt der Begriff C[7]auf zwei Arten mit dem Muster überein , vorausgesetzt, er C[.] erstreckt sich über solche Kontexte.

Ich halte es nicht für richtig, sie als Synonyme zu bezeichnen. Es gibt einige Überschneidungen in Bezug auf Forschung und Umsetzung. Ich bin mit Jays Arbeit überhaupt nicht vertraut, und ich bin nur ein bisschen mit Term Rewriting-Systemen vertraut, daher kann mir auch etwas fehlen.

Der Mustervergleich hat im Allgemeinen folgendes Problem: Sie haben eine Struktur (einen Baum oder eine Liste oder ein Multiset) und möchten prüfen, ob die Struktur mit einem Muster (oder einem von mehreren Mustern) übereinstimmt. Diese Frage ist sicherlich relevant für das Umschreiben von Begriffen, da in Umschreibungssystemen die Tatsache, dass ein Begriff mit einem Muster übereinstimmt, bedeutet, dass der Begriff in einen anderen Begriff umgeschrieben werden kann, aber dies ist kein Synonym für das Umschreiben von Begriffen. (Es gibt möglicherweise eine Formulierung für den Mustervergleich als Umschreiben: "Können Sie einen Begriff so umschreiben, dass er mit dem Muster übereinstimmt?", Aber das habe ich noch nie gesehen.)

Pattern Matching in einer funktionalen Programmiersprache hat eine logische Interpretation in Bezug auf Fokussierung (siehe beispielsweise Krishnaswamis "Focusing on Pattern Matching" ). Term-Rewriting-Systeme hingegen führen häufig das Matching Modulo einiger Gleichungseigenschaften durch, die in den meisten funktionalen Programmiersprachen nicht vorhanden sind (in ML oder Haskell können Sie keine Übereinstimmung mit einem Multiset erzielen). Es gibt jedoch keinen fundamentalen Grund, warum übereinstimmende Modulo-Gleichungseigenschaften in funktionalen Sprachen nicht vorhanden sein sollten.

(Ich schreibe das lieber als Kommentar, aber ich kann es derzeit nicht.)

Korrigieren Sie mich, wenn ich falsch liege, aber nach meinem Verständnis besteht ein weiterer Unterschied zwischen Pattern Matching und Term Rewriting, abgesehen von dem, was Martin Berger in seiner ausgezeichneten Antwort sagte , darin, dass Pattern Matching - Regeln eine feste Reihenfolge haben (in Implementierungen wie Haskells), während dies bei Regeln für das Umschreiben von Begriffen nicht unbedingt der Fall sein muss. Wie zu erwarten, kann diese Funktion einen großen Unterschied machen, wenn man das Verhalten (insbesondere die Beendigung) der Regeln betrachtet (siehe z. B. "Eine sanfte Einführung in Haskell, Version 98", Abschnitt 4.2 oder nur die Fakultät) Beispiel bei "Learn you a Haskell" ).

Kenner der Umschreibungstheorie müssten mehr dazu sagen (zum Beispiel, wie passt das Schreiben genau zu einem solchen Vergleich?), Aber es scheint mir fair, Martin Berger zuzustimmen, dass der Begriff Umschreibung auch umfasst Pattern Matching (zumindest, da dies in Sprachen wie Haskell implementiert ist), in dem Ausmaß, dass beide als Geräte (eher trocken) betrachtet werden können, die lediglich termbezogene Regeln verwenden.