Gibt es einen Standard-Umgang mit der Interaktion zwischen separater Kompilierung und verschiedenen Arten der Abschlusskonvertierung beim Kompilieren von Funktionsaufrufen höherer Ordnung?
Ich kenne drei funktionsähnliche Konstrukte, die in den meisten Programmiersprachen eindeutig kompiliert sind: Closures, (Top-Level-) Funktionen und C ++ - Style-Funktionsobjekte. Syntaktisch werden sie auf die gleiche Weise aufgerufen, aber ein Compiler würde optimal Callsites in bestimmter Form generieren:
%Vor% (In C ++ wäre cls_call T::operator() für obj 's Klasse T . C ++ erlaubt auch virtuelle Funktoren, aber das ist im Wesentlichen der Schließungsfall mit einer zusätzlichen Indirektion.)
An diesem Punkt sollten Aufrufe von map (x => x > 3) lst und map (x => x > y) lst verschiedene map -Funktionen aufrufen, weil der erste ein einfacher Funktionszeiger nach dem Hochziehen ist und der zweite ein Abschluss.
Ich kann mir vier Arten vorstellen, mit diesem Thema umzugehen:
Der C ++ (98) -Ansatz, der den Aufrufer dazu zwingt, entweder eine Form einer Aufrufseite (über den formalen Parametertyp: virtueller Funktor, Funktionszeiger oder nicht virtueller Funktor) auszuwählen oder die separate Kompilierung mit a zu löschen Vorlage, die Lösung 2 unten effektiv spezifiziert.
Überladen: Der Compiler könnte mehrere Instanziierungen von map und allen anderen Funktionen höherer Ordnung mit entsprechenden Namensänderungen durchführen. In der Tat gibt es einen separaten internen Funktionstyp pro Aufrufstandortform, und die Überladungsauflösung wählt den richtigen aus.
Vergeben Sie eine global einheitliche Call-Site-Form. Dies bedeutet, dass alle Funktionen der obersten Ebene ein explizites env -Argument haben, auch wenn sie es nicht benötigen, und dass "zusätzliche" Closures eingeführt werden müssen, um nicht geschlossene Argumente zu umbrechen.
Behalten Sie die "natürliche" Signatur für Funktionen auf oberster Ebene bei, schreiben Sie jedoch vor, dass die gesamte Verarbeitung von Funktionsparametern höherer Ordnung durch Sperrungen erfolgen muss. Die "zusätzlichen" Schließungen für bereits geschlossene Funktionen rufen eine Wrapper-Trampolin-Funktion auf, um den nicht verwendeten env -Parameter zu verwerfen. Dies scheint eleganter als Option 3, aber schwieriger effizient zu implementieren. Entweder erzeugt der Compiler eine Vielzahl von Wrappern, die auf der Grundlage von Aufrufkonventionen unabhängig sind, oder er verwendet eine kleine Anzahl von auf Aufrufkonventionen reagierenden Thunks ...
Nachdem wir ein optimiertes Schema für die Umwandlung von Schließungskonvertierung und Lambda-Hub entwickelt haben, scheint es, als würde das Problem akuter werden.
>Wie auch immer, Fragen:
Das ist eine ziemlich tiefe Frage mit vielen Verzweigungen, und ich möchte hier keinen wissenschaftlichen Artikel schreiben. Ich kratze nur an der Oberfläche und werde Sie an anderer Stelle auf weitere Informationen hinweisen. Ich stütze meine Antwort auf persönliche Erfahrungen mit dem Glorious Haskell Compiler und mit Glorious Glasgow Haskell Compiler . smlnj.org/">Standard ML of New Jersey , sowie wissenschaftliche Artikel über diese Systeme geschrieben.
Die wichtigste Unterscheidung in einem ambitionierten Compiler ist die Unterscheidung zwischen bekannten Aufrufen und unbekannten Aufrufen. Für Sprachen mit Funktionen höherer Ordnung ist eine sekundäre, aber dennoch wichtige Unterscheidung, ob der Aufruf voll gesättigt ist (was wir nur an einer bekannten Call-Site entscheiden können).
Ein bekannter Aufruf bedeutet eine Aufrufstelle, an der der Compiler genau weiß, welche Funktion aufgerufen wird und wie viele Parameter er erwartet.
Ein unbekannter Aufruf bedeutet, dass der Compiler nicht herausfinden kann, welche Funktion aufgerufen werden könnte.
Ein bekannter Aufruf ist voll gesättigt , wenn die aufgerufene Funktion alle erwarteten Parameter erhält und direkt in den Code geht. Wenn die Funktion weniger Argumente erhält als erwartet, wird die Funktion teilweise angewendet und der Aufruf führt nur zur Zuweisung eines Abschlusses
Zum Beispiel, wenn ich die Haskell-Funktionen schreibe
%Vor% dann ist der Aufruf von map bekannt und vollständig gesättigt .
Wenn ich schreibe
dann ist der Aufruf von map bekannt und teilweise angewendet .
Zum Schluss, wenn ich schreibe
Dann sind die Aufrufe von f und g beide unbekannt .
Das Wichtigste, was reife Compiler tun, ist bekannte Aufrufe optimieren . In Ihrer obigen Klassifikation fällt diese Strategie meist unter # 2.
Wenn all Sites zu einer Funktion aufgerufen werden, erstellt ein guter Compiler eine spezielle Aufrufkonvention nur für diese Funktion, zB die Übergabe von Argumenten in genau den richtigen Registern Dinge funktionieren gut.
Wenn einige, aber nicht alle Aufrufseiten einer Funktion bekannt sind, könnte der Compiler entscheiden, dass es sinnvoll ist, eine spezielle Aufrufkonvention für die bekannten Aufrufe zu erstellen, die entweder inline sind oder wird einen speziellen Namen verwenden, der nur dem Compiler bekannt ist. Die Funktion, die unter dem Namen im Quellcode exportiert wird, verwendet eine Standard Aufrufkonvention, und ihre Implementierung ist typischerweise die dünne Schicht, die einen optimierten Endanruf an die spezialisierte Version macht.
Wenn ein bekannter Aufruf nicht vollständig gesättigt ist, generiert der Compiler nur Code, um den Abschluss dort im Aufrufer zuzuweisen.
Die Darstellung von Closures (oder ob erstklassige Funktionen durch eine andere Technik wie Lambda-Lifting oder Defunktionalisierung behandelt werden) ist weitgehend orthogonal zur Behandlung bekannter gegen unbekannter Aufrufe.
(Es könnte sich lohnen, einen alternativen Ansatz zu erwähnen, der von MLton verwendet wird: Er ist ein Compiler für ganze Programme; er kann alle sehen Quellcode; es reduziert alle Funktionen auf die erste Ordnung mit einer Technik, die ich vergessen habe. Es gibt noch unbekannte Aufrufe, weil die allgemeine Kontrollflussanalyse in höheren Sprachen nicht handhabbar ist.
Zu Ihren letzten Fragen:
Ich denke, dieses Problem ist nur eine Facette des unordentlichen Problems namens "Wie man erstklassige Funktionen kompiliert". Ich habe noch nie einen speziellen Namen für dieses Problem gehört.
Ja, es gibt andere Ansätze. Ich habe eine skizziert und eine andere erwähnt.
Ich bin mir nicht sicher, ob es großartige, breit angelegte Studien zu Kompromissen gibt, aber die beste, die ich kenne, die ich sehr gut empfehle, ist Machen Sie ein schnelles Curry: Push / Enter vs. Eval / Bewerben für höhere Ordnung Sprachen von Simon Marlow und Simon Peyton Jones. Eines der vielen großartigen Dinge an diesem Papier ist, dass es erklärt, warum der Typ einer Funktion nicht Ihnen sagt, ob ein Aufruf dieser Funktion vollständig gesättigt ist.
Um Ihre nummerierten Alternativen abzuschließen: Nummer 1 ist ein Nicht-Starter. Populäre Compiler verwenden eine Hybridstrategie, die sich auf die Nummern 2 und 3 bezieht. Ich habe noch nie etwas von Nummer 4 gehört; die Unterscheidung zwischen bekannten und unbekannten Aufrufen scheint sinnvoller zu sein als die Unterscheidung von Funktionen der obersten Ebene von den Argumenten des Funktionstyps.
Tags und Links programming-languages compiler-construction functional-programming closures