Warum ist es einfacher, über Programmiersprachen und Programme nachzudenken, die keine Nebenwirkungen haben?

Ich las "The Why of Y" von Richard P. Gabriel . Es ist ein leicht zu lesender Artikel über den Y-Kombinator, der ziemlich selten ist. Der Artikel beginnt mit der rekursiven Definition der Fakultätsfunktion:

(letrec ((f (lambda (n)
              (if (< n 2) 1 (* n (f (- n 1)))))))
  (f 10))

Und erklärt, dass letrecmit einem Nebeneffekt definiert werden kann:

(let ((f #f))
  (set! f (lambda (n)
            (if (< n 2) 1 (* n (f (- n 1))))))
  (f 10))

Und der Rest des Artikels beschreibt, dass es auch möglich ist, letrecmit dem Y-Kombinator zu definieren :

(define (Y f)
  (let ((g (lambda (h)
             (lambda (x)
               ((f (h h)) x)))))
    (g g)))

(let ((f (Y (lambda (fact)
              (lambda (n)
                (if (< n 2) 1 (* n (fact (- n 1)))))))))
  (f 10))

Offensichtlich ist dies viel komplizierter als die Version mit dem Nebeneffekt. Der Grund, warum es vorteilhaft ist, den Y-Kombinator der Nebenwirkung vorzuziehen, ist nur durch die Aussage gegeben:

Es ist einfacher, über Programmiersprachen und Programme nachzudenken, die keine Nebenwirkungen haben.

Dies wird nicht weiter erläutert. Ich versuche eine Erklärung zu finden.

Offensichtlich finden Sie Beispiele für unglaublich schwer zu lesende reine Funktionen, die dieselben Berechnungen durchführen wie Funktionen mit Nebenwirkungen, die viel einfacher zu lesen sind. Besonders wenn Sie eine mechanische Transformation wie einen Y-Kombinator verwenden, um zu einer Lösung zu gelangen. Das ist nicht das, was mit "leichter zu überlegen" gemeint ist.

Der Grund, warum es einfacher ist, über Funktionen ohne Nebenwirkungen nachzudenken, ist, dass Sie sich nur mit den Ein- und Ausgängen befassen müssen. Bei Nebenwirkungen müssen Sie sich auch Gedanken darüber machen, wie oft Funktionen aufgerufen werden, in welcher Reihenfolge sie aufgerufen werden, welche Daten innerhalb der Funktion erstellt werden, welche Daten gemeinsam genutzt werden und welche Daten kopiert werden. Und all diese Informationen für alle Funktionen, die möglicherweise intern für die von Ihnen aufgerufene Funktion und rekursiv für diese Funktionen usw. aufgerufen werden.

Dieser Effekt ist im Produktionscode mit mehreren Ebenen viel einfacher zu erkennen als in Spielzeugbeispielfunktionen. Meistens bedeutet dies, dass Sie sich viel mehr auf die Typensignatur einer Funktion verlassen können. Sie bemerken die Last der Nebenwirkungen wirklich, wenn Sie eine Weile reine funktionale Programmierung durchführen und dann darauf zurückkommen.

Eine interessante Eigenschaft von Sprachen ohne Nebenwirkungen ist, dass die Einführung von Parallelität, Parallelität oder Asynchronität die Bedeutung des Programms nicht ändern kann. Es kann es schneller machen. Oder es kann es langsamer machen. Aber es kann nichts falsch machen.

Dies macht es trivial, Programme automatisch zu parallelisieren. In der Tat so trivial, dass Sie normalerweise zu viel Parallelität haben! Das GHC-Team experimentierte mit automatischer Parallelisierung. Sie fanden heraus, dass selbst einfache Programme in Hunderte oder sogar Tausende von Threads zerlegt werden konnten. Der Overhead all dieser Threads wird jede mögliche Beschleunigung um mehrere Größenordnungen überwältigen.

Für die automatische Parallelisierung von Funktionsprogrammen lautet das Problem also "Wie gruppieren Sie kleine atomare Operationen zu nützlichen Größen paralleler Teile", im Gegensatz zu unreinen Programmen, bei denen das Problem darin besteht, "wie Sie große monolithische Operationen in nützliche aufteilen" Größen von parallelen Stücken ". Das Schöne daran ist, dass Ersteres heuristisch gemacht werden kann (denken Sie daran: Wenn Sie etwas falsch machen, kann das Schlimmste passieren, dass das Programm etwas langsamer läuft als es sein könnte), während Letzteres dem Lösen des Anhaltens entspricht Problem (im allgemeinen Fall), und wenn Sie es falsch verstehen, stürzt Ihr Programm einfach ab (wenn Sie Glück haben!) Oder gibt subtil falsche Ergebnisse zurück (im schlimmsten Fall).

Sprachen mit Nebenwirkungen verwenden eine Aliasing-Analyse , um festzustellen , ob ein Speicherort möglicherweise nach einem Funktionsaufruf neu geladen werden muss. Wie konservativ diese Analyse ist, hängt von der Sprache ab.

Für C muss dies ziemlich konservativ sein, da die Sprache nicht typsicher ist.

Für Java und C # müssen diese aufgrund ihrer erhöhten Typensicherheit nicht so konservativ sein.

Zu konservativ zu sein, verhindert Lastoptimierungen.

Eine solche Analyse wäre in einer Sprache ohne Nebenwirkungen unnötig (oder trivial, je nachdem, wie Sie sie betrachten).

Es gibt immer Optimierungen, um die von Ihnen angegebenen Annahmen zu nutzen. Das Neuordnen von Vorgängen fällt mir ein.

Ein amüsantes Beispiel, das mir in den Sinn kommt, taucht tatsächlich in einigen älteren Assemblersprachen auf. Insbesondere hatte MIPS die Regel, dass der Befehl nach einem bedingten Sprung ausgeführt wurde, unabhängig davon, welcher Zweig genommen wurde. Wenn Sie dies nicht wollten, setzen Sie nach dem Sprung einen NOP. Dies geschah aufgrund der Struktur der MIPS-Pipeline. In die bedingte Sprungausführung war ein natürlicher 1-Zyklus-Stall eingebaut, sodass Sie mit diesem Zyklus genauso gut etwas Nützliches tun können!

Compiler suchen häufig nach einer Operation, die für beide Zweige ausgeführt werden muss, und schieben sie in diesen Steckplatz, um ein wenig mehr Leistung zu erzielen. Wenn ein Compiler dies jedoch nicht kann, aber nachweisen kann, dass die Operation keine Nebenwirkungen hatte, kann der Compiler sie opportunistisch an dieser Stelle festhalten. Somit würde der Code auf einem Pfad einen Befehl schneller ausführen. Auf dem anderen Weg wird kein Schaden angerichtet.

"letrec kann mit einem Nebeneffekt definiert werden ..." Ich sehe keinen Nebeneffekt in Ihrer Definition. Ja, es set!wird eine typische Methode zur Erzeugung von Nebenwirkungen in Schema verwendet, aber in diesem Fall gibt es keine Nebenwirkungen - da fes rein lokal ist, kann es von keiner anderen Funktion als lokal referenziert werden. Es ist daher keine Nebenwirkung aus externer Sicht. Was dieser Code tut ist do eine Einschränkung in der Scoping von Schema - Hack um die standardmäßig nicht eine Lambda - Definition beziehen sich auf sich selbst zulässt.

Einige andere Sprachen haben Deklarationen, bei denen ein Ausdruck, der zum Erzeugen des Werts für eine Konstante verwendet wird, auf die Konstante selbst verweisen kann. In einer solchen Sprache kann die exakte äquivalente Definition verwendet werden, dies führt jedoch eindeutig nicht zu einem Nebeneffekt, da nur eine Konstante verwendet wird. Siehe zum Beispiel dieses äquivalente Haskell-Programm:

let f = \ n -> if n < 2 
                 then 1 
                 else n*(f (n-1)) 
        in (f 5)

(was 120 ergibt).

Dies hat eindeutig keine Nebenwirkungen (damit eine Funktion in Haskell einen Nebeneffekt hat, muss sie ihr in eine Monade eingeschlossenes Ergebnis zurückgeben, aber der hier zurückgegebene Typ ist ein einfacher numerischer Typ), ist jedoch strukturell identisch mit dem Code, den Sie zitieren.

Dies wird nicht weiter erläutert. Ich versuche eine Erklärung zu finden.

Es ist etwas, das vielen von uns innewohnt, die massive Codebasen debuggt haben, aber Sie müssen sich lange genug mit einer ausreichend großen Skala auf der Ebene der Aufseher auseinandersetzen, um dies zu würdigen. Es ist, als würde man verstehen, wie wichtig es ist, beim Poker in Position zu sein. Zunächst scheint es kein so nützlicher Vorteil zu sein, am Ende jeder Runde den letzten Platz einzunehmen, bis Sie eine Handhistorie von einer Million Händen aufzeichnen und feststellen, dass Sie in Position so viel mehr Geld gewonnen haben als aus.

Trotzdem stimme ich der Idee nicht zu, dass eine Änderung einer lokalen Variablen ein Nebeneffekt ist. Aus meiner Sicht verursacht eine Funktion keine Nebenwirkungen, wenn sie nichts außerhalb ihres Bereichs ändert, dass alles, was sie berührt und manipuliert, nichts unterhalb des Aufrufstapels oder eines Speichers oder einer Ressource beeinflusst, die die Funktion nicht selbst erworben hat .

Im Allgemeinen ist es am schwierigsten, in einer komplexen, umfangreichen Codebasis zu argumentieren, die nicht über das perfekteste Testverfahren verfügt, das man sich vorstellen kann, ein beständiges Statusmanagement, wie alle Änderungen an granularen Objekten in einer Videospielwelt, während Sie durch Dutzende von Daten waten Tausende von Funktionen, während versucht wurde, eine endlose Liste von Verdächtigen einzugrenzen, bei denen tatsächlich eine systemweite Invariante verletzt wurde ("das sollte niemals passieren, wer hat es getan?"). Wenn außerhalb einer Funktion nie etwas geändert wird, kann dies möglicherweise keine zentrale Fehlfunktion verursachen.

Dies ist natürlich nicht in allen Fällen möglich. Jede Anwendung, die eine auf einem anderen Computer gespeicherte Datenbank aktualisiert, ist von Natur aus so konzipiert, dass sie Nebenwirkungen verursacht, sowie jede Anwendung, die zum Laden und Schreiben von Dateien entwickelt wurde. Aber es gibt noch viel mehr, was wir in vielen Funktionen und Programmen ohne Nebenwirkungen tun können, wenn wir zum Beispiel über eine umfangreiche Bibliothek unveränderlicher Datenstrukturen verfügen und diese Denkweise weiter berücksichtigen.

Lustigerweise ist John Carmack auf den LISP- und Unveränderlichkeits-Zug gesprungen, obwohl er in den Tagen der am besten mikroabgestimmten C-Codierung angefangen hat. Ich habe festgestellt, dass ich etwas Ähnliches mache, obwohl ich immer noch viel C benutze. Ich denke, das ist die Natur von Pragmatikern, die jahrelang debuggt und versucht haben, komplexe, groß angelegte Systeme als Ganzes von einer Aufsebenebene aus zu betrachten. Selbst diejenigen, die überraschend robust und weitgehend fehlerfrei sind, können immer noch das unangenehme Gefühl haben, dass etwas Falsches um die Ecke lauert, wenn viele komplexe persistente Zustände unter den komplexesten miteinander verbundenen Graphen von Funktionsaufrufen geändert werden die Millionen von Codezeilen. Selbst wenn jede einzelne Schnittstelle mit einem Komponententest getestet wird und alle bestehen, gibt es '

In der Praxis finde ich oft, dass funktionale Programmierung es schwieriger macht, eine Funktion zu verstehen. Es dreht mein Gehirn immer noch in Drehungen und Knoten, besonders mit komplexer rekursiver Logik. Der gesamte intellektuelle Aufwand, der mit dem Herausfinden einiger in einer funktionalen Sprache geschriebener Funktionen verbunden ist, wird jedoch durch den eines komplexen Systems in den Schatten gestellt, bei dem persistente Zustände über Zehntausende von Funktionen hinweg geändert werden, wobei sich jede Funktion, die Nebenwirkungen verursacht, zur Gesamtsumme summiert Komplexität der Argumentation über die Richtigkeit des gesamten Systems als Ganzes.

Beachten Sie, dass Sie keine reine Funktionssprache benötigen, damit Funktionen Nebenwirkungen vermeiden. In einer Funktion geänderte lokale Zustände zählen nicht als Nebeneffekt, wie eine forfür eine Funktion lokale Schleifenzählervariable nicht als Nebeneffekt zählt. Ich schreibe heutzutage sogar C-Code mit dem Ziel, Nebenwirkungen nach Möglichkeit zu vermeiden, und habe mir eine Bibliothek unveränderlicher, threadsicherer Datenstrukturen ausgedacht, die teilweise geändert werden können, während der Rest der Daten flach kopiert wird, und es hat mir geholfen, a Sehr viel Grund zur Richtigkeit meines Systems. In diesem Sinne stimme ich dem Autor überhaupt nicht zu. Zumindest in C und C ++ in unternehmenskritischer Software kann eine Funktion dokumentieren, dass sie keine Nebenwirkungen hat, wenn sie nichts berührt, was möglicherweise die Welt außerhalb der Funktion beeinflussen könnte.