Monaden

Lesehinweis

Anhang 0 enthält eine Einleitung und Hinweise zu Vorkenntnissen und Grundbegriffen, muß aber nicht zuerst gelesen werden. Der Abschnitt „Die Produktkontrolle“  soll die Frage nach dem Nutzen der Zustandsmonade beantworten und insofern die Beschäftigung mit Monaden motivieren.

Zu Anfang der Beschäftigung mit Monaden, können Monoide als einfache Spezialfälle einer Monade betrachtet werden.

Eine Monoid  " ; " ist eine Abbildung " ; ", mit der zu einer Operation "o ₀ " und einer Operation " o ₁" die Hintereinanderausführung dieser beiden Operationen als die Operation "o ₀ ; o ₁" geschrieben werden kann.

Stellt man eine den Rechnerzustand verändernde Operation bildlich durch ein Rechteck mit je einem eingehenden und einem ausgehenden Pfeil dar, so kann man die Operation "o ₀ ; o ₁" auch wieder als ein solches Rechteck darstellen.

Operation als Hintereinanderausführung zweier Operationen

       o0 ; o1   |
     .-----------|-----------.
     |           V           |
     | .-------------------. |
     | |        o0         | |
     | '-------------------' |
     |           |           |
     |           V           |
     | .-------------------. |
     | |        o1         | |
     | '-------------------' |
     '-----------|-----------'
                 V

Die Abbildung " ; " zum Verbinden zweier Operationen wird auch mit dem Namen "bind" bezeichnet.

Typ der Monoidverbindung

Hat eine Operation den Typ "O ", so ist der Typ der Monoidabbildung " ; " also der Typ "O  × O  → O " (einem Paar von Operationen wird eine Operation zugeordnet). Durch Curryfizierung kann dieser Typ auch als "O  → O  → O " (rechtsassoziativ zu lesen) interpretiert werden.

Monoide in Java 

Das im Anhang aufgelistete Java -Programm "Monoid" implementiert ein Monoid mit der Abbildung "bind" und wendet sie zur Verbindungen zweier Operationen an.

Assoziativität

Das Monoid " ; " soll Operationen so verbinden, daß von einer Verbindung auch dreier (oder mehrer) Operationen gesprochen werden kann, ohne daß dazu weiter beschrieben werden muß, welche beiden der drei Operationen „zuerst“ verbunden werden. Durch diese Forderung wird die Bedeutung des deutschsprachigen Begriffs „Hintereinanderausführung“ nur mit anderen Worten beschrieben, denn bei einer Hintereinanderausführung von drei Operationen ist eine Klammerung von zweien dieser Operationen ohne Bedeutung. Man kann vergleichsweise sagen, daß es für ein langes Rohr, das durch Verbindung von drei Rohrstücken erzeugt wurde, auch nicht mehr relevant ist, welche beiden Rohrstücken zuerst verbunden wurden.

Daher verlangt man, daß die Verbindungsabbildung " ; " eines Monoids assoziativ ist.

Assoziativität des Monoids

(o ₀  ; o ₁ ) ; o ₂  = o ₀  ; (o ₁  ; o ₂ )

Die Verbindungsabbildung " ; " erfüllt gerade diese Eigenschaft, denn ob man zuerst eine Operation "o ₀" und eine Operation "o ₁" (in dieser Reihenfolge) und dann eine Operation "o ₂ " oder zuerst eine Operation "o ₀" und dann eine Operation "o ₁" und eine Operation "o ₂ " (in dieser Reihenfolge) ausführt ist tatsächlich egal: Beides sind nur zwei verschiedene sprachliche Formulierungen für denselben Sachverhalt.

"(o ₀ ; o ₁) ; o ₂" soll gleich "o ₀ ; (o ₁ ; o ₂ )" sein

(o0 ; o1) ; o2   |
.----------------|----------------.
|                |                |
|      (o0 ; o1) v                |
|    .-----------------------.    |
|    |                       |    |
|    | .-------------------. |    |
|    | |        o0         | |    |
|    | '-------------------' |    |
|    |           |           |    |
|    |           V           |    |
|    | .-------------------. |    |
|    | |        o1         | |    |
|    | '-------------------' |    |
|    '-----------------------'    |
|                |                |
|                V                |
|      .-------------------.      |
|      |        o2         |      |
|      '-------------------'      |
'----------------|----------------'
                 V

o0 ; (o1 ; o2)   |
.----------------|----------------.
|                V                |
|      .-------------------.      |
|      |        o0         |      |
|      '-------------------'      |
|                |                |
|      (o1 ; o2) V                |
|    .-----------------------.    |
|    |                       |    |
|    | .-------------------. |    |
|    | |        o1         | |    |
|    | '-------------------' |    |
|    |           |           |    |
|    |           V           |    |
|    | .-------------------. |    |
|    | |        o2         | |    |
|    | '-------------------' |    |
|    '-----------------------'    |
|                |                |
'----------------|----------------'
                 V

Die neutrale Operation

Es gibt außerdem eine neutrale Operation "[ ]", deren Durchführung vor oder nach einer anderen Operation, den Vorzustand bzw. Nachzustand dieser Operation nicht verändert.

Neutralität von "[ ]"

[ ] : o  = o

o  : [ ] = o

Zusammenfassung des bisher Gesagten

Zusammengefaßt ist ein Monoid " ; " also eine Abbildung "B × B → B, (o ₀, o ₁) ↦ o ₀ : o ₁", die das Assoziativgesetz "(o ₀ ; o ₁) ; o ₂ = o ₀ ; (o ₁ ; o ₂ )" erfüllt und zu der es ein neutrales Element "[ ]" gibt, so daß "[ ] ; o  = o " und "o  ; [ ] = o ".

Operationen mit Produkt

Eine Operation verändert den Zustand des Rechners. Auf einem bestimmten Rechner hat jede Operation daher den gleichen Typ : Sie arbeitet ausgehend von einem Vorzustand  und hinterläßt einen Nachzustand. Beide Zustände sind dabei vom Typ „Zustand des Rechners“.

In einem Quelltext eines Programms würde man diese Operationen etwa als "o ₀ ; o ₁ " hintereinander schreiben. Der Informationsfluß von "o ₀" nach "o ₁" ist dabei „verborgen“, es tritt kein Element in der Notation auf, das den Zustand symbolisiert, der von "o ₀" nach "o ₁" übertragen wird, wenn man nicht die Verbindungsabbildung " ; " selber als solch ein Element ansehen will, doch auch diese kann man kaum als Darstellung des Zustands ansehen. Allerdings ist dies bei der Notation "o ₁(o ₀(z ))" ganz ähnlich, nur wird diese vereinbarungsgemäß so verstanden, daß der Wert des Terms "o ₀(z )" das Argument der Abbildung "o ₁" sein soll, während das Semikolon in Beschreibungen imperativer Sprachen selten explizit als Überträger eines Zustandes beschrieben wird.

Nun sollen Operationen "o " betrachtet werden, die bei ihrer Ausführung noch einen Wert "t  " vom Typ "T  " als ihr Produkt  festgelegen. Dieses Produkt wird nicht  als Teil des Nachzustandes angesehen, es bildet gemeinsam mit der Zustandsänderung das Verhalten  einer solchen Operation. Solche eine Operation wird auch eine Produktoperation  genannt (hier ist „Produkt“  nicht im Sinne von „Multiplikationsprodukt“  zu verstehen, sondern als das Ergebnis der Operation bei Sicht von außen).

Eine Operation "o " mit Produkt "t  " vom Typ "T  " und Nachzustand

                  Vorzustand
                       |
                       V
                  .---------.
                  | o       | T
                  |         |-------> Produkt
                  |         | t
                  '---------'            ^
                       |                 .
                       V                 .
                   Nachzustand   <.... Verhalten

