Monoid-Stapelmaschine

Vor nicht allzu langer Zeit erschien auf Habré ein ausgezeichneter und inspirierender Artikel über Compiler und gestapelte Maschinen. Es zeigt den Weg von einer einfachen Implementierung eines Bytecode-Executors zu immer effizienteren Versionen. Ich wollte am Beispiel der Entwicklung einer gestapelten Maschine zeigen, wie dies auf Haskell-Weise möglich ist.

Am Beispiel der Sprachinterpretation für eine gestapelte Maschine werden wir sehen, wie das mathematische Konzept von Halbgruppen und Monoiden zur Entwicklung und Erweiterung der Programmarchitektur beiträgt, wie die Monoidalgebra verwendet wird und wie Programme in Form einer Reihe von Homomorphismen zwischen algebraischen Systemen erstellt werden. Als Arbeitsbeispiele erstellen wir zunächst einen Interpreter, der in Form von EDSL untrennbar mit dem Code verbunden ist, und bringen ihm dann verschiedene Dinge bei: Aufzeichnen beliebiger Debugging-Informationen, Trennen des Programmcodes vom Programm selbst, Durchführen einer einfachen statischen Analyse und Berechnen mit verschiedenen Effekten.

Der Artikel richtet sich an diejenigen, die die Haskell-Sprache auf mittlerem Niveau und darüber kennen, an diejenigen, die sie bereits in der Arbeit oder in der Forschung verwenden, und an alle Neugierigen, die einen Blick darauf geworfen haben, was Funktionäre noch zu tun haben. Nun, natürlich für diejenigen, die der vorige Absatz nicht erschreckt hat.

Es stellte sich heraus, dass es viel Material mit vielen Beispielen im Code gab. Um dem Leser das Verständnis zu erleichtern, ob er sich damit befassen muss, werde ich kommentierte Inhalte geben.

Übersetzungs- und Interpretationsaufgaben bieten viele interessante und nützliche Beispiele, um die unterschiedlichsten Aspekte der Programmierung zu demonstrieren. Sie ermöglichen es Ihnen, verschiedene Ebenen der Komplexität und Abstraktion zu erreichen und dabei recht praktisch zu bleiben. In diesem Artikel konzentrieren wir uns auf die Demonstration der Fähigkeiten zweier wichtiger mathematischer Strukturen - einer Halbgruppe und eines Monoids . Sie werden nicht so oft diskutiert wie Monaden oder Linsen, und sie erschrecken kleine Programmierer nicht. Diese Strukturen sind viel einfacher zu verstehen, aber trotzdem liegen sie der funktionalen Programmierung zugrunde. Die virtuose Beherrschung monoidaler Typen, die von Fachleuten demonstriert wird, bewundert die Einfachheit und Eleganz von Lösungen.

Die Suche nach dem Wort "Monoid" in Artikeln über Habré gibt nicht mehr als vier Dutzend Artikel heraus (ungefähr die gleichen Monaden, zum Beispiel gibt es dreihundert davon). Sie alle beginnen konzeptionell mit so etwas wie: Ein Monoid ist so viele ... und dann listen sie mit verständlicher Begeisterung auf, was ein Monoid ist - von Linien bis zu Fingerbäumen, von Parsern mit regulären Ausdrücken bis zu Gott weiß was noch ! In der Praxis denken wir jedoch in umgekehrter Reihenfolge: Wir haben ein Objekt, das modelliert werden muss, wir analysieren seine Eigenschaften und stellen fest, dass es die Zeichen der einen oder anderen abstrakten Struktur aufweist. Wir entscheiden: Brauchen wir Konsequenzen aus diesem Umstand und wie verwenden wir es? Wir werden diesen Weg gehen. Gleichzeitig werden wir der Sammlung nützlicher Monoide einige interessante Beispiele hinzufügen.

Sprachen und Programme für Stapelmaschinen

Stapelmaschinen im Studium der funktionalen Programmierung erscheinen normalerweise in dem Moment, in dem sie sich dem Konzept der Faltung nähern. In diesem Fall wird eine äußerst präzise Implementierung des Ausführenden des einfachsten Stapelrechners gegeben, zum Beispiel:

calc :: String -> [Int] calc = interpretor . lexer where lexer = words interpretor = foldl (flip interprete) [] interprete c = case c of "add" -> binary $ \(x:y:s) -> x + y:s "mul" -> binary $ \(x:y:s) -> x * y:s "sub" -> binary $ \(x:y:s) -> y - x:s "div" -> binary $ \(x:y:s) -> y `div` x:s "pop" -> unary $ \(x:s) -> s "dup" -> unary $ \(x:s) -> x:x:s x -> case readMaybe x of Just n -> \s -> n:s Nothing -> error $ "Error: unknown command " ++ c where unary fs = case s of x:_ -> fs _ -> error $ "Error: " ++ c ++ " expected an argument." binary fs = case s of x:y:_ -> fs _ -> error $ "Error: " ++ c ++ " expected two arguments." 

Toller Start ins Gespräch! Dann beginnen sie in der Regel, Effekte anzuhängen: Sie ändern die foldl Faltung in foldM , stellen die Gesamtheit durch die Monade " Either String foldM , fügen dann die Protokollierung hinzu, verpacken alles mit dem WriterT Transformator, führen ein Wörterbuch für Variablen mit StateT und so weiter. Um die Coolness monadischer Berechnungen zu demonstrieren, implementieren sie manchmal einen mehrdeutigen Rechner, der alle möglichen Werte des Ausdrucks zurückgibt $$$(2 \ pm 3) * ((4 \ pm 8) \ pm 5)$ . Dies ist ein langes, gutes und interessantes Gespräch. Wir werden unsere Geschichte jedoch sofort anders führen, obwohl wir sie mit demselben Ergebnis beenden.

Warum geht es im Allgemeinen um das Falten? Weil Faltung (Katamorphismus) eine Abstraktion der sequentiellen Verarbeitung induktiver Daten ist . Die Stapelmaschine läuft linear durch den Code, führt eine Folge von Anweisungen aus und generiert einen Wert - den Status des Stapels. Ich stelle mir die Arbeit einer Faltungsstapelmaschine gerne als Translation von Matrix-RNA in einer lebenden Zelle vor. Das Ribosom durchläuft Schritt für Schritt die gesamte RNA-Kette, vergleicht die Tripletts von Nukleotiden mit Aminosäuren und bildet die Primärstruktur des Proteins.

