Warum algebraische Effekte nötig sind

• Algebraische Effekte (Effect Handlers) sind flexible Werkzeuge zur Steuerung des Kontrollflusses, mit denen sich verschiedene Sprachfunktionen wie Ausnahmebehandlung, Generatoren und Coroutines auf Bibliotheksebene implementieren lassen
• Sie lassen sich auch auf in der funktionalen Programmierung häufige Themen wie Kontextverwaltung, Dependency Injection und den Ersatz globalen Zustands anwenden
• Sie tragen zur Einfachheit des API-Designs und zur automatischen Weitergabe von Zustand bzw. Umgebung im Code bei
• Zu den Vorteilen zählen außerdem Garantie funktionaler Reinheit, Replay-Fähigkeit und Sicherheits-Audits
• Durch jüngste Fortschritte in der Compilertechnik haben sich auch die Performance-Probleme deutlich verbessert

---

Überblick über algebraische Effekte (Algebraic Effects)

Algebraische Effekte (auch bekannt als Effect Handlers) sind ein Sprachfeature, das in letzter Zeit viel Aufmerksamkeit erhält. Sie gehören zu den Kernfunktionen von Ante und verschiedenen Forschungssprachen wie Koka, Effekt, Eff und Flix und verbreiten sich derzeit schnell. Viele Materialien erklären das Konzept von Effect Handlers, doch an einer tiefergehenden Erklärung, warum sie tatsächlich gebraucht werden, mangelt es oft. Dieser Artikel stellt die praktischen Einsatzmöglichkeiten und Vorteile algebraischer Effekte möglichst breit vor.

Syntax und Semantik im Schnelldurchlauf

• Algebraische Effekte ähneln „fortsetzbaren Ausnahmen“
• Effektfunktionen lassen sich etwa mit effect SayMessage deklarieren
• Mit foo () can SayMessage = ... kann angegeben werden, dass eine Funktion diesen Effekt verwenden darf
• Mit handle foo () | say_message () -> ... lässt sich der Effekt ähnlich wie mit try/catch bei Ausnahmen behandeln

Über diese Grundstruktur lassen sich Effektaufrufe und ihre Steuerung realisieren.

Erweiterung des Kontrollflusses durch benutzerdefinierte Abstraktionen

Der größte Vorteil algebraischer Effekte besteht darin, dass sich mit einem einzigen Sprachfeature Funktionen, für die ursprünglich jeweils eigene Sprachkonstrukte nötig waren — etwa Generatoren, Ausnahmen, Coroutines oder Asynchronität — als Bibliotheken implementieren lassen.

• Verwendet eine Funktion polymorphe Effektvariablen (can e), lassen sich verschiedene Effekte als Funktionsargumente übergeben und kombinieren
• Beispielsweise kann eine map-Funktion so deklariert werden, dass die übergebene Funktion einen beliebigen Effekt e nutzen darf, wodurch sie sich natürlich mit unterschiedlichen Effekten wie Ausgabe oder Asynchronität kombinieren lässt

Beispiele für die Implementierung von Ausnahmen und Generatoren

• Ausnahmen implementieren: Wird nach dem Auslösen eines Effekts kein resume aufgerufen, verhält sich das wie eine Ausnahme
• Generatoren implementieren: Definiert man einen Yield-Effekt, kann bei jedem Yield eines Werts ein externer Handler eingreifen und den Ablauf abhängig von Bedingungen steuern; auch fortgeschrittene Muster wie Filterung lassen sich mit relativ einfachem Code schreiben

Dass sich mehrere Effekte kombinieren lassen, ist ebenfalls ein großer Vorteil gegenüber bisherigen Techniken zur Effektabstraktion.

Einsatz als Abstraktionsschicht

Algebraische Effekte sind nicht nur zur Erweiterung grundlegender Programmierfunktionen nützlich, sondern auch in vielen Szenarien von Business-Anwendungen sehr brauchbar.

Dependency Injection

• Abhängige Objekte wie Datenbanken oder Ausgaben lassen sich als Effekte abstrahieren und über Handler verwalten
• Auch Test-Mocks oder die Umleitung von Ausgaben lassen sich flexibel umsetzen

Bedingtes Logging oder Ausgabesteuerung

• Ob Log-Meldungen ausgegeben werden, kann zentral anhand des Log-Levels gesteuert werden

