Verwendung von Prozesskalkülen und PL-Theorie für die Entwicklung moderner Programmiersprachen

10

Seit einiger Zeit interessiere ich mich sehr für Programmiersprachtheorie und Prozesskalküle und habe begonnen, sie zu studieren. Um ehrlich zu sein, würde es mir nichts ausmachen, Karriere zu machen. Ich finde die Theorie unglaublich faszinierend. Eine ständige Frage, auf die ich immer wieder stoße, ist, ob entweder PL-Theorie oder Prozessrechnung überhaupt eine Bedeutung für die Entwicklung moderner Programmiersprachen haben. Ich sehe so viele Varianten des Pi-Kalküls da draußen und es gibt viel aktive Forschung, aber werden sie jemals benötigt oder haben wichtige Anwendungen? Der Grund, warum ich frage, ist, dass ich es liebe, Programmiersprachen zu entwickeln, und das wahre Endziel wäre, die Theorie zu verwenden, um tatsächlich einen PL zu erstellen. Für das, was ich geschrieben habe, gab es überhaupt keine Korrelation zur Theorie.

Stefan G.
quelle

Antworten:

9

Meine Antwort ist wirklich nur eine Ausarbeitung von Gilles ', die ich nicht gelesen hatte, bevor ich meine schrieb. Vielleicht ist es trotzdem hilfreich.

Lassen Sie mich meinen Versuch, Ihre Frage zu beantworten, mit einer Unterscheidung zwischen zwei Dimensionen der Arbeit mit Programmiersprachen beginnen, die sich ganz unterschiedlich auf die Theorie der Programmiersprache im Allgemeinen und die Prozessrechnung im Besonderen beziehen.

  • Reine Forschung.

  • Produktorientierte Forschung und Entwicklung.

Letzteres findet typischerweise in der Industrie mit dem Ziel statt, Programmiersprachen als Produkt bereitzustellen. Die Teams, die Java bei Oracle und C # bei Microsoft entwickeln, sind Beispiele. Im Gegensatz dazu ist reine Forschung nicht an Produkte gebunden. Ziel ist es, Programmiersprachen als Objekte von intrinsischem Interesse zu verstehen und die mathematischen Strukturen zu untersuchen, die allen Programmiersprachen zugrunde liegen.

Aufgrund unterschiedlicher Ziele sind verschiedene Aspekte der Programmiersprachtheorie für die reine Forschung und für produktorientierte Forschung und Entwicklung relevant. Das folgende Bild kann einen Hinweis darauf geben, was wo wichtig ist.

Geben Sie hier die Bildbeschreibung ein

Man kann an dieser Stelle fragen, warum die beiden Dimensionen so scheinbar unterschiedlich sind und wie sie sich dennoch verhalten.