Die Faltungsmaschine hat eine Reihe von Einschränkungen. Hauptsache, das Programm wird immer von Anfang bis Ende und einmal gelesen. Verzweigungs-, Schleifen- und Unterprogrammaufrufe erfordern eine konzeptionelle Änderung des Interpreters. Natürlich nichts Kompliziertes, aber eine solche Maschine kann nicht mehr durch eine einfache Faltung beschrieben werden.

Nach der Hypothese der sprachlichen Relativitätstheorie wirken sich die Eigenschaften der von uns verwendeten Sprache direkt auf die Eigenschaften unseres Denkens aus. Achten wir nicht auf die Maschine, sondern auf die Sprachen und Programme , die sie steuert.

Alle stapelorientierten Sprachen, sowohl relativ niedrige Ebenen (Bytecodes von Java- und Python- oder .NET-virtuellen Maschinen) als auch Sprachen höherer Ebenen (PostScript, Forth oder Joy), haben eine grundlegende gemeinsame Eigenschaft: Wenn Sie zwei korrekte Programme nacheinander schreiben, dann Holen Sie sich das richtige Programm. Richtig, richtig bedeutet nicht „richtig“. Dieses Programm kann bei allen Daten fehlerhaft abstürzen oder in endlosen Zyklen fehlschlagen und macht überhaupt keinen Sinn. Hauptsache, ein solches Programm kann von der Maschine ausgeführt werden. Wenn wir das richtige Programm in Teile zerlegen, können wir diese Teile leicht wiederverwenden, gerade wegen ihrer Richtigkeit. Schließlich können Sie in jeder Stapelsprache eine Teilmenge von Befehlen auswählen, die nur für den internen Status der Maschine (Stapel oder Register) ausgeführt werden und keinen externen Speicher verwenden. Diese Teilmenge bildet eine Sprache mit der Eigenschaft der Verkettung . In einer solchen Sprache hat jedes Programm die Bedeutung eines Maschinenzustandskonverters, und die sequentielle Ausführung von Programmen entspricht ihrer Zusammensetzung, was bedeutet, dass es auch ein Zustandskonverter ist.

Das allgemeine Muster ist zu sehen: Die Kombination (Verkettung) der richtigen Programme erzeugt das richtige Programm, die Kombination der Konverter erzeugt den Konverter. Es stellt sich heraus, dass die Stapelsprachenprogramme in Bezug auf die Verkettungsoperation geschlossen sind oder eine Struktur bilden, die als Groupoid oder Magma bezeichnet wird . Dies bedeutet, dass Sie das Programm durch Schreiben auf Band fast zufällig ausschneiden und dann aus den resultierenden Segmenten neue Programme erstellen können. Darüber hinaus können Sie mit einer einzigen Anweisung in Segmente schneiden.

Beim Verkleben ist Ordnung wichtig. Zum Beispiel sind diese beiden Programme zweifellos unterschiedlich:

Und was gibt uns das als Programmierer? Mit Assoziativität können Sie beliebige geeignete Programmabschnitte dafür vorkompilieren, optimieren und sogar parallelisieren und dann zu einem äquivalenten Programm kombinieren. Wir können es uns leisten, eine statische Analyse eines Teils des Programms durchzuführen und diese für die Analyse des gesamten Programms zu verwenden, gerade weil es uns egal ist, wo die Klammern platziert werden sollen. Dies sind sehr wichtige und ernsthafte Möglichkeiten für eine niedrige Sprache oder eine Zwischensprache, in der nicht eine Person schreibt, sondern ein Übersetzer. Und aus der Sicht eines Mathematikers und eines erfahrenen Funktionsarbeiters macht dies die Maschinenzustandskonvertierungsprogramme zu vollwertigen Endomorphismen . Endomorphismen bilden auch eine Halbgruppe mit einer Kompositionsoperation. In der Algebra werden solche Endomorphismen in Bezug auf eine Menge Transformationshalbgruppen genannt . Beispielsweise bilden endliche Zustandsmaschinen eine Halbgruppe der Transformation vieler Zustände.

"Halbgruppe" klingt halbherzig, irgendwie minderwertig. Vielleicht bilden Stapelprogramme eine Gruppe ? Äh ... nein, die meisten Programme sind irreversibel, das heißt, je nach Ausführungsergebnis ist es nicht möglich, die Originaldaten eindeutig wiederherzustellen. Aber wir haben ein neutrales Element. In Assemblersprachen wird es bezeichnet $$$\ texttt {nop}$ und tut nichts. Wenn ein solcher Operator nicht explizit in der Stapelsprache definiert ist, kann er leicht durch Kombinieren einiger Befehle erhalten werden, zum Beispiel: $$$\ texttt {inc dec}$ , $$$\ texttt {dup pop}$ oder $$$\ texttt {Swap Swap}$ . Solche Paare können sicher aus Programmen herausgeschnitten oder im Gegenteil an einer beliebigen Stelle eingefügt werden. Da es eine Einheit gibt, bilden unsere Programme eine Halbgruppe mit einer Einheit oder einem Monoid . Sie können sie also programmgesteuert in Form von Monoiden implementieren - Endomorphismen über dem Zustand der gestapelten Maschine. Auf diese Weise können Sie einen kleinen Satz grundlegender Vorgänge für den Computer definieren und dann Programme anhand ihrer Zusammensetzung erstellen, um eine gestapelte Sprache in Form einer eingebetteten domänenspezifischen Sprache (EDSL) zu erhalten.

In Haskell werden Halbgruppen und Monoide mit den Monoid Semigroup und Monoid . Ihre Definitionen sind einfach und spiegeln nur die Grundstruktur wider. Die Anforderungen an Assoziativität und Neutralität müssen vom Programmierer überprüft werden:

 class Semigroup a where (<>) :: a -> a -> a class Semigroup a => Monoid a where mempty :: a 

Ein Auto bauen

 {-# LANGUAGE LambdaCase, GeneralizedNewtypeDeriving #-} import Data.Semigroup (Max(..),stimes) import Data.Monoid import Data.Vector ((//),(!),Vector) import qualified Data.Vector as V (replicate) 

Wir werden sofort eine Maschine bauen, die einen Stapel und einen endlichen Speicher hat und auf gute, saubere Weise im Notfall anhalten kann. All dies wird ohne die Verwendung von Monaden realisiert, wobei die erforderlichen Daten in einem Typ zusammengefasst werden, der die Maschine beschreibt. Somit werden alle Basisprogramme und damit alle ihre Kombinationen reine Konverter ihres Zustands sein.

Beginnen wir mit der Definition des Typs für die virtuelle Maschine und der trivialen Setterfunktionen.

 type Stack = [Int] type Memory = Vector Int type Processor = VM -> VM memSize = 4 data VM = VM { stack :: Stack , status :: Maybe String , memory :: Memory } deriving Show emptyVM = VM mempty mempty (V.replicate memSize 0) setStack :: Stack -> Processor setStack x (VM _ sm) = VM xsm setStatus :: Maybe String -> Processor setStatus x (VM s _ m) = VM sxm setMemory :: Memory -> Processor setMemory x (VM s st _) = VM s st x 

Setter werden benötigt, um die Programmsemantik explizit zu machen. Mit Prozessor (Typ Processor ) meinen wir die Konverter- VM -> VM .

Nun definieren wir die Wrapper-Typen für das Transformationsmonoid und für das Programm:

 newtype Action a = Action { runAction :: a -> a } instance Semigroup (Action a) where Action f <> Action g = Action (g . f) instance Monoid (Action a) where mempty = Action id newtype Program = Program { getProgram :: Action VM } deriving (Semigroup, Monoid) 

Wrapper-Typen bestimmen das Prinzip der Kombination von Programmen: Dies sind Endomorphismen mit der umgekehrten Reihenfolge der Zusammensetzung (von links nach rechts). Durch die Verwendung von Wrappern kann der Compiler unabhängig bestimmen, wie der Program die Anforderungen der Monoid Semigroup und Monoid implementiert.

Der Programmausführer ist trivial:

 run :: Program -> Processor run = runAction . getProgram exec :: Program -> VM exec prog = run prog emptyVM 

Die Fehlermeldung wird von der Fehlerfunktion generiert:

 err :: String -> Processor err = setStatus . Just $ "Error! " ++ m 

Wir verwenden den Typ " Maybe " nicht so, wie er normalerweise verwendet wird: Ein leerer Nothing Wert im Status bedeutet, dass nichts Gefährliches passiert, und die Berechnung kann fortgesetzt werden. Der Zeichenfolgenwert weist wiederum auf Probleme hin. Der Einfachheit halber definieren wir zwei intelligente Konstruktoren: einen für Programme, die nur mit dem Stack arbeiten, und einen für Programme, die Speicher benötigen.

 program :: (Stack -> Processor) -> Program program f = Program . Action $ \vm -> case status vm of Nothing -> f (stack vm) vm _ -> vm programM :: ((Memory, Stack) -> Processor) -> Program programM f = Program . Action $ \vm -> case status vm of Nothing -> f (memory vm, stack vm) vm _ -> vm 

Jetzt können Sie grundlegende Sprachbefehle für die Arbeit mit dem Stapel und dem Speicher, die Ganzzahlarithmetik sowie Äquivalenz- und Ordnungsbeziehungen definieren.

 pop = program $ \case x:s -> setStack s _ -> err "pop expected an argument." push x = program $ \s -> setStack (x:s) dup = program $ \case x:s -> setStack (x:x:s) _ -> err "dup expected an argument." swap = program $ \case x:y:s -> setStack (y:x:s) _ -> err "swap expected two arguments." exch = program $ \case x:y:s -> setStack (y:x:y:s) _ -> err "exch expected two arguments." 

 --       indexed if = programM $ if (i < 0 || i >= memSize) then const $ err $ "expected index in within 0 and " ++ show memSize else f put i = indexed i $ \case (m, x:s) -> setStack s . setMemory (m // [(i,x)]) _ -> err "put expected an argument" get i = indexed i $ \(m, s) -> setStack ((m ! i) : s) 

 unary nf = program $ \case x:s -> setStack (fx:s) _ -> err $ "operation " ++ show n ++ " expected an argument" binary nf = program $ \case x:y:s -> setStack (fxy:s) _ -> err $ "operation " ++ show n ++ " expected two arguments" add = binary "add" (+) sub = binary "sub" (flip (-)) mul = binary "mul" (*) frac = binary "frac" (flip div) modulo = binary "modulo" (flip mod) neg = unary "neg" (\x -> -x) inc = unary "inc" (\x -> x+1) dec = unary "dec" (\x -> x-1) eq = binary "eq" (\x -> \y -> if (x == y) then 1 else 0) neq = binary "neq" (\x -> \y -> if (x /= y) then 1 else 0) lt = binary "lt" (\x -> \y -> if (x > y) then 1 else 0) gt = binary "gt" (\x -> \y -> if (x < y) then 1 else 0) 

Verzweigungen und Schleifen reichen für vollwertige Arbeiten nicht aus. Tatsächlich reicht für die eingebettete Sprache nur die Verzweigung aus. Schleifen können mithilfe der Rekursion in der Hostsprache (in Haskell) organisiert werden, aber wir werden unsere Sprache autark machen. Zusätzlich nutzen wir die Tatsache, dass die Programme eine Halbgruppe bilden und bestimmen den Kombinator der Wiederholung des Programms die angegebene Anzahl von Malen. Er wird die Anzahl der Wiederholungen vom Stapel nehmen.

 branch :: Program -> Program -> Program branch br1 br2 = program go where go (x:s) = proceed (if (x /= 0) then br1 else br2) s go _ = err "branch expected an argument." while :: Program -> Program -> Program while test body = program (const go) where go vm = let res = proceed test (stack vm) vm in case (stack res) of 0:s -> proceed mempty s res _:s -> go $ proceed body s res _ -> err "while expected an argument." vm rep :: Program -> Program rep body = program go where go (n:s) = proceed (stimes n body) s go _ = err "rep expected an argument." proceed :: Program -> Stack -> Processor proceed prog s = run prog . setStack s 

Die Typen der branch und while Funktionen weisen darauf hin, dass es sich nicht um eigenständige Programme handelt, sondern um Programmkombinatoren: Ein typischer Ansatz beim Erstellen von EDSL in Haskell. Die stimes Funktion stimes für alle Halbgruppen definiert und gibt die Zusammensetzung der angegebenen Anzahl von Elementen zurück.

Schließlich werden wir einige Programme für Experimente schreiben.

 --   fact = dup <> push 2 <> lt <> branch (push 1) (dup <> dec <> fact) <> mul --   fact1 = push 1 <> swap <> while (dup <> push 1 <> gt) ( swap <> exch <> mul <> swap <> dec ) <> pop --     --    range = exch <> sub <> rep (dup <> inc) --    , --      fact2 = mconcat [ dec, push 2, swap, range, push 3, sub, rep mul] --      fact3 = dup <> put 0 <> dup <> dec <> rep (dec <> dup <> get 0 <> mul <> put 0) <> get 0 <> swap <> pop --      copy2 = exch <> exch --     --     gcd1 = while (copy2 <> neq) ( copy2 <> lt <> branch mempty (swap) <> exch <> sub ) <> pop --       pow = swap <> put 0 <> push 1 <> put 1 <> while (dup <> push 0 <> gt) ( dup <> push 2 <> modulo <> branch (dec <> get 0 <> dup <> get 1 <> mul <> put 1) (get 0) <> dup <> mul <> put 0 <> push 2 <> frac ) <> pop <> get 1 

Es stellte sich heraus, 120 Codezeilen mit Kommentaren und Anmerkungen von Typen, die eine Maschine definieren, die mit 18 Befehlen mit drei Kombinatoren arbeitet. So funktioniert unser Auto.

 λ> exec (push 6 <> fact) VM {stack = [720], status = Nothing, memory = [0,0,0,0]} λ> exec (push 6 <> fact3) VM {stack = [720], status = Nothing, memory = [720,0,0,0]} λ> exec (push 2 <> push 6 <> range) VM {stack = [6,5,4,3,2], status = Nothing, memory = [0,0,0,0]} λ> exec (push 6 <> push 9 <> gcd1) VM {stack = [3], status = Nothing, memory = [0,0,0,0]} λ> exec (push 3 <> push 15 <> pow) VM {stack = [14348907], status = Nothing, memory = [43046721,14348907,0,0]} λ> exec (push 9 <> add) VM {stack = [9], status = Just "Error! add expected two arguments", memory = [0,0,0,0]} 

Tatsächlich haben wir nichts Neues gemacht - durch die Kombination von Endomorphismus-Konvertern sind wir im Wesentlichen zur Faltung zurückgekehrt, aber sie wurde implizit. Denken Sie daran, dass die Faltung eine Abstraktion der sequentiellen Verarbeitung induktiver Daten bietet. In unserem Fall werden die Daten induktiv generiert, wenn der Bediener die Programme klebt $$$\ diamant$ und sie werden im Endomorphismus in Form einer Kette von Zusammensetzungen von Maschinentransformationsfunktionen "gespeichert", bis diese Kette auf den Ausgangszustand angewendet wird. Im Fall von Kombinatoren branch und while beginnt sich while Kette in einen Baum oder eine Schleife zu verwandeln. Im allgemeinen Fall erhalten wir ein Diagramm, das den Betrieb eines Automaten mit Speicherspeicher, dh einer gestapelten Maschine, widerspiegelt. Es ist diese Struktur, die wir während der Ausführung des Programms „zusammenbrechen“.

Wie effektiv ist diese Implementierung? Die Zusammensetzung der Funktionen ist das Beste, was der Haskell-Compiler leisten kann. Er ist buchstäblich dafür geboren! Wenn es um die Vorteile der Nutzung des Wissens über Monoide geht, geben sie häufig ein Beispiel für die Differenzliste diffList - die Implementierung einer verknüpften Liste in Form einer Zusammensetzung von Endomorphismen. Differenzlisten beschleunigen aufgrund der Assoziativität der Funktionszusammensetzung die Bildung von Listen aus vielen Stücken grundlegend. Die Beschäftigung mit Wrapper-Typen führt nicht zu einer Erhöhung des Overheads, sondern "löst" sich in der Kompilierungsphase auf. Von der zusätzlichen Arbeit verbleibt bei jedem Schritt des Programms nur eine Statusprüfung.

Monoide kombinieren

Ich denke, dass Skeptiker und Gelegenheitsleser uns bereits verlassen haben und Sie sich erlauben können, sich zu entspannen und zur nächsten Abstraktionsebene zu gelangen.

Das Konzept von Halbgruppen und Monoiden wäre nicht so nützlich und universell, wenn es nicht ausnahmslos eine Reihe von Eigenschaften gäbe, die allen Halbgruppen und Monoiden eigen sind und die es uns ermöglichen, komplexe Strukturen aus einfachen Strukturen auf die gleiche Weise zu erstellen, wie wir komplexe Programme aus einfachen erstellen. Diese Eigenschaften gelten nicht mehr für Objekte, sondern für Typen, und es ist besser, sie nicht in mathematischer Notation zu schreiben, sondern in Form von Programmen in Haskell, die aufgrund des Curry-Howard-Isomorphismus ihre Beweise sind.

1) Monoide und Halbgruppen können "multipliziert" werden. Dies bezieht sich auf das Produkt von Typen, deren Abstraktion in Haskell ein Tupel oder Paar ist.

 instance (Semigroup a, Semigroup b) => Semigroup (a,b) where (a1, b1) <> (a2, b2) = (a1 <> a2, b1 <> b2) instance (Monoid a, Monoid b) => Monoid (a,b) where mempty = (mempty, mempty ) 

2) Es gibt ein einzelnes Monoid, es wird durch einen einzelnen Typ dargestellt () :

 instance Semigroup () where () <> () = () instance Monoid () where mempty = () 

