OCaml | ||
Datum der ersten Version | 1987 (CAML), 1996 (OCaml) | |
---|---|---|
Paradigma | Multiparadigma : Imperativ , Funktional , Objektorientiert | |
Entwickler | Inria | |
Letzte Version | 4.12.0 (24. Februar 2021) | |
Tippen | Stark , statisch | |
Dialekte | JoCaml, Frisches OCaml, GCaml, MetaOCaml, OCamlDuce, OcamlP3L | |
Beeinflusst von | ML | |
Beeinflusst | F # , Rost , OPA , Scala | |
Geschrieben in | OCaml | |
Betriebssystem | Plattformübergreifend | |
Lizenz | LGPL 2.1 | |
Webseite | ocaml.org | |
Dateierweiterung | ml und mli | |
OCaml , früher bekannt als Ziel Caml , ist das am weitesten fortgeschrittene Umsetzung der Caml Programmierung Sprache , erstellt von Xavier Leroy , Jérôme Vouillon , Damien Dolurez , Didier Rémy und ihren Mitarbeitern in 1996 . Diese Sprache aus der ML- Sprachfamilie ist ein Open-Source- Projekt, das hauptsächlich von Inria geleitet und gepflegt wird .
OCaml ist der Nachfolger von Caml Light , dem unter anderem eine Objektprogrammierungsschicht hinzugefügt wurde. Das Akronym CAML stammt von Categorical Abstract Machine Language , einem abstrakten Maschinenmodell , das jedoch in neueren Versionen von OCaml nicht mehr verwendet wird.
OCaml ist tragbar und leistungsstark und wird in so unterschiedlichen Projekten wie der Unison- Dateisynchronisierungssoftware , dem Coq- Assistenten für formale Beweise oder der Webversion von Facebook Messenger verwendet . Die symbolischen Verarbeitungsmöglichkeiten der Sprache ermöglichen die Entwicklung statischer Verifikationswerkzeuge, wie das SLAM-Projekt für Windows- Piloten von Microsoft oder ASTRÉE für bestimmte Bordsysteme von Airbus A380 .
Caml ist eine funktionale Sprache, die um Funktionen erweitert wurde, die eine zwingende Programmierung ermöglichen . OCaml erweitert die Möglichkeiten der Sprache, indem es objektorientierte Programmierung und modulare Programmierung ermöglicht . Aus all diesen Gründen fällt OCaml in die Kategorie der Multiparadigmensprachen .
Es integriert diese verschiedenen Konzepte in ein von ML geerbtes Typsystem, das sich durch eine statische , starke und abgeleitete Typisierung auszeichnet .
Das Typsystem erlaubt eine einfache Manipulation komplexer Datenstrukturen: Wir können leicht algebraische Typen , also hierarchische und potentiell rekursive Typen (Listen, Bäume etc.) darstellen und mit Hilfe des Mustervergleichs leicht manipulieren . Dies macht OCaml zu einer Sprache der Wahl in Bereichen, die die Manipulation komplexer Datenstrukturen erfordern, wie zum Beispiel Compiler .
Die starke Typisierung sowie das Fehlen expliziter Speichermanipulationen (Anwesenheit eines Garbage Collectors ) machen OCaml zu einer sehr sicheren Sprache. Es ist auch für seine Leistung bekannt, dank des Vorhandenseins eines nativen Code- Compilers .
Die Sprache Caml entstand aus dem Zusammentreffen der Programmiersprache ML, auf die sich das Team Formel von INRIA seit den frühen 1980er Jahren konzentriert , und der kategorischen abstrakten Maschine CAM Guy Cousineau , basierend auf der Arbeit von Pierre-Louis Curien im Jahr 1984 . Die erste Implementierung, geschrieben von Ascander Suarez (damals Doktorand an der Pariser Diderot-Universität ) und dann von Pierre Weis und Michel Mauny gepflegt, wurde 1987 veröffentlicht . Die Sprache unterschied sich allmählich von ihrem ML-Vater, weil das Inria-Team eine Sprache an seine eigenen Bedürfnisse anpassen und weiterentwickeln wollte, was durch die Standardisierungsbemühungen von Standard ML in Konflikt mit der auferlegten "Stabilität" von ML geriet.
Die Einschränkungen von CAM führten zur Entwicklung einer neuen Implementierung, die 1990 von Xavier Leroy unter dem Namen Caml Light entwickelt wurde . Diese Implementierung, eine aktuelle Version einschließlich ist noch in der Ausbildung verwendet heute , Obwohl das System nicht länger von dem gehalten INRIA , einem Dolmetscher arbeitet über Byte - Code ( Bytecode ) codiert in C , die es große Beweglichkeit verleiht. Das von Damien Dolurez entworfene Speicherverwaltungssystem erschien auch in Caml Light. In 1995 veröffentlichten Xavier Leroy eine Version von Caml genannt Caml Speziellem Licht , die einen nativen Code - Compiler eingeführt, und ein Modulsystem von Standard ML Module inspiriert.
OCaml, erstmals 1996 veröffentlicht , bringt ein von Didier Rémy und Jérôme Vouillon entworfenes Objektsystem zu Caml. Einige erweiterte Funktionen wie polymorphe Varianten oder Labels (die es ermöglichen, die Argumente einer Funktion anhand ihres Namens und nicht anhand ihrer Position zu unterscheiden) wurden im Jahr 2000 von Jacques Garrigue eingeführt. OCaml hat sich seitdem relativ stabilisiert (trotz des Fehlens einer Spezifikation, das geltende Dokument ist das offizielle Handbuch von Inria ). Viele Dialekte von OCaml sind erschienen und erforschen weiterhin spezifische Aspekte von Programmiersprachen (Nebenläufigkeit, Parallelität, Lazy Evaluation, XML-Integration…); siehe Abschnitt Abgeleitete Sprachen .
OCaml hat die meisten gemeinsamen Merkmale funktionaler Sprachen, insbesondere Funktionen höherer Ordnung und Closures ( Closures ) und eine gute Unterstützung der Tail-Rekursion .
Die statische Typisierung von OCaml erkennt eine große Anzahl von Programmierfehlern zur Kompilierzeit, die zur Laufzeit Probleme verursachen können. Im Gegensatz zu den meisten anderen Sprachen ist es jedoch nicht erforderlich, den verwendeten Variablentyp anzugeben. Tatsächlich verfügt Caml über einen Typinferenzalgorithmus , der es ermöglicht, den Typ von Variablen aus dem Kontext zu bestimmen, in dem sie verwendet werden.
Das ML-Typisierungssystem unterstützt parametrischen Polymorphismus , dh Typen, deren Teile bei der Definition des Werts unbestimmt sind. Dieses Feature, automatisch, ermöglicht eine Generika vergleichbar mit Generics in Java oder C # oder Templates in C ++ .
Die erforderlichen Erweiterungen der ML-Typisierung durch die Integration von erweiterten Funktionalitäten, wie der objektorientierten Programmierung, machen das Typsystem jedoch in bestimmten Fällen komplexer: Die Nutzung dieser Funktionalitäten kann dann für den Programmierer eine Lernzeit erfordern, die nicht ist nicht unbedingt mit anspruchsvollen Typensystemen vertraut.
Der Mustervergleich (auf Englisch : Mustervergleich ) ist ein wesentliches Element der Caml-Sprache. Es ermöglicht eine Vereinfachung des Codes dank einer flexibleren Schreibweise als herkömmliche Bedingungen, und die Vollständigkeit wird überprüft: Der Compiler schlägt ein Gegenbeispiel vor, wenn eine unvollständige Filterung festgestellt wird. Der folgende Code wird beispielsweise kompiliert, führt jedoch zu einer Warnung:
# type etat = Actif | Inactif | Inconnu;; type etat = Actif | Inactif | Inconnu # let est_actif = function # | Actif -> true # | Inactif -> false;; val est_actif : etat -> bool = <fun> Warning P: this pattern-matching is not exhaustive. Here is an example of a value that is not matched: InconnuDaher funktioniert das Programm, wenn die is_active- Funktion mit dem Status Active oder Inactive aufgerufen wird , aber wenn es Unknown ist , löst die Funktion die Match_failure- Ausnahme aus .
Die Module ermöglichen es, das Programm in eine Hierarchie von Strukturen zu unterteilen, die Typen und logisch verwandte Werte enthält (zum Beispiel befinden sich alle Listenmanipulationsfunktionen im Listenmodul). Die Nachkommen der ML-Familie sind die Sprachen, die derzeit über die ausgereiftesten Modulsysteme verfügen, die es ermöglichen, neben Namensräumen auch Abstraktion (zugängliche Werte, deren Implementierung versteckt ist) und Zusammensetzbarkeit (Werte, die auf verschiedenen Modulen aufbauen, solange sie auf eine bestimmte Schnittstelle reagieren).
Somit sind die drei syntaktischen Einheiten der syntaktischen Konstruktion Strukturen, Schnittstellen und Module. Strukturen enthalten die Implementierung von Modulen, Schnittstellen beschreiben die Werte, die von ihnen aus zugänglich sind (Werte, deren Implementierung nicht exponiert ist, sind abstrakte Werte, und solche, die in der Implementierung des Moduls überhaupt nicht vorkommen. sind nicht zugänglich, wie private Methoden in der objektorientierten Programmierung). Ein Modul kann mehrere Schnittstellen haben (sofern alle mit den Typen der Implementierung kompatibel sind), und mehrere Module können eine einzelne Schnittstelle verifizieren. Funktoren sind durch andere Strukturen parametrisierte Strukturen; Als Funktor können beispielsweise die Hash-Tabellen (Hashtbl-Modul) der Standardbibliothek OCaml verwendet werden, die als Parameter eine beliebige Struktur, die die Schnittstelle implementiert, bestehend aus einem Typ, einer Gleichheitsfunktion zwischen den Schlüsseln und einer Hash-Funktion, verwendet .
OCaml zeichnet sich insbesondere durch die Erweiterung der ML-Typisierung zu einem Objektsystem aus , das mit den klassischen Objektsprachen vergleichbar ist. Dies ermöglicht eine strukturelle Subtypisierung , bei der Objekte von kompatiblen Typen sind, wenn die Typen ihrer Methoden kompatibel sind, unabhängig von ihren jeweiligen Vererbungsbäumen . Diese Funktionalität, die als Äquivalent zum Duck-Typing dynamischer Sprachen angesehen werden kann, ermöglicht eine natürliche Integration von Objektkonzepten in eine allgemein funktionale Sprache.
Im Gegensatz zu objektorientierten Sprachen wie C++ oder Java, bei denen jede Klasse einen Typ definiert, definieren OCaml-Klassen also eher Typabkürzungen. Solange der Typ der Methoden kompatibel ist, können tatsächlich zwei Objekte zweier verschiedener Klassen gleichgültig im selben Kontext verwendet werden. Diese Eigenschaft der Objektschicht von OCaml bricht eine ganze Reihe allgemein akzeptierter Prinzipien: So ist es tatsächlich möglich, Subtyping ohne Vererbung durchzuführen. Die polymorphe Seite durchbricht das umgekehrte Prinzip. Es gibt auch Code-Beispiele, die zwar selten sind, aber Fälle von Vererbung ohne Subtyping zeigen. Die Stärke der Objektschicht liegt in ihrer Homogenität und ihrer perfekten Integration in die Philosophie und den Geist der OCaml-Sprache. Möglich sind auch funktionale Objekte, deren Attribute nicht geändert werden können und deren Methoden ggf. eine Kopie bei der Aktualisierung der Attribute oder der Definition von unmittelbaren Objekten oder on the fly zurückgeben.
Die OCaml-Distribution enthält:
OCaml-Tools werden regelmäßig unter Windows , GNU/Linux oder MacOS verwendet , existieren aber auch auf anderen Systemen wie BSD .
Mit dem Bytecode- Compiler können Sie Dateien erstellen, die dann von ocamlrun interpretiert werden. Der Bytecode ist plattformunabhängig gewährleistet diese große Portabilität (ocamlrun kann a priori auf jeder Plattform kompiliert werden , um einen funktionellen C - Compiler unterstützen). Der native Compiler erzeugt plattformspezifischen Assemblercode, der die Portabilität der erzeugten ausführbaren Datei zugunsten einer stark verbesserten Leistung opfert. Ein nativer Compiler ist für die Plattformen IA-32 , PowerPC , AMD64 , Alpha , Sparc , Mips , IA-64 , HPPA und StrongARM vorhanden .
Eine Kompatibilitätsschnittstelle ermöglicht es Ihnen, OCaml-Code mit C- Primitiven zu verknüpfen , und das Format von Gleitkomma-Arrays ist mit C und Fortran kompatibel . OCaml ermöglicht auch die Integration von OCaml-Code in ein C-Programm, wodurch es möglich ist, OCaml-Bibliotheken an C-Programmierer zu verteilen, ohne dass diese OCaml kennen oder gar installieren müssen.
OCaml-Tools sind größtenteils in OCaml codiert, mit Ausnahme einiger Bibliotheken und des Bytecode- Interpreters , die in C codiert sind. Insbesondere der native Compiler ist vollständig in OCaml codiert.
OCaml verfügt wie Java über eine automatisierte Speicherverwaltung, dank einer generationsübergreifenden inkrementellen Garbage Collection . Diese ist speziell an eine funktionale Sprache angepasst (optimiert für eine schnelle Zuweisung/Freigabe kleiner Objekte) und hat daher keinen nennenswerten Einfluss auf die Performance der Programme. Es ist konfigurierbar, um in atypischen Speichernutzungssituationen effizient zu bleiben.
OCaml unterscheidet sich von den meisten in akademischen Kreisen entwickelten Sprachen durch hervorragende Leistungen . Neben den "klassischen" lokalen Optimierungen durch den nativen Code-Generator profitieren die Performances vorteilhafterweise von der funktionalen und statisch und stark typisierten Natur der Sprache.
Somit werden die Typisierungsinformationen zur Kompilierzeit vollständig bestimmt und müssen nicht im nativen Code reproduziert werden, was es unter anderem ermöglicht, die Typisierungstests zur Laufzeit vollständig zu entfernen. Andererseits nutzen einige Algorithmen aus der Standardbibliothek die interessanten Eigenschaften rein funktionaler Datenstrukturen aus: So ist der Set-Union-Algorithmus asymptotisch schneller als der von imperativen Sprachen, weil er deren Nichtveränderlichkeit ausnutzt Mengen, um die Ausgabemenge zu bilden (dies ist die Methode zum Kopieren von Pfaden für persistente Datenstrukturen).
In der Vergangenheit wurden funktionale Sprachen von einigen Programmierern als langsam angesehen, da sie natürlich die Implementierung von Konzepten (Speicherwiederherstellung, teilweise Anwendung usw.) erfordern, von denen wir nicht wussten, wie sie effizient kompiliert werden können; Fortschritte in den Kompilierungstechniken haben es seitdem ermöglicht, den anfänglichen Vorteil der imperativen Sprachen aufzuholen. OCaml war eine der ersten funktionalen Sprachen, die die wiederentdeckte Effizienz der funktionalen Programmierung demonstrierte , indem sie diese Teile der Sprache effizient optimierte und einen Garbage Collector implementierte, der an häufige Zuweisungen funktionaler Sprachen angepasst war.
Im Allgemeinen ist die Ausführungsgeschwindigkeit etwas geringer als die eines entsprechenden Codes in C . Xavier Leroy spricht vorsichtig von „mindestens 50 % Leistung eines vernünftigen C-Compilers“. Diese Prognosen wurden inzwischen von zahlreichen Benchmarks bestätigt. In der Praxis Programme im Allgemeinen, mit Extremen in beiden Richtungen (manchmal schneller als C, manchmal stark verlangsamten durch ein unglückliches Zusammenspiel mit dem in diesem Bereich (der den C - Codes 1 bis 2 mal) bleiben garbage collector In jedem Fall, das ist immer noch schneller als die neuesten Sprachen, die nicht nativ kompiliert sind, wie Python oder Ruby , und vergleichbar mit statischen Sprachen, die spontan kompiliert werden, wie Java oder C # .
Die aus Forschungskreisen hervorgegangene Sprache OCaml profitiert nicht von der Werbekraft bestimmter aktueller Programmiersprachen. Daher ist es der allgemeinen Computeröffentlichkeit (wie auch den meisten funktionalen Sprachen) relativ wenig bekannt, hat sich aber dennoch in einigen Nischen fest etabliert, in denen die Qualitäten der Sprache Vorrang vor ihrer mangelnden Popularität haben.
OCaml ist die Sprache, die von den französischen Vorbereitungsklassen verwendet wird , wo es Caml Light im Hinblick auf die Computer-Optionstests für die Aufnahmeprüfungen an die Grandes écoles abgelöst hat. Die im Rahmen dieser Lehre verwendeten Dokumente beleuchten die Verbindungen zwischen funktionaler Programmierung und Mathematik und die Leichtigkeit, mit der die Sprachen der ML-Familie mit rekursiven Datenstrukturen umgehen, die für das Lehren von Algorithmen nützlich sind .
Er leidet in der Wissenschaft unter der Konkurrenz durch die Haskell- Sprache , die ihm in manchen funktionalen Programmierkursen vorgezogen wird, weil er unter anderem kein Konzept der imperativen Programmierung aufgreift .
OCaml ist eine recht verbreitete Sprache in der Suchwelt. Historisch waren die Sprachen des ML-Zweiges immer eng mit dem Bereich der formalen Beweissysteme verbunden ( Robin Milners ursprüngliches ML schien somit im LCF-Beweissystem verwendet zu werden). OCaml ist die Sprache, die von einer der wichtigsten Software auf diesem Gebiet verwendet wird, dem Coq- Proof-Assistenten .
OCaml ist in viele andere Bereiche der Informatikforschung involviert, einschließlich der Forschung zu Programmiersprachen und Compilern (siehe Abschnitt Abgeleitete Sprachen ) oder Unison- Dateisynchronisierungssoftware .
Trotz seiner relativ schüchternen Kommunikation hat sich OCaml in bestimmten Bereichen der Branche eine solide Nutzerbasis aufgebaut. So nutzt die Luftfahrtindustrie OCaml wegen seiner Programmiersicherheit und seiner Effizienz bei der Formulierung komplexer Algorithmen. In diesem Bereich können wir das Projekt ASTRÉE zitieren , das unter anderem von der Firma Airbus genutzt wird . Der synchrone Echtzeit-Programmiersprachen-Compiler Lustre , der für kritische Systeme wie Airbus-Avioniksysteme oder die Steuerung bestimmter Kernkraftwerke verwendet wird, ist ebenfalls in OCaml geschrieben.
OCaml wird von großen Playern der Softwarebranche wie Microsoft oder XenSource verwendet , die beide Mitglieder des Caml-Konsortiums sind. Es findet auch Anwendung in der Finanzinformatik, wie die Firma Jane Street zeigt , die viele OCaml-Programmierer beschäftigt, oder Lexifi, ein französisches Unternehmen, das sich auf das Design von Programmiersprachen für Finanzen spezialisiert und darüber hinaus international ausgezeichnet wurde.
Schließlich wird es auch von generalistischen freien Projekten wie MLDonkey , GeneWeb , dem Liquidsoap Webradio- Client , der FFTW-Bibliothek sowie einiger Software für die KDE- Desktopumgebung verwendet . Schließlich werden die mathematischen Formeln der MediaWiki- Software von einem in OCaml geschriebenen Programm generiert.
Betrachten Sie das folgende hello.ml-Programm:
print_endline "Hello world!"Es kann in kompiliert werden ausführbaren Bytecode mit dem ocamlc - Bytecode - Compiler:
$ ocamlc -o hello hello.mlEs kann auch mit dem nativen ocamlopt-Compiler in optimierten nativen Code kompiliert werden, der ausführbar ist:
$ ocamlopt -o hello hello.mlDas Programm kann dann vom ocamlrun- Bytecode- Interpreter ausgeführt werden:
$ ./hello Hello world!oder
$ ocamlrun hello Hello world!Der interaktive ocaml-Interpreter kann verwendet werden. Es startet eine "#"-Eingabeaufforderung, nach der OCaml-Anweisungen eingegeben werden können, die durch Zeichen abgeschlossen werden ;;(diese Zeichen für das Ende der Anweisung sollten nur im interaktiven Interpreter verwendet werden, sie sind nicht Teil der Sprachsyntax). Um beispielsweise eine Variable zu definieren, xdie das Ergebnis der Berechnung enthält 1 + 2 * 3, schreiben wir:
$ ocaml # let x = 1 + 2 * 3;;Nach Eingabe und Validierung dieses Ausdrucks bestimmt OCaml den Typ des Ausdrucks (in diesem Fall eine ganze Zahl) und zeigt das Ergebnis der Berechnung an:
val x : int = 7Man könnte versucht sein, alle Arten von Berechnungen durchzuführen. Achten Sie jedoch darauf, keine ganzen Zahlen und reelle Zahlen zu mischen, was in vielen Sprachen üblich ist, da sie in OCaml nicht automatisch konvertiert werden (Sie müssen eine Funktion verwenden, die eine ganze Zahl nimmt und eine reelle Zahl zurückgibt, oder umgekehrt, wenn der Operator verwendet ganze Zahlen). Im folgenden Beispiel erwartet der Operator +, dass zwei ganze Zahlen addiert werden, wenn es sich um zwei reelle Zahlen handelt:
# 2.3 + 1.;; Error: This expression has type float but an expression was expected of type intDieses einfache Beispiel gibt eine erste Vorstellung davon, wie der Typinferenzalgorithmus funktioniert. Tatsächlich haben wir beim Schreiben 2.3 + 1.die reellen Zahlen 2.3und 1.den +Integer- Operator hinzugefügt , was ein Problem darstellt. Um diese Berechnung durchzuführen, müssen wir einerseits sicherstellen, dass alle Zahlen den gleichen Typ haben (zum Beispiel ist es unmöglich zu addieren 2.3und 1weil 1eine ganze Zahl ungleich 1.oder ist 2.3) und andererseits das Gesetz verwenden use der internen Zusammensetzung +auf reelle Zahlen angewendet, +.in OCaml vermerkt . Also hätten wir schreiben sollen:
# 2.3 +. 1.;; - : float = 3.3Programme sind oft in Prozeduren und Funktionen strukturiert. Die Prozeduren bestehen aus einer Reihe von Befehlen, die mehrmals im Programm verwendet werden und der Einfachheit halber unter demselben Namen gruppiert sind. Eine Prozedur gibt keinen Wert zurück, da diese Rolle Funktionen zugewiesen wird. Viele Sprachen haben unterschiedliche Schlüsselwörter, um eine neue Prozedur oder eine neue Funktion einzuführen ( Prozedur und Funktion in Pascal , Unter und Funktion in Visual Basic …). OCaml hingegen hat nur Funktionen, und diese werden wie Variablen definiert. Um beispielsweise die Identität zu definieren, können wir schreiben:
# let id x = x;;Nach Eingabe und Validierung des Ausdrucks bestimmt der Typsynthesealgorithmus den Typ der Funktion. In dem von uns gegebenen Beispiel sagt jedoch nichts den Typ von voraus x, sodass die Funktion als polymorph erscheint (mit jedem Element der Menge 'averknüpft sie ein Bild, id xdas ein Element der Menge ist 'a):
val id : 'a -> 'a = <fun>Um eine Funktion aufzurufen, verwenden wir die folgende Syntax:
# id 5;; - : int = 5OCaml ermöglicht dank des Schlüsselworts functionoder auch die Verwendung anonymer Funktionen, d. h. Funktionen, die nicht mit einer Kennung verknüpft sind fun :
# function x -> x;; - : 'a -> 'a = <fun>Anonyme Funktionen können sofort aufgerufen oder zur Definition einer Funktion verwendet werden:
# (function x -> x + 1) 4;; - : int = 5 # let id = function x -> x;; val id : 'a -> 'a = <fun>Eine leistungsstarke Funktion von OCaml ist der Mustervergleich . Es kann mit den Schlüsselwörtern match withoder mit einer anonymen Funktion definiert werden, gefolgt von einem vertikalen Strich |, dem Muster, einem Pfeil ->und dem Rückgabewert:
# let est_nul x = # match x with # | 0 -> true (* la première barre verticale est facultative *) # | _ -> false;; val est_nul : int -> bool = <fun> # function # | 0 -> true (* la première barre verticale est facultative *) # | _ -> false;; - : int -> bool = <fun>Der Unterstrich _stellt das Standardmuster dar. Es ist möglich, mehreren Mustern gleichzeitig denselben Wert zuzuweisen:
# let contient_zero (x, y) = # match x, y with # | (0, _) | (_, 0) -> true # | _ -> false;; val contient_zero : int * int -> bool = <fun>Das Schlüsselwort wird whenverwendet, um eine Bedingung für das Muster auszudrücken:
# let contient_zero (x, y) = # match x, y with # | (x, y) when (x = 0 || y = 0) -> true # | _ -> false;; val contient_zero : int * int -> bool = <fun>Die Zeichen werden ..verwendet, um ein Muster auszudrücken, das die Zeichenbereiche filtert:
# let est_capitale c = # match c with # | 'a'..'z' -> false # | 'A'..'Z' -> true # | _ -> failwith "lettre invalide";; val est_capitale : char -> bool = <fun>Das Schlüsselwort wird asverwendet, um den gefilterten Wert zu benennen:
# let mettre_en_capitale c = # match c with # | 'a'..'z' as lettre -> Char.uppercase_ascii lettre # | 'A'..'Z' as lettre -> lettre # | _ -> failwith "lettre invalide";; val mettre_en_capitale : char -> char = <fun>Die Rekursion besteht darin, eine Funktion zu schreiben, die sich auf sich selbst bezieht, nach dem Modell der mathematischen Induktion. In OCaml werden rekursive Funktionen mit dem Schlüsselwort eingeführt rec.
Zum Beispiel können wir die Fakultätsfunktion definieren :
# let rec fact n = # match n with # | 0 -> 1 # | _ -> n * fact (n - 1);; val fact : int -> int = <fun>Wir können die Fibonacci-Folge definieren durch:
# let rec fib n = # match n with # | 0 -> 0 # | 1 -> 1 # | _ -> fib (n - 1) + fib (n - 2);; val fib : int -> int = <fun>Mit dem Schlüsselwort können Variablen und Funktionen innerhalb einer Funktion definiert werden in.
Zum Beispiel können wir die Fakultätsfunktion definieren:
# let fact n = # let rec fact_aux m a = # match m with # | 0 -> a # | _ -> fact_aux (m - 1) (m * a) # in fact_aux n 1;; val fact : int -> int = <fun>Wir können die Fibonacci-Folge definieren durch:
# let fib n = # let rec fib_aux m a b = # match m with # | 0 -> a # | _ -> fib_aux (m - 1) b (a + b) # in fib_aux n 0 1;; val fib : int -> int = <fun>Der OCaml-Compiler optimiert Terminalaufrufe: Wenn während der Auswertung einer Funktion der letzte Schritt der Aufruf einer (anderen) Funktion ist, springt OCaml direkt zu dieser neuen Funktion, ohne den Aufruf im Speicher zu behalten. jetzt nutzlos.
Insbesondere optimiert OCaml die Terminalrekursion . Zum Beispiel ist die zweite Funktion factoben (mit einem Hilfsparameter a) eine Terminalfunktion, die einer Schleife entspricht und ein äquivalentes Ergebnis liefert und somit der Leistung des entsprechenden zwingenden Codes entspricht.
Terminalrekursion ist genauso effizient wie Iteration; es ist daher vorzuziehen, wenn Sie damit Programme schreiben können, die übersichtlicher oder einfacher zu handhaben sind.
Die Listen werden in der Programmierung verwendet, insbesondere für die rekursive Verarbeitung. Die Elemente einer Liste haben alle den gleichen Typ. Um eine Liste zu erstellen, sind zwei Schreibweisen möglich, eine mit dem Verkettungsoperator ::und die andere mit dem Operator ; :
# 1 :: 2 :: 3 :: [];; - : int list = [1; 2; 3] # [1; 2; 3];; - : int list = [1; 2; 3]Der rechte Operand des letzten Verkettungsoperators ::eines Ausdrucks muss eine Liste sein:
# 1 :: 2 :: 3 :: [4; 5];; - : int list = [1; 2; 3; 4; 5]Es ist möglich, Listen mit dem Verkettungsoperator zu verketten @ :
# [1; 2; 3] @ [4; 5];; - : int list = [1; 2; 3; 4; 5]Um die Länge einer Liste herauszufinden, ohne die dafür List.lengthdefinierte Funktion zu verwenden, können wir schreiben:
# let rec longueur l = # match l with # | [] -> 0 # | _ :: q -> 1 + longueur q;; val longueur : 'a list -> int = <fun>Bei der Analyse dieser Funktion mit dem Typinferenzalgorithmus scheint es, dass die Liste jeden Datentyp enthalten kann 'a.
Die folgende Funktion erstellt eine Liste von Paaren aus zwei Listen: Die Länge dieser Liste entspricht der Länge der Liste, die im Parameter übergeben wurde, der die kürzeste ist.
# let rec couple l1 l2 = # match l1, l2 with # | ([], _) | (_, []) -> [] # | (t1 :: q1, t2 :: q2) -> (t1, t2) :: couple q1 q2;; val couple : 'a list -> 'b list -> ('a * 'b) list = <fun>Die folgende Funktion ruft das erste Element einer Liste ab:
# let premier_element l = # match l with # | [] -> failwith "liste vide" # | e :: _ -> e;; val premier_element : 'a list -> 'a = <fun>Die folgende Funktion ruft das zweite Element einer Liste ab:
# let deuxieme_element l = # match l with # | [] -> failwith "liste vide" # | [_] -> failwith "liste à un élément" # | _ :: e :: _ -> e;; val deuxieme_element : 'a list -> 'a = <fun>Die folgende Funktion ruft das erste Element der ersten Unterliste ab:
# let sous_premier_element l = # match l with # | [] -> failwith "liste vide" # | [] :: _ -> failwith "sous liste vide" # | (e :: _) :: _ -> e;; val sous_premier_element : 'a list list -> 'a = <fun>Die Funktionen höherer Ordnung sind Funktionen, die eine oder mehrere Funktionen in Eingang nehmen und/oder eine Funktion zurückgeben (dies wird als funktional bezeichnet). Die meisten funktionalen Sprachen haben Funktionen höherer Ordnung. OCaml In Bezug kann man Beispiele in den vordefinierten Modulen Funktionen finden Array, Listusw. Zum Beispiel der folgende Ausdruck:
# List.map (function i -> i * i) [0; 1; 2; 3; 4; 5];; - : int list = [0; 1; 4; 9; 16; 25]Die Funktion mapnimmt als Argument die anonyme Funktion, die insgesamt iihr Quadrat verknüpft, und wendet sie auf die Elemente der Liste an, wodurch die Liste der quadrierten Werte erstellt wird.
Ein anderes Beispiel :
# let double f i = f (f i);; val double : ('a -> 'a) -> 'a -> 'a = <fun>Die Funktion doublenimmt eine Funktion fund einen Wert als Parameter iund gilt zweimal ffür i.
# let trois = double (function i -> i + 1) 1;; val trois : int = 3 # let augmente_2 = double (function i -> i + 1);; val augmente_2 : int -> int = <fun> # let liste = # double ( # function # | [] -> [] # | e :: l -> (e + 1) :: l # ) [1; 2; 3];; val liste : int list = [3; 2; 3]Hier noch ein Beispiel:
# let rec parcours f e l = # match l with # | [] -> e # | t :: q -> f t (parcours f e q);; val parcours : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun> # (* somme des éléments de la liste [1; 1; 2] *) # parcours (+) 0 [1; 1; 2];; - : int = 4 # (* fonction calculant la somme des éléments d'une liste *) # let somme_liste = parcours (+) 0;; val somme_liste : int list -> int = <fun> # (* fonction calculant le produit des éléments d'une liste *) # let produit_liste = parcours ( *. ) 1.;; val produit_liste : float list -> float = <fun>Zum Schluss noch ein letztes Beispiel. Hier sind wir für die Definition eines neuen notierten Operators verantwortlich $. Dieser Operator führt die Kombination aus zwei Funktionen aus.
# let ( $ ) f g = function x -> f (g x) val ( $ ) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun> # let f x = x * x;; val f : int -> int = <fun> # let g x = x + 3;; val g : int -> int = <fun> # let h = f $ g;; val h : int -> int = <fun> # (* affiche 36 *) # print_int (h 3);;Um einen binären Baum eines beliebigen Typs zu definieren , verwenden wir einen rekursiven Typ. Wir können uns daher auf die folgende Schrift berufen:
# type 'a arbre = # | Feuille # | Branche of 'a arbre * 'a * 'a arbre;; type 'a arbre = Feuille | Branche of 'a arbre * 'a * 'a arbreDieser Baum besteht aus Zweigen, die sich wie gewünscht verzweigen und in Blättern enden. Um die Höhe eines Baumes zu kennen, verwenden wir dann:
# let rec hauteur = # function # | Feuille -> 0 # | Branche (gauche, _, droite) -> 1 + max (hauteur gauche) (hauteur droite);; val hauteur : 'a arbre -> int = <fun>Hier ist ein Beispiel für eine Funktion, die Memoization verwendet . Dies ist eine Funktion, die den n- ten Term der Fibonacci-Folge berechnet . Im Gegensatz zur klassischen rekursiven Funktion speichert diese die Ergebnisse und kann sie dank der Hash-Tabelle in konstanter Zeit ausgeben.
(* Taille de la table de hachage. *) let _HASH_TABLE_SIZE = 997 (* Retourne le n-ième terme de la suite de Fibonacci. *) let rec fibo = (* Pré-définitions. Ce code est exécuté une fois lors de la définition de la fonction, mais ne l'est pas à chaque appel. Cependant, `h` reste dans l'environnement de cette fonction pour chaque appel. *) let h = Hashtbl.create _HASH_TABLE_SIZE in (* Premiers termes. *) Hashtbl.add h 0 0; Hashtbl.add h 1 1; function | n when n < 0 -> invalid_arg "fibo" (* Pas de nombre négatif. *) | n -> try Hashtbl.find h n (* On a déjà calculé `fibo n`, on ressort donc le résultat stocké dans la table `h`. *) with Not_found -> (* Si l'élément n'est pas trouvé, … *) let r = fibo (n - 1) + fibo (n - 2) in (* … on le calcule, … *) Hashtbl.add h n r; (* … on le stocke, … *) r (* … et on renvoie la valeur. *)Wir schlagen hier vor, eine einfache Funktion zu implementieren, die es erlaubt, ein Polynom beliebigen Grades abzuleiten. Wir müssen zuerst den Typ angeben, der unser Polynom darstellt:
# type polyn = # | Num of float (* constante *) # | Var of string (* variable *) # | Neg of polyn (* négation *) # | Add of polyn * polyn (* addition *) # | Sub of polyn * polyn (* soustraction *) # | Mul of polyn * polyn (* multiplication *) # | Div of polyn * polyn (* division *) # | Pow of polyn * int;; (* exponentiation *) type polyn = Num of float | Var of string | Neg of polyn | Add of polyn * polyn | Sub of polyn * polyn | Mul of polyn * polyn | Div of polyn * polyn | Pow of polyn * intHier ist nun die Funktion, die dieses Polynom in Bezug auf die in Parameter angegebene Variable x herleitet.
# let rec deriv x = function # | Num _ -> Num 0. # | Var y when y = x -> Num 1. # | Var _ -> Num 0. # | Neg p -> Neg (deriv x p) (* -p' *) # | Add (p, q) -> Add (deriv x p, deriv x q) (* p' + q' *) # | Sub (p, q) -> Sub (deriv x p, deriv x q) (* p' - q' *) # | Mul (p, q) -> Add (Mul (deriv x p, q), Mul (p, deriv x q)) (* p'q + pq' *) # | Div (p, q) -> Div (Sub (Mul (deriv x p, q), Mul (p, deriv x q)), Pow (q, 2)) (* (p'q - pq')/q^2 *) # | Pow (p, 0) -> Num 0. # | Pow (p, 1) -> deriv x p # | Pow (p, n) -> Mul (Num (float_of_int n), Mul (deriv x p, Pow (p, n - 1))) (* n * p' * p^(n - 1) *) val deriv : string -> polyn -> polyn = <fun>Die OCaml-Implementierung wurde von anderen Autoren für andere Kompilierungsziele als Bytecode und nativen Code angepasst . Wir werden finden :
Viele Sprachen erweitern OCaml, um Funktionen hinzuzufügen.