Statt "o ₀ ; o ₁" wird auch die Schreibweise "o ₁(o ₀(…))" verwendet. Es handelt sich bei dieser Schreibweise aber nicht um die Anwendung einer Funktion "o ₁ " auf das Ergebnis einer Funktion "o ₀ ", da hier zusätzlich auch noch der von der Operation "o ₀ " hinterlassene Nachzustand als Vorzustand zur Operation "o ₁(o ₀(…)) " fungiert. Dieses Phänomen gibt es bei der Anwendung von Funktionen in der Mathematik nicht. In Programmiersprachen empfindet man es aber oft gerade als elegant, nur die Übergabe des Produkts von "o ₀" in Anlehnung an die mathematische Funktionsschreibweise als "o ₁(o ₀(…))" zu notieren und die Übergabe des Zustandes dabei mitzuverstehen, ohne daß dieser Zustand dabei explizit als Parameter oder Argument angegeben wird.

Die Operation "o ₁" soll in "o ₀ ; o ₁" also durch das Produkt "t ₀ " der vorangehenden Operation "o ₀" parametrisiert sein, sie soll also davon abhängen. Die durch den Parameter bestimmte Operation arbeitet dann auf dem Vorzustand, den die erste Operation "o ₀" hinterlassen hat.

Mit der Verbindung " ; " wird hier also bei der hier behandelten Zustandsmonade eine gegenüber der Monoidverbindung " ; " um die „Übergabe“ eines Wertes erweiterte Verbindung notiert. Zur Unterscheidung wird die Verbindung " ; " hier auch als eine Verbindung mit Produktweitergabe  bezeichnet.

Parametrisierte und bestimmte Operationen

In der Operation "o ₀ ; o ₁" ist die Operation "o ₀" ist also bereits vollständig bestimmt, während die Operation "o ₁" noch parametrisiert  ist und erst durch das Produkt der vorherigen Operation "o ₀" bestimmt wird.

Die Bezeichnung „parametrisierte Operation “  ist eine etwas anschaulichere Bezeichnung für eine Abbildung, die eine Operation ergibt. Soll für eine Operation besonders betont werden, daß sie nicht  parametrisiert ist, so wird sie als eine bestimmte Operation  bezeichnet. (Eine bestimmte Operation somit ist als nichts anderes als eine Operation.) Wird eine parametrisierte Operation "o " auf ein Argument "t " angewendet, so ergibt sich die bestimmte Operation "o (t )".

Eine bestimmte Operation "o "

                   Vorzustand
                       |
                       V
                  .---------.
                  | o       | T 
                  |         |-------> Produkt
                  |         | t 
                  '---------'
                       |
                       V
                   Nachzustand

Eine parametrisierte Operation "o "

Vorgaben ....>     Vorzustand
   .                   |
   .                   V
   v              .---------.
                  | o       | T 
Parameter ---->>  |         |-------> Produkt
                  |         | t 
                  '---------'            ^
                       |                 .
                       V                 .
                   Nachzustand  <....Verhalten

Im Schaubild wird der Doppelpfeil "->>  " mit einem nachfolgenden Abstand zu seinem Ziele verwendet, der andeuten soll, daß die Operation, auf die er weist, durch den Wert dieses Doppelpfeil zuerst bestimmt  wird. Erst die so bestimmte Operation arbeitet dann auf dem Vorzustand und ergibt ein Produkt und einen Nachzustand.

Die hier verwendeten Kompaßdiagramme  stellen Operationen so dar, daß Pfeile, die in senkrechter Richtung  auf einen Kasten treffen, zeitliche Zustandsflüsse  darstellen, während Pfeile, die in waagerechter Richtung ankoppeln, Wertflüsse  darstellen. So findet sich über einem Kästchen sein Vorzustand, darunter sein Nachzustand, links ein das Kästchen festlegender (beeinflussender) Wert, rechts ein vom Kästchen ermittelter Wert (Produkt). Vorzustand und Nachzustand bilden gemeinsam die Vorgaben  einer Operation, Produkt und Zustandsänderung das Verhalten  der Operation.

Insgesamt kann man sagen, daß eine parametrisierte Operation auf ihre Vorgaben mit einem bestimmten Verhalten reagiert.

Referentielle Transparenz parametrisierter Operationen

In manchen Programmiersprachen könnte ein Ausdruck "rand(10)" eine Pseudozufallszahl im Bereich von 0 bis 9 bezeichnen. Solch ein Ausdruck ist aber nicht referentiell transparent, so daß er in einer rein funktionalen Programmiersprache anscheinend nicht vorkommen kann. Der Ausdruck "rand(10)" bezeichnet keinen bestimmten Wert. Genauer gesagt: Der Wert ist durch den Ausdruck selber (also den Namen vor der runden Klammer und den Wert in der Klammer) nicht eindeutig bestimmt. (Er ist auch noch mitbestimmt durch den Zustand des Rechners und vielleicht den Zustand der Welt.)

Wie kann man solch einen Ausdruck überhaupt verstehen? Kann man ihn als Anwendung einer Funktion im mathematischen Sinne verstehen? Anscheinend ist das nicht möglich, da der Wert "rand(10)" nicht als Anwendung der Funktion "rand" auf den Wert "10" verstanden werden kann, denn sonst wäre der Wert bestimmt.

Nicht-referentiell-transparente Interpretation

         .--------.
         | rand   |
10 ----->|        |-----> Pseudozufallszahl
         |        |
         '--------'

Es gibt aber doch eine Möglichkeit diesen Ausdruck mit einer mathematischen Funktion zu verstehen, der aber eines Umwegs bedarf: Der Ausdruck "rand(10)" wird als Bezeichnung einer Operation verstanden. Insofern ist er  eindeutig: Er bezeichnet die  Operation, welche eine Pseudozufallszahl im Bereich von 0 bis 9 ergibt. Wenn eine Programmiersprache Operationen, die sich bei der Auswertung eines Ausdrucks ergeben, dann stillschweigend aktiviert und deren Produkt als Wert des Ausdrucks verwendet, ergibt sich schließlich die Pseudozufallszahl als Wert des Ausdrucks.

Die folgende Abbildung zeigt, wie mit dem Ausdruck "rand( 10 )" in dieser Interpretation eindeutig eine bestimmte Operation  bezeichnet wird, die dann wieder aus einem Vorzustand ein durch den Vorzustand eindeutig bestimmtes Verhalten  zeigt. In Programmiersprachen wird dieses Produkt der Operation dann üblicherweise als Wert des Ausdrucks "rand( 10 )" verwendet. Man könnte die Schreibweise ohne diesen Umweg eindeutig machen, wenn man stets etwas wie die Zuweisung "( Nachzustand, Zahl )=rand( Vorzustand, 10 )" schriebe, was aber als zu kompliziert empfunden wird. In objektorientierten Programmiersprachen wird dies allerdings einigermaßen häufig in der Schreibweise "zustand.rand( 10 )" mit dem den Zustand kapselnden Objekt "zustand" als Durchführer der Operation "rand( 10 )" verwendet; dabei ist aber nicht garantiert, daß der Wert dieses Ausdrucks nicht auch durch Zustände außerhalb des angegebenen Objekts beeinflußt wird.

Referentiell transparente Interpretation (ausführliche bildliche Darstellung): Die Funktion "rand" bestimmt eindeutig die Operation "rand( 10 )"; der Vorzustand dieser Operation bestimmt eindeutig deren Produkt und den Nachzustand

                                        | Vorzustand
                                        V
         .--------.            .------------------.
         | rand   | eindeutig  | Operation        | eindeutig
10 ----->|        |-------->>  | "rand( 10 )"     |----------> Produkt
         |        |            |                  | 
         '--------'            '------------------'
                                        | eindeutig
                                        V
                                   Nachzustand

Die nächste Abbildung stellt den gleichen Sachverhalt mit dem schon beschriebenen Doppelpfeil (für die Parametrisierung) dar.

Referentiell transparente Interpretation (verkürzte bildliche Darstellung)

                            Vorzustand
                                |
                                V
                           .---------.
             Parameter     | rand    |
        10 ------------>>  |         |-------> Pseudozufallszahl
   Argumentwert            |         |
                           '---------'

Parametrisierte Operationen erlauben es also, manchmal-bequeme Ausdrücke, wie "rand(10)", referentiell transparent zu interpretieren.

(Es ist nicht so überraschend, daß sich hinter einer auf den ersten Blick nicht-deterministischen Operation eine Kombination deterministischer Bestandteile verbirgt, wenn man daran denkt, daß klassische Prozessoren ja nur deterministische Operationen bieten.)

Nicht-parametrisierte Operationen als Startpunkte

Man kann eine Programmiersprache nach dem bisher Gesagten also als ein System zur Bezeichnung parametrisierter Operationen aufbauen. Doch, wenn es nur  parametrisierte Operationen gäbe, dann könnte ein Ausdruck wie "f(g(h(…)))" nie zu Ende geführt werden, weil jede Operation, die in die Klammern gesetzt wird, wieder ein weiteres Argument verlangte.

Daher sollte die Sprache noch um nicht-parametrisierte Operationen "g" erweitert werden. Mit diesen kann man dann "f(g)" schreiben, wobei "f" eine parametrisierte Operation und "g" eine nicht-parametrisierte Operation bezeichnet (also eine bestimmte Operation), die einer Konstanten (im Gegensatz zu einer Funktion) entspricht.

Einen solchen Ausdruck kann man daher als eine Verbindung von bestimmten und parametrisierten Operationen verstehen, wobei mit einer bestimmten Operation "g" begonnen wird, der dann eine parametrisierte Operation folgen kann. Weitere parametrisierte Operationen können dem folgen.

Durch diese Ausführungen sollte nun motiviert worden sein, warum der Text sich nun mit der Hintereinanderausführung von einer bestimmten und einer parametrisierten Operation  beschäftigen wird.

Hintereinanderausführung mit Produktweitergabe

Das folgende Schaubild veranschaulicht die Hintereinanderausführung " ; " zweier Operationen. Die erste, bestimmte Operation liefert einen Wert "t ₀" vom Typ "T ₀", die zweite Operation ist durch solch einen Wert parametrisiert. Die zweite, zunächst parametrisierte, Operation ergibt ein Produkt "t ₁" vom Typ "T ₁" und hinterläßt einen bestimmten Nachzustand.

Insgesamt ergibt sich durch die Hintereinanderausführung dann eine bestimmte Operation "o ₀ ; o ₁", die ein Produkt "t ₁" vom Typ "T ₁" ergibt und den Nachzustand von "o ₁" hinterläßt.

Eine bestimmte Operation "o ₀ ; o ₁" als Hintereinanderausführung einer bestimmten Operation "o ₀" und einer parametrisierten Operation "o ₁"

                       Vorzustand
  o0 ; o1                  |
.--------------------------|-----------------------.
|                          |                       |
|                          V                       |
|                     .--------.                   |
|                     | o0     | T0      Produkt   |
|                     |        |------------.      |
|                     |        | t0         |      |
|                     '--------'            |      |
|                          |                |      |
|       .-----------------------------------'      |
|       |                  |                       |
|       |                  V                       |
|       |             .--------.                   |
|       |             | o1     | T1                |
|       '--------->>  |        |--------------------------------> Produkt
|    Argument         |        | t1                |
|                     '--------'                   |
'--------------------------|-----------------------'
                           |
                           V
                       Nachzustand

Die beiden Operationen, welche von der Monade verbunden werden, sind nicht ganz gleich. Die erste Operation "o ₀" ist nämlich nicht  parametrisiert, wie die zweite Operation "o ₁". Die Verbindung "o ₀ ; o ₁" ist wieder, wie der erste Operand, nicht  parametrisiert.

Eine nicht-parametrisierte Operation ist eine bestimmte  Operation, während bei einer parametrisierten Operation die Operation noch offen gelassen ist und erst durch das Argument bestimmt wird. Die Verbindung " ; " akzeptiert also eine bestimmte Operation und fügt ihr eine passende, durch das Produkt der ersten Operation parametrisierte, zweite Operation hinzu, um schließlich wieder eine bestimmte Operation zu ergeben. An diese könnte also dann wiederum eine parametrisierte Operation angeschlossen werden.

Typ der monadischen Abbildung

Der Typ "OT  " ( „T-Operation“ ) soll der Typ einer Operation mit einem Produkt vom Typ "T  " sein. Ist eine solche Operation vom Typ "OT₁ " durch einen Parameter "t ₀" vom Typ "T ₀ " parametrisiert, so ergibt sie sich also erst aus der Anwendung einer Abbildung "o ₁" vom Typ "T ₀ → OT ₁ " auf das Argument "t ₀". Wenn eine andere Operation "o ₀" dieses Argument "t ₀" vom Typ "T ₀ " liefern soll, so muß ihr Typ also "OT ₀ " sein. Die Monade kann dann die bestimmte Operation "o ₀" mit der bestimmten Operation "o ₁(t ₀)" verbinden, indem sie zuerst die Operation "o ₁(t ₀)" anhand des von "o ₀" gelieferten Wertes "t ₀" festlegt und dann diese Operation "o ₁(t ₀)" auf den Nachzustand von "o ₀" anwendet, wodurch sich ein weiterer Wert "t ₁" vom Typ "T ₁" ergibt, da die Operation "o ₁(t ₀)" ja den Typ "OT ₁ " hat. Insgesamt ergibt sich also durch die Verbindung ein Wert "t ₁" vom Typ "T ₁ " und der von der Operation "o ₁(t ₀)" hinterlassene Nachzustand.

Der Typ der monadischen Abbildung " ; " ist also "OT ₀ × (T ₀  → OT ₁ ) → OT ₁ ", nach Curryfizierung kann dieser Typ auch als "OT ₀ → (T ₀  → OT ₁ ) → OT ₁ " geschrieben werden.

Der Operationstypkonstruktor

Für die Arbeit mit der vorgestellten Monade ist es hilfreich, zwei Konstruktoren zur Verfügung zu haben.

Der Operationstypkonstruktor "O" erlaubt es, zu einem Typ den Typ einer Operation mit einem Produkt dieses Typs  zu notieren. Ist beispielsweise "{0, 1, 2, 3}" der Typ der natürlichen Zahlen, die kleiner als die Zahl "4" sind, so soll "O{0, 1, 2, 3}" der Typ einer Operation mit einem Ergebnis vom Typ "{0, 1, 2, 3}" sein. Es sei daran erinnert, daß eine solche Operation durch einen Vorzustand beeinflußt werden kann und ihren Nachzustand beeinflussen kann, also mehr Verbindungen hat als nur die Ermittlung eines Wertes vom Typ "{0, 1, 2, 3}". Der Typ des Zustandes wird jedoch nicht beim Typ mit angegeben, sondern ist im Operationstypkonstruktor enthalten, der insofern für jeden Rechner ein anderer Typ ist. Dieser Operationstypkonstruktor wurde ja schon im vorherigen Abschnitt verwendet. Er wurde wegen seiner Bedeutung hier noch einmal besonders beschrieben.

Der Operationskonstruktor

Zu einer bestimmten Produktoperation gehört ein Wert und eine Zustandsänderung  (Abbildung des Vorzustandes auf den Nachzustand). Ein Operationskonstruktor soll aus einem Wert eine Operation machen. Wenn dies möglichst neutral  geschehen soll, so liegt es nahe, den Wert als Wert der Operation festzulegen und als Zustandsänderung die neutrale Zustandsveränderung zu verwenden, nämlich die Zustandsveränderung an, die den Zustand unverändert läßt. Es soll also aus einem Wert "t " vom Typ "T  " eine Operation "o " vom Typ "OT   " entstehen, die eindeutig dadurch bestimmt ist, daß ihr Produkt der Wert "t " und ihr Nachzustand ihr Vorzustand ist. Diese Operation wird mit dem Operationskonstruktor "O" als "Ot " bezeichnet, also als die Operation mit dem Wert "t ".

Der Operationskonstruktor liefert also zu einem Wert die naheliegende Operation, welche diesen Wert quasi als eine Operation darstellt oder repräsentiert. Insofern erlaubt er es, die Menge der Werte in die Menge der Operationen einzubetten.

Eine Operation "Ot ", die als Wert des Operationskonstruktors "O" gebildet wurde, soll hier auch als eine Wertrepräsentation  bezeichnet werden, da sie den Wert "t " als Operation repräsentiert. Eine solche Wertrepräsentation "Ot " wird gelegentlich auch mit eckigen Klammern als "[t ]" geschrieben.

Der Typ des Operationskonstruktor für den Typ "T  " ist "T  → OT  ". (Dieser Konstruktor ist also parametrisch polymorph.)

Parametrisierte Werte und Operationen

Für parametrisierte Werte (Funktionen) und Operationen müssen keine speziellen Mittel eingeführt werden, da diese durch normale Abbildungen in den Menge der Wert bzw. der Operationen beschrieben werden können, was ja auch schon verwendet wurde.

Übungsfrage Warum ist der Operationskonstruktor "O" selber eine parametrisierte Operation?

Monaden als Tripel

Man sieht den Operationstypkonstruktor, den Operationskonstruktor und die Verbindungsabbildung zusammen als die Monade an. (In diesem Text wurde zur Vereinfachung zuvor die Verbindungsabbildung gelegentlich auch als Monade bezeichnet.) Man verlangt, daß diese drei Axiomen genügen, die das bisher schon Beschriebene noch einmal ausdrücklich verlangen. Die ersten beiden Axiome legen neben der Neutralität  des Operationskonstruktors hinsichtlich des Zustands auch fest, welche Bedeutung  dieser hinsichtlich von Produkten hat, und zwar jeweils für seine Verwendung als eine durch einen Parameter bestimmte Operation auf der linken Seite einer Verbindung (Axiom LUNIT ) und für seine Verwendung als parametrisierte Operation auf der rechten Seite einer Verbindung (Axiom RUNIT ). Das letzte Axiom ASSOC  verlangt die Assoziativität  bestimmter Operationen hinsichtlich des Zustands.

Das Axiom LUNIT

Das Axiom LUNIT  ist eine Gleichheit von zwei Operationen. Es macht eine Aussage über die Bedeutung von Wertrepräsentationen "Ot  " auf der linken  Seite einer Verbindung " ; ".

Die bestimmte Operation "o (t  )" soll dieselbe Operation sein, wie die, die man erhält, wenn man die Operation "Ot  ", welche den Wert "t  " als Operation repräsentiert mit der parametrisierten Operation "o " verbindet.

LUNIT

o (t ) = Ot  ; o

Der Operationskonstruktor "O" erzeugt zu einem Wert "t  " die diesen Wert repräsentierende Operation "Ot  ", deren Produkt eben dieser Wert "t  " ist. Die „Einspeisung“ eines Wertes "t  " als Argument in eine parametrisierte Operation "o " über den Umweg der Produktoperation "Ot  " mit dem Wert "t  " als Produkt soll die gleiche Operation "Ot  ; o " ergeben wie die direkte Verwendung des Wertes "t  " als Argument der parametrisierten Operation "o ".

Damit verlangt man also vom Operationskonstruktor "O", daß er zu einem Wert "t  " diejenige Operation ergibt, deren Produkt der Wert "t  " ist. Insofern kann dieses Axiom als Definition des Produktes einer Anwendung "Ot  " des Operationskonstruktors "O" verstanden werden. Außerdem soll der Zustand durch "Ot  " nicht verändert werden.

LUNIT  verlangt die Gleichheit dieser beiden Operationen

                      Vorzustand
  Ot ; o                   |   
.--------------------------|-----------------------.
|                          |                       |
|                          V                       |
|                     .--------.                   |
|                     | Ot     | T                 |
|                     |        |------------.      |
|                     |        | t          |      |
|                     '--------'            |      |
|                          |                |      |
|       .------------------|----------------'      |
|       |                  |                       |
|       |                  V                       |
|       |             .--------.                   |
|       |             | o      | T'                |
|       '--------->>  |        |--------------------------------> Produkt
|                     |        | t                 |
|                     '--------'                   |
'--------------------------|-----------------------'
                           |
                           V
                       Nachzustand

                       Vorzustand
                           |
                    o(t)   V
                      .--------.
                      | o      | T'
            t ---->>  |        |-------> Produkt
                      |        | t'
                      '--------'
                           |
                           V
                      Nachzustand

Das Axiom RUNIT

Das Axiom RUNIT  ist eine Gleichheit von zwei Operationen. Es macht eine Aussage über die Bedeutung von des Operationskonstruktors als parametrisierter Operation "O" auf der rechten  Seite einer Verbindung " ; ".

RUNIT

o  = o  ; O

Als parametrisierte Operation kann der Operationskonstruktor selber einer anderen Operation folgen, wobei das Argument für seinen Parameter dann durch das Produkt der vorherigen Operation gegeben sein soll. Gemäß seiner Definition nach LUNIT  muß dann sein Produkt gleich dem Produkt der vorangehenden Operation "o " sein. Er ist also hinsichtlich des Produktes „neutral“ und reicht dies lediglich unverändert als sein eigenes Produkt weiter.

RUNIT  verlangt nun, daß er auch insgesamt neutral ist, er soll also auch den nach der Durchführung von "o ₀" vorgefundenen Vorzustand unverändert läßt, so daß dieser dann der Nachzustand der Durchführung von "O" in "o  ; O" wird.

Das wurde auch schon von LUNIT  festgelegt. Warum ist RUNIT  dann überhaupt noch nötig? RUNIT  und LUNIT  definieren gemeinsam nicht nur den Operationskonstruktor "O" sondern auch gleichzeitig noch (teilweise) die Hintereinanderausführung " ; "; und das, was LUNIT  für diese verlangt, geht noch nicht aus RUNIT  hervor.

Während die Typfestlegungen von "B" und " ; " sozusagen deren „Syntax“ definieren, legen die drei Axiome gemeinsam deren Bedeutung fest, wobei von der bereits etablierten Bedeutung der Anwendung einer Funktion auf ein Argument Gebrauch gemacht wird.

RUNIT  verlangt die Gleichheit dieser beiden Operationen

                                 
                       Vorzustand
  o | O                    |
.--------------------------|-----------------------.
|                          |                       |
|                          V                       |
|                     .--------.                   |
|                     |  o     | T                 |
|                     |        |------------.      |
|                     |        | t          |      |
|                     '--------'            |      |
|                          |                |      |
|       .------------------|----------------'      |
|       |                  |                       |
|       |                  V                       |
|       |             .--------.                   |
|       |             | O      | T'                | T
|       '--------->>  |        |--------------------------------> Produkt
|                     |        | t'                | t
|                     '--------'                   |
'--------------------------|-----------------------'
                           |
                           V
                       Nachzustand

                       Vorzustand
                           |
                           V
                      .--------.
                      | o      | T
                      |        |-------> Produkt
                      |        | t
                      '--------'
                           |
                           V
                      Nachzustand

Rein-formal parametrisierte Operationen