Die wichtigste Erkenntnis ist, dass die Erforschung und Entwicklung von Programmiersprachen mehrere Dimensionen hat: technische, soziale und wirtschaftliche. Fast per Definition ist die Industrie an der wirtschaftlichen Auszahlung von Programmiersprachen interessiert. Microsoft et al. Entwickeln Sprachen nicht aus der Güte ihres Herzens heraus, sondern weil sie glauben, dass Programmiersprachen ihnen einen wirtschaftlichen Vorteil verschaffen. Und sie haben eingehend untersucht, warum einige Programmiersprachen erfolgreich sind, andere, die scheinbar ähnlich sind oder über erweiterte Funktionen verfügen, nicht. Und sie fanden heraus, dass es keinen einzigen Grund gibt. Programmiersprachen und ihre Umgebungen sind komplex, ebenso wie die Gründe für die Übernahme oder Ignorierung einer bestimmten Sprache. Der größte Faktor für den Erfolg einer Programmiersprache ist jedoch die bevorzugte Bindung von Programmierern an Sprachen, die bereits weit verbreitet sind: Je mehr Menschen eine Sprache verwenden, desto mehr Bibliotheken, Werkzeuge und Lehrmaterialien stehen zur Verfügung und desto produktiver ist ein Programmierer kann diese Sprache verwenden. Dies wird auch als Netzwerkeffekt bezeichnet. Ein weiterer Grund sind die kostenintensiven Sprachwechsel für Einzelpersonen und Organisationen: Das Beherrschen der Sprache, insbesondere für einen weniger erfahrenen Programmierer, und wenn die semantische Distanz zu vertrauten Sprachen groß ist, ist eine ernsthafte, zeitaufwändige Anstrengung. Angesichts dieser Tatsachen kann man sich fragen, warum neue Sprachen überhaupt Anklang finden. Warum entwickeln Unternehmen überhaupt neue Sprachen? Warum bleiben wir nicht einfach bei Java oder Cobol? Ich denke, es gibt mehrere Hauptgründe für den Erfolg einer Sprache.

  • Es eröffnet sich eine neue Programmierdomäne, die keine zu verdrängenden Amtsinhaber hat. Das Hauptbeispiel ist das Web mit dem damit einhergehenden Aufstieg von Javascript.

  • Sprachklebrigkeit. Damit meine ich den hohen Preis für einen Sprachwechsel. Aber manchmal wechseln Programmierer in verschiedene Bereiche, nehmen eine Programmiersprache mit und sind mit der alten Sprache im neuen Bereich erfolgreich.

  • Eine Sprache wird von einem großen Unternehmen mit ernsthafter finanzieller Feuerkraft vorangetrieben. Diese Unterstützung verringert das Risiko einer Adoption, da Frühanwender ziemlich sicher sein können, dass die Sprache in einigen Jahren noch unterstützt wird. Ein gutes Beispiel dafür ist C #.

  • Eine Sprache kann mit überzeugenden Werkzeugen und Ökosystemen kommen. Auch hier könnte C # und sein .Net- und Visual Studio-Ökosystem als Beispiel genannt werden.

  • Alte Sprachen übernehmen neue Funktionen. Es fällt mir Java ein, das in jeder Iteration mehr gute Ideen aus der Tradition der funktionalen Programmierung aufgreift.

  • Schließlich könnte eine neue Sprache intrinsische technische Vorteile haben, z. B. ausdrucksstärker sein, eine bessere Syntax haben, Systeme eingeben, die mehr Fehler auffangen usw.

Vor diesem Hintergrund sollte es nicht überraschen, dass zwischen reiner Programmiersprachenforschung und kommerzieller Programmiersprachenentwicklung eine gewisse Trennung besteht. Während beide darauf abzielen, die Softwarekonstruktion und -entwicklung effizienter zu gestalten, insbesondere für Software in großem Maßstab, muss die Arbeit mit industriellen Programmiersprachen mehr daran interessiert sein, eine schnelle Einführung zu ermöglichen, um eine kritische Masse zu erreichen und den Netzwerkeffekt zu erzielen. Dies führt zu einem Forschungsschwerpunkt auf Dinge, die arbeitende Programmierer interessieren. Dies sind in der Regel Bibliotheksverfügbarkeit, Compilergeschwindigkeit, Qualität des kompilierten Codes, Portabilität usw. Die Prozessrechnung, wie wir sie heute praktizieren, ist für Programmierer, die an Mainstream-Projekten arbeiten, von geringem Nutzen (obwohl ich glaube, dass sich dies in Zukunft ändern wird).

λπβ-Reduktion für funktionale Programmierung, Auflösung / Vereinheitlichung für Logikprogrammierung, Namensübergabe für gleichzeitige Berechnung). Um zu verstehen, ob eine Sprache wie Scala eine brauchbare vollständige Typinferenz haben kann, müssen wir uns keine Sorgen um die JVM machen. In der Tat wird das Nachdenken über die JVM ein besseres Verständnis der Typinferenz beeinträchtigen. Deshalb ist die Abstraktion der Berechnung in winzige Kernkalküle wichtig und mächtig.

