In welchen Sprachen ist die Funktionsabstraktion nicht primitiv?

7

Im Haskell-Funktionstyp ( -> ) ist es kein algebraischer Datentypkonstruktor, und man kann ihn nicht so implementieren, dass er identisch ist mit ( -> ).

Ich frage mich also, in welchen Sprachen kann ich meine Version von ( -> ) schreiben? Wie heißt diese Eigenschaft?

UPD Umformulierung der Frage dank der Diskussion:

Welche Sprachen haben -> nicht als primitiven Typ?

Warum -> ist notwendig primitiv?

    
Yrogirg 30.03.2012, 13:42
quelle

8 Antworten

3

Meinst du meta-zirkuläre Evaluatoren wie in SICP? Du kannst dein eigenes DSL schreiben? Wenn Sie einen eigenen "Funktionstyp" erstellen, müssen Sie selbst darauf achten, ihn "anzuwenden".

Sie könnten beispielsweise Ihre eigene "Funktion" in C erstellen, zum Beispiel mit einer Nachschlagetabelle, die Funktionszeiger enthält, und Ganzzahlen als Funktionen verwenden. Für solche "Funktionen" müssten Sie natürlich Ihre eigene "Call" -Funktion bereitstellen:

%Vor%

Sie möchten wahrscheinlich auch etwas komplexere Funktionen aus primitiven erstellen, zum Beispiel die Verwendung von Arrays von Ints, um die sequenzielle Ausführung Ihrer "primitiven Funktionen" 1, 2, 3, ... zu signalisieren und letztendlich eine ganz neue Sprache für sich selbst zu erfinden.

Ich denke, die frühen Assembler hatten keine Möglichkeit, aufrufbare "Makros" zu erstellen und mussten GOTO verwenden.

Sie könnten Trampolining verwenden, um Funktionsaufrufe zu simulieren. Sie könnten nur globale Variablen speichern, mit seichter Bindung vielleicht. In einer solchen Sprache wären "Funktionen" definierbar, jedoch nicht primitiver Typ.

Es ist also nicht notwendig, Funktionen in einer Sprache zu haben, obwohl es praktisch ist.

In Common Lisp defun ist nichts anderes als ein Makro, das einen Namen und ein aufrufbares Objekt assoziiert (obwohl lambda immer noch eingebaut ist). In AutoLisp gab es ursprünglich keinen speziellen Funktionstyp, und Funktionen wurden direkt in Anführungszeichen von s -Ausdrücken dargestellt, wobei das erste Element eine Argumente -Liste war. Sie können Ihre Funktion durch die Verwendung von cons und list Funktionen aus Symbolen direkt in AutoLisp erstellen:

%Vor%

Einige Sprachen (wie Python) unterstützen mehr als einen primitiven Funktionstyp, jeder mit seinem Aufrufprotokoll - nämlich Generatoren, die mehrfache Wiedereinträge und Rückgaben unterstützen (selbst wenn syntaktisch dasselbe def Schlüsselwort verwendet wird). Sie können sich leicht eine Sprache vorstellen, mit der Sie Ihr eigenes Anrufprotokoll definieren und so neue Funktionstypen erstellen können.

Bearbeiten: Als Beispiel betrachten Sie den Umgang mit mehreren Argumenten in einem Funktionsaufruf, die Wahl zwischen automatischem Currieren oder automatischen optionalen Argumenten usw. In Common LISP sagen Sie, Sie könnten sich leicht zwei verschiedene% co_de erstellen % Makros, um die zwei aufrufenden Protokolle direkt darzustellen. Stellen Sie sich Funktionen vor, die mehrere Werte nicht über einen Klumpen von Aggregaten (Tupel, in Haskell) zurückgeben, sondern direkt in designierte Empfängervariablen / Slots. Alle sind verschiedene Arten von Funktionen.

    
Will Ness 30.03.2012, 14:22
quelle
11

Ich kann mir keine Sprachen vorstellen, die Pfeile als benutzerdefinierten Typ haben. Der Grund dafür ist, dass Pfeile - Typen für Funktionen - in in das Typsystem eingebettet sind, bis hin zum einfach typisierten Lambda-Kalkül. Dass der Pfeiltyp grundlegend für die Sprache sein muss, kommt direkt von der Tatsache, dass die Art, wie Sie Funktionen im Lambda-Kalkül bilden, über eine Lambda-Abstraktion erfolgt (was auf der Typebene Pfeile einführt).