Vereinfachung des API-Designs und automatische Weitergabe von Kontext

Nutzung von State-Effekten

• In Situationen, in denen ein Context-Objekt oder Umgebungsinformationen weitergereicht werden müssen, kann eine effektbasierte Implementierung, die nur get/set verwendet, die Zustandsverwaltung ohne explizites Weiterreichen automatisieren
• Bisher musste der Kontext an jede Funktion als Argument übergeben werden; mit einem State-Effekt lässt sich dieser Teil verbergen

Ersatz für globale Objekte

• Auch Zustände, die bisher über globale Objekte wie Zufallszahlengeneratoren oder Speicherallokation verwaltet wurden, lassen sich als Effekte abstrahieren, was Vorteile bei Code-Klarheit, Testbarkeit und Concurrency bringt
• Durch den Austausch des Handlers kann die tatsächliche Quelle von Zufallszahlen flexibel geändert werden

Unterstützung für Direct Style

• Bisher mussten oft mehrere Objekte verschachtelt behandelt werden, etwa durch Option-Typen oder Error-Wrapping
• Effekte ermöglichen es, solche Fehler- oder Nebenwirkungspfade auch ohne derartige Wrapper sauber auszudrücken

Garantie von Reinheit und Sicherheits-Audits

Nebenwirkungen explizit machen

• In den meisten Sprachen mit Effect Handlers müssen Funktionen mit Nebenwirkungen diese in ihrer Typsignatur explizit angeben, etwa mit can IO oder can Print
• Bei Thread-Erzeugung oder Software Transactional Memory (STM) sind zwingend reine Funktionen erforderlich

Log-Replay und deterministisches Networking

• Auf Basis von Reinheit lassen sich Handler wie record und replay bauen, mit denen sich Ausführungsergebnisse reproduzieren lassen
• Damit sind deterministische Ergebnisse und Rollbacks etwa für Debugging, Datenbanken und Game-Networking möglich

Unterstützung für Capability-based Security

• Da in der Typsignatur einer Funktion alle unbehandelten Effekte sichtbar werden, ist das bei Sicherheits-Audits externer Bibliotheken sehr hilfreich
• Wenn eine zuvor nebenwirkungsfreie Funktion nach einem Update plötzlich can IO erhält, kann aufrufender Code das sofort erkennen

Allerdings kann es auch dazu kommen, dass Effekte automatisch weitergereicht werden und dadurch unbeabsichtigt verarbeitet werden.

Effizienz und Fazit

• Früher galt die Laufzeiteffizienz als Schwäche, doch in letzter Zeit wurden viele Fälle — etwa tail-resumptive Effekte — stark optimiert
• Je nach Sprache kommen jeweils wirksame Compilerstrategien zum Einsatz, etwa closure call, evidence passing oder Handler-Spezialisierung

Es ist zu erwarten, dass algebraische Effekte in den Programmiersprachen der Zukunft eine noch wesentlich zentralere Rolle einnehmen werden.

[GN⁺]

Hacker-News-Kommentare

