Was sind inszenierte Funktionen (konzeptionell)?

24

In einem kürzlich erschienenen CACM-Artikel [1] präsentieren die Autoren eine Implementierung für inszenierte Funktionen . Sie verwenden den Begriff so, als ob er bekannt wäre, und keine der Referenzen scheint eine offensichtliche Einführung zu sein.

Sie geben eine kurze Erklärung (Betonung meiner und Referenznummer geändert; es ist 22 im Original)

Im Rahmen der Programmerstellung können Programmierer durch mehrstufige Programmierung (MSP, Staging for Short) nach Taha und Sheard [2] die Auswertung eines Programmausdrucks explizit auf eine spätere Stufe verschieben (also einen Ausdruck inszenieren). Die vorliegende Stufe fungiert effektiv als Codegenerator, der das Programm der nächsten Stufe zusammenstellt (und möglicherweise ausführt).

Taha und Sheard schreiben jedoch (Hervorhebung meiner):

Ein mehrstufiges Programm umfasst das Generieren, Kompilieren und Ausführen von Code innerhalb desselben Prozesses. Mehrstufige Sprachen drücken mehrstufige Programme aus. Die Bereitstellung und folglich die mehrstufige Programmierung sprechen die Notwendigkeit von Allzwecklösungen an, bei denen sich der Aufwand für die Laufzeitinterpretation nicht lohnt.

Sie führen dann mehrere Verweise auf ältere Arbeiten an, die angeblich zeigen, dass die Inszenierung effektiv ist, was darauf hindeutet, dass das Konzept noch älter ist. Sie geben keine Referenz für den Begriff an sich.

Diese Aussagen scheinen orthogonal zu sein, wenn nicht sogar widersprüchlich. Vielleicht ist das, was Rompf und Odersky schreiben, eine Anwendung dessen, was Taha und Sheard vorschlagen, aber vielleicht ist es eine andere Perspektive auf dasselbe. Sie scheinen sich darin einig zu sein, dass ein wichtiger Punkt darin besteht, dass Programme Teile von sich zur Laufzeit (neu) schreiben, aber ich weiß nicht, ob dies eine notwendige und / oder ausreichende Fähigkeit ist.

Was ist Inszenierung bzw. Interpretation von Inszenierung in diesem Kontext? Woher kommt der Begriff?


  1. Lightweight Modular Staging: Ein pragmatischer Ansatz zur Generierung von Laufzeitcode und kompilierten DSLs von T. Rompf und M. Odersky (2012)
  2. MetaML und mehrstufige Programmierung mit expliziten Anmerkungen von W. Taha und T. Sheard (2000)
Raphael
quelle
Welchen Widerspruch sehen Sie zwischen den beiden Aussagen? Für mich sehen sie so aus, als würden sie über dasselbe reden, mit unterschiedlicher Betonung.
Gilles 'SO- hör auf böse zu sein'
@Gilles Ich brauche keine Runtime-Code-Generierung / -Kompilierung, um die Auswertung von etwas zu verzögern (siehe continuables). Es kann sehr gut sein, dass es nur ein weiterer Schwerpunkt ist (ich gebe diese Option in der Frage zu), aber ich kann nicht wirklich sagen.
Raphael
Die Dokumentation zur Implementierung der Programmiersprache Julia und zur Metaprogrammierung finden Sie unter @generated functions: julia.readthedocs.org/en/latest/manual/metaprogramming/…
SalchiPapa

Antworten:

21

Meines Wissens wurde der Begriff Inszenierte Berechnung von Bill Scherlis zum ersten Mal in dieser Arbeit verwendet . Zuvor wurde der Begriff " Teilevaluierung " für fast dasselbe Konzept verwendet, aber die Idee der Stufenberechnung unterscheidet sich geringfügig. Beide Ideen beziehen sich auf Kleenes Satz von Smn .