Dieser Abschnitt behandelt rein-formal parametrisierte Operationen als Vorbereitung auf die Behandlung des Axioms ASSOC.

Eine Wertrepräsentation stellt einen Wert als Operation dar. Sie kann verwendet werden, wenn inhaltlich ein Wert  benötigt wird, aber formal eine Operation  angegeben werden muß. Genauso kann es manchmal vorkommen, daß inhaltlich eine Operation  angegeben werden soll, aber formal eine parametrisierte Operation  angegeben werden muß. Auch hier wird dann wieder eine parametrisierte Operation gesucht, welche eine Operation möglichst neutral  oder kanonisch  repräsentiert, also ohne etwas willkürlich hinzuzufügen, oder—wenn schon etwas hinzugefügt werde muß—das Neutrale hinzuzufügen. Das legt es nahe, einer Operation "o  " diejenige parametrisierte Operation zuzuordnen, die für jeden Argumentwert wieder die Operation "o  " ergibt. Dies ist aber gerade die parametrisierte Operation " λx . o ". Sie hängt nur rein-formal  von einem Parameter ab, ergibt aber tatsächlich stets die gleiche Operation " o ".

Ein nur rein-formal parametrisierte Operation wird durch ein Kästchen dargestellt, das auf der Seite des Parameters einen Doppelstrich hat. Dadurch wird angedeutet, daß der Parameter faktisch ignoriert wird, der Doppelstrich stellt das " λx ." also bildlich dar.

Eine rein-formal parametrisierte Operation " λx . o "

                    Vorzustand
                        |
                        V
                  .-----------.
                  ||  \x.o    | T1
Parameter ---->>  ||          |-------> Produkt
                  ||          | t1
                  '-----------'
                        |
                        V
                    Nachzustand

Als Kuriosität sei erwähnt, daß die rein-formal parametrisierte Operation " λx . Bt " den einfachen Wert "t " sozusagen maximal formal aufgebläht darstellt. Solch eine Darstellung wird aber in dieser Form in diesem Text nicht benötigt.

Das Axiom ASSOC

Die einfache Form des Assoziativgesetzes für das Monoid lautete folgendermaßen.

Assoziativität des Monoids

(o ₀  ; o ₁ ) ; o ₂  = o ₀  ; (o ₁  ; o ₂ )

Es kann für Operationen mit einem Produkt aber nicht genau in dieser Form weiterverwendet werden, denn es enthält bestimmte  Operationen und keine parametrisierten  Operationen, die ein mit der Verbindung " ; " eingespeistes Produkt akzeptieren würden.

Sind die Operation "o ₀ " und die Operation "o ₁ " beide bestimmte Operationen mit einem Produkt, so ist die Schreibweise "(o ₀ ; o ₁) " nicht mit dem Typsystem und der Verbindungsoperation vereinbar, da die bestimmte Operation "o ₁ " das Produkt der Operation "o ₀ " nicht akzeptieren kann. Um dieses Problem zu beheben wird aus der bestimmten Operation "o ₁ " formal eine parametrisierte Berechung "  λx . o ₁" gemacht, deren Wert aber für jedes Argument wieder die bestimmte Operation "o ₁ " ist. Die Schreibweise "(o ₀ ;  λx . o ₁)" beschreibt dann mit dem Typsystem vereinbar eine bestimmte Operation mit Produkt. Die Information des „störenden“ Produktes von "o ₀ " geht dabei verloren.

Nun kann das Assoziativitätsgesetz für Verbindungen mit Produkt angegeben werden:

ASSOC

(o ₀ ;  λx . o ₁) ;  λy . o ₂ = o ₀ ;  λx . (o ₁ ;  λy . o ₂)

Es verlangt also die Assoziativität der Hintereinandersausführung bestimmter Operationen hinsichtlich des Zustandes. Die Lambda-Abstraktionen erlauben dabei die Verwendung der Verbindung " ; " wenn auf der rechten Seite eine nicht-parametrisierte Operation stehen soll.

Hinsichtlich des Wertes soll keine Assoziativität verlangt werden, denn dies würde für Funktionen der Aussage "f ₂(f ₁(x ))=(f ₂(f ₁))x " entsprechen, die aber so nicht verlangt werden soll. Das Produkt der beiden Seiten des Axioms ASSOC  ist das Produkt der Produktoperation "o ₂" bei dem von den vorangehenden Operationen hinterlassenem (gleichen) Vorzustand.

"(o ₀ ;  λx . o ₁) ;  λy . o ₂" soll gleich "o ₀ ;  λx . (o ₁ ; λy . o ₂)" sein

     (o0 ; \x.o1) ; \y.o2  |
     .---------------------|---------------------.
     |                     |                     |
     |   (o0 ; \x.o1)      |                     |
     |    .----------------|----------------.    |
     |    |                V                |    |
     |    |       .-----------------.       |    |
     |    |       |        o0       |-----. |    |
     |    |       '-----------------'     | |    |
     |    | .--------------|--------------' |    |
     |    | |              V                |    |
     |    | |     .-----------------.       |    |
     |    | '->>  ||     \x.o1      |----------. |
     |    |       '-----------------'       |  | |
     |    '----------------|----------------'  | |
     |                     |                   | |
     | .-------------------|-------------------' |
     | |                   V                     |
     | |          .-----------------.            |
     | '------>>  ||     \y.o2      |-------------------->
     |            '-----------------'            |
     '---------------------|---------------------'
                           V

o0 ; \x.(o1 ; \y.o2)       |
.--------------------------|--------------------------.
|                          V                          |
|                 .-----------------.                 |
|                 |       o0        |---------------. |
|                 '-----------------'               | |
|                          |                        | |
| .------------------------|------------------------' |
| |                        |                          |
| |      \x.(o1|\y.o2)     |                          |
| |     .------------------|------------------.       |
| |     ||                 V                  |       |
| |     ||        .-----------------.         |       |
| |     ||        |        o1       |-----.   |       |
| |     ||        '-----------------'     |   |       |
| |     ||                 |              |   |       |
| '->>  ||  .--------------|--------------'   |       |
|       ||  |              V                  |       |
|       ||  |     .-----------------.         |       |
|       ||  '->>  ||     \y.o2      |----------------------->
|       ||        '-----------------'         |       |
|       '------------------|------------------'       |
'--------------------------|--------------------------'
                           V

Monaden mit Produktweitergabe in Java 

Das im Anhang aufgelistete Java -Programm "Monade" implementiert eine Monade mit Produktweitergabe.

Die Produktkontrolle

In der Verbindung "(o  ;  p )" kann das Produkt der Operation "o  " die Operation "p  " wie ein Argument bestimmen. Mit der Darstellung "Ot  " kann ein Wert "t  " durch eine Operation "Ot  " dargestellt werden. Von großer Bedeutung für den Nutzen von Zustandsmonaden in rein funktionalen Sprachen ist aber auch gerade das, was in solchen Sprachen nicht  möglich ist:

Es gibt außerhalb einer Operationsspezifikation und abgesehen von Parametern keine Darstellung des Produkts einer Operation als formal textbestimmten Term.

Um deutlicher zu sagen, was nicht  möglich ist, nehmen wir an, es gäbe in einer funktionalen Sprache eine parametrisch polymorphe Abbildung "W", die praktisch das Gegenteil des Operationskonstruktors "O" sein soll. Die parametrisch polymorphe Abbildung "W" hätte also für einen Produkttyp "T   " den Typ "OT  → T   " und es gälte "WOt   = t  ".

