Kategorietheorie (nicht) zum Programmieren?

21

Nachdem ich Haskell und andere nicht so reine FP-Sprachen gelernt hatte, entschloss ich mich, über Kategorietheorie zu lesen. Nachdem ich ein gutes Verständnis der Kategorietheorie erlangt hatte, begann ich darüber nachzudenken, wie die Konzepte der Kategorietheorie zum Entwerfen von Programmen verwendet werden können, aber egal, wie sehr ich es versucht habe, scheint dies nicht der richtige Weg zu sein.

Nachdem ich viele erfolglose Versuche unternommen hatte, Kategorietheorie mit dem Entwerfen von Programmen in Verbindung zu bringen, kam ich zu dem Schluss, dass:

  • Die Kategorietheorie ist hilfreich beim Entwerfen einer Programmiersprache .
  • Die Kategorietheorie verwenden Sie nicht, wenn Entwerfen von Programmen nicht verwendet (selbst wenn eine Sprache verwendet wird, die auf Kategorienprinzipien basiert). Zum Beispiel: Wenn Sie in Haskell programmieren, verwenden Sie Typen, Typenkonstruktoren, Funktionen, Funktionen höherer Ordnung usw., um Ihr Programm zu entwerfen, nicht kategorietheoretische Konzepte.

Zusammenfassend haben wir unter Schichtsystem (Reihenfolge ist niedrig zu hoch):

Kategorietheorie -> Programmiersprache -> Programm

Auf einer bestimmten Ebene verwenden Sie die Konzepte der unmittelbar darunter liegenden Ebene .

Ist dieses Verständnis richtig? Wenn nicht und du glaubst das in wir Entwerfen von Programmen Konzepte der Kategorietheorie direkt verwenden können, verweisen Sie auf einige Artikel oder Blog-Beiträge, in denen dies demonstriert wird.

HINWEIS: Mit dem Entwerfen von Programmen ist das Entwerfen von Programmen gemeint, die auf verschiedenen Konzepten basieren, wie Parallelität, Parallelität, Reaktivität, Nachrichtenübermittlung usw.

functional-programming category-theory Ankur
quelle
1
Betrachten Sie Monaden als Teil der Programmiersprache oder -programme? Pfeile?
Dave Clarke
2
Dies erscheint mir zumindest teilweise als eine philosophische Frage. Ich bin nicht sicher, ob es eine einzige richtige Antwort gibt. Ein Experte der Kategorietheorie wird die Intuition anwenden, die er beim Programmieren gewonnen hat, ein anderer wird andere Denkweisen bevorzugen.
Raphael
2
Die meisten Programme, die geschrieben werden, verwenden Programmiersprachen, die nicht von der Kategorietheorie inspiriert sind. Soweit ich das beurteilen kann, ist dem durchschnittlichen Programmierer die Kategorietheorie nicht bekannt, weshalb die meisten Programme (einschließlich Ihres Betriebssystems und Ihres Browsers) nicht von höherer Mathematik inspiriert sind.
Yuval Filmus
1
@YuvalFilmus: Meine Frage richtet sich an funktionale Programmiersprachen
Ankur
1
Siehe auch diese Frage für einige CS-Anwendungen von Monoiden
vzn

Antworten:

13

Nun, das hängt natürlich davon ab, welche Art von Programm Sie entwerfen möchten.

Wenn Sie ein Buchhaltungsprogramm für den Schokoladenladen Ihrer Tante entwerfen, kann ich kaum bezweifeln, dass die Kategorietheorie von großem Nutzen sein wird.

Aber es gibt natürlich Situationen, in denen die Kategorietheorie beim Entwerfen von Programmen enorm nützlich ist (womit ich auch Datenstrukturen, Bibliotheken usw. meine). Solche Situationen treten meistens auf, wenn die beteiligten Programme mathematischer Natur sind.

Wenn Sie Programme schreiben möchten, die mit exakten reellen Zahlen und anderen in der mathematischen Analyse vorkommenden Strukturen rechnen, müssen Sie zunächst die Frage beantworten, was es bedeutet, ein kompliziertes mathematisches Objekt (wie eine differenzierbare Funktion, eine Mannigfaltigkeit usw.) korrekt zu implementieren. ). Hier hilft es sehr, Kategorietheorie und -logik zu kennen, da sie Ihnen eine systematische Möglichkeit bieten, Definitionen mathematischer Strukturen in Spezifikationen und Implementierungen entsprechender Datenstrukturen zu übersetzen. Das Schlagwort, nach dem Sie suchen sollten, ist Realisierbarkeitstheorie . Dies ist jedoch nur ein Beispiel.

