Referenzanforderung: Kategorietheorie, wie sie für Typsysteme gilt

13

Ich höre immer wieder, wie man Kategorietheorie lernen muss, um die Theorie der Programmiersprache wirklich zu verstehen. Bisher habe ich viel PL gelernt, ohne jemals in den Bereich der Kategorien einzusteigen. Ich nahm jedoch an, dass es Zeit war, den Sprung zu wagen, um zu sehen, was ich vermisst hatte.

Leider scheint keine der Quellen, die ich finden kann, irgendwelche Verbindungen zu Typsystemen oder zur Programmierung herzustellen. Sie sagen, es ist eine Einführung in die Kategorietheorie für Informatiker, aber dann in allgemeinen abstrakten Unsinn (das sage ich liebevoll), ohne praktische Beispiele oder Anwendungen zu nennen.

Ich denke, meine Frage hat zwei Gründe:

  1. Ist Kategorietheorie wesentlich für das Verständnis der "tiefen Konzepte" in PL?
  2. Was ist eine Quelle, die die Kategorietheorie unter dem Gesichtspunkt praktischer Anwendungen zu Typsystemen und Programmierung erklärt?

Bisher habe ich mich am weitesten mit einer vagen Vorstellung von Funktoren beschäftigt (die, soweit ich das beurteilen kann, nicht mit Funktoren in ML zu tun zu haben scheinen). Ich fürchte mich vor der Abstraktion, die ich im Kopf behalten muss, um Monaden aus kategorietheoretischer Sicht zu verstehen.

Gartenkopf
quelle
2
@Raphael Es ist eine schlechte Idee, eine Frage zu stellen, die aus zwei verschiedenen Fragen besteht, die nur vage miteinander zusammenhängen. Aber Frage 1 ist nicht subjektiv. Es ist eher eine Bitte um Klarstellung und Erklärung. Ich denke, Frage 2 war in dem Sinne gemeint, dass er mit einem Verweis auf einen Ort, an dem er erklärt wird, zufrieden ist, anstatt auch mit einer tatsächlichen Erklärung.
Thomas Klimpel
2
In Zukunft ist es besser, nur eine Frage pro Beitrag zu stellen. Sie können Frage 1 stellen und dann abhängig von den erhaltenen Antworten entscheiden, ob Sie Frage 2 separat stellen möchten. Dadurch läuft es oft reibungsloser.
DW
1
@ Raffael Wie ist Frage eins subjektiv? Es könnte schwer zu beurteilen sein - ist es das, was Sie meinen? Und es könnte als Antwort haben: "Es kommt darauf an, welche Art von Person Sie sind." - ist es das, was Sie meinen? Es könnte sich immer noch herausstellen, dass es definitiv wesentlich oder definitiv nicht wesentlich ist, oder? (Und die Leute scheinen zuzustimmen, dass es nicht wesentlich ist.)
k.stm
1
@ k.stm Die allgemeine Form der Frage macht mir Sorgen. Wenn sich jemand die Frage stellt: "Ist Algebra wichtig, um die tiefen Konzepte formaler Sprachen zu verstehen?", Dann weiß ich, dass verschiedene Menschen unterschiedliche Antworten geben werden - basierend auf ihren Vorlieben und ihrem Geschmack. Ich erwarte nicht, dass es hier anders ist.
Raphael
1
@Raphael Okay, ich verstehe. Aber ich denke, das sind Leute, die subjektive Antworten auf eine objektive Frage geben. (Es fühlt sich an, als würden Leute sagen "Oh, ich trinke fünf Tassen am Tag und ich fühle mich großartig!", Wenn sie gefragt werden, ob Kaffee gesund ist oder nicht.)
k.stm

Antworten:

15

Die Kategorietheorie ist nicht erforderlich, um Programmiersprachen zu verstehen, und es ist nicht einmal erforderlich, fortgeschrittene Forschungen über Programmiersprachen durchzuführen. Die meisten Programmiersprachen kennen (viel) keine Kategorietheorie.

Kategorietheoretische Methoden haben sich vor allem in einem kleinen Teil der Programmiersprachenforschung als nützlich erwiesen, und zwar bei der Analyse der funktionalen Programmierung, insbesondere seit Moggis großer Entdeckung, dass einige Computereffekte eine monadische Struktur aufweisen. In den 1990er Jahren, nach Moggis Durchbruch, wurde viel geforscht, um kategoriale Methoden auf andere Formen von Programmiersprachen auszudehnen. Nach meinem besten Wissen haben sich kategoriale Methoden jedoch für OO, gleichzeitige, parallele und verteilte Berechnungen, zeitgesteuerte Berechnungen oder Compiler nicht als besonders nützlich erwiesen. Aus diesem Grund haben die Menschen die Ausweitung kategorialer Methoden größtenteils aufgegeben.

Kategoriale Ansätze zur getippten Programmierung funktionieren gut in reinen Funktionen. In der Tat sind einige einfache Schreibsysteme Kategorien. Dies ist beschrieben in z

Derzeit wird viel an Typen für gleichzeitige Prozesse gearbeitet (z. B. Sitzungstypen), und seit September 2016 ist keine dieser Typen kategorischer Natur.

