Warum wir algebraische Effekte brauchen

• Algebraische Effekte sind ein Sprachfeature, das Kontrollfluss wie fortsetzbare Ausnahmen abfängt und behandelt. Sie sind ein Kernfeature von Ante und spielen auch in Forschungssprachen wie Koka, Effekt, Eff und Flix eine zentrale Rolle.
• Mit demselben Mechanismus lassen sich Generatoren, Ausnahmen, async, Koroutinen und automatische Differenzierung auf Bibliotheksebene umsetzen; dank Effekt-Polymorphie müssen Funktionen wie map unabhängig von der Art des Effekts nur einmal geschrieben werden.
• Wenn man Dependency Injection und Kontextweitergabe wie Datenbankzugriff, Ausgabe, Logging oder Zustandsübergabe in Effekte umwandelt, lassen sich Test-Mocks, Ausgabesammlung und Log-Filterung durch Austausch von Handlern erledigen.
• Werden Effekte wie can IO, can Print oder can Fail in Funktionssignaturen sichtbar, ist das nützlich für Reinheitsgarantien, Aufzeichnen/Wiedergeben und Security Audits; bereits erlaubte Effekte können aber unbeabsichtigt an bestehende Handler weitergereicht werden.
• Eine traditionelle Schwäche waren Effizienzbedenken, doch neuere Sprachen reduzieren die Kosten durch Optimierung tail-resumptiver Effekte, Evidence Passing, Beschränkung auf ein einzelnes resume und Handler-Spezialisierung.

---

Das Grundmodell algebraischer Effekte

• Algebraische Effekte werden auch Effect Handlers genannt und lassen sich als Modell „fortsetzbarer Ausnahmen“ verstehen.
• In Ante-Pseudocode deklariert man Effektfunktionen und kennzeichnet in der Funktionssignatur mit can, dass der entsprechende Effekt verwendet werden kann.
  • Der Aufruf einer Effektfunktion wie say_message: Unit -> Unit entspricht dem „Werfen“ eines Effekts.
  • Die aufrufende Funktion macht die Möglichkeit, diesen Effekt zu verwenden, in der Signatur sichtbar, etwa foo () can SayMessage.
• Ein handle-Ausdruck fängt Effekte ähnlich wie try/catch ab und setzt die unterbrochene Berechnung mit einem Aufruf von resume fort.
  • Wenn der say_message-Handler print "Hello World!" ausführt und anschließend resume () aufruft, läuft die ursprüngliche Berechnung weiter und gibt 42 zurück.
• Der Begriff „algebraic“ ist größtenteils historisch übrig geblieben. Tatsächlich ist „Effect Handlers“ meist die genauere Bezeichnung, doch wegen der verbreiteten Vertrautheit wird hier der Name algebraische Effekte verwendet.

Benutzerdefinierter Kontrollfluss

• Algebraische Effekte ermöglichen es, mehrere Sprachfeatures mit einem einzigen Mechanismus zu implementieren.
  • Generatoren
  • Ausnahmen
  • async
  • Koroutinen
  • automatische Differenzierung
• Effekt-Polymorphie reduziert das Problem what color is your function.
  • map (input: Vec a) (f: a -> b can e): Vec b can e drückt aus, dass map denselben Effekt ausführt wie die Eingabefunktion f, egal welchen Effekt e diese ausführt.
  • Dasselbe map kann zusammen mit stdout-Ausgabe, asynchronen Funktionsaufrufen, Stream-yield usw. verwendet werden.
  • Viele Sprachen mit Effect Handlern erlauben es, die Effektvariable e wegzulassen und die vertraute Form map (input: Vec a) (f: a -> b): Vec b zu schreiben.
• Ausnahmen lassen sich implementieren, indem man beim Behandeln eines Effekts resume nicht aufruft.
  • Dafür definiert man throw: a -> never_returns für den Effekt Throw a.
  • Bei Division durch null wird throw "error: Division by zero!" aufgerufen; der Handler gibt die Nachricht aus und setzt die Berechnung nicht fort.
• Generatoren lassen sich mit yield: a -> Unit für den Effekt Yield a implementieren.
  • Beim Durchlaufen von Vektorelementen wird yield elem aufgerufen.
  • Der filter-Handler ruft, wenn der ge-yield-ete Wert die Bedingung erfüllt, erneut yield x auf und fährt mit resume () beim nächsten Element fort.
  • Der my_for_each-Handler führt für jeden ge-yield-eten Wert die Funktion f aus und fährt mit resume () fort.
• Auch ein kooperativer Scheduler lässt sich mit einem Effekt yield: Unit -> Unit bauen; der Handler übernimmt die Kontrolle und wechselt zur Ausführung einer anderen Funktion.
  • Das Scheduler-Beispiel von Effekt zeigt dieses Muster.
• Mehrere Effekte lassen sich gut miteinander komponieren; das gilt als Vorteil, der die Nutzbarkeit gegenüber anderen Effektabstraktionen erhöht.

Dependency Injection und Testbarkeit

• Effekte können auch in gewöhnlichen Business-Anwendungen für Dependency Injection verwendet werden.
• Statt ein Datenbankobjekt direkt als Funktionsargument zu übergeben, kann man einen Database-Effekt definieren.
  • Die bisherige Form nimmt ein DB-Objekt als Argument entgegen, etwa business_logic (db: Database) (x: I32).
  • Die effektbasierte Form wird zu business_logic (x: I32) can Database; intern wird query "..." aufgerufen.
• Die Wahl der konkreten Datenbank übernimmt ein Handler weiter oben im Call Stack.
  • So kann die Produktions-DB gegen eine andere DB oder eine Mock-DB für Tests ausgetauscht werden.
  • Ein mock_database-Handler kann query-Nachrichten ignorieren und mit resume stets DbResponse.Ok zurückgeben.
• Wird auch Ausgabe als Effekt behandelt, kann sie während Tests als String gesammelt werden, statt direkt auf stdout zu schreiben.
  • Der print_to_string-Handler fängt print msg-Aufrufe ab und hängt sie mit Zeilenumbrüchen an den String all_messages an.
  • output_messages kann den Rückgabewert 1234 und den Nachrichten-String prüfen, ohne tatsächlich etwas auszugeben.
• Logging kann mit einem Log-Effekt und LogLevel in bedingte Ausgabe umgewandelt werden.
  • log_handler ruft print msg auf, wenn der Level der Nachricht mindestens dem gesetzten Schwellwert entspricht.
  • foo () with log_handler Error gibt nur Fehlerlogs aus.

Sauberere APIs und Kontextweitergabe

• Algebraische Effekte können das Context-Objekt-Pattern, das durch ein Programm oder eine Bibliothek weitergereicht wird, als Effekt ausdrücken.
• Der Effekt Use a kann als Zustandseffekt betrachtet werden und stellt get: Unit -> a sowie set: a -> Unit bereit.
  • Der state-Handler hält den Anfangszustand, gibt bei get den aktuellen Kontext zurück und aktualisiert bei set auf den neuen Kontext.
  • Die beispielhafte state-Definition ignoriert Ownership-Regeln; in einer realen Implementierung kann eine Copy a-Beschränkung nötig sein.
• Ein Beispiel, bei dem Strings in einem Vektor gespeichert und Indizes als Schlüssel weitergereicht werden, zeigt die Kosten der Kontextweitergabe.
  • Ohne Effekte müssten push_string, get_string, append_with_separator, example usw. strings ständig als Argument entgegennehmen.
  • In der effektbasierten Implementierung rufen die primitiven Operationen push_string und get_string get/set auf, und höherer Code muss strings nicht direkt weiterreichen.
• Dieser Ansatz passt gut, wenn eine Bibliothek die interne Kontextweitergabe kapselt.
  • Nutzer der Bibliothek müssen sich nicht um interne Details der Kontextweitergabe kümmern.
  • Wer nicht an einen bestimmten Kontexttyp gebunden sein will, kann die benötigten Funktionen über ein Interface abstrahieren.

Ersatz für globale Variablen und Direct Style

• APIs, die äußerlich zustandslos wirken, aber tatsächlich Zustand benötigen, etwa Zufallszahlenerzeugung oder Speicherallokation, lassen sich statt über globale Variablen als Effekte ausdrücken.
• Das Beispiel der Zufallszahlenerzeugung zeigt die Last, ein Prng-Objekt durch das ganze Programm direkt weiterreichen zu müssen.
  • Ein globales Prng ist bequem, bringt aber Nachteile globaler Werte mit sich, etwa die Notwendigkeit von Thread-Sicherheit.
  • Mit random: Unit -> U8 des Effekts Random müssen Nutzer lediglich irgendwo weiter oben im Call Stack die Initialisierung per Handler angeben.
  • Soll später auf /dev/urandom oder eine andere Zufallsquelle umgestellt werden, reicht es, den Handler auszutauschen; der übrige Code im Call Stack muss nicht geändert werden.
• Auch Speicherallokation kann als Allocate-Effekt ausgedrückt werden.
  • allocate: (size: Usz) -> Alignment -> Ptr a
  • free: Ptr a -> Unit
  • Für die meisten Aufrufe verwendet man den globalen Allocator; in einem tight loop kann man dem Schleifenrumpf einen Handler hinzufügen und auf einen Arena-Allocator wechseln.
• Effekte ermöglichen Direct Style, statt Ergebnisse in dedizierte Wrapper-Werte zu packen und weiterzureichen.
  • Bei Maybe t muss man den Erfolgsfall mit and_then und map fortsetzen.
  • Syntax Sugar wie Rusts ? dient dazu, sich auf den guten Pfad zu konzentrieren.
  • Effektbasiertes get_line_from_stdin (): String can Fail, IO und parse (s: String): U32 can Fail werden wie gewöhnlicher sequenzieller Code geschrieben: line = ..., x = ..., x * 2.
• Fehlerbehandlung kann durch Anwenden eines Handlers modelliert werden, der den guten Pfad verlässt.
  • get_line_from_stdin () with default "42" behandelt den Fail-Effekt mit einem Standardwert.
• Auch unterschiedliche Fehlertypen komponieren sich auf natürliche Weise als Effektliste.
  • LibraryA.foo (): U32 can Throw LibraryA.Error
  • LibraryB.bar (): U32 can Throw LibraryB.Error
  • my_function kann Throw LibraryA.Error, Throw LibraryB.Error und Throw MyError gemeinsam deklarieren.
  • Wird die Wiederholung zu lang, kann man einen Typalias wie AllErrors = can Throw ... anlegen.
  • Derselbe Effekt Throw String wird zu einem zusammengeführt; wenn man sie trennen möchte, braucht man einen Wrapper-Typ wie MyError.

Reinheit, Wiederholbarkeit und Security Audits

• Die meisten Sprachen mit Effect Handlern verwenden Effekte dort, wo Seiteneffekte auftreten können; OCaml ist hier ungefähr die Ausnahme.
  • In Ante können Seiteneffekte nicht verwendet werden, wenn sie nicht mit can Print, can IO usw. markiert sind.
  • extern-Definitionen kann der Compiler nicht prüfen, daher muss man den Typdefinitionen vertrauen.
  • Die Möglichkeit, einen IO-Effekt nur im Debug-Modus auszuführen, um die Effektsicherheit im Release-Modus zu erhalten, ist ein geplantes Feature.
• Manche Funktionen verlangen als Eingabe reine Funktionen.
  • Beim Erzeugen eines Threads darf der erzeugte Thread nicht Handler aufrufen können, die dem aktuellen Thread gehören.
  • spawn_all (functions: Vec (Unit -> a pure)): Vec a can IO nimmt nur reine Funktionen entgegen, führt alle als Threads aus und wartet auf ihren Abschluss.