• Ich sehe dabei zwei Nachteile
  Der erste ist, dass im gegebenen Codeausschnitt überhaupt nicht ersichtlich ist, dass foo oder bar fehlschlagen können
  Um zu wissen, dass ein solcher Aufruf einen Error-Handler auslösen kann, muss man die Typ-Signatur direkt nachschlagen, und je nach Situation geht das nicht ohne IDE-Unterstützung nur manuell
  Der zweite ist, dass man, nachdem man erkannt hat, dass foo und bar fehlschlagen können, bei einem tatsächlichen Fehler im Call-Stack weit nach oben gehen muss, um einen with-Ausdruck zu finden, und danach dem entsprechenden Handler wieder nach unten folgen muss, um herauszufinden, welcher Code tatsächlich ausgeführt wird
  Dieses Verhalten lässt sich nicht statisch nachverfolgen und auch nicht direkt in der IDE per Sprung zur Definition verfolgen, weil my_function an mehreren Stellen mit unterschiedlichen Handlern aufgerufen werden kann
  Ich finde das Konzept sehr neuartig, habe aber letztlich Bedenken hinsichtlich Lesbarkeit und Debugging des Codes

  • Zum Problem, herauszufinden, welcher Code bei einem Laufzeitfehler aktiv wird: Genau das ist der Kern dynamischer Code-Injektion
    Wie bei anderen dynamischen Features wie shallow-binding oder deep-binding erfolgen Bindungen entlang des Call-Stacks
    Dass statische Analyse oder IDE-Sprünge nicht möglich sind, liegt ebenfalls an dieser Dynamik
    Ich glaube aber nicht, dass man sich in der Praxis allzu sehr darum kümmern muss
    Denn man ergänzt reinen Code nur um Effekte, sodass diese je nach Kontext als reine oder unreine Effekte, als Mock für Tests oder in Produktion unterschiedlich verdrahtet werden können
    Das folgt einem ähnlichen Prinzip wie Dependency Injection
    Ähnliches lässt sich auch mit traditionellen Monaden umsetzen, aber auch dort muss man letztlich den Call-Stack betrachten, um herauszufinden, wo eine Monade tatsächlich instanziiert wird
    Solche Techniken bieten Vorteile, haben aber auch klar erkennbare Kosten
    Sie sind nützlich für Tests und Sandboxing, machen aber weniger offensichtlich, was im Code konkret passiert

  • Jemand berichtet, eine Bachelorarbeit über IDE-Unterstützung für lexikalische Effekte und Handler geschrieben zu haben
    Alle oben angesprochenen Punkte seien seiner Meinung nach gut umsetzbar
    Link zur Arbeit

  • Es wird angemerkt, dass es im .NET-Umfeld die Tendenz gibt, Interfaces übermäßig zu verwenden, wodurch man mehrere Schritte braucht, um überhaupt zur Methodenimplementierung zu springen
    Oft ist die IDE-Hilfe sogar nutzlos, wenn die Implementierung in einem anderen Assembly liegt
    Bei fortgeschrittener Dependency Injection, insbesondere mit Autofac, werden wie bei dynamisch gescopten Variablen in LISP hierarchische Scopes aufgebaut, sodass zur Laufzeit entschieden wird, an welche Instanz ein Service gebunden wird
    In diesem Sinne könnte man Effekte als Injektion einer Interface-Instanz wie ISomeEffectHandler auffassen, wobei das Auftreten eines Effekts einem Methodenaufruf darauf entspricht
    Das konkrete Verhalten des Handlers, etwa Exceptions auslösen oder Logging, wird dann dynamisch durch die DI-Konfiguration bestimmt
    Bisher habe man meist das Muster verwendet, Exceptions zu throwen, aber man könne zu einem Design übergehen, das Effekte über Interfaces explizit macht und die Art der Behandlung vollständig der DI überlässt
    Dinge rund um Iteratoren wie yield habe man sich dabei noch nicht im Detail angesehen

  • Der Punkt, dass nicht sichtbar ist, dass foo und bar fehlschlagen können, sei gerade der Kern der Sache
    Man kann Code in direktem Stil schreiben, ohne sich um den Effektkontext kümmern zu müssen
    Auch die Suche danach, welcher Code im Fehlerfall ausgeführt wird, gehört zum Wesen der Abstraktion
    Welcher Effekt-Handler zur Laufzeit tatsächlich gebunden wird, wird erst später entschieden
    Das ist ähnlich wie bei f : g:(A -> B) -> t(A) -> B, wo man auch nicht im Voraus wissen kann, welcher Code ausgeführt wird, wenn g aufgerufen wird

  • Der Behauptung, statische Analyse sei unmöglich, weil man im Call-Stack nach oben wandern müsse, um den Handler zu finden, wird widersprochen
    Tatsächlich sei statische Analyse möglich, und in der IDE könne man etwa mit Funktionen wie „Zum Aufrufer springen“ auswählen, welche Handler verwendet werden

• Der „Pseudocode“ von Ante ist sehr beeindruckend
  Es wirkt wie eine gelungene Verbindung aus Eigenschaften von Haskell und der Ausdrucksstärke sowie Praxistauglichkeit von Elixir
  Es hinterlässt den Eindruck von Haskell für Entwickler
  Ich hoffe, dass der Compiler weiter reift
  Ich würde gern einmal eine App in Ante bauen

• Zur Behauptung, AE (Algebraic Effects) verallgemeinere den Kontrollfluss und könne auch Coroutines implementieren
  Ich denke, dass die einfachste Art, AE in einer neuen Sprach-Runtime zu implementieren, tatsächlich darin besteht, Coroutines zu verwenden und die grundlegende yield/resume-Struktur nur syntaktisch um Effekte zu erweitern
  Frage, ob ich dabei etwas übersehe

  • Als zentraler Unterschied zwischen AE und Coroutines wird Type Safety genannt
    Bei AE kann man explizit angeben, welche Effekte eine Funktion im Quellcode verwenden darf
    Wenn zum Beispiel query_db(): User can Database gilt, dann darf die Funktion auf die Datenbank zugreifen und beim Aufruf muss zwingend ein Database-Handler bereitgestellt werden
    Die Einschränkungen dessen, was möglich ist und was nicht, werden so sehr klar sichtbar
    Ähnlich wie Server Components in NextJS nicht direkt Client-Funktionen verwenden können, sind solche Sicherheitsbeschränkungen in vielen Bereichen beliebt

  • Effect-TS kommt dieser Vorgehensweise in JavaScript nahe, also der Nutzung von Coroutines, aber ob das am Ende wirklich eine gute Idee ist, ist unklar
    Ähnlich wie bei Dependency Injection im Spring-Framework besteht die Sorge, dass AE sich über den gesamten Code ausbreiten und letztlich nur zusätzliche Komplexität erzeugen
    Tatsächlich seien die Vorträge auf den EffectDays über den Einsatz von Effekten im Frontend meist kaum mehr als bedeutungsloser Boilerplate gewesen
    AE ist zwar ein faszinierendes Konzept, aber die Last, viele Dinge in Funktionen einzuwickeln, könnte gerade in JavaScript die typische Leichtigkeit des Schreibens beeinträchtigen
    Andererseits bietet ein Ansatz wie motioncanvas, der allein mit Coroutines komplexe 2D-Grafikszenarien einfach ausdrückt, klare Vorteile
    Passendes Video zu EffectDays
    MotionCanvas

  • Es wird behauptet, dass AE-Handler innerhalb eines Threads Code mehrfach resumen können, ähnlich wie call/cc
    Coroutines dagegen könnten bei jedem yield nur genau einmal wiederaufgenommen werden
    Gerade dieser unsichere Ausführungsfluss mache die Vorhersagbarkeit schwieriger, weshalb man lieber Funktionen bevorzuge, die explizit mehrfach aufgerufen werden können, oder stattdessen Iteratoren und andere Strukturen verwende

• Als Programmierabstraktion wirkt das Konzept äußerst attraktiv
  Aus der Kernel-Programmierung bei Sun kenne man etwa Aufrufe wie sleep(foo), nach denen der Code beim Aufwecken durch foo sehr kompakt geschrieben werden kann
  Die Last, allerlei Edge Cases einzeln über den Kontrollfluss behandeln zu müssen, werde dadurch geringer
  Wenn man nur auf Fragen der Speicherlokalität achte, könnte es sogar Spaß machen, viele Funktionen vorab in einen wartenden Zustand zu versetzen und den Algorithmus direkt als Mutation dieser Einheiten auszudrücken

• Zur Aussage „Algebraic Effects sind wie Exceptions, die fortgesetzt werden können“
  Es wird gefragt, worin sie sich praktisch von Typklassen wie ApplicativeError oder MonadError unterscheiden
  Die Art, Effekte anzugeben, die eine Funktion nutzen darf, erinnere an checked exceptions, und auch die Behandlung über handle-Ausdrücke sei fast identisch mit try/catch
  Solche Typklassen unterstützen bereits heute über handleError oder handleErrorWith das Abfangen von Fehlern
  Algebraic Effects hätten angeblich Vorteile für die „Sprachen der Zukunft“, seien aber im Grunde ein Konzept, das schon heute gut genutzt werde
  Erklärung in cats

  • Wenn man nur einen einzelnen Effekt betrachtet, gibt es vielleicht keinen großen Unterschied, aber sobald mehrere Effekte gleichzeitig gebraucht werden, ist direkte Effektunterstützung viel sauberer und intuitiver als explizit verschachtelte Monaden
    Beim Kombinieren von Monaden entstehen schnell lästige Probleme mit der Reihenfolge oder mit Funktionen, deren Ergebnisse nicht zu der erwarteten Monadenmenge passen und deshalb umsortiert werden müssen

  • Persönlich halte ich Monaden und Effekte nicht für konkurrierende Ansätze, sondern eher für komplementäre Interpretationen
    Siehe dazu auch entsprechende Arbeiten, etwa das Koka-Paper

  • Algebraic Effects arbeiten wie delimited continuations auf dem Programm-Stack
    Mit einem bloßen Monadentrick kann man nicht einfach sofort zu einem Effekt-Handler fünf Stack-Frames weiter oben springen, dort nur lokale Variablen ändern und dann wieder fünf Frames nach unten zurückkehren

  • Der Unterschied liege im statischen versus dynamischen Verhalten
    Beim Programmieren mit Monaden müsse man alle relevanten Methoden selbst implementieren, während man in einem Effektsystem zu jedem Zeitpunkt dynamisch Effekt-Handler installieren und bestehende Handler flexibel überschreiben könne
    Für Tests könne man zum Beispiel weiter unten eine spezielle Monade mit IO-Eigenschaften verwenden und nur darunter Effekt-Handler installieren, also auch komplexere Schichtungen aufbauen

  • Die Ähnlichkeiten sind groß, aber bei der Usability gibt es Unterschiede
    Algebraic Effects ähneln „free“-Monaden, sind aber eingebaut und dadurch syntaktisch einfacher und in der Komposition stärker
    In monadenzentrierten Sprachen wie Haskell lässt sich dank Typklassen-Inferenz im mtl-Stil und eingebauter bind-Syntax oberflächlich ein ähnlicher Effekt erzielen