Sie können sich also die Programmiersprachenforschung als einen riesigen Sandkasten vorstellen, in dem Menschen mit Spielzeug spielen. Wenn sie beim Spielen mit einem bestimmten Spielzeug etwas Interessantes finden und das Spielzeug gründlich untersucht haben, beginnt dieses interessante Spielzeug seinen langen Weg in Richtung industrieller Akzeptanz . Ich sage einen langen Marsch, weil Sprachmerkmale, die zuerst von Programmiersprachenforschern erfunden wurden, Jahrzehnte dauern, bis sie allgemein akzeptiert werden. Zum Beispiel wurde die Speicherbereinigung in den 1950er Jahren konzipiert und in den 1990er Jahren mit Java weit verbreitet. Pattern Matching stammt aus dem Jahr 1970 und ist erst seit Scala weit verbreitet.

Prozessrechnung ist ein besonders interessantes Spielzeug. Aber es ist zu neu, um gründlich untersucht zu werden. Das wird ein weiteres Jahrzehnt reiner Forschung dauern. Was derzeit in der prozesstheoretischen Forschung vor sich geht, ist, die größte Erfolgsgeschichte der Programmiersprachenforschung, die Theorie der (sequentiellen) Typen, aufzugreifen und die Theorie der Typen für die gleichzeitige Nachrichtenübermittlung zu entwickeln. Typisierungssysteme mit mäßiger Expressivität für die sequentielle Programmierung, so Hindley-Milner, sind mittlerweile gut verstanden, allgegenwärtig und werden von arbeitenden Programmierern akzeptiert. Wir möchten mäßig ausdrucksstarke Typen für die gleichzeitige Programmierung haben. Die Forschung dazu begann in den 1980er Jahren von Pionieren wie Milner, Sangiorgi, Turner, Kobayashi, Honda und anderen, die häufig explizit oder implizit auf der Idee der Linearität beruhten, die aus der linearen Logik stammt. In den letzten Jahren hat die Aktivität stark zugenommen, und ich gehe davon aus, dass sich dieser Aufwärtstrend auf absehbare Zeit fortsetzen wird. Ich erwarte auch, dass diese Arbeit in produktorientierte Forschung und Entwicklung einfließt, teilweise aus dem pragmatischen Grund, dass junge Forscher, die in Prozessrechnung geschult wurden, in industrielle Forschungs- und Entwicklungslabors gehen werden, aber auch aufgrund der Entwicklung der CPU- und Computerarchitektur weg aus sequentiellen Berechnungsformen.

Zusammenfassend würde ich mir keine Sorgen machen, dass Sie die neueste Theorie der Programmiersprache wie die Prozessrechnung nicht für Ihre eigene Arbeit beim Erstellen von Sprachen nützlich finden. Das liegt einfach daran, dass die Spitzentheorie die Bedenken der aktuellen Programmiersprachen nicht berücksichtigt. Es geht um zukünftige Sprachen. Es wird eine Weile dauern, bis die "reale Welt" aufholt. Das Wissen, mit dem Sie heute Sprachen erstellen, ist die Programmiersprachtheorie der Vergangenheit. Ich ermutige Sie, mehr über Prozessrechnung zu erfahren, da dies einer der spannendsten Bereiche der gesamten theoretischen Informatik ist.

Martin Berger
quelle
1
Beeindruckend! Wie lange hat es gedauert, dieses Diagramm zu erstellen, und kann ich es in Zukunft verwenden?
Cody
1
@cody Hat mit OmniGraffle ein paar Sekunden gedauert und kann es gerne verwenden.
Martin Berger
8

Die Wissenschaft des Programmiersprachen-Designs steckt noch in den Kinderschuhen. Die Theorie (die Untersuchung der Bedeutung von Programmen und der Ausdruckskraft einer Sprache) und der Empirismus (was Programmierer verwalten oder nicht schaffen) liefern viele qualitative Argumente, um beim Entwerfen einer Sprache auf die eine oder andere Weise abzuwägen. Wir haben jedoch selten einen quantitativen Grund, uns zu entscheiden.