Wenn Sie eine Funktion aus zwei Argumenten haben, aber ein Argument kennen, beispielsweise , können Sie einen Teil der Berechnung der Funktion sofort mit dem Wissen des ersten Arguments ausführen. Ihnen bleibt dann eine Funktion deren Berechnungen nur vom zweiten, unbekannten Argument abhängen.m ϕ m ( n )ϕ(m,n)mϕm(n)

Die Idee der partiellen Auswertung besteht darin, die spezialisierte Funktion automatisch zu berechnen . Angesichts der Code für die ursprüngliche Funktion , Teilbewertung hat statische Analyse , um zu bestimmen , welche Bits des Codes ist abhängig von und welche Bits hängen von , und wandelt sie zu einer Funktion , die, gegeben , Konstrukte . Das zweite Argument kann dann dieser spezialisierten Funktion zugeführt werden.ϕϕm(n) ϕn ' m m nmnϕmϕmn

Die Idee der inszenierten Berechnung besteht darin, zuerst über die Funktion nachzudenken . Es wird eine "inszenierte" Funktion genannt, da es in mehreren Stufen arbeitet. Sobald wir ihm das erste Argument , konstruiert er den Code für die spezialisierte Funktion . Dies ist die "erste Stufe". In der zweiten Stufe wird das zweite Argument an der den Rest der Arbeit erledigt. m ϕ m ϕ mϕmϕmϕm

So ist die Aufgabe der Teilauswertung ist den Code für eine gewöhnliche Funktion zu transformieren zu einer Funktion inszenierte . Scherlis ging davon aus, dass diese Transformation durch allgemeinere Mechanismen als die früheren partiellen Bewertungsmethoden erfolgen könnte. Das Thema "Stufenberechnung" befasst sich nun mit Themen wie:ϕ ϕϕ

  • Wie definiere ich inszenierte Funktionen?
  • Welche Programmiersprachen und Typsysteme sollten zur Definition von inszenierten Funktionen verwendet werden?
  • Was ist die Semantik solcher Sprachen?
  • Wie stellen wir die Kohärenz und Korrektheit von inszenierten Funktionen sicher?
  • Welche Techniken eignen sich zum automatischen oder halbautomatischen Erstellen von inszenierten Funktionen?
  • Wie beweisen wir die Richtigkeit solcher Techniken?

Stufenberechnung kann in der Praxis sehr wichtig sein. Tatsächlich ist jeder Compiler eine inszenierte Berechnung. Ausgehend von einem Quellprogramm wird ein übersetztes und optimiertes Zielprogramm erstellt, das dann die tatsächlichen Eingaben übernimmt und das Ergebnis berechnet. In der Praxis ist es schwierig, gestufte Berechnungsprogramme zu schreiben, da wir die verschiedenen Phasen aufeinander abstimmen und sicherstellen müssen, dass die richtigen Dinge zur richtigen Zeit erledigt werden. Jeder, der einen Compiler geschrieben hat, hat mit solchen Problemen zu kämpfen. Es ist auch schwierig, Programme zu schreiben, die andere Programme schreiben. Dies können maschinensprachliche Programme (Compiler), SQL-Abfragen (Datenbankmanipulationen) oder HTML / Server Pages / Javascript-Code (Webanwendungen) und unzählige andere Anwendungen sein.

Uday Reddy
quelle
So weit ich sehen kann, ist der Unterschied zwischen der gestuften Berechnung und der teilweisen Auswertung die Form von ? (Es gibt einige , die aus einer gestuften Berechnung erhalten werden können, aber nicht aus einer teilweisen Auswertung). ϕ ϕϕ
Ta Thanh Dinh
Sie meinen also, dass partielle Evaluierung eine Abstraktion über mehrstufige Programmierung ist, was bedeutet, dass partielle Evaluierung keine mehrstufige Programmierung impliziert, sondern dass mehrstufige Programmierung partielle Evaluierung impliziert. Wobei eine Teilevaluierung ein- oder mehrstufig erfolgen kann, da das Erlernen in funktionalen Sprachen nicht unbedingt mehrstufig ist und zur Laufzeit Code generiert wird, oder?
Denis631
1
Nicht genau. Ein Teilevaluator kompiliert ein normales Programm zu einem zweistufigen Programm und führt dann seine erste Stufe aus. Bei der inszenierten Programmierung schreiben Sie das mehrstufige Programm selbst.
Uday Reddy
9