Mit Hilfe dieser Abbildung "W" könnte man nun zu einer Operation "o " den vermeintlichen „Term“  "Wo " schreiben. Wenn ein Term nicht parametrisiert ist, dann bezeichnet er aber stets einen bestimmten Wert. Der vermeintlichen Term "Wo " könnte jedoch bei jeder Auswertung einen anderen Wert haben, nämlich das jeweilige Produkt der Operation "o ". Solch ein Term wäre eine nicht markierte Störung der referentiellen Transparenz, und deswegen gibt es in rein funktionalen Programmiersprachen keine solche Abbildung "W". Es gibt mit der Darstellung "O" zwar sozusagen einen Weg in die Operationen hinein, aber dann keinen Weg mehr heraus.

Somit wird die Verwendung des Produktes einer Operation kontrolliert :

Es ist zunächst nur möglich, das Produkt einer Operation mit der Verbindung " ;  " zum Parametrisieren einer anderen Operation einzusetzen.

Da eine parametrisierte Operation "p " jedoch in der Verbindung "(o  ;  p )" mit dem Produkt der Operation "o  " parametrisiert werden kann, steht der Name dieses Parameters in der Spezifikation von "p " dann zwar tatsächlich für ein Produkt, das bei jeder Auswertung von "(o  ;  p )" anders sein kann, doch unterscheidet sich dieser Parameter damit nicht von einem Parameter irgendeiner Funktion, der ja bei jeder Anwendung dieser Funktion einen anderen Wert haben kann. Die Parameter sind in der klassischen mathematischen Notation ja die Bestandteile, die dafür vorgesehen sind, bei jeder Auswertung einen anderen Wert zu haben. Insofern ist es unschädlich sie mit Produkten von Operationen zu belegen, mit denen sie diese Eigenschaft teilen. Von der klassischen mathematischen Notation abweichen würde man erst, wenn man auch Nichtparameterterme mit Produktwerten belegen könnte, was aber durch das Fehler der oben beschriebenen Abbildung "W" verhindert wird.

Produkte können durch die Verbindung " ; " direkt zu Parameterwerten werden und durch die Verwendung dieser Parameter in Ausdrücken können sie indirekt zu Parameterwerten werden, aber sie können den Wert eines Terms nicht beeinflussen, der selber nicht von einem Parameter abhängt.

Durch die Verbindung "(o  ;  p )" sind die Stellen, an denen Produkte als Parameter eingeführt werden, explizit markiert. Es ist nicht möglich, daß ein Produkt auf einmal der Wert eines nicht parametrisierten Terms ist, ohne daß eine solche Markierung sichtbar ist. Dadurch ist also sichergestellt, daß es in einer rein funktionalen Sprachen keinen Term "f()" geben kann, der als Anwendung einer Funktion auf null Argumente zu verstehen ist, und dessen Wert bei jedem Aufruf anders sein könnte, also beispielsweise der Wert einer Speicherzelle. Die referentielle Transparenz der Notation ist überall gewahrt. Diese Kontrolle und Eingrenzung der Verwendung des Produktes von Operationen ist in der Überschrift dieses Abschnitts mit „Produktkontrolle“ gemeint.

(In der Mathematik gibt es eigentlich keine Funktionen mit „null“ Argumenten, wie in dem Term "f()", denn in der Kategorie der Mengen und Abbildungen ist die leere Menge initiales Objekt, es gibt also genau eine Abbildung, deren Definitionsmenge die leere Menge ist, nämlich die „leere Abbildung“ [mit leerem Bild]. Jedoch kann man diesem Term im Rahmen der Universellen Algebra als 0-stellige Verknüpfung den gewünschten Sinn geben. Dort bildet eine n -stellige Verknüpfung ein n -Tupel aus Werten einer Menge in eine andere Menge ab. Der Term "f()" bezeichnet dann das Bild des 0-Tupels. [Dies ist auch ein Argument dafür, daß eine Abbildung von zwei Parametern ein fundamentaler Begriff ist und nicht einfach als Abbildung mit einem Parameter interpretiert werden kann, die auf ein 2-Tupel angewendet wird, denn dann wäre "f()" nicht die leere Abbildung, sondern der Wert einer Abbildung für ein 0-Tupel, wie bei den n -stelligen Verknüpfungen in der Universellen Algebra.])

Durch das Typsystem wird außerdem der Typ von Operationen vom Typ anderer Werte unterschieden, so daß der Programmierer sich dieses Typs auch stets bewußt sein muß.

Damit erlauben Monaden es, in rein funktionalen Sprache die Verarbeitung von Produkten zu notieren. Dies geschieht aber so, daß die referentielle Transparenz der Notation gewährt bleibt und der Programmierer es sich wegen des Typsystems stets bewußt macht, wann er Operationen verwendet und wann nicht.

Ausrechnen einer Anwendung

Eine Operation  "O" wird hier als ein Paar "(p,n)" von zwei Abbildungen eines Vorzustandes aus der Zustandsmenge "Z" in einen Wert aus einer Wertemenge "W" (das Produkt der Operation) und einen Nachzustand aus der Zustandsmenge "Z" aufgefaßt.

Für einen numerischen Speicher sei die Zustandsmenge beispielsweise das ganzzahlige Intervall "[0,256)".

Die stabile Leseoperation "L" ist durch die beiden folgenden Abbildungen gegeben:

Lp: Z → W, s  ↦ s 

Ln: Z → Z, s  ↦ s 

Die neutrale Schreiboperation "S(w)" ist für jeden Wert "w" durch die beiden folgenden Abbildungen gegeben:

S(w)p: Z → W, s  ↦ w

S(w)n: Z → Z, s  ↦ w

Damit wird die Abbildung "S: w  ↦ S(w )" als eine parametrisierte Operation angesehen, also eine Abbildung, die jedem Parameterwert "w " eine Schreiboperation "S(w )" zuordnet.

Die monadische Verbindung " ; " einer Operationen "A" und einer parametrisierten Operation "B" ist definiert durch:

 ; : OT ₀ × (T ₀  → OT ₁ ) → OT ₁ ,

(A ; B)s  = B(Ap(s ))An(s ).

Nun soll als Anwendungsbeispiel das Produkt und der Nachzustand einer Operation unter Ausnutzung der referentiellen Transparenz ausgerechnet werden.

Die Operation D sei gegeben durch

D ≔ (L ; λx . S(2 · x )).

Diese Operation liest einen Wert aus dem Speicher und schreibt das Doppelte (im Sinne der üblichen Restklassenarithmetik) zurück.

Es soll der Wert der Anwendung "D s" dieser Operation "D" auf den Zustand "s" ermittelt werden.

Ersetzt man das "D" in "D s" durch die obige Definition von "D" so ergibt sich:

(L ; λx . S(2 · x ))s.

Die Anwendung der obenstehenden Definition der monadischen Verbindung " ; " liefert

(λx . S(2 · x ))(Lp(s))Ln(s).

Nun kann die Definition der Abbildung "Lp" und der Abbildung "Ln" verwendet werden:

(λx . S(2 · x ))(s)s

Die Reduktion der Lambda-Abstraktion ist jetzt ebenfalls möglich:

S(2 · s)s

Die Operation "S(2 · s)" wird durch ihr Komponente "S(2 · s)p" und ihre Komponente "S(2 · s)n" dargestellt:

(S(2 · s)p s, S(2 · s)n s)

Nun kann die Definition dieser beiden Komponenten direkt eingesetzt werden und es ergibt sich

(2 · s, 2 · s).

Wir wissen jetzt also, daß das Produkt und der Nachzustand der Operation "D" jeweils durch das Zweifache des Vorzustandes gegeben sind und haben diese damit explizit ausgerechnet.

Dabei wurde durch das wiederholte Einsetzen wertgleicher Terme von der referentiellen Transparenz Gebrauch gemacht. Bei den obigen Schritten gibt es auch noch eine gewisse Freiheit der Wahl einer Reihenfolge: Einige Schritte könnten umgeordnet werden. All dies ist ein rein mathematisches Vorgehen, an keiner Stelle wurde operationale Semantik verwendet oder ein zeitlicher Ablauf von Operationen zugrundegelegt. Einige der verwendeten Werte können aber als Zustände und einige der verwendeten Operationen als Zeitschritte interpretiert werden.