Es gibt eine Verzögerung zwischen dem Zeitpunkt, zu dem sich eine Theorie so stabilisiert, dass eine Innovation in einer praktischen Programmiersprache verwendet werden kann, und dem Zeitpunkt, zu dem diese Innovation in „Mainstream“ -Sprachen erscheint. Beispielsweise kann gesagt werden, dass die automatische Speicherverwaltung mit Speicherbereinigung Mitte der 1960er Jahre für den industriellen Einsatz ausgereift war, aber erst 1995 mit Java den Mainstream erreicht hat. Der parametrische Polymorphismus wurde Ende der 1970er Jahre gut verstanden und hergestellt in Java Mitte der 200er Jahre. Auf der Skala der Karriere eines Forschers sind 30 Jahre eine lange Zeit.

Die weitgehende industrielle Übernahme einer Sprache ist Sache der Soziologen, und diese Wissenschaft steckt noch in den Kinderschuhen. Marktüberlegungen sind ein wichtiger Faktor - wenn Sun, Microsoft oder Apple eine Sprache pushen, hat dies viel mehr Auswirkungen als eine beliebige Anzahl von POPL- und PLDI-Papieren. Selbst für einen Programmierer, der die Wahl hat, ist die Verfügbarkeit von Bibliotheken in der Regel weitaus wichtiger als das Sprachdesign. Das heißt nicht, dass Sprachdesign nicht wichtig ist: Eine gut gestaltete Sprache ist eine Erleichterung! Es ist einfach normalerweise nicht der entscheidende Faktor.

Prozesskalküle befinden sich noch in einem Stadium, in dem sich die Theorie nicht stabilisiert hat. Wir glauben, dass wir sequentielle Berechnungen verstehen - alle Modelle von Dingen, die wir gerne als sequentielle Berechnung bezeichnen, sind gleichwertig (das ist die These von Church-Turing). Dies gilt nicht für die Parallelität: Unterschiedliche Prozesskalküle weisen tendenziell subtile Unterschiede in der Ausdruckskraft auf.

Prozesskalküle haben praktische Auswirkungen. Viele Berechnungen sind verteilt - sie umfassen Clients, die mit Servern sprechen, Server, die mit anderen Servern sprechen usw. Selbst lokale Berechnungen werden sehr oft mit mehreren Threads ausgeführt, um die Parallelität über mehrere Prozessoren zu nutzen und auf die Parallelität der Umgebung zu reagieren (Kommunikation mit unabhängigen Programmen) und mit dem Benutzer).

Sind Forschungsfortschritte erforderlich, um bessere Software zu entwickeln? Immerhin gibt es da draußen eine Milliarden-Dollar-Industrie, die den Pi-Kalkül nicht von einem Kuchen am Himmel unterscheiden kann. Andererseits gibt diese Branche Milliarden von Dollar aus, um Fehler zu beheben.

"Werden sie jemals gebraucht?" Ist in der Forschung niemals eine lohnende Frage. Es ist unmöglich, im Voraus vorherzusagen, was langfristige Konsequenzen haben wird. Ich würde sogar noch weiter gehen und sagen, dass es eine sichere Annahme ist, dass jede Forschung eines Tages Konsequenzen haben wird - wir wissen zu diesem Zeitpunkt einfach nicht, ob dieser Tag nächstes Jahr oder nächstes Jahrtausend kommen wird.

Gilles 'SO - hör auf böse zu sein'
quelle
3

Ich sehe so viele Varianten des Pi-Kalküls da draußen und es gibt viel aktive Forschung, aber werden sie jemals benötigt oder haben wichtige Anwendungen?

Der Grund, warum ich frage, ist, dass ich es liebe, Programmiersprachen zu entwickeln, und das wahre Endziel wäre, die Theorie zu verwenden, um tatsächlich einen PL zu erstellen. Für das, was ich geschrieben habe, gab es überhaupt keine Korrelation zur Theorie.