Obwohl Marcin zutreffend feststellt, dass Sie in einem Punkt-freien Stil programmieren können, ändert dies nichts an der Essenz dessen, was Sie tun. Eine Sprache ohne Pfeiltypen als Primitive zu haben, widerspricht den grundlegendsten Bausteinen von Haskell. (Die Sprache, auf die Sie in der Frage verweisen.)

Wenn der Pfeil als primitiver Typ verwendet wird, hat er auch einige wichtige Verbindungen zur konstruktiven Logik: Sie können den Funktionspfeiltyp als Implikation aus der Intuitionslogik und Programme mit diesem Typ als "Beweise" lesen. (Wenn Sie nämlich etwas vom Typ A - & gt; B haben, haben Sie einen Beweis, der eine Prämisse des Typs A annimmt und einen Beweis für B erzeugt.)

Die Tatsache, dass Sie durch die Verwendung von Pfeilen in der Sprache verwirrt sind, könnte bedeuten, dass Sie nicht grundsätzlich verstehen, warum sie so an das Design der Sprache gebunden sind. Vielleicht ist es Zeit, ein paar Kapitel zu lesen von Ben Pierces Link "Typen und Programmiersprachen" .

Bearbeiten: Sie können sich immer Sprachen anschauen, die keine starke Vorstellung von Funktionen haben und deren Semantik auf andere Weise definiert wurde - wie zB PostScript oder PostScript - aber in diesen Sprachen nicht definieren induktive Datentypen in gleicher Weise wie in funktionalen Sprachen wie Haskell, ML oder Coq. Um es anders auszudrücken: In jeder Sprache, in der Sie Konstruktoren für Datentypen definieren, entstehen Pfeile natürlich aus den Konstruktoren für diese Typen. Aber in Sprachen, in denen Sie keine induktiven Datentypen in der üblichen Weise definieren, erhalten Sie keine Pfeiltypen als natürlich, weil die Sprache einfach nicht so funktioniert.

Noch ein Schnitt: Ich werde noch einen weiteren Kommentar schreiben, da ich gestern Nacht darüber nachgedacht habe. Funktionstypen (und Funktionsabstraktion) bilden die Grundlage für fast alle Programmiersprachen - zumindest auf einer bestimmten Ebene, selbst wenn sie "unter der Haube" liegen. Es gibt jedoch Sprachen, die die Semantik von anderen Sprachen definieren. Dies stimmt zwar nicht genau mit dem überein, worüber Sie sprechen, aber PLT Redex ist ein solches System und wird für die Angabe und verwendet Debugging der Semantik von Programmiersprachen. Es ist nicht sehr nützlich aus Sicht der Praktiker (es sei denn, dein Ziel ist es, neue Sprachen zu entwerfen, in diesem Fall ist es ziemlich nützlich), aber vielleicht passt das, was du willst.

    
Kristopher Micinski 30.03.2012 14:28
quelle
3

Die Funktionsdefinition ist normalerweise primitiv, weil (a) Funktionen sind, wie Programme Dinge erledigen; und (b) diese Art von Lambda-Abstraktion ist notwendig, um in einem Punkt-Stil (d. h. mit expliziten Argumenten) programmieren zu können.

Wahrscheinlich kommen Sie am ehesten zu einer Sprache, die Ihren Kriterien entspricht, und basiert auf einem rein punktfreien Modell, mit dem Sie Ihren eigenen Lambda-Operator erstellen können. Vielleicht möchten Sie pointfree Sprachen im Allgemeinen und solche, die auf SKI Kalkül im Besonderen basieren: Ссылка

In einem solchen Fall haben Sie immer noch primitive Funktion Typen , und Sie werden immer, weil es ein grundlegendes Element des Typsystems ist. Wenn Sie überhaupt davon wegkommen wollen, wäre das Beste, was Sie tun könnten, eine Art Typensystem, das auf einer kategorientheoretischen Verallgemeinerung von Funktionen beruht, so dass Funktionen ein Spezialfall eines anderen Typs wären. Siehe Ссылка .

    
Marcin 30.03.2012 14:21
quelle
3
  

Welche Sprachen haben nicht - & gt; als primitiver Typ?

Nun, wenn Sie einen Typ meinen, der benannt werden kann, dann gibt es viele Sprachen, die sie nicht haben. Alle Sprachen, in denen Funktionen keine Bürger erster Klasse sind, haben keine - & gt; als eine Art könnte man irgendwo erwähnen.

