
 
 
 
 
 
 Die Autoren: David Binder, Universität Tübingen, Deutschland (2) Marco Tzschentke, Universität Tübingen, Deutschland Marius Muller, Universität Tübingen, Deutschland Klaus Ostermann, Universität Tübingen, Deutschland Authors: David Binder, Universität Tübingen, Deutschland (2) Marco Tzschentke, Universität Tübingen, Deutschland Marius Muller, Universität Tübingen, Deutschland Klaus Ostermann, Universität Tübingen, Deutschland Tisch links 
 
 
 
 
 
 
 
 
 
 Introduction 
 
 
 
 
 
 
 
 Translating To Sequent Calculus 2.1 Arithmetic Expressions 2.2 Let Bindings 2.3 Top-level Definitions 2.4 Algebraic Data and Codata Types 2.5 First-Class Functions 2.6 Control Operators 
 
 
 
 Evaluation Within a Context 3.1 Evaluation Contexts for Fun 3.2 Focusing on Evaluation in Core 
 
 
 
 
 Typing Rules 4.1 Typing Rules for Fun 4.2 Typing Rules for Core 4.3 Type Soundness 
 
 
 
 
 
 
 
 
 Insights 5.1 Evaluation Contexts are First Class 5.2 Data is Dual to Codata 5.3 Let-Bindings are Dual to Control Operators 5.4 The Case-of-Case Transformation 5.5 Direct and Indirect Consumers 5.6 Call-By-Value, Call-By-Name and Eta-Laws 5.7 Linear Logic and the Duality of Exceptions 
 
 Related Work 
 
 Conclusion, Data Availability Statement, and Acknowledgments Einführung Typische Regeln Verwandte Arbeiten Schlussfolgerung, Datenverfügbarkeitserklärung und Anerkennungen A. Die Beziehung zum sequentiellen Berechnen B. Typing Regeln für den Spaß C. Operative Semantik von Etiketten / Goto Referenzen 1 Einführung Nehmen wir an, Sie haben gerade Ihre eigene kleine Funktionssprache implementiert.Um es zu testen, schreiben Sie die folgende Funktion, die alle Zahlen in einer Liste multipliziert: Was Sie bei dieser Implementierung beeinträchtigt, ist, dass Sie eine offensichtliche Optimierung kennen: Die Funktion sollte null direkt zurückgeben, wenn sie eine null in der Liste trifft. Es gibt viele Möglichkeiten, dies zu erreichen, aber Sie wählen Ihre Sprache mit markierten Ausdrücken und einer goto-Anweisung zu erweitern. def mult(l)  label α { mult’(l; α) } Hier ist, wie Sie diesen Abschnitt lesen: Neben dem Listenargument l nimmt die Definition def mult(l; α)  . . . ein Argument α, das anzeigt, wie die Berechnung fortgesetzt werden sollte, sobald das Ergebnis der Multiplikation berechnet wird (wir wieder verwenden ; um diese beiden Arten von Argumenten zu trennen). Die Helperfunktion mult’ nimmt ein Listenargument l und zwei Argumente α und β; das Argument β zeigt an, wo die Funktion auf einem normalen Rückruf zurückkehren sollte, während α den Rückkehrpunkt einer Kurzlaufrechnung anzeigt. Im Körper von mult’ verwenden wir l Case {Nil ⇒ . . . , Cons(x, xs) ⇒ . . . .} wird sicherlich einen Fall ausführen, der auf der Liste α und β geteilt Der λμμ ̃-calculus, den Sie gerade gesehen haben, wurde zuerst von Curien und Herbelin [2000] als Lösung für eine langjährige offene Frage eingeführt: Wie sollte eine Begriffssprache für die aufeinanderfolgende Berechnung aussehen? Die aufeinanderfolgende Berechnung ist eine von zwei einflussreichen Beweisberechnungen, die von Gentzen [1935a,b] in einem einzigen Papier eingeführt wurden, wobei die andere Berechnung natürliche Deduktion ist. Die Begriffssprache für die natürliche Deduktion ist die gewöhnliche Lambda-Berechnung, aber es war schwierig, eine gute Begriffssprache für die aufeinanderfolgende Berechnung zu finden. Nachdem sie gefunden worden war, wurde die λμμ ̃-calculus Wir diskutieren oft mit Studenten und Kollegen über Ideen, die den λμμ ̃-calculus betreffen, und müssen sie daher zu seinen zentralen Ideen einführen. Aber wir können den λμμ ̃-calculus normalerweise nicht als ein Begriffszuweisungssystem für die sequentielle Berechnung motivieren, da die meisten von ihnen nicht mit ihm vertraut sind. Wir erklären den λμμ ̃-calculus auf dem Whiteboard stattdessen, indem wir kleine funktionelle Programme darin zusammenstellen. Eine solche Einführung fehlt leider noch in der veröffentlichten Literatur; die meisten bestehenden Präsentationen gehen entweder von der Kenntnis der sequentiellen Berechnung aus oder verbringen anderweitig viel Raum damit, sie zuerst einzuführen. Wir glauben, dass man den lambdaus verstehen kann, ohne zuerst über natürliche Warum sind wir über den λμμ ̃-calculus begeistert, und warum denken wir, dass mehr Menschen mit seinen zentralen Ideen und Konzepten vertraut werden sollten? Das Hauptmerkmal, das den λμμ ̃- Calculus von dem lambda Calculus unterscheidet, ist seine erstklassige Behandlung von Bewertungskontexten. Dies wird mit einem Beispiel klarer: Wenn wir den Ausdruck (2 + 3) ∗ 5 bewerten wollen, müssen wir uns zunächst auf den Unterdruck 2 + 3 konzentrieren und ihn zu seinem Ergebnis bewerten 5. Der Rest des Programms, der nach Abschluss der Bewertung ausgeführt wird, kann mit dem Bewertungskontext □ ∗ 5 dargestellt werden. Wir können keinen direkten Zugang zu einem Bewertungskontext wie □ ∗ 5 zu einem Variablen im Lambda-Typkalkulus haben, aber im λμμ ̃-Kalkulus können wir solche Bewertungskontexe an Covariables binden. Darüber hinaus gibt der μ-Operator direkten Zugang zum Bewertungskontext, in dem der Ausdruck derzeit bewertet wird. Ein solcher direkter Zugang zum Bewertungskontext ist für Der Rest dieses Dokuments ist wie folgt strukturiert: • In Abschnitt 2 stellen wir die Oberflächensprache Fun vor und zeigen, wie wir sie in den Sequenzrechnungs-basierten Sprachkern übersetzen können. Die Oberflächensprache ist hauptsächlich eine ausdrucksorientierte funktionelle Programmiersprache, aber wir haben einige Funktionen wie Codata-Typen und Steuerungsoperatoren hinzugefügt, deren Übersetzungen wichtige Einblicke in die Funktionsweise des λμμ ̃-calculus liefern. • In Abschnitt 3 diskutieren wir statische und dynamische Fokussierung, die zwei eng verwandte Techniken sind, um Subausdrücke, die keine Werte sind, in eine Position zu heben, in der sie bewertet werden können. • Abschnitt 4 führt die Schreibregeln für Fun und Core ein und beweist die Standardergebnisse für das Schreiben und die Auswertung. • Wir zeigen, warum wir über den λμμ ̃-calculus in Abschnitt 5 begeistert sind.Wir präsentieren verschiedene Programmiersprachenkonzepte, die viel klarer werden, wenn wir sie im λμμ ̃-calculus präsentieren: Wir zeigen, dass let-bindings genau doppelt für die Steuerung von Operatoren sind, dass Daten und Codata-Typen zwei vollkommen doppelte Wege sind, Typen zu spezifizieren, und dass die Fall-of-Case-Transformation nichts anderes ist als eine μ-Reduktion. • Schließlich diskutieren wir in Abschnitt 6 die damit verbundenen Arbeiten und geben Hinweise für die weitere Lesung. Dieses Papier wird von einer Haskell-Implementierung begleitet, die wir auch als interaktive Website zur Verfügung stellen (vgl. Abbildung 1). 
 
 Dieses Dokument ist unter der Lizenz CC BY 4.0 verfügbar. Dieses Papier ist unter der CC BY 4.0 Lizenz. Verfügbar im Archiv Verfügbar im Archiv [1] Für den interessierten Leser zeigen wir in Anhang A, wie die sequentielle Berechnung und die λμμ ̃- Berechnung miteinander verbunden sind.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Read My Stories

Abstraction

Dieses Audio ist in der Originalsprache der Geschichte produziert!

Was wäre, wenn Programmiersprachen vorausdenken könnten?

About Author

KOMMENTARE

Hängeetiketten

DIESER ARTIKEL WURDE VORGESTELLT IN

Related Stories

HackerNoon Decoded 2024: Wir feiern unsere Gaming-Community!

HackerNoon Decoded 2024: Celebrating Our Management Community!

Genuine Content Creation in the Age of AI: Why Startups Need Quality Content

HackerNoon Decoded 2024: Wir feiern unsere Remote-Work-Community!

HackerNoon Decoded 2024: Wir feiern unsere Gaming-Community!

HackerNoon Decoded 2024: Celebrating Our Management Community!

Genuine Content Creation in the Age of AI: Why Startups Need Quality Content

HackerNoon Decoded 2024: Wir feiern unsere Remote-Work-Community!

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps