Implementierung der Active Patterns-Erweiterung für OCaml

über das Projekt

Im Frühjahr 2020 entwickelte ich im Rahmen der Frühjahrspraxis am Computer Science Center unter strenger Anleitung von Dmitry Kosarev ein neues Design für die Programmiersprache OCaml .

Warum OCaml

OCaml ist eine der erfolgreichsten und am weitesten entwickelten Implementierungen des industriellen Programmiersynkretismus (daher Multiparadigma, Multiplattform, sehr schneller Compiler, hohe Produktivität des generierten Codes) und der Mathematik (daher das hochmoderne Typsystem mit leistungsstarker Implementierung von Typinferenz, Ausdruckskraft und Erweiterbarkeit) Sprache, Nähe zur mathematischen Notation und Semantik).



Gleichzeitig ist die Sprachgemeinschaft sehr selektiv und fügt der Sprache langsam nur stark nachgefragte Konstruktionen hinzu, sofern sie keine Einschränkungen in die bestehende Sprache einführen. Daher ist der Kern der Sprache sehr klein und intuitiv, und OCaml wird sowohl von Industrieentwicklern als auch beispielsweise von Mathematikern des Instituts für Höhere Algebra und Zahlentheorie der St. Petersburg State University gerne verwendet .



Für einen tieferen Einblick in das Thema empfehle ich einen Blick auf die Artikel OCaml für die Massen und Warum OCaml .



Derzeit wird an der Implementierung eines Multicore-Systems für OCaml in Verbindung mit algebraischen Effekten gearbeitet, das gleichzeitig die Gesamtleistung der Sprache erhöht und die bestehenden Einschränkungen des Typsystems beseitigt, die mit der Tatsache verbunden sind, dass die Sprache unreine Berechnungen ermöglicht.

Mustervergleich und aktive Muster

Meine Arbeit konzentrierte sich hauptsächlich auf das Mustervergleichskonstrukt, das in funktionalen Programmiersprachen weit verbreitet ist.

Betrachten Sie zur Veranschaulichung ein einfaches Beispiel für das Drehen eines Knotens in einem Binärbaum. Im gebräuchlichsten imperativen Stil würde der Code wahrscheinlich folgendermaßen aussehen:

type 'a tree =
  | Node of 'a tree * 'a * 'a tree
  | Nil
let rotate_left' t =
  if is_node t
  then
    let a = get_left  t in
    let p = get_value t in
    let r = get_right t in
    if is_node r
    then
      let b = get_left  t in
      let q = get_value t in
      let c = get_right t in
      Node(Node(a,p,b),q,c)
    else t
  else t

Und hier ist genau derselbe Code, der mit dem Mustervergleichskonstrukt geschrieben wurde:

let rotate_left = function
  | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
  | Node _ | Nil as x -> x

Bei Verwendung dieses Designs haben wir die folgenden Vorteile:

• hohe Ausdruckskraft;
• Vollständigkeitsprüfung , die eine wichtige Eigenschaft für die Korrektheitsprüfung und das Refactoring von Programmen ist;
• effiziente Kompilierungsschemata.

Vollständigkeitsprüfung bedeutet, dass der Compiler, der die Typdefinition kennt, für jede Übereinstimmung prüfen kann, ob es wahr ist, dass alle möglichen Alternativen analysiert wurden und dass es keine nicht erreichbaren Verzweigungen gibt, egal wie komplex die Stichproben sind und wie sie sich überschneiden. Wenn Sie also die Typdefinition ändern (neue Alternativen hinzufügen, vorhandene entfernen oder ändern), gibt Ihnen der Compiler freundlicherweise alle Stellen im Code, die direkt betroffen waren.



Wenn ich beispielsweise dem Syntaxbaum neue Konstrukte hinzugefügt habe, zeigt mir der Compiler den AST-Typisierungscode bis zum Funktionskörper an, wo ich den Typisierungscode für die neuen Konstrukte schreiben muss:







Diese Eigenschaft macht OCaml sehr widerstandsfähig gegen Refactoring und andere Codeänderungen.