Obwohl die anderen Antworten technisch korrekt sind, geben sie meiner Meinung nach kein korrektes Verständnis dafür, warum Informatiker an inszenierten Funktionen interessiert sind.

Durch das Erstellen von bereitgestellten Funktionen definieren Sie Programme, die Programme generieren. Eines der großen Ziele der modernen praktischen Sprachtheorie ist die Maximierung des Wiederverwendungspotenzials. Wir möchten es ermöglichen, Bibliotheken zu schreiben, die nicht nur nützliche Funktionen und Objekte sind, sondern Programmierern helfen, indem sie Architekturkonstruktionen höherer Ordnung bereitstellen.

Es wäre großartig, wenn wir den gesamten Kesselcode loswerden könnten. Wir sollten in der Lage sein, die Spezifikationssprache zu minimieren. Wenn wir beispielsweise einen ereignisgesteuerten Dispatcher wünschen, der mit einem bestimmten Thread-Design mit anderen Dispatchern kommuniziert, sollten wir dies kompakt spezifizieren können, und alle E / A-Listener sowie Warteschlangenobjekt- und Thread-Verbindungen sollten aus dieser Spezifikation aufgebaut werden können.

Domänensprachen sind in der Regel die kompakten Darstellungen, nach denen wir suchen. Wenn Personen eine Zeit lang in einer Domäne arbeiten, kann die Sprache, die sie verwenden, die meisten Informationen verdoppeln und zu einer schlanken Spezifikation werden. Diese Inszenierungstheorie tendiert also dazu, ein Übersetzungssystem von Domänensprachen in die Ausführungssprache zu werden.

Compiler sind technisch gesehen Hasen, aber es verfehlt das Ziel. Das Ziel des modernen Staging ist es, die Erstellung von Programmen zu ermöglichen, um die Wiederverwendung zu maximieren und die Programmerstellung zu automatisieren, wo immer dies möglich ist. Es wäre toll, wenn eines Tages funktionale Anforderungen eines Programms das Programm sind.

Siehe "Generative Programming" von Czarnecki und Eisenecker (ISBN-13: 978-0201309775).

ex0du5
quelle
@Raphael: Hier ist Kapitel drei mit den Grundlagen zu Domänen und Wiederverwendung. Schauen Sie sich auch die Optimierung an, die Sie erwähnen. FFT wird nicht durch Staging ausgeführt, um die Ausführung zu beschleunigen. Dies geschieht, damit der Programmierer die Wertetabelle nicht jedes Mal von Hand berechnen, in das Programm kopieren und eine große Liste erstellen muss. Es geht darum, die geleistete Arbeit zu minimieren und die grundlegenden Schritte wiederzuverwenden. Gleiches gilt für das Abrollen der Schleife. Wenn Sie es von Hand tun, werden die Informationen wiederholt und können nicht wiederverwendet werden.
Ex0du5
Diese DSL-Sichtweise scheint das Staging auf eine Ebene zu beschränken (einen DSL-Compiler im Programm), oder?
Raphael
1
@Raphael: Es kommt wirklich auf deinen Standpunkt an. Offensichtlich fügt das Konzept keine Rechenleistung hinzu, wenn es einfach als Quelle -> ausführbare Übersetzung betrachtet wird. Wir könnten einfach einen Compiler für die DS-Sprache erstellen und fertig sein. Woher seine Stärke kommt, liegt in der Iteration. Wenn Sie Bibliotheken erstellen, die in Zukunft von Projekten verwendet und erweitert werden, erscheinen natürliche Phasen innerhalb der Bibliotheksgrenzen. Möglicherweise verfügen Sie über eine Bibliothek, die Objektspezifikationen für die vollständige Serialisierung in eine Quelle umwandelt, und anschließend über eine weitere Bibliothek, die die Transportschicht erstellt, die auf einigen Versandspezifikationen
basiert
1
@Raphael: Die Inszenierung kann natürlicher aus mehreren Stufen bestehen. Wenn sich die Anforderungen eines Codeteils im Laufe der Zeit stark geändert haben, während andere wesentlich stabiler sind, kann es aufgrund von "Shearing Layern" angebracht sein, das Staging in Layer mit stabileren Schnittstellen zu unterteilen. Sie können dann mit Änderungen weniger auf das System einwirken und eine Inszenierungsform des Open-Closed-Prinzips einhalten. Das sind praktische Anliegen, die keine mathematische Notwendigkeit haben, aber alles basiert auf Praktikabilität. Wir wollen keine einzige Compilersprache, wir wollen Evolution zulassen.
ex0du5
5

