Wie unterscheiden sich imperative Sprachen stärker voneinander als funktionale Sprachen?

Ich lese Simon Peyton Jones ' Die Implementierung funktionaler Programmiersprachen und es gibt eine Aussage, die mich ein wenig überrascht hat (auf Seite 39):

Funktionale Sprachen sind in viel stärkerem Maße als imperative Sprachen syntaktische Variationen voneinander mit relativ wenigen semantischen Unterschieden.

Nun, dies wurde 1987 geschrieben und meine Gedanken zu diesem Thema könnten von moderneren Programmiersprachen beeinflusst werden, die damals weder bekannt noch beliebt waren. Allerdings fällt es mir schwer, das zu glauben. Zum Beispiel denke ich, dass die beschriebene Miranda-Programmiersprache (ein früherer Vorgänger von Haskell) eine viel andere Semantik hat als eine strenge Sprache wie ML, als C zu Pascal oder vielleicht sogar C zu smalltalk (obwohl ich das abtreten werde) C ++ bietet eine Bestätigung seines Standpunkts :-).

Andererseits stütze ich mich dabei auf mein intuitives Verständnis. Hat Simon Peyton Jones größtenteils recht, oder ist dies ein kontroverser Punkt?

Simon hat im Grunde genommen recht, was die Erweiterung betrifft. Wir wissen ziemlich genau, wie die Semantik moderner funktionaler Sprachen aussieht, und es handelt sich tatsächlich um relativ kleine Variationen - sie repräsentieren jeweils leicht unterschiedliche Übersetzungen in eine monadische Metasprache. Sogar eine Sprache wie Scheme (eine dynamisch typisierte imperative Sprache höherer Ordnung mit erstklassiger Kontrolle) hat eine Semantik, die der von ML und Haskell ziemlich nahe kommt.

Aus denotational Sicht, können Sie , indem sie eine ziemlich einfache Domain - Gleichung für die Semantik von Schema beginnen - nennen es . Leute konnten und haben solche Gleichungen in den späten 70ern / frühen 80ern gelöst, also ist das nicht so schlimm. In ähnlicher Weise gibt es auch für Scheme eine relativ einfache operationale Semantik. (Beachten Sie, dass wenn ich "Schema" sage, ich untypisierte Lambda-Rechnung plus Fortsetzungen plus Zustand meine, im Gegensatz zu dem tatsächlichen Schema, das ein paar Warzen hat, wie es alle realen Sprachen tun.)$V$

Aber um zu einer Kategorie zu gelangen, die für die Interpretation moderner typisierter funktionaler Sprachen geeignet ist, wird es ziemlich beängstigend. Im Grunde konstruieren Sie eine ultrametrisch angereicherte Kategorie von partiellen Äquivalenzbeziehungen über diesen Bereich. (Als Beispiel siehe Birkedal, Stovring und Thamsborgs "Realisierbarkeitssemantik des parametrischen Polymorphismus, allgemeine Referenzen und rekursive Typen".) Leute, die operationale Semantik bevorzugen, kennen dieses Material als schrittindizierte logische Beziehungen. (Siehe zum Beispiel Ahmed, Dreyer und Rossbergs "State-Dependent Representation Independence".) In beiden Fällen sind die verwendeten Techniken relativ neu.

Der Grund für diese mathematische Komplexität ist, dass wir in der Lage sein müssen, den parametrischen Polymorphismus und den Zustand höherer Ordnung gleichzeitig zu interpretieren. Aber wenn Sie dies getan haben, sind Sie im Grunde genommen zu Hause frei, da diese Konstruktion alle harten Teile enthält. Jetzt können Sie ML- und Haskell-Typen über die üblichen monadischen Übersetzungen interpretieren. MLs strenger, effektiver Funktionsraum a -> bübersetzt sich in right>$\left<a\right> \to T\left<b\right>$$\left<a\right> \to \left<b\right>$$T(A)$$\left<a\right>$a$\to$