• Man habe ursprünglich geglaubt, Algebraic Effects würden nur in statischen Typsystemen behandelt, kürzlich aber gelernt, dass es auch dynamischere Strukturen gibt
  Besonders eindrucksvoll seien zwei ältere Texte über eine dynamische Variante von Eff gewesen (der erste, der zweite)
  Auch Konzepte wie „parametrisierte Operationen mit verallgemeinerter Arität“ wirken spannend, wenn es darum geht, Abstraktion mit Programmierung zu verbinden

  • Was gefällt dir an statischen Typsystemen nicht?

• Es wird erwähnt, dass ein altes Konzept zuletzt unter neuem Namen und in neuem Rahmen wieder aufgetaucht ist
  Einführung in das LISP Condition System
  Erfahrungsbericht zu Algebraic Effects

• Jemand hat in einer frühen Alpha von OCaml 5 mit Effects Protohackers gemacht
  Das habe Spaß gemacht, aber die Toolchain sei damals etwas unbequem gewesen
  Ante vermittle ein ähnliches Gefühl, weshalb man auf die weitere Entwicklung gespannt sei

  • Seit OCaml 5.3 seien Effects deutlich besser als früher
    Ein Typsystem dafür gebe es zwar noch nicht, aber inzwischen wirke alles wesentlich aufgeräumter

• Nach viel Zeit mit Prolog sucht jemand nach einer Sprache, die nichtdeterministische Funktionskomposition und Compile-Time-Type-Checks leicht ermöglicht
  Ante sei dafür einer der interessanten Kandidaten
  Der Hinweis folgt, dass man Entwicklerwerkzeuge und Editor-Plugins wie LSP und tree-sitter nicht vergessen dürfe

  • Der Autor von Ante antwortet, dass es bereits LSP-Unterstützung gebe, wenn auch noch sehr grundlegend
    Für eine neue Sprache sei Tooling von Anfang an unverzichtbar
    Weil auch die Debugging-Erfahrung wichtig sei, denke man zudem darüber nach, zumindest im debug mode standardmäßig Replayability zu unterstützen

• Zur Aussage „Algebraic Effects sind wie Exceptions, die fortgesetzt werden können“
  Es wird gefragt, ob das Common Lisp Conditions ähnelt
  Interessant sei, dass alte Konzepte oft nur unter neuem Namen wieder auftauchen

  • Algebraic Effects sind viel allgemeiner als das LISP Condition System
    Weil Continuations multi-shot sein können, ähnelt das eher call/cc in Scheme
    Es wird aber auch erwähnt, dass diese Form von Parallelität unter Umständen schlechter sein kann, als sie gar nicht zu haben

  • In Smalltalk gibt es „resumable exceptions“

  • Wer Effekte nur als umbenanntes altes Condition System betrachtet, kommt in der Diskussion kaum weiter
    Die heute diskutierten Algebraic Effects unterscheiden sich in mehr als nur der Begrifflichkeit

  • Auch Dependency Injection kann in diesem Zusammenhang erwähnt werden