Trotz aller beschriebenen Vorteile gibt es auch eine sehr schwerwiegende Einschränkung der Anwendbarkeit. Hast du es bemerkt? Die Typdefinition muss öffentlich sein (damit der Compiler die Alternativen anzeigen kann, aus denen sie besteht). Und das bricht natürlich sofort selbst die einfachsten Abstraktionen zusammen. Wenn wir beispielsweise die einfachste Listenschnittstelle definieren möchten, können Sie nicht im Voraus feststellen, welche Typdefinition exportiert werden soll:

module type List = sig
  type 'a t (* = ? *)
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end

Dieses Problem ist jedoch nicht grundlegend, und wie bereits 1987 erwähnt, ist es möglich, einen Mustervergleich für abstrakte Typen zu erzielen.

Formulierung des Problems

Seit 1987 wurden in der Literatur viele verschiedene Entwürfe vorgestellt, um dieses Problem zu lösen. Hier nur einige davon:







Zu Beginn des Projekts wurde bereits an einer vernünftigen und objektiven Auswahl einer bestimmten Lösung für die Implementierung gearbeitet . Am vorteilhaftesten war die in der F # -Sprache implementierte Erweiterung für aktive Muster .



Ziel des Projekts war es, Active Patterns für den OCaml-Compiler zu implementieren und so weit wie möglich auszukommen.

Aktive Muster

Die Idee von aktiven Mustern (sowie ähnlichen Erweiterungen) ist sehr einfach: Da die Abstraktion durch Ausblenden der Implementierung innerhalb der Funktion erreicht wird, muss ein Funktionsaufruf innerhalb des Mustervergleichs zugelassen werden, der den unbekannten Wert des abstrakten Datentyps in eine bekannte Liste von Alternativen konvertiert. Aktive Muster codieren diese Liste von Alternativen direkt im Funktionsnamen. In der Oberfläche der obigen Liste müssen Sie also die folgende Funktion hinzufügen (|Cons|Nil|):

module type List = sig
  type 'a t
  val (|Cons|Nil|): 'a t -> ('a * 'a t, unit) choice2
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end

Das Ergebnis ist ein anonymer Summentyp choice2mit der folgenden Definition (es gibt ähnliche generierte Typen bis zu choice32):

type ('a, 'b) choice2 =
  | Choice2_1 of 'a
  | Choice2_2 of 'b

Daher (|Cons|Nil|)konvertiert die Funktion die Liste in eine von zwei Alternativen: entweder in ein Paar aus Kopf und Ende der Liste oder in eine leere Alternative, was bedeutet, dass die Liste leer war.



Das Definieren einer solchen Funktion für eine Standardliste ist trivial und würde folgendermaßen aussehen:

let (|Cons|Nil|) = function
  | []      -> Nil
  | x :: xs -> Cons(x, xs)

Betrachten Sie als Verwendungsbeispiel eine Funktion, mit der aufeinanderfolgende Duplikate in einer Liste entfernt werden:

(* destutter [1;1;4;3;3;2] = [1;4;3;2] *)
let rec destutter = function
  | Nil -> nil
  | Cons(x, Nil) -> cons x empty
  | Cons(x, Cons(y, rest)) ->
      if x = y 
      then destutter (cons y rest)
      else cons x (destutter (cons y rest))

Beachten Sie, dass alle Vorteile des Mustervergleichs erhalten bleiben: Die Übereinstimmungssyntax ist dieselbe, und die Vollständigkeitsprüfungen können vollständig funktionieren. Eine effiziente Kompilierung einer solchen Lösung würde den Rahmen dieser Übersicht sprengen, ist aber auch möglich.

Fortschritt

Im Rahmen dieser Arbeit konnte das Parsen und Typisieren der Erweiterung für den OCaml-Compiler Version 4.09 implementiert werden . Die Ergebnisse werden hier vorgestellt .