Nach der Gleichungstheorie ist es durchaus gerechtfertigt, beide Sprachen syntaktische Variationen voneinander zu nennen, da beide Sprachen durch Übersetzungen in leicht unterschiedliche Teilmengen derselben Sprache beschrieben werden können.

Der Unterschied im Spielgefühl zwischen ML und Haskell ergibt sich tatsächlich aus den intensiven Eigenschaften der beiden Sprachen, dh der Ausführungszeit und dem Speicherverbrauch. ML hat ein kompositorisches Leistungsmodell (dh die Zeit- / Raumkosten eines Programms können aus den Zeit- / Raumkosten seiner Untertitel berechnet werden), wie dies bei einer echten Call-by-Name-Sprache der Fall wäre. Tatsächlich wird Haskell mit Call-by-Need implementiert, einer Art Memoization, und daher ist seine Leistung nicht kompositorisch. Wie lange ein an eine Variable gebundener Ausdruck für die Auswertung benötigt, hängt davon ab, ob er zuvor verwendet wurde oder nicht. Dies ist in der Semantik, auf die ich oben angespielt habe, nicht modelliert.

Wenn Sie die Intensitätseigenschaften ernst nehmen möchten, zeigen ML und Haskell ernstere Unterschiede. Es ist wahrscheinlich immer noch möglich, eine gemeinsame Metasprache für sie zu entwickeln, aber die Interpretation der Typen wird sich in Bezug auf die proof-theoretische Idee der Fokussierung systematischer unterscheiden . Ein guter Ort, um dies zu lernen, ist Noam Zeilbergers Doktorarbeit.

Meines Erachtens bezog sich SPJ auf rein funktionale Sprachen, dh auf Sprachen, die referenziell transparent sind. Dies schließt zB Haskell, Miranda, Clean, aber nicht ML ein. Wenn Sie eine rein funktionale Sprache haben, können Sie ihr im Allgemeinen eine relativ saubere und klar definierte Denotationssemantik geben. Diese Semantik wird im Allgemeinen wie eine für den Lambda-Kalkül aussehen, mit einigen Änderungen hier und da. Im Allgemeinen werden Sie ein Typensystem haben, das etwas ähnelt, das System F ähnelt - in einigen Punkten vielleicht mächtiger, in anderen eingeschränkter. Aus diesem Grund ist das Extrahieren / Kompilieren von Code in Haskell, O'Caml usw. für anspruchsvolle, typabhängig geschriebene Proof-Assistenten wie Agda relativ einfach.

In diesem Rahmen gibt es viel Spielraum. Natürlich gibt es immer noch einen Unterschied zwischen einer nicht strengen und einer strengen Sprache. In Abwesenheit von Nebenwirkungen besteht der einzige Unterschied darin, dass eine nicht strenge Sprache mehr Ausdrücke enthält, die nicht bottom bedeuten - sofern die beiden Bewertungsstrategien nicht bottom ergeben, stimmen sie überein.

Simons Aussage passt auch in einen sehr wichtigen historischen Kontext. Zum Zeitpunkt der Geburt von Haskell (1987) gab es eine Vielzahl von nicht strengen funktionalen Sprachen - nicht nur Miranda, sondern auch Lazy ML, Orwell, Clean und viele andere. Abgesehen von bestimmten syntaktischen Variationen waren sie alle sehr ähnlich. Welches war genau die Motivation für das Haskell-Komitee zu bilden. Weitere Informationen hierzu finden Sie unter "Eine Geschichte von Haskell: Faulenzen im Unterricht": http://research.microsoft.com/en-us/um/people/simonpj/papers/history-of-haskell/ .

Ich denke, SPJ hat Recht damit, dies für die Kernsemantik zu sagen.