Das ist eine knifflige Frage! Ich werde Ihnen meine persönliche Meinung sagen und ich betone, dass dies meine Meinung ist .

Ich denke nicht, dass pi-calculus direkt als Notation für die gleichzeitige Programmierung geeignet ist. Ich denke jedoch, dass Sie es auf jeden Fall studieren sollten, bevor Sie eine gleichzeitige Programmiersprache entwerfen. Der Grund ist, dass Pi-Kalkül ein niedriges Niveau ergibt - aber vor allem kompositorisch! --- Konto der Parallelität. Infolgedessen kann es alles ausdrücken, was Sie wollen, aber nicht immer bequem.

Um diesen Kommentar zu erklären, müssen Sie ein wenig über Typen nachdenken. Erstens benötigen nützliche Programmiersprachen im Allgemeinen eine Art Typdisziplin, um Abstraktionen zu erstellen. Insbesondere benötigen Sie einen Funktionstyp, um beim Erstellen von Software prozedurale Abstraktionen verwenden zu können.

Nun ist die natürliche Typdisziplin des Pi-Kalküls eine Variante der klassischen linearen Logik. Siehe zum Beispiel Abramskys Artikel Process Realizability , der zeigt, wie Sie einfache gleichzeitige Programme als Beweis für Sätze aus der linearen Logik interpretieren. (Die Literatur enthält viel Arbeit über Sitzungstypen zum Eingeben von Pi-Calculus-Programmen, aber Sitzungstypen und lineare Typen sind sehr eng miteinander verbunden.)

ABAB

Dies ist aus der POV-Typentheorie in Ordnung, aber beim Programmieren umständlich. Der Grund dafür ist, dass Programmierer nicht nur ihre Funktionsaufrufe, sondern auch den Aufrufstapel verwalten. (In der Tat sehen Codierungen von Lambda-Kalkül in Pi-Kalkül normalerweise wie CPS-Transformationen aus.) Durch das Tippen wird sichergestellt, dass dies niemals vermasselt wird, aber dennoch wird dem Programmierer viel Buchhaltung aufgezwungen.

Dies ist kein Problem, das nur in der Parallelitätstheorie auftritt - der Mu-Kalkül bietet eine gute beweistheoretische Darstellung von sequentiellen Steuerungsoperatoren wie call / cc, aber zu dem Preis, den Stapel explizit zu machen, was ihn zu einer umständlichen Programmiersprache macht.

Wenn Sie also eine gleichzeitige Programmiersprache entwerfen, sollten Sie meiner Meinung nach Ihre Sprache mit übergeordneten Abstraktionen als dem rohen Pi-Kalkül entwerfen, aber Sie sollten sicherstellen, dass sie sauber in einen vernünftigen typisierten Prozesskalkül übersetzt wird. (Ein schönes aktuelles Beispiel hierfür sind die Prozesse, Funktionen und Sitzungen höherer Ordnung von Tonhino, Caires und Pfenning : Eine monadische Integration .)