Aber, wie @Kristopher eloquent und exzellent erklärt hat, sind Funktionen die Grundbausteine ​​aller Berechnungen (oder können zumindest als solche wahrgenommen werden). Daher gibt es sogar in Java, zum Beispiel, Funktionen, die aber sorgfältig vor dir verborgen sind.

Und, wie jemand Assembler erwähnte - man könnte behaupten, dass die Maschinensprache (der meisten modernen Computer) eine Annäherung an das Modell der Registermaschine ist. Aber wie ist es gemacht? Mit Millionen und Milliarden logischer Schaltungen, von denen jede eine Materialisierung von ziemlich primitiven reinen Funktionen wie NOT oder NAND ist, die in einer bestimmten physikalischen Reihenfolge angeordnet sind (was natürlich die Art und Weise ist, wie Hardware-Generatoren die Funktionszusammensetzung implementieren ). Obwohl Sie Funktionen im Maschinencode möglicherweise nicht sehen, sind sie immer noch die Basis.

    
Ingo 31.03.2012 00:25
quelle
3

In Martin-Löf-Typentheorie werden Funktionstypen über indizierte Produkttypen (sogenannte Π-Typen) .

Grundsätzlich kann der Typ der Funktionen von A bis B als (möglicherweise unendlicher) Datensatz interpretiert werden, wobei alle Felder vom selben Typ B sind und die Feldnamen genau alle Elemente sind von A . Wenn Sie eine Funktion f auf ein Argument x anwenden müssen, suchen Sie das Feld in f entsprechend x .

Der Wikipedia-Artikel listet einige Programmiersprachen auf, die auf der Martin-Löf-Typentheorie basieren. Ich bin nicht vertraut mit ihnen, aber ich nehme an, dass sie eine mögliche Antwort auf Ihre Frage sind.

    
Roman Cheplyaka 31.03.2012 20:20
quelle
3

Philip Wadlers Paper Call-by-value ist dual zu call-by-name stellt einen Kalkül dar, in dem Variablenabstraktion und kovariable Abstraktion primitiver sind als Funktionsabstraktion. Es gibt zwei Definitionen von Funktionstypen in Bezug auf diese Primitiven: Ein implementiert call-by-value und der andere call-by-name.

Inspiriert von Wadlers Paper habe ich eine Sprache (Ambidexer) implementiert, die zwei Konstruktoren für Funktionstypen bereitstellt, die Synonyme für Typen sind, die aus den Primitiven konstruiert wurden. Einer ist für Call-by-Value und einer für Call-by-Name. Weder Weder Dual-Kalkül noch Ambidexter bietet benutzerdefinierte Typkonstruktoren. Diese Beispiele zeigen jedoch, dass Funktionstypen nicht notwendigerweise primitiv sind und dass eine Sprache denkbar ist, in der Sie Ihre eigenen (- & gt;) definieren können.

    
Scott Turner 05.04.2012 08:50
quelle
2

In Scala können Sie eine der Function Eigenschaften, z. a Set[A] kann als A => Boolean verwendet werden, da es das Merkmal Function1[A,Boolean] implementiert. Ein anderes Beispiel ist PartialFunction[A,B] , das übliche Funktionen erweitert, indem es eine "Bereichsprüfung" -Methode isDefinedAt bereitstellt.

In Scala sind jedoch Methoden und Funktionen unterschiedlich, und es gibt keine Möglichkeit, die Funktionsweise von Methoden zu ändern. Normalerweise merkt man den Unterschied nicht, da Methoden automatisch auf Funktionen gehoben werden.

Sie haben also eine Menge Kontrolle darüber, wie Sie Funktionen in Scala implementieren und erweitern, aber ich denke, Sie haben einen echten "Ersatz" im Sinn. Ich bin mir nicht sicher, ob das überhaupt Sinn macht.

Oder suchen Sie vielleicht Sprachen mit einer Art Verallgemeinerung von Funktionen? Dann würde sich Haskell mit Arrow Syntax qualifizieren: Ссылка

    
Landei 30.03.2012 14:00
quelle
2

Ich nehme an, die dumme Antwort auf Ihre Frage ist Assemblercode . Dies bietet Ihnen Primitive sogar "niedrigere" Ebene als Funktionen. Sie können Funktionen als Makros erstellen, die Register- und Sprungelemente verwenden.

Die meisten vernünftigen Programmiersprachen geben Ihnen eine Möglichkeit, Funktionen als eingebrannte Sprachfunktion zu erstellen, weil Funktionen (oder "Unterprogramme") die Essenz einer guten Programmierung sind: Wiederverwendung von Code.

    
Dan Burton 30.03.2012 17:22
quelle