Wie kommt eine reine funktionale Programmiersprache ohne Zuweisungsanweisungen aus?

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.

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.

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.)

"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.

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 :-)

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 :)

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