Wie kommt eine reine funktionale Programmiersprache ohne Zuweisungsanweisungen aus?

26

Bei der Lektüre des berühmten SICP stellte ich fest, dass die Autoren es eher ablehnen, die Aufgabenerklärung zu Schema in Kapitel 3 einzuführen. Ich las den Text und verstehe, warum sie sich so fühlen.

Da Schema die erste funktionale Programmiersprache ist, die ich jemals kenne, wundert es mich, dass es einige funktionale Programmiersprachen gibt (natürlich nicht Schema), die ohne Zuweisungen auskommen.

Verwenden wir das Beispiel aus dem Buch, das bank accountBeispiel. Wie geht das, wenn es keine Zuweisungsanweisung gibt? Wie ändere ich die balanceVariable? Ich frage das, weil ich weiß, dass es einige sogenannte reine Funktionssprachen gibt, und nach der vollständigen Theorie von Turing kann dies auch getan werden.

Ich habe C, Java, Python gelernt und benutze in jedem Programm, das ich geschrieben habe, viele Aufgaben. Es ist also wirklich eine aufschlussreiche Erfahrung. Ich hoffe wirklich, dass jemand kurz erklären kann, wie Zuweisungen in diesen funktionalen Programmiersprachen vermieden werden und welche tiefgreifenden Auswirkungen (falls vorhanden) dies auf diese Sprachen hat.

Das oben erwähnte Beispiel ist hier:

(define (make-withdraw balance)
    (lambda (amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds")))

Dies änderte die balancevon set!. Für mich sieht es sehr nach einer Klassenmethode aus, um das Klassenmitglied zu wechseln balance.

Wie gesagt, ich kenne mich mit funktionalen Programmiersprachen nicht aus. Wenn ich also etwas Falsches über sie gesagt habe, kann ich Sie gerne darauf hinweisen.

Gnijuohz
quelle
1
Bezüglich des Lernens einer rein funktionalen Sprache: Ich würde es nicht unbedingt empfehlen, dies sofort zu tun. Wenn Sie Haskell lernen, müssen Sie nicht nur lernen, wie man Programme ohne veränderbare Variablen schreibt, sondern auch die Faulheit und die Art und Weise, wie Haskell IO durchführt. Das könnte auf einmal ein bisschen viel sein. Wenn Sie lernen möchten, Programme ohne veränderlichen Status zu schreiben, ist es wahrscheinlich am einfachsten, eine Reihe von Schema-Programmen zu schreiben, ohne set!andere Funktionen zu verwenden, die mit a enden !. Sobald Sie damit vertraut sind, sollte der Übergang zu Pure FP einfacher sein.
13.

Antworten:

21

Wie geht das, wenn es keine Zuweisungsanweisung gibt? Wie ändere ich die Bilanzvariable?

Sie können keine Variablen ohne einen Zuweisungsoperator ändern.

Ich frage das, weil ich weiß, dass es einige sogenannte reine Funktionssprachen gibt, und nach der vollständigen Theorie von Turing kann dies auch getan werden.

Nicht ganz. Wenn eine Sprache Turing vollständig ist, bedeutet dies, dass sie alles berechnen kann, was die andere Sprache Turing vollständig berechnen kann. Dies bedeutet nicht, dass alle Funktionen, die andere Sprachen haben, vorhanden sein müssen.

Es ist kein Widerspruch, dass eine vollständige Programmiersprache von Turing den Wert einer Variablen nicht ändern kann, solange Sie für jedes Programm, das veränderbare Variablen enthält, ein gleichwertiges Programm schreiben können, das keine veränderbaren Variablen enthält (wobei "gleichwertig" bedeutet) dass es dasselbe berechnet). Und tatsächlich kann jedes Programm so geschrieben werden.

Zum Beispiel: In einer rein funktionalen Sprache wäre es einfach nicht möglich, eine Funktion zu schreiben, die bei jedem Aufruf einen anderen Kontostand zurückgibt. Sie können jedoch jedes Programm, das eine solche Funktion verwendet, auf andere Weise neu schreiben.


Da Sie nach einem Beispiel gefragt haben, betrachten wir ein imperatives Programm, das Ihre Funktion zum Zurückziehen (in Pseudocode) verwendet. Mit diesem Programm kann der Benutzer von einem Konto abheben, Einzahlungen vornehmen oder den Geldbetrag auf dem Konto abfragen:

account = make-withdraw(0)
ask for input until the user enters "quit"
    if the user entered "withdraw $x"
        account(x)
    if the user entered "deposit $x"
        account(-x)
    if the user entered "query"
        print("The balance of the account is " + account(0))

Hier ist eine Möglichkeit, dasselbe Programm zu schreiben, ohne veränderbare Variablen zu verwenden (ich kümmere mich nicht um referenziell transparentes IO, da die Frage nicht danach bestand):

function IO_loop(balance):
    ask for input
    if the user entered "withdraw $x"
        IO_loop(balance - x)
    if the user entered "deposit $x"
        IO_loop(balance + x)
    if the user entered "query"
        print("The balance of the account is " + balance)
        IO_loop(balance)
    if the user entered "quit"
        do nothing

 IO_loop(0)

Dieselbe Funktion könnte auch ohne Verwendung von Rekursion geschrieben werden, indem eine Falte über der Benutzereingabe verwendet wird (was idiomatischer wäre als eine explizite Rekursion), aber ich weiß noch nicht, ob Sie mit Falten vertraut sind, also habe ich es in a geschrieben Art und Weise, die nichts verwendet, was Sie noch nicht wissen.

sepp2k
quelle
Ich kann Ihren Standpunkt sehen, aber ich möchte ein Programm, das auch das Bankkonto simuliert und diese Dinge auch ausführen kann (Abheben und Einzahlen). Gibt es dann eine einfache Möglichkeit, dies zu tun?
Gnijuohz
@ Gnijuohz Es kommt immer darauf an, welches Problem genau Sie lösen wollen. Wenn Sie beispielsweise ein Startguthaben und eine Liste von Abhebungen und Einzahlungen haben und das Guthaben nach diesen Abhebungen und Einzahlungen wissen möchten, können Sie einfach die Summe der Einzahlungen abzüglich der Summe der Abhebungen berechnen und zum Startguthaben addieren . Also im Code wäre das newBalance = startingBalance + sum(deposits) - sum(withdrawals).
12.
1
@ Gnijuohz Ich habe meiner Antwort ein Beispielprogramm hinzugefügt.
12.
Vielen Dank für die Zeit und Mühen, die Sie in das Schreiben und Umschreiben der Antwort gesteckt haben! :)
Gnijuohz
Ich würde hinzufügen, dass die Verwendung von Continuation auch ein Mittel sein könnte, um dies im Schema zu erreichen (sofern Sie der Continuation ein Argument übergeben können?)
dader51
11

Sie haben Recht, dass es einer Methode für ein Objekt sehr ähnlich sieht. Das liegt daran, dass es im Wesentlichen so ist. Die lambdaFunktion ist eine Schließung, die die externe Variable balancein ihren Gültigkeitsbereich zieht . Mehrere Closures, die sich über dieselbe (n) externe (n) Variable (n) schließen, und mehrere Methoden für dasselbe Objekt sind zwei verschiedene Abstraktionen, um genau dasselbe zu tun. Wenn Sie beide Paradigmen verstehen, kann eine für die andere implementiert werden.

Die Art und Weise, wie reine funktionale Sprachen mit dem Status umgehen, ist Betrug. Wenn Sie zum Beispiel in Haskell Eingaben von einer externen Quelle lesen möchten (was natürlich nicht deterministisch ist und nicht notwendigerweise das gleiche Ergebnis zweimal liefert, wenn Sie es wiederholen), wird ein Monadentrick verwendet, um "We have" zu sagen Wir haben diese andere Pretend-Variable, die den Zustand des gesamten Rests der Welt darstellt , und wir können sie nicht direkt untersuchen, aber das Lesen von Eingaben ist eine reine Funktion, die den Zustand der Außenwelt aufnimmt und die deterministische Eingabe dieses exakten Zustands zurückgibt wird immer rendern, plus den neuen Zustand der Außenwelt. " (Das ist natürlich eine vereinfachte Erklärung. Wenn Sie sich über die Funktionsweise informieren, wird Ihr Gehirn ernsthaft geschädigt.)

Oder im Falle eines Bankkontoproblems kann die Variable anstelle eines neuen Werts den neuen Wert als Funktionsergebnis zurückgeben, und der Aufrufer muss sich dann in einem funktionalen Stil damit befassen, indem er im Allgemeinen alle Daten neu erstellt Das verweist auf diesen Wert mit einer neuen Version, die den aktualisierten Wert enthält. (Dies ist keine so umfangreiche Operation, wie es sich anhört, wenn Ihre Daten mit der richtigen Baumstruktur eingerichtet sind.)

Mason Wheeler
quelle
Ich bin wirklich an unserer Antwort und dem Beispiel von Haskell interessiert, aber aufgrund mangelnder Kenntnisse darüber kann ich den letzten Teil Ihrer Antwort (
naja
3
@ Gnijuohz Der letzte Absatz besagt, dass b = makeWithdraw(42); b(1); b(2); b(3); print(b(4))man nur tun kann, b = 42; b1 = withdraw(b1, 1); b2 = withdraw(b1, 2); b3 = withdraw(b2, 3); print(withdraw(b3, 4));wo withdraweinfach definiert ist als withdraw(balance, amount) = balance - amount.
12.
3

"Mehrfachzuweisungsoperatoren" sind ein Beispiel für ein Sprachmerkmal, das im Allgemeinen Nebenwirkungen hat und mit einigen nützlichen Eigenschaften funktionaler Sprachen (wie der verzögerten Auswertung) nicht kompatibel ist.

Dies bedeutet jedoch nicht, dass die Zuweisung im Allgemeinen nicht mit einem rein funktionalen Programmierstil kompatibel ist (siehe z. B. diese Diskussion ), und es bedeutet auch nicht, dass Sie keine Syntax erstellen können, die Aktionen ermöglicht, die im Allgemeinen wie Zuweisungen aussehen werden ohne Nebenwirkungen umgesetzt. Das Erstellen einer solchen Syntax und das Schreiben effizienter Programme ist jedoch zeitaufwändig und schwierig.

In Ihrem konkreten Beispiel haben Sie Recht - das Set! Operator ist eine Aufgabe. Es ist kein nebenwirkungsfreier Operator und es ist ein Ort, an dem Scheme mit einer rein funktionalen Herangehensweise an die Programmierung bricht.

Letztlich wird jede rein funktionale Sprache zu haben , mit der rein funktionalen Ansatz irgendwann zu brechen - die überwiegende Mehrheit der nützlichen Programme tun Nebenwirkungen hat. Die Entscheidung, wo dies getan werden soll, ist in der Regel eine Frage der Bequemlichkeit, und Sprachentwickler werden versuchen, dem Programmierer die größtmögliche Flexibilität bei der Entscheidung zu geben, wo sie mit einem rein funktionalen Ansatz brechen möchten, der für ihr Programm und ihre Problemdomäne geeignet ist.

Blaubeerfelder
quelle
"Letztendlich wird jede rein funktionale Sprache irgendwann mit dem rein funktionalen Ansatz brechen müssen - die große Mehrheit der nützlichen Programme hat Nebenwirkungen." Viele nützliche Programme können ohne veränderbare Variablen geschrieben werden.
sepp2k
1
... und mit "der überwiegenden Mehrheit" nützlicher Programme meinen Sie "alle", richtig? Es fällt mir schwer, mir überhaupt die Möglichkeit vorzustellen, dass es ein Programm gibt, das vernünftigerweise als "nützlich" bezeichnet werden kann und keine E / A-Vorgänge ausführt. Dies erfordert Nebenwirkungen in beide Richtungen.
Mason Wheeler
@MasonWheeler SQL-Programme machen keine E / A als solche. Es ist auch nicht ungewöhnlich, eine Reihe von Funktionen zu schreiben, die IO nicht in einer Sprache ausführen, die eine REPL hat, und diese dann einfach von einer REPL aufzurufen. Dies kann sehr nützlich sein, wenn Ihre Zielgruppe die REPL verwenden kann (insbesondere, wenn Sie Ihre Zielgruppe sind).
12.
1
@MasonWheeler: Nur ein einfaches Gegenbeispiel: Für die konzeptionelle Berechnung von n Stellen von pi sind keine E / A- Vorgänge erforderlich. Es ist "nur" Mathematik und Variablen. Die einzige erforderliche Eingabe ist n und der Rückgabewert ist Pi (bis n Stellen).
Joachim Sauer
1
@ Joachim Sauer Vielleicht möchten Sie das Ergebnis auf dem Bildschirm ausdrucken oder dem Benutzer auf andere Weise darüber berichten. Und zunächst möchten Sie einige Konstanten von irgendwo in das Programm laden. Also, wenn Sie pedantisch sein wollen, alle nützlichen Programme haben an einem gewissen Punkt IO zu tun, auch wenn es trivial Fällen ist die implizite sind und immer von der Programmierer von der Umgebung versteckt
blueberryfields
3

In einer rein funktionalen Sprache würde man ein Bankkontenobjekt als Stream-Transformer-Funktion programmieren. Das Objekt wird als eine Funktion aus einem unendlichen Strom von Anfragen von den Kontoinhabern (oder wem auch immer) zu einem potenziell unendlichen Strom von Antworten betrachtet. Die Funktion beginnt mit einem anfänglichen Kontostand und verarbeitet jede Anforderung im Eingabestream, um einen neuen Kontostand zu berechnen, der dann an den rekursiven Aufruf zurückgemeldet wird, um den Rest des Streams zu verarbeiten. (Ich erinnere mich, dass SICP in einem anderen Teil des Buches das Paradigma des Stream-Transformers erörtert.)

Eine ausführlichere Version dieses Paradigmas wird als "funktionale reaktive Programmierung" bezeichnet und hier auf StackOverflow beschrieben .

Die naive Art, Stream-Transformatoren zu erstellen, hat einige Probleme. Es ist möglich (in der Tat ziemlich einfach), fehlerhafte Programme zu schreiben, die alle alten Anforderungen beibehalten und Platz verschwenden. Im Ernst, es ist möglich, die Antwort auf die aktuelle Anfrage von zukünftigen Anfragen abhängig zu machen. An Lösungen für diese Probleme wird derzeit gearbeitet. Neel Krishnaswami ist die Kraft hinter ihnen.

Haftungsausschluss : Ich gehöre nicht zur Kirche der reinen funktionalen Programmierung. Tatsächlich gehöre ich keiner Kirche an :-)

Uday Reddy
quelle
Ich vermute, du gehörst zu einem Tempel? :-P
Gnijuohz
1
Der Tempel des freien Denkens. Keine Prediger da.
Uday Reddy
2

Es ist nicht möglich, ein Programm zu 100% funktionsfähig zu machen, wenn es irgendetwas Nützliches bewirken soll. (Wenn keine Nebenwirkungen erforderlich sind, hätte die gesamte Überlegung auf eine konstante Kompilierungszeit reduziert werden können.) Wie im Rückzugsbeispiel können Sie die meisten Prozeduren funktionsfähig machen, aber schließlich benötigen Sie Prozeduren mit Nebenwirkungen (Eingabe vom Benutzer, Ausgabe auf Konsole). Das heißt, Sie können den größten Teil Ihres Codes funktionsfähig machen, und dieser Teil ist auch automatisch leicht zu testen. Dann machen Sie einen zwingenden Code für die Eingabe / Ausgabe / Datenbank / ..., der ein Debuggen erfordern würde, aber den größten Teil des Codes sauber zu halten, wird nicht allzu viel Arbeit bedeuten. Ich verwende dein Auszahlungsbeispiel:

(define +no-founds+ "Insufficient funds")

;; functional withdraw
(define (make-withdraw balance amount)
    (if (>= balance amount)
        (- balance amount)
        +no-founds+))

;; functional atm loop
(define (atm balance thunk)
  (let* ((amount (thunk balance)) 
         (new-balance (make-withdraw balance amount)))
    (if (eqv? new-balance +no-founds+)
        (cons +no-founds+ '())
        (cons (list 'withdraw amount 'balance new-balance) (atm new-balance thunk)))))

;; functional balance-line -> string 
(define (balance->string x)
  (if (eqv? x +no-founds+)
      (string-append +no-founds+ "\n")
      (if (null? x)
          "\n"
          (let ((first-token (car x)))
            (string-append
             (cond ((symbol? first-token) (symbol->string first-token))
                   (else (number->string first-token)))
             " "
             (balance->string (cdr x)))))))

;; functional thunk to test  
(define (input-10 x) 10) ;; define a purly functional input-method

;; since all procedures involved are functional 
;; we expect the same result every time.
;; we use this to test atm and make-withdraw
(apply string-append (map balance->string (atm 100 input-10)))

;; no program can be purly functional in any language.
;; From here on there are imperative dirty procedures!

;; A procedure to get input from user is needed. 
;; Side effects makes it imperative
(define (user-input balance)
  (display "You have $")
  (display balance)
  (display " founds. How much to withdraw? ")
  (read))

;; We need a procedure to print stuff to the console 
;; as well. Side effects makes it imperative
(define (pretty-print-result x)
  (for-each (lambda (x) (display (balance->string x))) x))

;; use imperative procedure with atm.
(pretty-print-result (atm 100 user-input))

Es ist möglich, dasselbe in fast jeder Sprache zu tun und dieselben Ergebnisse zu erzielen (weniger Fehler), obwohl Sie möglicherweise temporäre Variablen innerhalb einer Prozedur setzen und sogar Sachen mutieren müssen, aber das ist nicht so wichtig wie die Prozedur wirkt tatsächlich funktional (die Parameter allein bestimmen das Ergebnis). Ich glaube, Sie werden in jeder Sprache ein besserer Programmierer, nachdem Sie ein wenig LISP programmiert haben :)

Sylwester
quelle
+1 für das ausführliche Beispiel und realistische Erklärungen zu Funktionsteilen und nicht reinen Funktionsteilen des Programms und Erwähnung, warum FP dennoch wichtig ist.
Zelphir Kaltstahl
1

Die Zuweisung ist eine schlechte Operation, weil sie den Zustandsraum in zwei Teile unterteilt, vor der Zuweisung und nach der Zuweisung. Dies führt zu Schwierigkeiten beim Verfolgen, wie die Variablen während der Programmausführung geändert werden. Die folgenden Dinge in funktionalen Sprachen ersetzen Aufgaben:

  1. Funktionsparameter, die direkt mit Rückgabewerten verknüpft sind
  2. Auswählen verschiedener Objekte, die zurückgegeben werden sollen, anstatt vorhandene Objekte zu ändern.
  3. Erstellen neuer, faul bewerteter Werte
  4. Auflisten aller möglichen Objekte, nicht nur der Objekte, die sich im Speicher befinden müssen
  5. keine Nebenwirkungen
tp1
quelle
Dies scheint die gestellte Frage nicht anzusprechen. Wie programmiert man ein Bankkontenobjekt in einer reinen Funktionssprache?
Uday Reddy
Es sind nur Funktionen, die von einem Bankkontodatensatz in einen anderen umwandeln. Der Schlüssel ist, dass bei solchen Transformationen neue Objekte ausgewählt werden, anstatt vorhandene zu ändern.
tp1
Wenn Sie einen Bankkontodatensatz in einen anderen umwandeln, möchten Sie, dass der Kunde die nächste Transaktion für den neuen Datensatz ausführt und nicht für den alten. Der "Kontaktpunkt" für den Kunden muss ständig aktualisiert werden, um auf den aktuellen Datensatz zu verweisen. Das ist eine Grundidee der "Modifikation". Bankkonten "Objekte" sind keine Bankkontodaten.
Uday Reddy