Obwohl es viele fortgeschrittene Feinheiten gibt, auf die man hinweisen kann, wie beispielsweise die Standardeinstellung für strenge oder verzögerte Evaluierung, wie Sie bereits erwähnt haben, die Details von Typsystemen oder wie größere Codeeinheiten (Module, Strukturen) organisiert sind, ist das mentale Modell eines Programms sehr ähnlich in allen funktionalen Sprachen.

Wählen Sie eine bestimmte angegebene Funktion und schreiben Sie sie in alle Sprachen, die Sie vergleichen. Sie werden wahrscheinlich feststellen, dass die Struktur und Semantik der verschiedenen Implementierungen für alle sehr ähnlich sind, einschließlich Abstraktionsgrad, gewählte Datenstrukturen, Ich nehme alle Müllabfuhr usw. an.

Angenommen, eine C-Implementierung im Vergleich zu einer Smalltalk-Implementierung derselben Funktion weist wahrscheinlich eine andere Struktur auf (Funktionen und Datenstrukturen auf niedriger Ebene im Vergleich zu Objekten) und konzentriert sich auf verschiedene Detailebenen (z. B. manuelle Speicherverwaltung im Vergleich zur Garbage Collection) ) und arbeiten auf verschiedenen Abstraktionsebenen.

Das Weltbild des funktionalen Sprachgestaltungsraums ist einfach spezifischer und kohärenter als das des "imperativen Programmierraums", in dem Assembly, C, Smalltalk, Forth und Dutzende anderer radikal unterschiedlicher Sprachen zu einer Gesamtkategorie zusammengefasst sind.

Ich denke, das Zitat von Simon PJ ist eigentlich eine kleine Bemerkung.

Die Ähnlichkeit zwischen den Sprachen hängt davon ab, welchen Konsens die Forscher- und Sprachdesigner-Community erzielt hat. Es steht außer Frage, dass es in der funktionalen Programmiergemeinschaft einen höheren Grad an Übereinstimmung gibt als in der imperativen Programmiergemeinschaft. Es ist aber auch so, dass die funktionalen Programmiersprachen zumeist von Forschern und nicht von Praktikern entworfen werden. Ein solcher Konsens ist also selbstverständlich.

Fast alle funktionalen Sprachen verwenden Garbage Collected Memory Management und rekursive Datenstrukturen (von Lisp erstellt), die meisten von ihnen verwenden "algebraische" Datentypen und Pattern Matching (von Hope erstellt), viele von ihnen verwenden Funktionen höherer Ordnung und polymorphe Funktionen ( entstanden durch ML). Darüber hinaus verschwindet der Konsens. Sie unterscheiden sich in den verwendeten Modulsystemen, im Umgang mit Zustandsänderungsoperationen und anderen Recheneffekten sowie in der Auswertungsreihenfolge (Call-by-Name vs. Call-by-Value) usw.

Imperative Programmiersprachen verwenden im Allgemeinen verschachtelte Kontrollstrukturen (von Algol 60 erstellt) und Typsysteme (von Algol 60 erstellt, aber von Algol 68 konsolidiert). Sie haben im Allgemeinen eine umständliche Oberflächensyntax (die wiederum auf Algol 60 zurückgeht), machen halbherzige Versuche, Funktionen höherer Ordnung und polymorphe Typen zu handhaben, und unterscheiden sich in ihrer Unterstützung für Blockstruktur- und Modulsysteme. Die Bewertungsreihenfolge ist wahrscheinlich einheitlicher, da Call-by-Name nach den 60er Jahren im Wesentlichen aus den imperativen Sprachen verschwunden ist.

Daher ist mir nicht klar, dass der Unterschied zwischen den beiden Klassen von Sprachen in ihrer Einheitlichkeit so groß ist.

Es wäre wirklich lohnenswert, die klareren und einheitlicheren Bezeichnungen der funktionalen Programmierung in zwingende Programmiersprachen zu bringen. Ich sehe, dass Scala einen Anfang in diese Richtung gemacht hat. Es bleibt abzuwarten, ob sich der Trend fortsetzt.