ML (Programmiersprache) - ML (programming language)
Paradigma | Multiparadigma : funktional , zwingend |
---|---|
Entworfen von | Robin Milner und andere an der University of Edinburgh |
Erstmals erschienen | 1973 |
Schreibdisziplin | Abgeleitet , statisch , stark |
Dialekte | |
OCaml , Standard-ML , F# | |
Beeinflusst von | |
ICH SCHWIMME | |
Beeinflusst | |
Clojure , Coq , Cyclone , C++ , Elm , F# , F* , Haskell , Idris , Kotlin , Miranda , Nemerle , OCaml , Opa , Erlang , Rust , Scala , Standard ML |
ML ( Meta Language ) ist eine universelle funktionale Programmiersprache . Es ist bekannt für die Verwendung des polymorphen Hindley-Milner-Typsystems , das die Typen der meisten Ausdrücke automatisch zuweist, ohne dass explizite Typannotationen erforderlich sind, und die Typsicherheit gewährleistet – es gibt einen formalen Beweis dafür, dass ein gut typisiertes ML-Programm keine Laufzeit verursacht Typfehler. ML bietet Musterabgleich für Funktionsargumente, Garbage Collection , imperative Programmierung , Call-by-Value und Currying . Es wird stark in der Programmiersprachenforschung verwendet und ist eine der wenigen Sprachen, die vollständig mit formaler Semantik spezifiziert und verifiziert werden können . Seine Typen und Mustervergleiche machen es gut geeignet und werden häufig verwendet, um mit anderen formalen Sprachen zu arbeiten, wie zum Beispiel beim Schreiben von Compilern , beim automatisierten Beweisen von Theoremen und bei der formalen Verifikation .
Überblick
Zu den Merkmalen von ML gehören eine Call-by-Value- Auswertungsstrategie , erstklassige Funktionen , automatische Speicherverwaltung durch Garbage Collection, parametrischer Polymorphismus , statische Typisierung , Typinferenz , algebraische Datentypen , Mustervergleich und Ausnahmebehandlung . ML verwendet statische Bereichsregeln .
ML kann als unreine funktionale Sprache bezeichnet werden, da sie zwar die funktionale Programmierung fördert, aber Nebenwirkungen zulässt (wie Sprachen wie Lisp , aber im Gegensatz zu einer rein funktionalen Sprache wie Haskell ). Wie die meisten Programmiersprachen verwendet ML Eager Evaluation , was bedeutet, dass alle Unterausdrücke immer ausgewertet werden, obwohl eine Lazy Evaluation durch die Verwendung von Closures erreicht werden kann . So kann man wie in Haskell unendliche Ströme erzeugen und verwenden, aber ihr Ausdruck ist indirekt.
Die Stärken von ML werden hauptsächlich in der Sprachgestaltung und -manipulation (Compiler, Analysatoren, Theorembeweiser) eingesetzt, aber es ist eine universelle Sprache, die auch in Bioinformatik und Finanzsystemen verwendet wird.
ML wurde von Robin Milner und anderen in den frühen 1970er Jahren an der University of Edinburgh entwickelt und seine Syntax ist von ISWIM inspiriert . Historisch wurde ML konzipiert, um Beweistaktiken im LCF-Theorembeweiser zu entwickeln (dessen Sprache pplambda , eine Kombination aus dem Prädikatenkalkül erster Ordnung und dem einfach typisierten polymorphen Lambdakalkül , ML als Metasprache hatte).
Heute gibt es mehrere Sprachen in der ML-Familie; die drei bekanntesten sind Standard ML (SML), OCaml und F# . Ideen von ML haben zahlreiche andere Sprachen beeinflusst, wie Haskell, Cyclone , Nemerle , ATS und Elm .
Beispiele
Die folgenden Beispiele verwenden die Syntax von Standard ML. Andere ML-Dialekte wie OCaml und F# unterscheiden sich in kleinen Punkten.
Fakultät
Die Fakultätsfunktion , ausgedrückt als reine ML:
fun fac (0 : int) : int = 1
| fac (n : int) : int = n * fac (n - 1)
Dies beschreibt die Fakultät als rekursive Funktion mit einem einzigen abschließenden Basisfall. Es ähnelt den Beschreibungen von Fakultäten, die in Mathematiklehrbüchern zu finden sind. Ein Großteil des ML-Codes ähnelt in seiner Einrichtung und Syntax der Mathematik.
Ein Teil der gezeigten Definition ist optional und beschreibt die Typen dieser Funktion. Die Notation E : t kann als Ausdruck E vom Typ t gelesen werden . Zum Beispiel wird dem Argument n der Typ integer (int) zugewiesen , und fac (n : int), das Ergebnis der Anwendung von fac auf die ganze Zahl n, hat auch den Typ integer. Die Funktion fac als Ganzes hat dann den Typ function von integer bis integer (int -> int), dh fac akzeptiert eine ganze Zahl als Argument und gibt ein ganzzahliges Ergebnis zurück. Dank Typinferenz können die Typannotationen weggelassen werden und werden vom Compiler abgeleitet. Ohne die Typanmerkungen umgeschrieben, sieht das Beispiel so aus:
fun fac 0 = 1
| fac n = n * fac (n - 1)
Die Funktion basiert auch auf dem Mustervergleich, einem wichtigen Teil der ML-Programmierung. Beachten Sie, dass Parameter einer Funktion nicht unbedingt in Klammern stehen, sondern durch Leerzeichen getrennt sind. Wenn das Argument der Funktion 0 (null) ist, wird die ganze Zahl 1 (eins) zurückgegeben. Für alle anderen Fälle wird die zweite Zeile versucht. Dies ist die Rekursion und führt die Funktion erneut aus, bis der Basisfall erreicht ist.
Es ist nicht garantiert, dass diese Implementierung der Fakultätsfunktion terminiert, da ein negatives Argument eine unendliche absteigende Kette rekursiver Aufrufe verursacht. Eine robustere Implementierung würde vor der Wiederholung wie folgt auf ein nicht negatives Argument prüfen:
fun fact n = let
fun fac 0 = 1
| fac n = n * fac (n - 1)
in
if (n < 0) then raise Domain else fac n
end
Der problematische Fall (wenn n negativ ist) demonstriert eine Verwendung des Ausnahmesystems von ML.
Die Funktion kann weiter verbessert werden, indem ihre innere Schleife als Schwanzaufruf geschrieben wird , sodass der Aufrufstapel nicht proportional zur Anzahl der Funktionsaufrufe wachsen muss. Dies wird erreicht, indem der inneren Funktion ein zusätzlicher Akkumulator- Parameter hinzugefügt wird . Endlich kommen wir an
fun fact n = let
fun fac 0 acc = acc
| fac n acc = fac (n - 1) (n * acc)
in
if (n < 0) then raise Domain else fac n 1
end
Liste umgekehrt
Die folgende Funktion kehrt die Elemente in einer Liste um. Genauer gesagt gibt es eine neue Liste zurück, deren Elemente im Vergleich zur gegebenen Liste in umgekehrter Reihenfolge angeordnet sind.
fun reverse [] = []
| reverse (x :: xs) = (reverse xs) @ [x]
Diese Implementierung von Reverse ist zwar korrekt und klar, aber ineffizient und erfordert quadratische Zeit für die Ausführung. Die Funktion kann so umgeschrieben werden, dass sie in linearer Zeit ausgeführt wird :
fun 'a reverse xs : 'a list = List.foldl (op ::) [] xs
Insbesondere ist diese Funktion ein Beispiel für parametrischen Polymorphismus. Das heißt, es kann Listen konsumieren, deren Elemente einen beliebigen Typ haben, und Listen desselben Typs zurückgeben.
Module
Module sind das System von ML zur Strukturierung großer Projekte und Bibliotheken. Ein Modul besteht aus einer Signaturdatei und einer oder mehreren Strukturdateien. Die Signaturdatei spezifiziert die zu implementierende API (wie eine C-Header-Datei oder eine Java-Schnittstellendatei ). Die Struktur implementiert die Signatur (wie eine C-Quelldatei oder eine Java-Klassendatei). Im Folgenden wird beispielsweise eine arithmetische Signatur und eine Implementierung davon mit rationalen Zahlen definiert:
signature ARITH =
sig
type t
val zero : t
val succ : t -> t
val sum : t * t -> t
end
structure Rational : ARITH =
struct
datatype t = Rat of int * int
val zero = Rat (0, 1)
fun succ (Rat (a, b)) = Rat (a + b, b)
fun sum (Rat (a, b), Rat (c, d)) = Rat (a * d + c * b , b * d)
end
Diese werden mit dem Befehl 'use' in den Interpreter importiert. Die Interaktion mit der Implementierung ist nur über die Signaturfunktionen erlaubt, beispielsweise ist es nicht möglich, direkt über diesen Code ein Datenobjekt 'Rat' anzulegen. Der Block 'Struktur' verbirgt alle Implementierungsdetails nach außen.
Die Standardbibliotheken von ML werden auf diese Weise als Module implementiert.
Siehe auch
- Standard-ML und Standard-ML §-Implementierungen
-
Abhängiges ML : eine abhängig typisierte Erweiterung von ML
- ATS : eine Weiterentwicklung der abhängigen ML
- Lazy ML : ein experimentell faul bewerteter ML-Dialekt aus den frühen 1980er Jahren
- PAL (Programmiersprache) : eine Bildungssprache im Zusammenhang mit ML
- OCaml : ein ML-Dialekt mit "industrieller Stärke", der zur Implementierung von Coq . verwendet wird
- F# : eine plattformübergreifende Open-Source-Functional-First-Sprache für das .NET Framework
- CoffeeScript und TypeScript : Metasprachen für ECMAScript
Verweise
Weiterlesen
- Die Definition von Standard-ML , Robin Milner, Mads Tofte , Robert Harper , MIT Press 1990; (überarbeitete Ausgabe fügt Autor David MacQueen hinzu), MIT Press 1997, ISBN 0-262-63181-4 .
- Kommentar zu Standard ML , Robin Milner , Mads Tofte , MIT Press 1997, ISBN 0-262-63137-7 .
- ML für den Working Programmer , Lawrence Paulson , Cambridge University Press 1991, 1996, ISBN 0-521-57050-6 .
- Harper, Robert (2011). Programmierung in Standard-ML (PDF) . Carnegie Mellon Universität.
- Elemente der ML-Programmierung , Jeffrey D. Ullman , Prentice-Hall 1994, 1998, ISBN 0-13-790387-1 .
Externe Links
- Standard-ML von New Jersey, eine weitere beliebte Implementierung
- F#, eine ML-Implementierung mit dem Microsoft .NET Framework
- MLton, ein das gesamte Programm optimierender Standard-ML-Compiler
- Nachfolger ML – oder sML
- CakeML, eine Read-Eval-Print-Loop-Version von ML mit formal verifizierter Laufzeit und Übersetzung in Assembler