Anhang 0 Vorbemerkungen

Der Anhang 0 enthält Texte, die eigentlich Vorbemerkungen  oder Vorbereitungen  zum Haupttext darstellen, aber deren Lektüre vor dem Haupttext nicht unbedingt für jeden Leser nötig ist. Um zu empfehlen, zunächst gleich mit der Lektüre des Haupttexts zu beginnen, wurden diese Vorbemerkungen in den Anhang geschrieben, obwohl sie als „Vorbemerkungen“ ja vor dem Haupttext stehen sollten.

Anhang 0 Einleitung

Es ist nicht ganz einfach, einen Satz zu schreiben, der mit „Eine Monade ist“  beginnt, weil die Bezeichnung in der Literatur etwas uneinheitlich verwendet wird. Außerdem wäre es bei der Wiedergabe einer Definition, sei es nun einer, wie sie in der Kategorietheorie üblich ist, oder einer, wie sie in Zusammenhang mit rein funktionalen Programmiersprachen üblich ist, nicht gleich offensichtlich, welchen Nutzen  solch eine Definition hat.

Daher beginnt dieser Text statt dessen mit einer Einführung in die Verbindung von Operationen. Später kann die gegebene Erklärung dann verallgemeinert werden, um schließlich zu einer allgemeineren Definition von Monaden zu gelangen. Die Absicht ist es, die Grundlagen der Anwendungen von Monaden zunächst so weit zu vereinfachen, daß sie möglichst verständlich und motiviert sind. Dabei wird mit einer Vereinfachung eines der wichtigsten Typen von Monaden begonnen: der sogenannten Zustandsmonade, die bei der Modellierung von Operationen in rein funktionalen Umgebungen eingesetzt wird.

Eine weitere Besonderheit dieses Textes ist es, daß Monaden hier unabhängig  von einer bestimmten rein funktionalen Programmiersprache behandelt werden. Obwohl der hier dargestellte Monaden-Begriff doch durch die Verwendung von Monaden in rein funktionalen Programmiersprachen motiviert ist, verwendet dieser Text nur wenig Quelltexte solcher Sprachen. Insofern kann dieser Text auch für Leser ohne Kenntnisse bestimmter rein funktionaler Programmiersprachen lesbar sein, obwohl er auch für Leser hilfreich ist, die Monaden in rein funktionalen Programmiersprachen verstehen wollen. Auch werden keine Kenntnisse über Kategorietheorie vorausgesetzt, wiewohl allgemeine Grundkenntnisse der Mathematik und des Programmierens bei der Lektüre sicher dienlich sind.

Zur Veranschaulichung der Implementation und Verwendung von Monaden in der Programmierung finden sich im Anhang Programme in Java ; der Rest des Textes ist aber auch ohne Java -Kenntnisse lesbar. Die Implementation in einer Programmiersprache, die nicht rein funktional ist, ist zwar aufwendiger, macht aber auch Vorgänge ausdrücklich sichtbar, die in rein funktionalen Sprachen sonst eher hinter den Kulissen ablaufen, und kann daher gerade beim Lernen hilfreich sein.

Für den Text werden die Begriffe „Abbildung“, „System“, „Zustand“, „Operation“, „Parametrisierung“, „Operation“ und „Assoziativität“ vorausgesetzt, wie sie in den Lehrgängen beschrieben werden, auf die nun verwiesen wird, und dort bei Bedarf nachgeschlagen werden können. Um nicht zu viel Zeit für Vorbereitungen aufzuwenden, empfiehlt es sich aber im allgemeinen, zunächst den Artikel vom Anfang des Artikels beginnend zu lesen.

(noch nicht verfügbar:) Mathematiklehrgang mit Erklärung der Begriffe: Abbildung, Parameter, kartesisches Produkt, Parametrisierung, Lambda-Kalkül, Abstraktion, Assoziativität, Curryfizierung
>722126 Physiklehrgang mit Erklärung der Begriffe: Zustand, Vorgang, Operation.

Anhang 1 Nachbemerkungen

Der Anhang 1 enthält Anmerkungen, die nach dem Haupttext gelesen werden können.

Anhang 1 Dedekind s Schreibweise

Die Verbindungsoperation " ; " erinnert an den senkrechte Strich " | " in einer Schreibweise wie sie zur Verbindung von Programmen in manchen Kommandointerpretierern verwendet wird, aber auch an die Schreibweise "x  | f  ", die Dedekind  in einem Entwurf zu „Was sind und was sollen die Zahlen? “ zunächst verwendete. Wenn man annimmt, daß Dedekind  auch Terme wie "x  | f   | g " verwendet hätte, dann käme dies der monadischen Schreibweise schon recht nahe, bedenkt man, daß der Term "x " ein bestimmter Wert ist und "f  " ein parametrisierter Wert (also eine Funktion) ist, so verlangt dann auch der Operator " | " links etwas Bestimmtes und rechts etwas Parametrisiertes—so wie die Klammern in "f (x )" links etwas Parametrisiertes und innen etwas Bestimmtes verlangen; freilich sind dies jeweils Schreibweisen, bei denen ein Zustand nicht vorkommt.

In Unix  kann man eine Datei "file" mit "|" nicht direkt an ein Programm wie "grep" leiten, also "file | grep" schreiben, es muß erst aus "file" ein Programm erzeugt werden, dessen Ausgabe der Inhalt der Datei "file" ist, also schreibt man "cat file | grep". Das "cat file" entspricht hier der Abbildung "[x ]": Beide verändern den Typ einer Information in den von einer binären Abbildung verlangten Typ und entsprechen damit dem Operationskonstruktor einer Monade.

Interessanterweise lassen sich die monadischen Axiome für Personen, die mit Unix  vertraut sind vielleicht in der folgenden Form besser verstehen, wobei verlangt wird, daß das Verhalten der beiden Kommandozeilen jeweils gleich ist.

LUNIT

cat file | filter

filter file

Beispiel zu LUNIT

cat tmp.txt | more

more tmp.txt

RUNIT

filter | cat

filter

Beispiel zu RUNIT

ls | cat

ls

ASSOC

( prog0 | prog1 )| prog2

prog0 |( prog1 | prog2 )

Anhang 2 Programmbeispiele

Der Anhang 2 enthält Programmbeispiele.

Anhang 2 Das Java-Programm "Monoid"

Das folgende Java -Programm "Monoid" implementiert ein Monoid mit der binären Abbildung "bind" und wendet diese zur Verbindungen zweier Operationen an. Dabei wird die Inkrementierungsoperation (zum Erhöhen des Wertes im Speicher um eins) mit sich selber verbunden, um eine neue Operation zu erzeugen, die den Wert des Speichers um zwei erhöht. Diese neue Operation wird dann auf einen als Beispiel zu verstehenden Anfangszustand angewendet und der sich ergebende Nachzustand wird angezeigt.

In diesem Programm wird ein Monoid als etwas definiert, das die in dem Programm definierte Schnittstelle "Bind<Something>" implementiert. Also ist in diesem Beispiel die Klasse "BindOperations" ein Monoid. Diese Klasse akzeptiert im Konstruktor (der hier eigentlich auch zur Schnittstelle gehören sollte) zwei Operationen. Die Operation "composition" ergibt dann eine neue Operation, deren Nachzustand (Ergebnis) der Nachzustand nach der Hintereinanderausführung dieser beiden Operationen ist.

Monoid.java

class NumericalState
{ final int numericalValue; 
  NumericalState( final int numericalValue )
  { this.numericalValue = numericalValue; }}