• Software Transactional Memory (STM) ist eine Nebenläufigkeitstechnik, die reine Funktionen benötigt.
  • Mehrere Funktionen werden gleichzeitig ausgeführt; wenn während einer Transaktion ein Wert von einem anderen Thread geändert wird, wird die Transaktion neu gestartet.
  • Eine Proof-of-Concept-Implementierung in Effekt findet sich unter effekt-stm.
• Reinheit kann ähnlich wie das Debugging-Tool rr Möglichkeiten zum Aufzeichnen/Wiedergeben bieten.
  • Zwei Handler, record und replay, behandeln die Top-Level-Effekte, die main ausgibt, typischerweise IO.
  • record zeichnet das Auftreten von Effekten und ihre Ergebnisse auf und leitet sie zur tatsächlichen Behandlung wieder an den eingebauten IO-Handler weiter.
  • replay führt kein echtes IO aus, sondern verwendet die Ergebnisse aus dem Effektlog.
  • Wenn Debug-Builds standardmäßig aufzeichnen, erhält man deterministisches Debugging.
• Die Effektliste in Funktionssignaturen hilft ähnlich wie Capability Based Security bei Security Audits.
  • Bei get_pi: Unit -> F64 weiß man, dass die Funktion nicht heimlich im Hintergrund IO ausführt.
  • Wird sie nach einem Bibliotheksupdate zu get_pi: Unit -> F64 can IO, bekommt der aufrufende Code einen Fehler, sofern er nicht bereits selbst IO verlangt.
  • Es ist wünschenswert, nur die minimal nötigen Effekte zu deklarieren, etwa nur Print statt des gesamten IO.
  • Das Hinzufügen eines neuen Effekts gilt als Änderung, die Semantic Versioning bricht.
  • Verwandtes Material sind Capability Based Security und Designing with Static Capabilities and Effects.

Grenzen und Implementierungsstrategien

• Eine Grenze des Effektansatzes ist, dass unbeabsichtigte Behandlung möglich ist.
  • Wenn eine Funktion neu IO verlangt, muss das keinen Fehler auslösen, falls die aufrufende Funktion IO bereits erlaubt.
  • Dasselbe gilt für den Fail-Effekt: Wenn eine Bibliotheksfunktion, die früher nicht fehlschlug, später Fail auslösen kann, kann dies an einen bestehenden Fail-Handler weitergereicht werden.
  • Dieses Verhalten kann je nach Situation in Ordnung sein, aber von der Absicht abweichen, wenn man eine separate Behandlung wie das Bereitstellen eines Standardwerts wollte.
• Der klassische Hauptnachteil waren Effizienzbedenken, doch die Kompilierungsergebnisse neuerer Effektsprachen haben sich stark verbessert.
• Viele Sprachen mit algebraischen Effekten optimieren tail-resumptive Effekte zu gewöhnlichen Closure-Aufrufen.
  • Tail-resumptive Effekte sind Effekte, bei denen der Handler ganz am Ende resume aufruft.
  • Die meisten realen Effekte fallen in diese Kategorie, ebenso die meisten Beispiele im Text.
  • Ausnahmen gelten als Sonderfall, weil sie resume überhaupt nicht aufrufen.
• Die Optimierungsstrategien unterscheiden sich je nach Sprache.
  • Koka verwendet Evidence Passing, zieht Effekte bis zum Handler hoch und kompiliert ohne Runtime nach C.
  • Ante und OCaml beschränken resume darauf, höchstens einmal aufgerufen zu werden.
    • Diese Beschränkung schließt einige Effekte wie Nichtdeterminismus aus.
    • Dafür vereinfacht sie die Ressourcenbehandlung und ermöglicht es, interne Continuations mit Ansätzen wie segmented stacks effizienter zu implementieren.
  • Effekt spezialisiert Handler vollständig im Programm und entfernt sie.
    • Dieser Ansatz bringt die Einschränkung mit sich, dass die meisten Funktionen second-class werden.
    • In boxed Form lassen sich first-class Funktionen erhalten und auf ein Pay-as-you-go-Modell umstellen.
    • Verwandtes Material sind die Effekt-Dokumentation zu captures und das Paper.