Bei der Multiplikation bilden die Halbgruppen selbst eine Halbgruppe, und unter Berücksichtigung des Einheitentyps können wir sagen, dass Monoide ein Monoid bilden! Die Assoziativität und Neutralität einer Einheit wird bis zum Isomorphismus erfüllt, dies ist jedoch nicht wichtig.

3) Abbildungen in eine Halbgruppe bzw. Monoidform, eine Halbgruppe oder ein Monoid. Und hier ist es auch einfacher, diese Aussage in Haskell zu schreiben:

 instance Semigroup a => Semigroup (r -> a) where f <> g = \r -> fr <> gr instance Monoid a => Monoid (r -> a) where mempty = const mempty 

Wir werden diese Kombinatoren verwenden, um die Funktionen der von uns erstellten Stapelsprache zu erweitern. Nehmen wir eine große Änderung vor und machen unsere grundlegenden Befehlsfunktionen , die Programme zurückgeben . Dadurch werden sie nicht ihrer monoidalen Eigenschaften beraubt, sondern es können beliebige Informationen von außen in die Arbeit aller Maschinenbefehle eingegeben werden. Hier ist was gemeint ist:

 (command1 <> command2) r == command1 r <> command2 r 

Die Informationen können beispielsweise ein externes Wörterbuch mit einigen Definitionen oder eine Möglichkeit sein, ein Protokoll der Berechnungen zu führen, die während des Debuggens benötigt werden. Dies ist der Aktion des Monadenlesers sehr ähnlich, die nur eine Funktion ist.