Das heißt, man kann nie zu viel Mathematik lernen, und es ist nützlich, die Kategorietheorie zu kennen. Es ist also eine Frage von Kosten / Nutzen. Wenn Sie Mathematik mögen, wenn Sie vielleicht etwas Hintergrundwissen in der Algebra haben (z. B. was ist die freie Gruppe über eine Menge, freier Ring usw.), dann wird das Erlernen der Kategorietheorie einfach sein, und wenn Sie vorhaben, eine Arbeit zu machen, die (inspiriert von) funktionale Programmierung, das Kennen von Kategorien wird nützlich sein.

Schließlich ist Kategorietheorie eine schöne Mathematik und es lohnt sich, sie einfach zu studieren, weil sie so ordentlich ist.


Siehe Uday Reddys Beitrag in dieser Diskussion für eine andere Ansicht.

Martin Berger
quelle
"Nach meinem besten Wissen haben sich kategoriale Methoden jedoch nicht als besonders nützlich für ... erwiesen." Das ist genau mein Problem. Die operationale Semantik kann all diese Konzepte genau beschreiben, sodass ich nicht das Gefühl hatte, etwas verpasst zu haben. Ich liebe Mathematik, aber mein Hintergrund in der abstrakten Algebra fehlt leider. Ich verstehe nur die Grundlagen der allgemeinen algebraischen Strukturen. Dies hat das Erfassen der Kategorietheorie besonders umständlich gemacht.
Gardenhead
2
@gardenhead Dann ist CT vielleicht gar nicht so nützlich für dich. Wenn Sie viele Artikel im Bereich "Funktionale Programmierung" lesen möchten, einschließlich der Arbeit an Typen, dann werden viele von ihnen die Sprache CT verwenden.
Martin Berger
Ist das ein Duplikat?
Raphael
2
Ich würde zusätzlich das Buch cs.unibo.it/~asperti/PAPERS/book.pdf "Categories, Types, and Structures" vorschlagen , das anscheinend vergriffen ist, aber das ist ein Link zu einem PDF von einem der Die Homepages der Autoren, also denke ich, es ist legitim.
John Forkosh
6

Das Erlernen der Kategorietheorie ist eine enorme Zeitinvestition, und die Frage, ob es sich lohnt, ist sehr berechtigt. Auch damit habe ich immer noch zu kämpfen und ich weiß bereits, warum ich es lernen sollte. Ich schrieb:

Ich mochte Assemblersprache, als ich anfing zu programmieren, und die Mengenlehre fühlt sich ähnlich an wie Assemblersprache. Die Kategorietheorie ist eine Alternative, um alle verwurzelten Vorurteile über Logik und Modelltheorie, die in die ZFC-Mengen-Theorie des Mainstreams eingebettet sind, zu umgehen.

Die Idee hier ist, Kategorien anstelle von Mengen oder "nicht spezifizierten Bits" als mögliche Semantik für eine gegebene Typentheorie oder Programmiersprache zu verwenden. Warum sollte man das wollen? Betrachten Sie die Dualität zwischen einer Handlung und einer Beobachtung. Unterschiedliche Beobachtungen (oder zumindest deren zeitliche Reihenfolge) stören sich nicht (außerhalb der Quantenmechanik), dies gilt jedoch nicht unbedingt für unterschiedliche Handlungen. Die in der Mengenlehre verankerten Vorurteile gegenüber der Logik erschweren die Modellierung von Handlungen im Vergleich zur Modellierung von Beobachtungen.


Ich bin nicht davon überzeugt, dass es wirklich eine perfekte Entsprechung zwischen Kategorietheorie und Typentheorie gibt, wie hier behauptet :

Durch eine Syntax-Semantik-Dualität kann man die Typentheorie als eine formale syntaktische Sprache oder einen Kalkül für die Kategorietheorie betrachten, und umgekehrt kann man die Kategorietheorie als eine Semantik für die Typentheorie betrachten.

Es ist richtig, dass die Kategorietheorie Semantik für die Typentheorie liefern kann (was sehr nützlich sein kann), aber ich bezweifle, dass die Typentheorie wirklich eine ausreichend mächtige formale syntaktische Sprache bietet, um alle in der Kategorietheorie durchgeführten Berechnungen auszudrücken.


In der Praxis kann der Nutzen der Kategorietheorie durch das Vorschlagen nützlicher Fragen und Analogien entstehen. Die Kategorietheorie kann aber auch Aktivitäten und Fragen vorschlagen, die sich letztendlich nur als Ablenkung (Zeitverschwendung) von den wirklich wichtigen Themen herausstellen. Und Sie können sicherlich Logik und Typentheorie lernen, ohne sich um Kategorietheorie zu kümmern.

Thomas Klimpel
quelle
Danke für deine Gedanken. Ihre Gründe für das Erlernen der Kategorietheorie scheinen sich von meinen zu unterscheiden. Ihre Interessen entstammen einer rein mathematischen Perspektive, während ich mein Verständnis von Typen erweitern möchte. Trotzdem ist es schön zu wissen, dass es für andere Leute, die sich um mich kümmern, schwierig ist, sich der Kategorie zu nähern und sie anzuwenden
gardenhead