Die Antwort findet sich in der technischen Perspektive des betreffenden Artikels [1]. Das betrachtete Problem ist das Spannungsfeld zwischen allgemeinem und spezifischem Code:

Programme können für allgemeine oder spezielle Zwecke geschrieben werden. Allgemeiner Code hat den Vorteil, dass er in einer Vielzahl von Situationen verwendet werden kann, wohingegen Spezialcode so geschrieben werden kann, dass er die einzigartigen Merkmale der Ausführungsumgebung ausnutzt und auf Kosten der Wiederverwendbarkeit effizienter wird.

Natürlich wollen wir diese Spannung lösen, dh allgemeinen Code und spezifische Implementierung erreichen:

Wir können die Frage stellen: Ist es möglich, Code für allgemeine Zwecke zu schreiben, der sich dann jedoch automatisch auf die jeweilige Situation während der Ausführung spezialisiert?

Dies hat zu der Idee geführt, dass sich (allgemeine) Programme zur Laufzeit (neu) schreiben, um einer bestimmten Situation gerecht zu werden:

Ein wichtiger Forschungsschwerpunkt war daher die Suche nach Sprach- und Compilertechnologien, mit denen Programmierer Universalcode schreiben können, der zur Laufzeit korrekt und effizient in hochleistungsfähigen Spezialcode umgewandelt wird.

Ich denke, Javas JIT ist ein gutes Beispiel. Eine besondere Idee ist die mehrstufige Programmierung, die Lee folgendermaßen erklärt:

Eine der Kernideen dieser Forschungsrichtung ist das Konzept der Inszenierung. Wir stellen uns die Ausführung eines Programms vor, das in einer Reihe von Stufen abläuft, wobei jede Stufe Werte berechnet, die von späteren Stufen verwendet werden. Was wir also suchen, ist, den Programmcode so zu schreiben, dass diese Phasen irgendwie sichtbar werden. Wenn dies erreicht ist, können wir veranlassen, dass der Code der späteren Stufe in Codegeneratoren kompiliert wird, die gegen die Ergebnisse von Berechnungen der früheren Stufe optimiert werden.

Das heißt, "Staging" ist eine Betrachtung geeigneter Funktionen / Codes, die Phasen in der Berechnung / Ausführung identifizieren, die vereinfacht werden können, wenn die Ergebnisse früherer Phasen bekannt sind. "Verzögerung" der Berechnung wie im ersten Zitat in der Frage kann ein notwendiger Nebeneffekt sein, um die Stufen richtig zu trennen, aber es ist nicht der Punkt.

Rompf und Odersky erwähnen die schnelle Fouriertransformation als ein Beispiel, das lehrreich sein kann.


  1. Der Fuchs und der Igel: technische Perspektive von Peter Lee (2012)
Raphael
quelle