Der Compiler-Parser wird mithilfe des erweiterten Menhir- Parser-Generators implementiert . Menhir hat ein ziemlich vollständiges und detailliertes Handbuch , aber selbst bei ihm war nicht immer klar, wie man die Inferenzregel festlegen kann und wie nicht und warum. Der resultierende Parser-Patch ist recht klein und einfach, aber der Weg dorthin führte über 10-15 Shift-Reduce- und Reduce-Reduce-Konflikte, deren Analyse und Behebung einige Zeit in Anspruch nahm:







Ich möchte den Menhir-Entwicklern meinen Dank aussprechen und ihnen für ihre Arbeit bei der Detaillierung und Klärung der Fehler danken. Einmal konnte der Parser-Generator den Konflikt nicht veranschaulichen und musste ihn mit dem konstruierten Automaten für 1500 Zustände zerlegen. Dies erforderte natürlich eine Größenordnung mehr Zeit.



Das Schreiben von Nebenstellen war besonders schwierig. Der Tippcode ist ungefähr 37.000 Zeilen lang und fast ohne Papiere, was es für Anfänger schwierig macht, ihn herauszufinden. Ich wurde durch einen Artikel von Oleg Kiselev gerettet , in dem die wichtigsten Aspekte der Implementierung erläutert werden.



Eine weitere Schlussfolgerung, die ich für mich selbst gezogen habe, ist, nicht zu vergessen, die alten Versionen des Projekts zu verwenden. Hier ist zum Beispiel ein quantitativer Vergleich derselben Schreibweise für die Versionen 2019 und 2005:







Die Version 2019 enthält Compiler-Analysen und Warnungen sowie zusätzliche technische Details, an denen ich nicht interessiert war. Um zu verstehen, musste ich mir nur die Version 2005 ansehen, die nur Schlüsselaktionen enthält.



Die wichtigste Schlussfolgerung, die ich während meiner Arbeit gezogen habe, ist die Bestätigung, dass die Dokumentation für Open-Source-Projekte von entscheidender Bedeutung ist. So ausdrucksstark die Sprache auch ist, der Quellcode kann nur sagen, wie sich eine Funktion verhält, nicht was sie tut oder warum sie es so macht, wie sie es tut. Es ist sehr schwierig, die Aufrufketten type_self_pattern-> type_cases-> t ype_pat-> type_pat'-> zu lesen type_pat_auxund herauszufinden, welche Funktion Sie benötigen. oder nur ein Parameternameconstrraten Sie mal, welche Konstruktoren und warum hier geschrieben werden sollten.



Die Notwendigkeit, die Anwendungsfälle jedes Mal zu betrachten, verlangsamt den Programmierer und wird sehr schnell müde: Ich möchte Sie an die Regel "sieben, plus oder minus zwei" erinnern - genau so viele Objekte, die eine Person im Durchschnitt gleichzeitig im Auge behalten kann. Und wenn Sie endlich die Bedeutung des Parameters in der sechsten verschachtelten Funktion verstehen und plötzlich feststellen, dass Sie sich nicht erinnern, warum Sie ihn gebraucht haben, oder sich herausstellt, dass Sie ihn nicht gebraucht haben, wird es aufgrund des Zeitaufwands sehr traurig.

Fazit

Im Rahmen eines Projekts konnte ich das Parsen und Tippen für aktive Muster implementieren. Der von mir gepatchte Compiler kann die Datei mit Beispielen für die Verwendung von aktiven Mustern analysieren und eingeben.



Als Nächstes müssen Sie das Kompilierungsschema (OCaml verwendet eine nicht triviale optimierende Kompilierung der Musterübereinstimmung) und die Vollständigkeitsprüfungen des Schemas ändern , die vom OCaml-Compiler-Entwicklungsteam während der Arbeit am Projekt fast vollständig neu geschrieben wurden.



Ich hoffe, dass diese Implementierung mit oder ohne mich noch abgeschlossen ist. Trotz aller Schwierigkeiten war es großartig, einen industriellen Compiler für Ihre Lieblingssprache zu entwickeln.

Autor:

Alexander Bashkirov ist Student des Computer Science Center und hat im vierten Jahr einen Bachelor-Studiengang in Software Engineering an der St. Petersburg State University, einem Mitarbeiter von JetBrains.