Wir werden ein Protokoll in die Struktur der Maschine einführen, es jedoch nicht an einen bestimmten Typ binden, sondern an den Typparameter ausgeben. Wir werden mit der verallgemeinerten monoidalen Operation in das Tagebuch schreiben.

 data VM a = VM { stack :: Stack , status :: Maybe String , memory :: Memory , journal :: a } deriving Show mkVM = VM mempty mempty (V.replicate memSize 0) setStack x (VM _ st ml) = VM x st ml setStatus st (VM s _ ml) = VM s st ml setMemory m (VM s st _ l) = VM s st ml addRecord x (VM s st mj) = VM s st m (x<>j) newtype Program a = Program { getProgram :: Action (VM a) } deriving (Semigroup, Monoid) type Program' a = (VM a -> VM a) -> Program a 

Von nun an erlauben wir uns, nicht für alle Definitionen Typanmerkungen anzugeben, so dass der Compiler sie unabhängig behandeln kann. Sie sind nicht kompliziert, obwohl sie umständlich werden. Dank intelligenter Designer, die sich um alle Änderungen kümmern, müssen die Teams selbst nicht geändert werden. Ganz klein.

 program fp = Program . Action $ \vm -> case status vm of Nothing -> p . (f (stack vm)) $ vm m -> vm programM fp = Program . Action $ \vm -> case status vm of Nothing -> p . (f (memory vm, stack vm)) $ vm m -> vm proceed p prog s = run (prog p) . setStack s rep body p = program go id where go (n:s) = proceed p (stimes n body) s go _ = err "rep expected an argument." branch br1 br2 p = program go id where go (x:s) = proceed p (if (x /= 0) then br1 else br2) s go _ = err "branch expected an argument." while test body p = program (const go) id where go vm = let res = proceed p test (stack vm) vm in case (stack res) of 0:s -> proceed p mempty s res _:s -> go $ proceed p body s res _ -> err "while expected an argument." vm 

Es bleibt zu lehren, externe Informationen in den Programmausführer einzugeben. Dies ist sehr einfach, indem verschiedene Künstler mit unterschiedlichen Protokollierungsstrategien erstellt werden. Der erste Darsteller wird der einfachste, leiseste sein und keine Mühe damit verschwenden, ein Tagebuch zu führen:

 exec prog = run (prog id) (mkVM ()) 

Hier war uns ein einzelnes Monoid () nützlich - ein neutrales Element in der Monoidalgebra. Ferner ist es möglich, eine Funktion für einen Ausführenden zu definieren, der bereit ist, diese oder jene Informationen über den Zustand der Maschine im Journal aufzuzeichnen.

 execLog p prog = run (prog $ \vm -> addRecord (p vm) vm) (mkVM mempty) 

Informationen können zum Beispiel sein:

 logStack vm = [stack vm] logStackUsed = Max . length . stack logSteps = const (Sum 1) logMemoryUsed = Max . getSum . count . memory where count = foldMap (\x -> if x == 0 then 0 else 1) 

:

 λ> exec (push 4 <> fact2) VM {stack = [24], status = Nothing, memory = [0,0,0,0], journal = ()} λ> journal $ execLog logSteps (push 4 <> fact2) Sum {getSum = 14} λ> mapM_ print $ reverse $ journal $ execLog logStack (push 4 <> fact2) [4] [3] [2,3] [3,2] [2,2] [3,2] [3,3,2] [4,3,2] [4,4,3,2] [5,4,3,2] [3,5,4,3,2] [2,4,3,2] [12,2] [24] 

, , . :

 f &&& g = \r -> (fr, gr) 

 λ> let report p = journal $ execLog (logSteps &&& logStackUsed) p λ> report (push 8 <> fact) (Sum {getSum = 48},Max {getMax = 10}) λ> report (push 8 <> fact1) (Sum {getSum = 63},Max {getMax = 4}) λ> report (push 8 <> fact2) (Sum {getSum = 26},Max {getMax = 9}) λ> report (push 8 <> fact3) (Sum {getSum = 43},Max {getMax = 3}) 

&&& , . , Haskell . , .

. — , Haskell. .

, , — . , : . ( ) , ( ) . , , . - .

! :

 data Code = IF [Code] [Code] | REP [Code] | WHILE [Code] [Code] | PUT Int | GET Int | PUSH Int | POP | DUP | SWAP | EXCH | INC | DEC | NEG | ADD | MUL | SUB | DIV | EQL | LTH | GTH | NEQ deriving (Read, Show) 

$$$\rightarrow$ :

 fromCode :: [Code] -> Program' a fromCode = hom where hom = foldMap $ \case IF b1 b2 -> branch (hom b1) (hom b2) REP p -> rep (hom p) WHILE tb -> while (hom t) (hom b) PUT i -> put i GET i -> get i PUSH i -> push i POP -> pop DUP -> dup SWAP -> swap EXCH -> exch INC -> inc DEC -> dec ADD -> add MUL -> mul SUB -> sub DIV -> frac EQL -> eq LTH -> lt GTH -> gt NEQ -> neq NEG -> neg 

, . foldMap , . fromCode , , , c:

 λ> stack $ exec (fromCode [PUSH 2, PUSH 5, EXCH, SUB, REP [DUP, INC]]) [5,4,3,2] λ> stack $ exec (fromCode $ read "[PUSH 2, PUSH 5, EXCH, SUB, REP [DUP, INC]]") [5,4,3,2] 

$$$\rightarrow$ , case . : ! Program :

 newtype Program a = Program { getProgram :: ([Code], Action (VM a)) } deriving (Semigroup, Monoid) run = runAction . snd . getProgram 

run , fromCode :

 toCode :: Program' a -> [Code] toCode prog = fst . getProgram $ prog id 

, . , :

 type Program' a = (Code -> VM a -> VM a) -> Program a program cfp = Program . ([c],) . Action $ \vm -> case status vm of Nothing -> pc . f (stack vm) $ vm _ -> vm programM cfp = Program . ([c],) . Action $ \vm -> case status vm of Nothing -> pc . f (memory vm, stack vm) $ vm _ -> vm 

