"Monadentransformatoren sind stärker als Effekte" - Beispiele?

78

Das Papier "Programmieren und Denken mit algebraischen Effekten und abhängigen Typen" von Edwin C. Brady über Effekte in Idris enthält die (nicht referenzierte) Behauptung, dass:

Obwohl [Effekte und Monadentransformatoren] in der Leistung nicht gleichwertig sind - Monaden und Monadentransformatoren können mehr Konzepte ausdrücken - werden viele gängige effektive Berechnungen erfasst.

Welche Beispiele gibt es, die von Monadentransformatoren modelliert werden können, aber keine Effekte?

functional-programming monads effects idris geoff_h
quelle
22
Dies ist eine nützliche Frage, die von mehr Personen als nur dem Autor des Papiers beantwortet werden kann. Ein Beispiel für mehr Leistung ist das Zulassen doppelter Effekte.
Brian McKenna
5
Ich würde gerne die Antwort auf diese Frage wissen. Ich möchte nicht mit dem Autor des Papiers Kontakt aufnehmen müssen, wenn ich es hier finden konnte.
Bryn Keller
3
Das ist eine gute Frage , auch wenn es etwas Papier erwähnt ...
CND
11
Wenn ich mich richtig an Artikel erinnere, die ich in Andrej Bauers Blog gefunden habe , sind algebraische Effekte nur stilisierte Verwendungen der abgegrenzten Fortsetzungsmonade. Monaden sind also mindestens so mächtig wie algebraische Effekte. Die Homepage der Eff-Sprache , die von Grund auf algebraische Effekte verwendet, enthält Links zu einigen dieser Artikel. Ich poste dies nicht als Antwort, da ich die Details selbst nicht wirklich kenne.
Pyon
@ EduardoLeón Begrenzte Fortsetzungen finden sich in Bauer und Pretnar 2010, Programmieren mit algebraischen Effekten und Handlern (pdf) ; Das Papier endet mit der Frage: "Schließlich sind Fortsetzungen das kanonische Beispiel für einen nicht-algebraischen Recheneffekt. Es ist daher ein wenig überraschend, dass eff eine flexible und saubere Form der begrenzten Kontrolle bietet, zumal Fortsetzungen überhaupt nicht in unserem Design enthalten waren." Agenda. Was können wir dann von eff über Steuerungsoperatoren in einer effektiven Umgebung lernen? "
Charles Stewart

Antworten:

10

Fortsetzungen können mit CPS als Monaden modelliert werden, aber sie sind keine algebraischen Effekte, da sie nicht mit Lawvere-Theorien modelliert werden können. Siehe Martin Hyland und John Power, 2007, The Category Theoretic Understanding of Universal Algebra: Lawvere Theories and Monads (pdf) , ENTCS 172: 437-458.

Charles Stewart
quelle
Danke für die Antwort. Ich denke darüber nach und versuche, die Kategorietheorie in etwas Programmierteres zu übersetzen, um meinen Kopf herumzukriegen. @Eduardo kommentierte oben, dass Effekte isomorph zu begrenzten Fortsetzungen waren. Ich vermute also, dass es eine gewisse Intuition darüber gibt, dass nicht begrenzte Fortsetzungen nicht modelliert werden können. Effekte müssen möglicherweise auf eine bestimmte Region beschränkt und behandelt werden, bevor effektive Werte entweichen können, während Monaden ansteckender sind.
geoff_h
1
@geoff_h Ich sagte, algebraische Effekte könnten als Verwendungen der abgegrenzten Fortsetzungsmonade modelliert werden, nicht dass sie äquivalent sind - was durchaus der Fall sein könnte, aber ich weiß es nicht wirklich.
Pyon
@Eduardo Aber Eff erlaubt eine Darstellung von begrenzten Fortsetzungen - wenn auch eine, die manchmal rekursive Typen erfordert. Dies deutet auf einen Isomorphismus hin - Effekte können als begrenzte Fortsetzungen modelliert werden, begrenzte Fortsetzungen können als Effekte modelliert werden - aber vielleicht kann Eff auch einige nicht-algebraische Effekte darstellen - obwohl ich nicht sicher bin, ob ich ein gutes Verständnis dafür habe, was a nicht-algebraischer Effekt würde bedeuten.
geoff_h
@geoff_h Ich vermute, dass die Beziehung zwischen algeberaischen Effekten und begrenzten Fortsetzungen eher der Beziehung zwischen Monaden und CPS ähnelt: Letzteres bietet die Ausdruckskraft von Kontrollkonstrukten des ersteren, bietet jedoch nicht die Fähigkeit, Datentypen zu konstruieren.
Charles Stewart