Wofür kann in der Domänentheorie die in metrischen Räumen vorhandene zusätzliche Struktur verwendet werden?

10

Smyths Kapitel im Handbuch der Logik in der Informatik und andere Referenzen beschreiben, wie metrische Räume als Domänen verwendet werden können. Ich verstehe, dass vollständige metrische Räume eindeutige Fixpunkte ergeben, aber ich verstehe nicht, warum metrische Räume wichtig sind. Ich würde mich über Gedanken zu den folgenden Fragen sehr freuen.

Was sind gute Beispiele für die Verwendung von (Ultra / Quasi / Pseudo) metrischen Räumen in der Semantik? Insbesondere in Bezug auf ein Beispiel: Warum brauchen wir die metrische Struktur? Was fehlt CPOs, das die Metrik liefert?ω

Außerdem: Ist die eindeutige Fixpunkteigenschaft wichtig? Was ist ein gutes Beispiel?

Vielen Dank!

Ben
quelle

Antworten:

15

Im Vergleich zur Domänenstruktur liefert die metrische Struktur zusätzliche Daten zum Trägersatz. Grundsätzlich können Sie zwei beliebige Elemente eines metrischen Raums vergleichen und wissen außerdem, wie stark sich zwei Elemente unterscheiden, während in Domänen die Ordnungsstruktur partiell ist und Sie kein quantitatives Maß dafür haben, wie viele Elemente sich unterscheiden.

Pragmatisch gesehen ist diese zusätzliche Struktur insofern nützlich, als sie das Lösen von Domänengleichungen erheblich erleichtert. In den 80er Jahren gab es viele niederländische Informatiker, die metrische Raumgleichungen verwendeten, um die Parallelität zu modellieren, aber es ist auch von aktuellem Interesse.

2nn) Ultrametrische Räume sind das geheime Bezeichnungsleben von schrittindizierten Modellen. In Birkedal, Stovring und Thamsborgs Artikel "Die kategorietheoretische Lösung rekursiver metrischer Raumgleichungen" finden Sie einige neuere Arbeiten in diesem Bereich.

Nun, all diese Arbeiten haben sich darauf konzentriert, überhaupt Modelle zu erhalten, aber das ist nicht das einzige, woran wir interessiert sind - wir können Teilaufträge in einem Bezeichnungsmodell nicht einfach durch metrische Strukturen ersetzen und erwarten, dass dies genau dasselbe bedeutet Sache. Sie fragen sich vielleicht, wie sich Metrikmodelle auf Eigenschaften wie beispielsweise die vollständige Abstraktion auswirken.

timeoutneen

Dieses zusätzliche Auflösungsvermögen ist sowohl die Stärke als auch die Schwäche metrischer Techniken. In ihrer Anmerkung "Schrittindizierung: das Gute, das Schlechte und das Hässliche" zeigen Benton und Hur, dass die zusätzliche Struktur von schrittweise indizierten Modellen für sie sehr nützlich ist, um Korrektheitsnachweise für realisierbare Programmiersprachen zu liefern, die in Begriffen implementiert sind von schlechten Low-Level-Sprachen. Die zusätzliche Struktur hindert sie jedoch auch daran, Optimierungen durchzuführen, die in gewissem Sinne "zu effektiv" sind, da dies die Entfernungsinformationen durcheinander bringen könnte. Es hilft und tut ihnen also weh.

Df

Möglicherweise möchten Sie dies jedoch nicht tun. Zum Beispiel habe ich in meiner eigenen jüngsten Forschung (mit Nick Benton) an der synchronen Datenflussprogrammierung höherer Ordnung gearbeitet. Hier besteht die Idee darin, dass wir interaktive Programme durch die Zeit als Stream-Funktionen modellieren können. Natürlich möchten wir rekursive Definitionen berücksichtigen (stellen Sie sich zum Beispiel vor, Sie schreiben eine Funktion, die einen Zahlenstrom als Eingabe empfängt und einen Zahlenstrom ausgibt, der der Summe der bisher gesehenen Stromelemente entspricht).

Ein explizites Ziel dieser Arbeit ist es jedoch sicherzustellen, dass nur fundierte Definitionen zulässig sind, während rekursive Definitionen weiterhin zulässig sind. Daher modelliere ich Streams als ultrametrische Räume und fungiere auf ihnen als nicht expansive Karten (abgesehen davon verallgemeinert dies die Kausalitätsbedingung der reaktiven Programmierung). Unter der von mir verwendeten Metrik entspricht eine geschützte Definition von Stream-Funktionen einer kontraktiven Funktion für Streams, und so existiert nach Banachs Fixpunktsatz ein eindeutiger Fixpunkt. Intuitiv bedeutet die Eindeutigkeitseigenschaft, dass die Berechnung von Fixpunkten unabhängig von dem Element des Raums, mit dem wir beginnen, gleich funktioniert. Auf diese Weise können wir Fixpunkte kontraktiver Funktionen auf einem Raum berechnen, auch wenn der Raum kein Minimum hat Element im Sinne der Domänentheorie.

Neel Krishnaswami
quelle