interface Operation<State>
{ State run( State state ); }

class IncrementOperation implements Operation<NumericalState>
{ public NumericalState run( final NumericalState state )
  { return new NumericalState(( state.numericalValue + 1 )% 4 ); }}

interface Bind<Something>{ Something composition(); }

class BindOperations implements Bind<Operation<NumericalState>>
{ final Operation<NumericalState> first;
  final Operation<NumericalState> second;
  BindOperations
  ( final Operation<NumericalState> first,
    final Operation<NumericalState> second )
  { this.first = first;
    this.second = second; }
  public Operation<NumericalState> composition()
  { return new Operation<NumericalState>()
    { public NumericalState run( final NumericalState state )
      { final NumericalState state1 = first.run( state );
        final NumericalState state2 = second.run( state1 ); 
        return state2; }}; }}

class Monoid
{ static Operation<NumericalState> bind
  ( Operation<NumericalState> first, 
    Operation<NumericalState> second )
  { return new BindOperations( first, second ).composition(); }
  final static Operation<NumericalState> incrementOperation =
  new IncrementOperation();
  public static void main( final String[] _ )
  { final NumericalState initialState = new NumericalState( 0 );
    final Operation<NumericalState> incrementTwice = 
    bind( incrementOperation, incrementOperation );
    final NumericalState finalState = incrementTwice.run( initialState );
    java.lang.System.out.println( finalState.numericalValue ); }}

System.out

2

Anhang Das Java -Programm "Monade"

Das folgende Java -Programm zeigt die Verbindung zweier Operationen mit Produkt. Die zweite Operation ist dabei parametrisiert. In der Methode "main" ist das „monadische Hauptprogramm“  "bind( bind( value( initValue ), writeValue() ), readValue() )" enthalten, das man symbolisch-verkürzt auch als "[ initValue ]; writeValue; readValue" schreiben kann.

Der Operationskonstruktor "value" erzeugt aus dem Anfangswert "initValue" eine bestimmte Operation mit Produkt "value( initValue )". Diese wird mit Hilfe der Verbindung "bind" mit der parametrisierten Operation "writeValue()" zu der bestimmten Operation "bind( value( initValue ), writeValue() )" verbunden, welche dann wieder mit der Operation "readValue()" verbunden wird.

So wird der Wert "initValue" bei der Durchführung der Operation "writeValue" in den „Speicher“ (als Zustand) geschrieben und von der Durchführung der Operation "readValue" wieder als deren Produkt aus dem Speicher gelesen. Das Programm gibt dann dieses letzte Produkt aus.

Monade.java

/* The general explanation of "a state" and "a value": it might be anything.
   These are fundamental notions for the rest. */

interface StateType {};

interface ValueType {};

/* A product and state pair is what is left after an operation was executed. */
interface ProductAndState<ValueType,StateType> 
{ ValueType getProduct();
  StateType getState(); }

/* An operation can be execute to leave a product and a state. */
interface Operation<ValueType,StateType>
{ ProductAndState<ValueType,StateType> execute( StateType state ); }

/* A parameterized operation determines an operation by a value. */
interface ParameterizedOperation<ValueType,StateType,ParameterType>
{ Operation<ValueType,StateType> of( final ParameterType parameter ); }

/* The operation "bind" now can be defined on theses interfaces
   Here, "ProductType" is the type of the final result of the
   bind operation, while "ValueType" is the type of the product
   of the left operand. */

class Bind<ValueType,StateType,ProductType>
{ Operation<ValueType,StateType> firstOperation;
  ParameterizedOperation<ProductType,StateType,ValueType> secondOperation;
  Bind
  ( final Operation<ValueType,StateType> firstOperation, 
    final ParameterizedOperation<ProductType,StateType,ValueType> secondOperation )
  { this.firstOperation = firstOperation;
    this.secondOperation = secondOperation; }
  Operation<ProductType,StateType> composition()
  { return new Operation<ProductType,StateType>()
    { public ProductAndState<ProductType,StateType> execute( final StateType initialState )
      { ProductAndState<ValueType,StateType> intermediateProductAndState = 
        firstOperation.execute( initialState );
        return secondOperation.of( intermediateProductAndState.getProduct() )
        .execute( intermediateProductAndState.getState() ); }}; }}

/* For the following example, the memory state and the product
   is given by an int-Value. */

class MemoryState implements StateType
{ MemoryState( final int value ){ this.value = value; }
  int value; 
  public int getValue(){ return this.value; }}

class IntValue implements ValueType
{ IntValue( final int value ){ this.value = value; }
  public int asInt(){ return this.value; }
  int value; }

/* The interfaces "ProductAndState" and "Operation" now are
implemented for the example application. */

class IntProductAndMemoryState implements ProductAndState<IntValue,MemoryState>
{ final IntValue product; 
  final MemoryState state; 
  IntProductAndMemoryState( final IntValue product, final MemoryState state )
  { this.product = product; this.state = state; }
  public IntValue getProduct(){ return product; }
  public MemoryState getState(){ return state; }}

class IntValueOperation implements Operation<IntValue,MemoryState>
{ final IntValue value;
  IntValueOperation( final IntValue value ){ this.value = value; }
  public ProductAndState<IntValue,MemoryState> 
  execute( final MemoryState state )
  { return new IntProductAndMemoryState( value, state ); }}

/* Two operations to read from the state (memory) and to write
   to the state are now being declared.
   For technical reasons, four instead of two classes are required,
   with the first two classes being helper classes. */

class ReaderOperation implements Operation<IntValue,MemoryState>
{ ReaderOperation(){}
  public ProductAndState<IntValue,MemoryState> 
  execute( final MemoryState state )
  { return new IntProductAndMemoryState
    ( new IntValue( state.getValue() ), state ); }}

class WriterOperation implements Operation<IntValue,MemoryState>
{ IntValue value; WriterOperation( final IntValue value )
  { this.value = value; }
  public ProductAndState<IntValue,MemoryState> 
  execute( final MemoryState state )
  { return new IntProductAndMemoryState
    (( IntValue )null, new MemoryState( value.asInt() )); }}

class ReadValue
implements ParameterizedOperation<IntValue,MemoryState,IntValue>
{ public Operation<IntValue,MemoryState> of( IntValue value )
  { return new ReaderOperation(); /* ignores the value */ }}

class WriteValue
implements ParameterizedOperation<IntValue,MemoryState,IntValue>
{ public Operation<IntValue,MemoryState> of( IntValue value )
  { return new WriterOperation( value ); /* writes the value */ }}

class Monade
{ 

  /* Next some abbreviations are being declared so as to
  improve readability. */

  static Operation<IntValue,MemoryState> bind
  ( final Operation<IntValue,MemoryState> first, 
    final ParameterizedOperation<IntValue,MemoryState,IntValue> second )
  { return new Bind<IntValue,MemoryState,IntValue>( first, second ).composition(); }

  static Operation<IntValue,MemoryState> value( final int i )
  { return new IntValueOperation( new IntValue( i )); }
  

  static ParameterizedOperation<IntValue,MemoryState,IntValue> writeValue()
  { return new WriteValue(); }

  static ParameterizedOperation<IntValue,MemoryState,IntValue> readValue()
  { return new ReadValue(); }

  /* The main method is writing a value "initValue" into memory 
     with the parametrized operation "writeValue", which is then
     read with the parametrized operation "readValue".
     The product of this read operation then is being printed. */

  public static void main( final String[] _ )
  { final MemoryState initState = new MemoryState( 0 );
    final int initValue = 2;

    ProductAndState<IntValue,MemoryState> productAndState = 
    bind( bind( value( initValue ), writeValue() ), readValue() ).
    execute( initState );

    java.lang.System.out.println( productAndState.getProduct().asInt() ); }}

System.out

2