Heute beenden wir unsere Artikelserie zur funktionalen Programmierung. Es stellte sich heraus, 11 Teile. Ich glaube, das ist eine Leistung. In diesem Artikel implementieren wir einen einfachen Stapelrechner (auch als "umgekehrte polnische Notation" bekannt). Die Implementierung basiert fast vollständig auf Funktionen mit nur einem speziellen Typ und im Allgemeinen ohne Vergleich mit der Stichprobe. Dies ist daher ein hervorragendes Testfeld für die in unserer Serie behandelten Konzepte.
Ich möchte @kleidemos separat danken. Er war der Hauptübersetzer und Manager der gesamten Artikelserie. Vielen Dank!
Wenn Sie mit einem solchen Taschenrechner nicht vertraut sind, funktioniert er wie folgt: Zahlen werden auf den Stapel geschoben, und Operationen wie Addition und Multiplikation wählen Zahlen oben im Stapel aus und setzen das Ergebnis der Operation zurück.
Schema der einfachen Berechnung auf dem Stapel:
Bevor Sie ein solches System entwerfen, sollten Sie überlegen, wie es verwendet wird. Nach einer Forth-ähnlichen Syntax geben wir jeder Aktion eine entsprechende Bezeichnung, damit Sie im obigen Beispiel Folgendes schreiben können:
EMPTY ONE THREE ADD TWO MUL SHOW
Vielleicht ist es unmöglich, genau diese Syntax zu erhalten, aber versuchen wir, dem so nahe wie möglich zu kommen.
Stapeldatentyp
Zunächst müssen Sie die Datenstruktur für den Stapel definieren. Der Einfachheit halber können Sie eine Liste von Gleitkommazahlen verwenden.
type Stack = float list
Es ist jedoch besser, es in einen einzelnen Fall-Union-Typ zu packen, um den Typ visueller zu gestalten:
type Stack = StackContents of float list
Warum es besser ist, genau das zu tun, können Sie hier lesen.
Erstellen Sie nun einen neuen Stapel mit StackContents als Konstruktor:
let newStack = StackContents [1.0;2.0;3.0]
Verwenden Sie zum Extrahieren von Inhalten aus einem vorhandenen Stapel das Muster, das mit StackContents übereinstimmt:
let (StackContents contents) = newStack // "contents" // float list = [1.0; 2.0; 3.0]
Push-Funktion
Als nächstes brauchen wir eine Möglichkeit, Zahlen auf diesen Stapel zu setzen. Fügen Sie dazu einfach mit " :: " einen neuen Wert am Anfang der Liste hinzu.
Funktionsbeispiel:
let push x aStack = let (StackContents contents) = aStack let newContents = x::contents StackContents newContents
Diese Funktion verfügt über eine Reihe von Funktionen, die es wert sind, besprochen zu werden.
Zunächst sollten Sie darauf achten, dass die list unveränderlich ist. Dies bedeutet, dass die Funktion einen vorhandenen Stapel übernehmen und einen neuen zurückgeben muss. Dies ist nicht nur eine Änderung an einem vorhandenen Stapel. Tatsächlich haben alle Funktionen in diesem Beispiel ein ähnliches Format:
Input: Stack - Output: Stack
Zweitens, warum gehen die Parameter in dieser Reihenfolge? Warum sollte der Stapel zuerst oder zuletzt gehen? Im Abschnitt über das Entwerfen von Funktionen mit Teilanwendung wurde gesagt, dass der am häufigsten geänderte Parameter der letzte sein sollte. Es wird bald möglich sein zu überprüfen, ob diese Empfehlungen befolgt werden.
Schließlich kann die Funktion präziser gestaltet werden, indem sie mit dem Muster im Funktionsparameter selbst übereinstimmt, anstatt den Funktionskörper einzulassen.
Die umgeschriebene Version:
let push x (StackContents contents) = StackContents (x::contents)
Viel besser!
Schauen Sie sich übrigens ihre anmutige Unterschrift an:
val push : float -> Stack -> Stack
Wie bereits erwähnt, sagt uns die Unterschrift viel.
In diesem Fall könnte ich nur anhand ihrer Signatur erraten, was diese Funktion tut, ohne zu wissen, dass sie "Push" heißt.
Dies ist ein weiterer Grund, warum es eine gute Idee war, explizite Typnamen zu haben. Wenn der Stapel nur eine Liste von Gleitkommazahlen wäre, wäre die Funktion nicht so selbstdokumentierend.
Überprüfen Sie auf die eine oder andere Weise:
let emptyStack = StackContents [] let stackWith1 = push 1.0 emptyStack let stackWith2 = push 2.0 stackWith1
Funktioniert super!
Stapel hochgestellt mit Push
Mit dieser einfachen Funktion können Sie leicht eine Operation definieren, die eine bestimmte Zahl auf den Stapel schiebt.
let ONE stack = push 1.0 stack let TWO stack = push 2.0 stack
Aber warte eine Minute! Sie sehen, dass der stack auf beiden Seiten des Ausdrucks erwähnt wird? In der Tat ist es nicht notwendig, es zweimal zu erwähnen. Stattdessen können Sie den Parameter weglassen und eine Funktion mit Teilanwendung schreiben:
let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0
Nun ist es offensichtlich, dass der stack zweimal erwähnt werden müsste, wenn die push Funktion eine andere Reihenfolge von Parametern hätte.
Es lohnt sich auch, eine Funktion zu definieren, die einen leeren Stapel erstellt:
let EMPTY = StackContents []
Überprüfen Sie die empfangenen Funktionen:
let stackWith1 = ONE EMPTY let stackWith2 = TWO stackWith1 let stackWith3 = THREE stackWith2
Ärgern diese Zwischenstapel? Ist es möglich, sie loszuwerden? Natürlich! Beachten Sie, dass die Funktionen ONE, TWO und THREE dieselbe Signatur haben:
Stack -> Stack
Sie sind also perfekt miteinander verbunden! Die Ausgabe einer Funktion kann wie folgt eingegeben werden:
let result123 = EMPTY |> ONE |> TWO |> THREE let result312 = EMPTY |> THREE |> ONE |> TWO
Aus dem Stapel herausspringen
Mit der Hinzufügung zum Stapel herausgefunden, aber was ist mit der pop Funktion?
Beim Abrufen vom Stapel ist es offensichtlich erforderlich, die Oberseite des Stapels zurückzugeben, aber ist es nur das?
In einem objektorientierten Stil lautet die Antwort ja . Im Fall von OOP würde der Stapel jedoch hinter den Kulissen geändert, so dass das oberste Element entfernt würde.
In einem funktionalen Stil ist der Stapel jedoch unveränderlich. Es gibt nur eine Möglichkeit, das oberste Element zu entfernen: Erstellen Sie einen neuen Stapel ohne dieses Element. Damit der Aufrufer Zugriff auf den neuen reduzierten Stapel hat, muss dieser zusammen mit dem obersten Element zurückgegeben werden.
Mit anderen Worten, die pop Funktion sollte zwei Werte zurückgeben, das oberste Element und den neuen Stapel. Der einfachste Weg, dies in F # zu tun, besteht darin, einfach ein Tupel zu verwenden.
Implementierung:
/// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack)
Die resultierende Funktion ist auch sehr einfach.
Der contents wie vor direkt aus dem Parameter extrahiert.
Anschließend wird der Inhalt des contents mit dem Ausdruck match..with überprüft.
Dann wird das oberste Element vom Rest der Liste getrennt, ein neuer Stapel wird basierend auf den verbleibenden Elementen erstellt, und schließlich wird all dies als Tupelpaar zurückgegeben.
Versuchen Sie, diesen Code auszuführen, und sehen Sie, was passiert. Sie erhalten einen Kompilierungsfehler!
Der Compiler hat einen Fall festgestellt, der nicht bearbeitet wurde. Was passiert, wenn der Stapel leer ist?
Sie müssen entscheiden, wie Sie damit umgehen wollen.
Normalerweise bevorzuge ich die Verwendung eines speziellen Status für den Fehler, aber in diesem speziellen Fall habe ich es vorgezogen, eine Ausnahme auszulösen. Behobene Version von pop mit leerer Fallbehandlung:
let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow"
Überprüfen Sie:
let initialStack = EMPTY |> ONE |> TWO let popped1, poppedStack = pop initialStack let popped2, poppedStack2 = pop poppedStack
und Ausnahmetest:
let _ = pop EMPTY
Arithmetische Funktionen
Nachdem das Hinzufügen und Löschen abgeschlossen ist, können Sie mit den Funktionen "Hinzufügen" und "Multiplizieren" arbeiten:
let ADD stack = let x,s = pop stack // let y,s2 = pop s // let result = x + y // push result s2 // let MUL stack = let x,s = pop stack // let y,s2 = pop s // let result = x * y // push result s2 //
Online-Tests:
let add1and2 = EMPTY |> ONE |> TWO |> ADD let add2and3 = EMPTY |> TWO |> THREE |> ADD let mult2and3 = EMPTY |> TWO |> THREE |> MUL
Es funktioniert!
Refactoring Zeit ...
Offensichtlich wird in diesen beiden Funktionen eine erhebliche Menge an Code dupliziert. Wie können wir das beheben?
Beide Funktionen extrahieren zwei Werte aus dem Stapel, wenden eine bestimmte Binärfunktion auf sie an und schieben das Ergebnis dann zurück auf den Stapel. Sie können den allgemeinen Code an die Binärfunktion ausgeben, die eine mathematische Funktion mit zwei Parametern übernimmt:
let binary mathFn stack = // let y,stack' = pop stack // let x,stack'' = pop stack' // let z = mathFn xy // push z stack''
Beachten Sie, dass in dieser Implementierung verschiedene Versionen desselben Objekts mit einer unterschiedlichen Anzahl von Anführungszeichen gekennzeichnet sind. Dies liegt daran, dass numerische Suffixe leicht zu Verwirrung führen können.
Frage: Warum haben die Parameter genau diese Reihenfolge, anstatt dass mathFn nach dem stack ?
Nachdem Sie eine binary , ist es viel einfacher, ADD und andere Funktionen zu definieren:
Erster Versuch, ADD mit binary zu implementieren:
let ADD aStack = binary (fun xy -> x + y) aStack
Aber Sie können Lambda loswerden, weil es repräsentiert die genaue Definition der eingebauten Funktion + :
let ADD aStack = binary (+) aStack
Auch hier kann eine Teilanwendung verwendet werden, um den Stapelparameter auszublenden. Endgültige Definition:
let ADD = binary (+)
Definition anderer mathematischer Funktionen:
let SUB = binary (-) let MUL = binary (*) let DIV = binary (../)
Probieren Sie es online aus:
let div2by3 = EMPTY |> THREE|> TWO |> DIV let sub2from5 = EMPTY |> TWO |> FIVE |> SUB let add1and2thenSub3 = EMPTY |> ONE |> TWO |> ADD |> THREE |> SUB
Ebenso können Sie eine Hilfsfunktion für unäre Operationen erstellen
let unary f stack = let x,stack' = pop stack push (fx) stack'
Und definieren Sie einige unäre Funktionen:
let NEG = unary (fun x -> -x) let SQUARE = unary (fun x -> x * x)
Interaktiver Modus:
let neg3 = EMPTY |> THREE|> NEG let square2 = EMPTY |> TWO |> SQUARE
Alles zusammenfügen | Alles zusammenfügen
In den anfänglichen Anforderungen wurde erwähnt, dass wir die Ergebnisse zeigen möchten, daher lohnt es sich, die SHOW-Funktion zu definieren.
let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack //
Bitte beachten Sie, dass in diesem Fall die neue Version des über pop empfangenen Stacks ignoriert wird. Das Endergebnis ist der ursprüngliche Stapel, als hätte er sich nie geändert.
Schließlich können Sie das folgende Beispiel aus den ursprünglichen Anforderungen schreiben
EMPTY |> ONE |> THREE |> ADD |> TWO |> MUL |> SHOW
Mach weiter
Es macht Spaß, aber was können Sie noch tun?
Sie können mehrere zusätzliche Funktionen definieren:
/// let DUP stack = // let x,_ = pop stack // push x stack /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let START = EMPTY
Mit diesen zusätzlichen Funktionen können Sie einige elegante Beispiele schreiben:
START |> ONE |> TWO |> SHOW START |> ONE |> TWO |> ADD |> SHOW |> THREE |> ADD |> SHOW START |> THREE |> DUP |> DUP |> MUL |> MUL // 27 START |> ONE |> TWO |> ADD |> SHOW // 3 |> THREE |> MUL |> SHOW // 9 |> TWO |> SWAP |> DIV |> SHOW // 9 div 2 = 4.5
Verwendung von Komposition anstelle von Pipelining
Das ist aber noch nicht alles. Tatsächlich gibt es eine andere interessante Möglichkeit, diese Funktionen darzustellen.
Wie bereits erwähnt, haben alle dieselbe Signatur:
Stack -> Stack
Da Eingabe und Ausgabe vom gleichen Typ sind, können diese Funktionen auch mit dem Kompositionsoperator >> kombiniert werden, und zwar nicht nur über Pipeline-Operatoren.
Einige Beispiele:
// let ONE_TWO_ADD = ONE >> TWO >> ADD START |> ONE_TWO_ADD |> SHOW // let SQUARE = DUP >> MUL START |> TWO |> SQUARE |> SHOW // let CUBE = DUP >> DUP >> MUL >> MUL START |> THREE |> CUBE |> SHOW // let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2 START |> THREE |> SQUARE |> SUM_NUMBERS_UPTO |> SHOW
In jedem dieser Beispiele wird eine neue Funktion unter Verwendung einer Zusammensetzung anderer Funktionen definiert. Dies ist ein gutes Beispiel für einen „kombinatorischen“ Ansatz zur Erstellung von Funktionen.
Förderer vs. Zusammensetzung
Wir haben zwei verschiedene Möglichkeiten gesehen, unser Modell zu verwenden. unter Verwendung von Förderbändern und Zusammensetzung. Aber was ist der Unterschied? Und warum sollte einer dem anderen vorgezogen werden?
Der Unterschied besteht darin, dass Pipelines in gewisser Weise eine "Echtzeit-Transformation" sind. Zum Zeitpunkt der Verwendung der Pipeline werden Operationen sofort durch die Übertragung eines bestimmten Stapels ausgeführt.
Auf der anderen Seite ist Komposition so etwas wie ein „Plan“, den wir implementieren möchten und der Funktionen aus einer Reihe von Komponenten ohne direkte Anwendung erstellt.
Sie können beispielsweise einen „Plan“ zum Berechnen des Quadrats einer Zahl durch eine Kombination kleiner Operationen erstellen:
let COMPOSED_SQUARE = DUP >> MUL
Ich kann das Äquivalent nicht basierend auf Pipelines angeben.
let PIPED_SQUARE = DUP |> MUL
Dies führt zu einem Kompilierungsfehler. Ich benötige eine bestimmte Stapelinstanz, damit der Ausdruck funktioniert:
let stackWith2 = EMPTY |> TWO let twoSquared = stackWith2 |> DUP |> MUL
Und selbst in diesem Fall kann ich nur für diese bestimmte Eingabe eine Antwort erhalten und keinen allgemeinen Berechnungsplan, der auf einer Eingabe basiert, wie im Beispiel mit COMPOSED_SQUARE .
Eine andere Möglichkeit, einen „Plan“ zu erstellen, besteht darin, das Lambda explizit an primitivere Funktionen zu übergeben:
let LAMBDA_SQUARE = unary (fun x -> x * x)
Dies ist ein expliziterer Weg (und höchstwahrscheinlich schneller), aber alle Vorteile und die Klarheit des kompositorischen Ansatzes gehen verloren.
Im Allgemeinen sollten Sie nach Möglichkeit einen kompositorischen Ansatz anstreben!
Vollständiger Code
Vollständiger Code für alle obigen Beispiele:
// ============================================== // // ============================================== type Stack = StackContents of float list // ============================================== // // ============================================== /// let push x (StackContents contents) = StackContents (x::contents) /// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow" // ============================================== // () // ============================================== // // // let binary mathFn stack = let y,stack' = pop stack let x,stack'' = pop stack' let z = mathFn xy push z stack'' // // // let unary f stack = let x,stack' = pop stack push (fx) stack' // ============================================== // () // ============================================== /// let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack // /// let DUP stack = let x,s = pop stack push x (push xs) /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let DROP stack = let _,s = pop stack // s // // ============================================== // , // ============================================== // // ------------------------------- let EMPTY = StackContents [] let START = EMPTY // // ------------------------------- let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0 // // ------------------------------- let ADD = binary (+) let SUB = binary (-) let MUL = binary (*) let DIV = binary (../) let NEG = unary (fun x -> -x) // ============================================== // , // ============================================== let SQUARE = DUP >> MUL let CUBE = DUP >> DUP >> MUL >> MUL let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2
Fazit
Wir haben einen einfachen stapelbasierten Taschenrechner. Wir haben gesehen, wie Sie mit einigen primitiven Operationen ( push , pop , binary , unary ) und anderen eine vollwertige DSL erstellen können, die einfach zu implementieren und zu verwenden ist.
Wie Sie sich vorstellen können, basierte dieses Beispiel ziemlich stark auf der Forth-Sprache. Ich empfehle das kostenlose Buch "Thinking Forth" , das nicht nur die Forth-Sprache, sondern auch andere ( nicht objektorientierte!) Methoden zum Zerlegen von Aufgaben beschreibt, die für die funktionale Programmierung im Allgemeinen gleichermaßen anwendbar sind.
Die Idee zu diesem Artikel kam mir aus Ashley Feniellos wunderschönem Blog. Wenn Sie tiefer in die Emulation einer auf F # basierenden stapelbasierten Sprache eintauchen möchten, beginnen Sie damit. Viel Spaß!
Zusätzliche Ressourcen
Es gibt viele Tutorials für F #, einschließlich Materialien für diejenigen, die mit C # oder Java-Erfahrung kommen. Die folgenden Links können hilfreich sein, wenn Sie tiefer in F # einsteigen:
Es werden auch verschiedene andere Möglichkeiten beschrieben , um mit dem Lernen von F # zu beginnen .
Schließlich ist die F # Community sehr anfängerfreundlich. Bei Slack gibt es einen sehr aktiven Chat, der von der F # Software Foundation unterstützt wird, mit Anfängerräumen, an denen Sie frei teilnehmen können . Wir empfehlen Ihnen dringend, dies zu tun!
Vergessen Sie nicht, die Seite der russischsprachigen Community F # zu besuchen! Wenn Sie Fragen zum Erlernen einer Sprache haben, diskutieren wir diese gerne in Chatrooms:
Über Übersetzungsautoren
Übersetzt von @kleidemos
Übersetzungs- und redaktionelle Änderungen wurden durch die Bemühungen der russischsprachigen Community von F # -Entwicklern vorgenommen . Wir danken auch @schvepsss und @shwars für die Vorbereitung dieses Artikels zur Veröffentlichung.