, , , . , -:

 none = const id exec prog = run (prog none) (mkVM ()) execLog p prog = run (prog $ \c -> \vm -> addRecord (pc vm) vm) (mkVM mempty) logStack _ vm = [stack vm] logStackUsed _ = Max . length . stack logSteps _ = const (Sum 1) --   logCode c _ = [c] logRun com vm = [pad 10 c ++ "| " ++ pad 20 s ++ "| " ++ m] where c = show com m = unwords $ show <$> toList (memory vm) s = unwords $ show <$> stack vm pad nx = take n (x ++ repeat ' ') debug :: Program' [String] -> String debug = unlines . reverse . journal . execLog logRun 

 pop = program POP $ \case x:s -> setStack s _ -> err "POP expected an argument." push x = program (PUSH x) $ \s -> setStack (x:s) dup = program DUP $ \case x:s -> setStack (x:x:s) _ -> err "DUP expected an argument." swap = program SWAP $ \case x:y:s -> setStack (y:x:s) _ -> err "SWAP expected two arguments." exch = program EXCH $ \case x:y:s -> setStack (y:x:y:s) _ -> err "EXCH expected two arguments." app1 cf = program c $ \case x:s -> setStack (fx:s) _ -> err $ "operation " ++ show c ++ " expected an argument" app2 cf = program c $ \case x:y:s -> setStack (fxy:s) _ -> err $ "operation " ++ show c ++ " expected two arguments" add = app2 ADD (+) sub = app2 SUB (flip (-)) mul = app2 MUL (*) frac = app2 DIV (flip div) neg = app1 NEG (\x -> -x) inc = app1 INC (\x -> x+1) dec = app1 DEC (\x -> x-1) eq = app2 EQL (\x -> \y -> if (x == y) then 1 else 0) neq = app2 NEQ (\x -> \y -> if (x /= y) then 1 else 0) lt = app2 LTH (\x -> \y -> if (x > y) then 1 else 0) gt = app2 GTH (\x -> \y -> if (x < y) then 1 else 0) proceed p prog s = run (prog p) . setStack s rep body p = program (REP (toCode body)) go none where go (n:s) = if n >= 0 then proceed p (stimes n body) s else err "REP expected positive argument." go _ = err "REP expected an argument." branch br1 br2 p = program (IF (toCode br1) (toCode br2)) go none where go (x:s) = proceed p (if (x /= 0) then br1 else br2) s go _ = err "IF expected an argument." while test body p = program (WHILE (toCode test) (toCode body)) (const go) none where go vm = let res = proceed p test (stack vm) vm in case (stack res) of 0:s -> proceed p mempty s res _:s -> go $ proceed p body s res _ -> err "WHILE expected an argument." vm put i = indexed (PUT i) i $ \case (m, x:s) -> setStack s . setMemory (m // [(i,x)]) _ -> err "PUT expected an argument" get i = indexed (GET i) i $ \(m, s) -> setStack ((m ! i) : s) indexed cif = programM c $ if (i < 0 || i >= memSize) then const $ err "index in [0,16]" else f 

, ! , .

-, :

 λ> toCode fact1 [PUSH 1,SWAP,WHILE [DUP,PUSH 1,GTH] [SWAP,EXCH,MUL,SWAP,DEC],POP] 

EDSL, .

-, , toCode fromCode -.

 λ> toCode $ fromCode [PUSH 5, PUSH 6, ADD] [PUSH 5, PUSH 6, ADD] λ> exec (fromCode $ toCode (push 5 <> push 6 <> add)) VM {stack = [11], status = Nothing, memory = [0,0,0,0], journal = ()} 

, : , . ghci fact , , Ctrl+C . , toCode , .

, , , - :

 λ> putStrLn $ debug (push 3 <> fact) PUSH 3 | 3 | 0 0 0 0 DUP | 3 3 | 0 0 0 0 PUSH 2 | 2 3 3 | 0 0 0 0 LTH | 0 3 | 0 0 0 0 DUP | 3 3 | 0 0 0 0 DEC | 2 3 | 0 0 0 0 DUP | 2 2 3 | 0 0 0 0 PUSH 2 | 2 2 2 3 | 0 0 0 0 LTH | 0 2 3 | 0 0 0 0 DUP | 2 2 3 | 0 0 0 0 DEC | 1 2 3 | 0 0 0 0 DUP | 1 1 2 3 | 0 0 0 0 PUSH 2 | 2 1 1 2 3 | 0 0 0 0 LTH | 1 1 2 3 | 0 0 0 0 PUSH 1 | 1 1 2 3 | 0 0 0 0 MUL | 1 2 3 | 0 0 0 0 MUL | 2 3 | 0 0 0 0 MUL | 6 | 0 0 0 0 

. . , , !

, . — . , , .

, : , . , , . !

, , :

 listing :: Program' a -> String listing = unlines . hom 0 . toCode where hom n = foldMap f where f = \case IF b1 b2 -> ouput "IF" <> indent b1 <> ouput ":" <> indent b2 REP p -> ouput "REP" <> indent p WHILE tb -> ouput "WHILE" <> indent t <> indent b c -> ouput $ show c ouput x = [stimes n " " ++ x] indent = hom (n+1) 

: , , , .

 λ> putStrLn . listing $ fact2 INC PUSH 1 SWAP EXCH SUB DUP PUSH 0 GTH IF REP DUP INC : NEG REP DUP DEC DEC DEC REP MUL λ> putStrLn . listing $ gcd1 WHILE EXCH EXCH NEQ EXCH EXCH LTH IF : SWAP EXCH SUB POP 

. , , . .

, — , . , . :

Wenn Sie nacheinander Valenzbefehle ausführen, werden diese auf folgende nicht triviale Weise kombiniert:

 infix 7 :> data Arity = Int :> Int deriving (Show,Eq) instance Semigroup Arity where (i1 :> o1) <> (i2 :> o2) = let a = 0 `max` (i2 - o1) in (a + i1) :> (a + o1 + o2 - i2) instance Monoid Arity where mempty = 0:>0 

Und dann können Sie einen Homomorphismus aufbauen:

 arity :: Program' a -> Arity arity = hom . toCode where hom = foldMap $ \case IF b1 b2 -> let i1 :> o1 = hom b1 i2 :> o2 = hom b2 in 1:>0 <> (i1 `max` i2):>(o1 `min` o2) REP p -> 1:>0 WHILE tb -> hom t <> 1:>0 PUT _ -> 1:>0 GET _ -> 0:>1 PUSH _ -> 0:>1 POP -> 1:>0 DUP -> 1:>2 SWAP -> 2:>2 EXCH -> 2:>3 INC -> 1:>1 DEC -> 1:>1 NEG -> 1:>1 _ -> 2:>1 

, , . , , .

( ):

 λ> arity (exch <> exch) 2 :> 4 λ> arity fact1 1 :> 1 λ> arity range 2 :> 1 λ> arity (push 3 <> dup <> pow) 0 :> 1 

? , "" . Program' a -> Max Int , . , , :

 memoryUse :: Program' a -> Max Int memoryUse = hom . toCode where hom = foldMap $ \case IF b1 b2 -> hom b1 <> hom b2 REP p -> hom p WHILE tb -> hom t <> hom b PUT i -> Max (i+1) GET i -> Max (i+1) _ -> 0 

 λ> memoryUse fact1 Max {getMax = 0} λ> memoryUse fact3 Max {getMax = 1} λ> memoryUse pow Max {getMax = 2} 

. , .

, : , , , 0:>_ . . , .

 isReducible p = let p' = fromCode p in case arity p' of 0:>_ -> memoryUse p' == 0 _ -> False reducible = go [] . toCode where go res [] = reverse res go res (p:ps) = if isReducible [p] then let (a,b) = spanBy isReducible (p:ps) in go (a:res) b else go res ps --    Last,  , --     spanBy test l = case foldMap tst $ zip (inits l) (tails l) of Last Nothing -> ([],l) Last (Just x) -> x where tst x = Last $ if test (fst x) then Just x else Nothing --    Endo    --  intercalate  splitOn     -- Data.List  Data.List.Split reduce p = fromCode . process (reducible p) . toCode $ p where process = appEndo . foldMap (\x -> Endo $ x `replaceBy` shrink x) shrink = toCode . foldMap push . reverse . stack . exec . fromCode replaceBy xy = intercalate y . splitOn x 

 λ> let p = push 6 <> fact1 <> swap <> push 5 <> dup <> push 14 <> gcd1 <> put 1 λ> toCode $ p [PUSH 6,PUSH 1,SWAP,WHILE [DUP,PUSH 1,GTH] [SWAP,EXCH,MUL,SWAP,DEC],POP,SWAP,PUSH 5,DUP,PUSH 14,WHILE [EXCH,EXCH,NEQ] [EXCH,EXCH,LTH,IF [] [SWAP],EXCH,SUB],POP,PUT 1] λ> toCode $ reduce p [PUSH 720,SWAP,PUSH 5,PUSH 1,PUT 1] λ> execLog logSteps (push 8 <> p) VM {stack = [5,8,720], status = Nothing, memory = [0,1,0,0], journal = Sum {getSum = 107}} λ> execLog logSteps (push 8 <> reduce p) VM {stack = [5,8,720], status = Nothing, memory = [0,1,0,0], journal = Sum {getSum = 6}} 

, , , , - ( ).

: , , , ..? ? , , !

m VM -> VM VM -> m VM , . : " — , ?!" , VM -> m VM , , , . Haskell >=> " ". , Action ActionM , :

 newtype ActionM ma = ActionM { runActionM :: a -> ma } instance Monad m => Semigroup (ActionM ma) where ActionM f <> ActionM g = ActionM (f >=> g) instance Monad m => Monoid (ActionM ma) where mempty = ActionM return 

, , >=> . .

 {-# LANGUAGE LambdaCase, GeneralizedNewtypeDeriving, TupleSections #-} import Data.Monoid hiding ((<>)) import Data.Semigroup (Semigroup(..),stimes,Max(..)) import Data.Vector ((//),(!),Vector,toList) import qualified Data.Vector as V (replicate) import Control.Monad import Control.Monad.Identity type Stack = [Int] type Memory = Vector Int memSize = 4 data VM a = VM { stack :: Stack , status :: Maybe String , memory :: Memory , journal :: a } deriving Show mkVM = VM mempty mempty (V.replicate memSize 0) setStack x (VM _ st ml) = return $ VM x st ml setStatus st (VM s _ ml) = return $ VM s st ml setMemory m (VM s st _ l) = return $ VM s st ml addRecord x (VM s st ml) = VM s st m (x<>l) ------------------------------------------------------------ data Code = IF [Code] [Code] | REP [Code] | WHILE [Code] [Code] | PUT Int | GET Int | PUSH Int | POP | DUP | SWAP | EXCH | INC | DEC | NEG | ADD | MUL | SUB | DIV | MOD | EQL | LTH | GTH | NEQ | ASK | PRT | PRTS String | FORK [Code] [Code] deriving (Read, Show) newtype ActionM ma = ActionM {runActionM :: a -> ma} instance Monad m => Semigroup (ActionM ma) where ActionM f <> ActionM g = ActionM (f >=> g) instance Monad m => Monoid (ActionM ma) where ActionM f `mappend` ActionM g = ActionM (f >=> g) mempty = ActionM return newtype Program ma = Program { getProgram :: ([Code], ActionM m (VM a)) } deriving (Semigroup, Monoid) type Program' ma = (Code -> VM a -> m (VM a)) -> Program ma program cfp = Program . ([c],) . ActionM $ \vm -> case status vm of Nothing -> pc =<< f (stack vm) vm m -> return vm programM cfp = Program . ([c],) . ActionM $ \vm -> case status vm of Nothing -> pc =<< f (memory vm, stack vm) vm m -> return vm run :: Monad m => Program ma -> VM a -> m (VM a) run = runActionM . snd . getProgram toCode :: Monad m => Program' ma -> [Code] toCode prog = fst . getProgram $ prog none none :: Monad m => Code -> VM a -> m (VM a) none = const return --     exec :: Program' Identity () -> VM () exec = runIdentity . execM execM :: Monad m => Program' m () -> m (VM ()) execM prog = run (prog none) (mkVM ()) execLog p prog = run (prog $ \c -> \vm -> return $ addRecord (pc vm) vm) (mkVM mempty) f &&& g = \c -> \r -> (fcr, gcr) logStack _ vm = [stack vm] logStackUsed _ = Max . length . stack logSteps _ = const (Sum 1) logCode c _ = [c] logRun com vm = [pad 10 c ++ "| " ++ pad 20 s ++ "| " ++ m] where c = show com m = unwords $ show <$> toList (memory vm) s = unwords $ show <$> stack vm pad nx = take n (x ++ repeat ' ') debug p = unlines . reverse . journal <$> execLog logRun p ------------------------------------------------------------ pop,dup,swap,exch :: Monad m => Program' ma put,get,push :: Monad m => Int -> Program' ma add,mul,sub,frac,modulo,inc,dec,neg :: Monad m => Program' ma eq,neq,lt,gt :: Monad m => Program' ma err m = setStatus . Just $ "Error : " ++ m pop = program POP $ \case x:s -> setStack s _ -> err "pop expected an argument." push x = program (PUSH x) $ \s -> setStack (x:s) dup = program DUP $ \case x:s -> setStack (x:x:s) _ -> err "dup expected an argument." swap = program SWAP $ \case x:y:s -> setStack (y:x:s) _ -> err "swap expected two arguments." exch = program EXCH $ \case x:y:s -> setStack (y:x:y:s) _ -> err "expected two arguments." put i = indexed (PUT i) i $ \case (m, x:s) -> setStack s <=< setMemory (m // [(i,x)]) _ -> err "put expected an argument" get i = indexed (GET i) i $ \(m, s) -> setStack ((m ! i) : s) indexed cif = programM c $ if (i < 0 || i >= memSize) then const $ err "index in [0,16]" else f app1 cf = program c $ \case x:s -> setStack (fx:s) _ -> err $ "operation " ++ show c ++ " expected an argument" app2 cf = program c $ \case x:y:s -> setStack (fxy:s) _ -> err $ "operation " ++ show c ++ " expected two arguments" add = app2 ADD (+) sub = app2 SUB (flip (-)) mul = app2 MUL (*) frac = app2 DIV (flip div) modulo = app2 MOD (flip mod) neg = app1 NEG (\x -> -x) inc = app1 INC (\x -> x+1) dec = app1 DEC (\x -> x-1) eq = app2 EQL (\x -> \y -> if (x == y) then 1 else 0) neq = app2 NEQ (\x -> \y -> if (x /= y) then 1 else 0) lt = app2 LTH (\x -> \y -> if (x > y) then 1 else 0) gt = app2 GTH (\x -> \y -> if (x < y) then 1 else 0) proceed p prog s = run (prog p) <=< setStack s rep body p = program (REP (toCode body)) go none where go (n:s) = if n >= 0 then proceed p (stimes n body) s else err "rep expected positive argument." go _ = err "rep expected an argument." branch br1 br2 p = program (IF (toCode br1) (toCode br2)) go none where go (x:s) = proceed p (if (x /= 0) then br1 else br2) s go _ = err "branch expected an argument." while test body p = program (WHILE (toCode test) (toCode body)) (const go) none where go vm = do res <- proceed p test (stack vm) vm case (stack res) of 0:s -> proceed p mempty s res _:s -> go =<< proceed p body s res _ -> err "while expected an argument." vm ask :: Program' IO a ask = program ASK $ \case s -> \vm -> do x <- getLine setStack (read x:s) vm prt :: Program' IO a prt = program PRT $ \case x:s -> \vm -> print x >> return vm _ -> err "PRT expected an argument" prtS :: String -> Program' IO a prtS s = program (PRTS s) $ const $ \vm -> print s >> return vm fork :: Program' [] a -> Program' [] a -> Program' [] a fork br1 br2 p = program (FORK (toCode br1) (toCode br2)) (const go) none where go = run (br1 p) <> run (br2 p) ------------------------------------------------------------ fromCode :: Monad m => [Code] -> Program' ma fromCode = hom where hom = foldMap $ \case IF b1 b2 -> branch (hom b1) (hom b2) REP p -> rep (hom p) WHILE tb -> while (hom t) (hom b) PUT i -> put i GET i -> get i PUSH i -> push i POP -> pop DUP -> dup SWAP -> swap EXCH -> exch INC -> inc DEC -> dec ADD -> add MUL -> mul SUB -> sub DIV -> frac MOD -> modulo EQL -> eq LTH -> lt GTH -> gt NEQ -> neq NEG -> neg _ -> mempty fromCodeIO :: [Code] -> Program' IO a fromCodeIO = hom where hom = foldMap $ \case IF b1 b2 -> branch (hom b1) (hom b2) REP p -> rep (hom p) WHILE tb -> while (hom t) (hom b) ASK -> ask PRT -> ask PRTS s -> prtS s c -> fromCode [c] fromCodeList :: [Code] -> Program' [] a fromCodeList = hom where hom = foldMap $ \case IF b1 b2 -> branch (hom b1) (hom b2) REP p -> rep (hom p) WHILE tb -> while (hom t) (hom b) FORK b1 b2 -> fork (hom b1) (hom b2) c -> fromCode [c] 

: stdin .

 ask, prt :: Program' IO a ask = program ASK $ \case s -> \vm -> do x <- getLine setStack (read x:s) vm prt = program PRT $ \case x:s -> \vm -> print x >> return vm _ -> err "PRT expected an argument" prtS :: String -> Program' IO a prtS s = program (PRTS s) $ const $ \vm -> print s >> return vm 

- , :

 ioprog = prtS "input first number" <> ask <> prtS "input second number" <> ask <> rep (prt <> dup <> inc) <> prt 

 λ> exec ioprog input first number 3 input second number 5 3 4 5 6 7 8 VM {stack = [8,7,6,5,4,3], status = Nothing, memory = [0,0,0,0], journal = ()} 

, :

 fork :: Program' [] a -> Program' [] a -> Program' [] a fork br1 br2 p = program (FORK (toCode br1) (toCode br2)) (const go) pure where go = run (br1 p) <> run (br2 p) 

: run VM -> m VM , — , , [] , — .

:

 λ> stack <$> exec (push 5 <> push 3 <> add `fork` sub) [[8],[2]] λ> stack <$> exec (push 5 <> push 3 `fork` dup <> push 2) [[2,3,5],[2,5,5]] 

: $$$(2 \pm 3)*((4 \pm 8)\pm 5)$ ::

 λ> let pm = add `fork` sub λ> stack <$> exec (push 2 <> push 3 <> push 4 <> push 8 <> pm <> push 5 <> pm <> pm <> mul) [[40],[-28],[20],[-8],[8],[4],[-12],[24]] 

:

 λ> journal <$> execLog logSteps (push 8 <> fact `fork` fact1 `fork` fact2 `fork` fact3) [Sum {getSum = 48},Sum {getSum = 63},Sum {getSum = 34},Sum {getSum = 43}] 

, fork , , fork .

. . , /, , .

- μάγμα . , , , . , , , Lego: , - . , , , .

Lego , , — , , . , , . — ! , . , - . ( -) , . — ! "" , , , , . , , .

. - , . — , . .