Der beste Weg, um herauszufinden, wie nützlich Kategorietheorie ist, besteht darin, sich Programme anzusehen, die von Leuten geschrieben wurden, die sich mit Kategorietheorie (und Mathematik im Allgemeinen) auskennen. Ein offensichtliches Beispiel dafür ist Martín Escardó und seine unmöglichen Funktionen, zum Beispiel:

M. Escardó und P. Oliva: Was sequentielle Spiele, das Tychonoff-Theorem und die Doppel-Negations-Verschiebung gemeinsam haben , mathematisch strukturierte funktionale Programmierung 2010, ACM Press. (mit begleitenden Haskell- und Agda-Dateien )

Sie können sich beschweren, dass dies nicht nur Kategorietheorie, sondern auch Logik und Topologie ist. Solche Beschwerden wären stark irreführend. Die beste Kategorietheorie wird immer mit anderen Dingen vermischt.

Abschließend rate ich davon ab, auf der Grundlage einer selbst zugewiesenen Lektüre großartige Schlussfolgerungen über die Natur der Dinge zu ziehen.

Andrej Bauer
quelle
Genau darum geht es mir. Wenn ich Buchhaltungssoftware entwerfe, ist das Typensystem meine Sprache für das Design. Wenn ich selbst eine mathematische Software entwerfe, verwende ich das Typensystem, um kategorietheoretische Konzepte darzustellen. Was grundsätzlich darauf hinweist, dass Typentheorie ODER Typensysteme allgemeinere Abstraktionen sind als Kategorietheorie.
Ankur
1
Das ist eine lächerliche Aussage. Ich denke, Sie sollten vielleicht noch etwas lernen, bevor Sie solche pauschalen Aussagen machen. Vielleicht können Sie mit existentialtype.wordpress.com/2011/03/27/the-holy-trinity
Andrej Bauer
Ich bin kein Forscher, Doktorand, Wissenschaftler, Mathematiker oder Kategorietheoretiker, also ärgere dich nicht über meine Aussagen, sie werden nicht in einer wissenschaftlichen Zeitschrift oder in Forschungsberichten veröffentlicht. Ich bin nur ein Programmierer, der versucht, die andere Seite der Medaille zu verstehen. Übrigens, danke für den Link.
Ankur
1
Mir ist das klar, und genau deshalb schlage ich vor, dass Sie vorsichtig sein sollten, wenn Sie Schlussfolgerungen ziehen, wie Sie es tun: Sie haben einfach nicht die Informationen, die erforderlich sind, um solche Schlussfolgerungen zu ziehen. Und aus diesem Grund verweise ich Sie auch auf einen Blogbeitrag von Bob Harpher und nicht etwa auf ein technisches Buch über die Beziehung zwischen Typentheorie und Kategorietheorie. Ich versuche zu helfen, aber ich würde im Gegenzug etwas mehr Vorbehalte von Ihnen erwarten, wenn es darum geht, großartige Schlussfolgerungen über das Wesen eines ganzen Zweigs der Mathematik zu ziehen.
Andrej Bauer
Zum Beispiel haben Sie festgestellt, dass "Typentheorie eine allgemeinere Abstraktion als Kategorietheorie ist". Dies ist ein Beispiel für eine Aussage, die Sie aufgrund geringer Kenntnisse nicht machen sollten. Ich arbeite professionell in diesem Bereich und selbst ich würde sehr vorsichtig sein, um eine solche Schlussfolgerung zu ziehen, oder das Gegenteil.
Andrej Bauer
6

Früher benutzten die Leute CT, um Datentypen zu beschreiben.

  1. Der Datentyp wurde durch eine bestimmte Kategorie definiert, deren Objekte endliche Folgen von (Spezifikationssprachen-) Typen sind und deren Pfeile Projektionen oder auch Kompositionen der Datentypoperationen waren. Beispielsweise ist das Objekt die Domäne und die Codomäne der Push-Operation von Stapeln. Dies gibt Ihnen Syntax, aber Sie haben immer noch keine Vorstellung von Semantik.
  2. Eine Algebra, also eine Instanz des Typs, ist ein Funktor aus der Theorie zu Ens, der Kategorie der (kleinen) Mengen. (Wir verwenden "klein", um Russells Paradoxon zu vermeiden, aber es spielt meistens keine Rolle.)
  3. Es zeigt sich, dass die Abschlusseigenschaften der Kategorien Familien logischer Theorien entsprechen. Wenn beispielsweise die Theoriekategorie unter Produkten geschlossen ist, kann der Datentyp durch Gleichungen axiomatisiert werden. Wenn die Theoriekategorie durch Pullbacks geschlossen wird, kann der Datentyp durch Hornsätze axiomatisiert werden.

Ich bin mir nicht ganz sicher, ob irgendjemand mehr darauf achtet. Ich würde denken, dass dies und die Links dort es detaillierter erklären würden.

Vilcxjo
quelle