Neel Krishnaswami
quelle
In welchem ​​Sinne müssen Sie den Aufrufstapel in -calculus verwalten? Dies geschieht automatisch in Milners Codierung von in und auch in der neuen Van Bakel / Vigliotti-Codierung. Funktionen sind eine vollkommen feine Form von syntaktischem Zucker in -calculus. πλππ
Martin Berger
Außerdem ist der Kalkül ein wirklich umständlicher Bericht über sequentielle Steuerungsoperatoren wie call / cc. Solche Operatoren werden im -caluclus viel einfacher und natürlicher ausgedrückt , da das Springen eindeutig eine Form der Nachrichtenübermittlung ist. -calculus hat keinen natürlichen Namensbegriff, zu dem Sie springen können. Sie müssen ihn daher als Funktionsanwendung codieren oder zusätzliche Elemente hinzufügen. λμπλ
Martin Berger
Eine fruchtbare Art, über Funktionen nachzudenken, besteht darin, dass es sich um Client-Server-Interaktionen handelt, bei denen der Rückkanal affin ist und der Serverkanal repliziert wird. Dies kann leicht eingegeben werden. Sitzungstypen erfassen dies nicht vollständig, da sie hinsichtlich der von ihnen erzwungenen Interaktionsbeschränkungen etwas zu schwach sind.
Martin Berger
Alles in allem möchte man natürlich nicht mehr in raw -calculus programmieren als in raw -calculus. Beide Formalismen sind Vereinfachungen, die es uns ermöglichen, uns auf einige Merkmale der Berechnung zu konzentrieren, die ausschließlich anderen vorbehalten sind. πλ
Martin Berger
@ MartinBerger: Ich hatte gehofft, Sie zu überzeugen, zu antworten! Ich meine, wenn Sie in raw programmieren und auch Funktionen verwenden möchten, schreiben Sie am Ende Begriffe, die im Bild der Milner-Übersetzung enthalten sind, und müssen daher "den Stapel verwalten". in dem Sinne, dass Sie im Wesentlichen Fortsetzungen und explizite Ersetzungen verwalten würden. (Abgesehen davon wusste ich nichts über das Papier von van Bakel / Vigliotti - danke!)π
Neel Krishnaswami
1

Sie sagen, dass "das wahre Endziel darin besteht, die Theorie zu verwenden, um tatsächlich einen PL zu erstellen." Sie geben also vermutlich zu, dass es andere Ziele gibt?

Aus meiner Sicht besteht der Hauptzweck der Theorie darin, Verständnis zu vermitteln, das darin bestehen kann, über vorhandene Programmiersprachen sowie die darin geschriebenen Programme nachzudenken. In meiner Freizeit verwalte ich eine große Software, einen E-Mail-Client, der vor langer Zeit in Lisp geschrieben wurde. Alle mir bekannten PL-Theorien wie Hoare-Logik, Trennungslogik, Datenabstraktion, relationale Parametrizität und kontextbezogene Äquivalenz usw. sind in der täglichen Arbeit nützlich. Wenn ich zum Beispiel die Software um eine neue Funktion erweitere, weiß ich, dass sie die ursprüngliche Funktionalität beibehalten muss, was bedeutet, dass sie sich in allen alten Kontexten gleich verhalten sollte, auch wenn sie etwas Neues bewirken wird neue Kontexte. Wenn ich nichts über kontextbezogene Äquivalenz wüsste, wäre ich wahrscheinlich nicht einmal in der Lage, das Problem auf diese Weise zu erfassen.

Bei Ihrer Frage zu Pi-Calculus denke ich, dass Pi-Calculus noch etwas zu neu ist, um Anwendungen im Sprachdesign zu finden. Auf der Wikipedia-Seite zu pi-calculus werden BPML und occam-pi als Sprachdesigns mit pi-calculus erwähnt. Sie können sich aber auch die Seiten des Vorgängers CCS und andere Prozesskalküle wie CSP, Join Calculus und andere ansehen, die in vielen Programmiersprachenentwürfen verwendet wurden. Sie können auch im Abschnitt "Objekte und Pi-Kalkül" des Sangiorgi- und Walker-Buches nachsehen , wie sich Pi-Kalkül auf vorhandene Programmiersprachen bezieht.

Uday Reddy
quelle
0

Ich suche gerne nach praktischen Implementierungen von Prozesskalkülen in freier Wildbahn :) (neben dem Lesen über die Theorie).

  1. Asynchrone Kanäle von Clojure basieren auf CSP: http://clojure.com/blog/2013/06/28/clojure-core-async-channels.html
  2. Golang hat auch Kanäle, die auf CSP basieren (dieser inspirierte Rich Hickey für Clojure, glaube ich): http://www.informit.com/articles/printerfriendly/1768317
  3. Es gibt einen Typen, der eine ACP-basierte Erweiterung für Scala (Index) erstellt hat, aber ich habe nicht genug Ruf, um den Link zu veröffentlichen ...

usw.

Yen wel
quelle