# Crème de la Crem: Composable Representable Executable Machines

Architectural Pearl

Marco Perone  TrevisoItaly<EMAIL_ADDRESS>0000-0002-1004-0431 and
Georgios Karachalias  TweagParisFrance<EMAIL_ADDRESS>0009-0008-3071-7842

###### Abstract.

In this paper we describe how to build software architectures as a composition
of state machines, using ideas and principles from the field of Domain-Driven
Design. By definition, our approach is _modular_ , allowing one to compose
independent subcomponents to create bigger systems, and _representable_ ,
allowing the implementation of a system to be kept in sync with its graphical
representation.

In addition to the design itself we introduce the _Crem_ library, which
provides a concrete state machine implementation that is both compositional
and representable. _Crem_ uses Haskell’s advanced type-level features to allow
users to specify allowed and forbidden state transitions, and to encode
complex state machine—and therefore domain-specific—properties. Moreover,
since _Crem_ ’s state machines are representable, _Crem_ can automatically
generate graphical representations of systems from their domain
implementations.

domain architecture, domain-driven design, state machine

††ccs: Hardware Finite state machines††ccs: Software and its engineering
Software design engineering

##  1\. Introduction

Tactical Domain-Driven Design focuses on identifying transactional boundaries
and is often combined with an event-based architecture (Stopford, 2018), which
is based on the flow of messages (e.g. commands and events) throughout an
application domain and the clear separation of responsibilities among several
components (e.g. aggregates, policies and projections).

Such separation often allows to fruitfully discuss with non-technical domain
experts the details of the inner workings of the domain itself and to
translate them directly into working code. Moreover, as the understanding of
the domain deepens as time passes, the architecture itself allows for
refactorings towards deeper insights.

Still, terms and concepts like aggregates, policies and projections lack a
precise definition and delimitation, and this tends to create discussions and
confusion.

Another issue we experienced developing systems using Domain-Driven Design
techniques is the distance which appears between the theoretical model
developed through distilling knowledge from the domain experts and the
concrete implementation of such a model. This is basically the same issue
which happens with stale documentation, where the documentation of a piece of
code is not up-to-date with the current behaviour of the code itself.

With the work described in this paper we try to mitigate these issues bringing
together ideas from Domain-Driven Design, state machines and functional
programming, expressing DDD and event-based architectures in terms of state
machines using Haskell.

The main novel contributions of this paper are:

  * •

Using state machines to implement policies and projections, building on top of
the existing knowledge of treating aggregates as state machines (Ploch, 2022).

This allows to use state machines as the unique underlying concept needed to
implement a whole application domain.

Moreover, such an approach makes it all compositional, since state machines
compose extremely well.

  * •

Implementing state machines, and therefore architectures based on them, in
such a way that information could be extracted from the implementation and
used as documentation of the system.

Specifically, we are able to generate a graphical representation out of the
domain implementation which describes the relevant information about the
domain itself. This is extremely helpful when discussing the behaviour of the
domain with domain experts, removing the need for understanding and explaining
the bare code behaviour.

The ability of generating a graphical representation out of a state machine
was already available with _motor_ (Wickström, 2019). While _motor_ is focused
on building single state machines, this article and the _Crem_ library improve
the situation introducing compositionality.

  * •

Making explicit the connection between an abstract model and its concrete
implementation via a novel combination of Domain-Driven Design ideas and state
machines.

  * •

Using Haskell’s powerful type system to encode complex properties of the
implemented state machines, and therefore of the domains they represent.

With _Crem_ we are able to express explicitly which state transitions are
allowed and which, on the other hand, are forbidden.

Using Haskell we are able to get access both to features mimicking dependent
types, needed for the whole machinery to work, and also to the whole ecosystem
of production-ready libraries and frameworks.

For example, with _Crem_ we can create systems, with an architecture based on
Domain-Driven Design principles, just by composing state machines as follows

$\begin{array}[]{@{\hspace{0mm}}l@{\hspace{0mm}}}\mathit{wholeCartDomain}::\mathit{StateMachine}~{}\mathit{CartCommand}~{}[\mathit{CartView}]\\\
\mathit{wholeCartDomain}=\mathit{Kleisli}\\\
\quad(\mathit{Feedback}~{}\mathit{cart}~{}\mathit{paymentGateway})\\\
\quad\mathit{paymentStatus}\\\ \end{array}$

and generate a graphical representation describing the implemented system (see
Figure 7).

##  2\. Domain-Driven Design

Domain-driven design, as a community and as a practice, aims to build software
for complex domains creating a shared understanding of the domain and
expressing it in a model, which describes the problem space (Verraes, 2021).

One popular shape of such models, which emerges naturally from Event Storming
workshops (Brandolini, 2015), is rooted in ideas such as Aggregates (Evans,
2003), Event Sourcing (Young, 2007)111Notice that the architecture that we
describe in the paper is very well suited for Event Sourcing, but does not
rely on it and is actually independent of how persistence is dealt with and
CQRS (Young, 2010) and is captured in Figure 1.

Figure 1. Domain-Driven Design Model. Arrow direction denotes the flow on
information. Solid arrows describe software interactions, while dotted ones
refer to human ones. Square boxes represent data types, while rounded ones
represent processes.

The flow of such an architecture goes as follows:

  * •

A user expresses their desired interaction with the software with a _Command_
, comprising all the necessary information to execute that command.

  * •

The _Command_ is received by an _Aggregate_ , which has the role of making
sure that every invariant of the system is preserved. Then, it emits its
decisions as _Events_.

  * •

_Events_ describe the relevant state transitions of the system, containing all
the data necessary to propagate information through the system and potentially
to reconstruct the current state of the system.

  * •

_Policies_ describe the reactive logic of the application. Whenever an _Event_
is emitted by an _Aggregate_ , the system might decide to react to it emitting
a new _Command_.

  * •

_Projections_ aggregate the information contained in the _Events_ and
condensate them into specialised _Views_.

  * •

_Views_ describe the information which are then shown to and used by the user
to decide which _Command_ they should require next.

We will henceforth use the colors used for defining the terms whenever there
is an instance of this term. For example, as _Aggregate_ is colored
red222Traditionally in $\mathit{EventStorming}$ aggregates are yellow, but it
doesn’t render well on paper, so we switched to red., the _Cart_ aggregate
will also be red.

As a recurring example, we will consider the checkout process of a standard
ecommerce systems. In such a context, a user emits a _PayCart_ command
instructing the system to process the payment of their cart. The _Cart_
aggregate will check all the system invariants to ensure that the cart is in a
state where it could actually be paid (e.g. it is not empty); if every
invariant is satisfied, the aggregate will emit a _CartPaymentInitiated_
event. A _PaymentGateway_ policy will contact an external system to actually
process the payment; if the payment is processed correctly, the policy will
emit a _MarkCartAsPaid_ command. The command will then be processed by the
_Cart_ aggregate, which will emit a _CartPaymentCompleted_ event. The
_PaymentStatus_ projection will react to the _CartPaymentInitiated_ and
_CartPaymentCompleted_ events to provide the user with a _CartState_ view
describing the current state of the payment.

Aggregates and projections are by their nature pure stateful processes,
meaning that the only effect which can take place is state management. In
particular their logic does not depend on the interaction with the external
world. All the relevant information for making sensible decisions is contained
either in their state or provided by the incoming messages.

On the other hand, policies are by nature impure, since they often deal with
interacting with external systems.

The cycle which get created between aggregates and policies helps to split the
write side of the domain logic between its pure and its effectful parts,
increasing the testability of the system.

##  3\. State machines

In the architecture described above, while commands, events and views are just
simple data, on the other hand aggregates, policies and projections are
stateful processes. As such, they could be implemented as state machines. By
_state machine_ we always mean a _Mealy machine_ (Mealy, 1955), which is
composed of a stateful function and the current value for the state.
Practically, it consists of the current value of the state and an action to
emit an output determined from an input and the current value of the state,
while being able to update the state.

In Haskell terms, one potential implementation could be the following.

$\begin{array}[]{c@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l}\lx@intercol{\textbf{data}}~{}\mathit{Mealy}~{}s~{}a~{}b=\mathit{Mealy}\hfil\lx@intercol\\\
\quad\\{\hfil\hskip 2.84526pt&\mathit{initialState}\hfil\hskip
2.84526pt&::\hfil\hskip 2.84526pt&s\\\ \quad,\hfil\hskip
2.84526pt&\mathit{action}\hfil\hskip 2.84526pt&::\hfil\hskip 2.84526pt&s\to
a\to(b,s)\\\ \quad\\}\hfil\hskip 2.84526pt\\\ \end{array}$

State machines come with many practical benefits:

  * •

They are extremely compositional and allow combining simple state machines
into more complex ones in several ways.

For examples, two machines could be composed sequentially, feeding the output
of the first machines as inputs of the second.

Or they could be executed in parallel, providing the inputs to both machines
and collecting their outputs.

Or they could be executed in alternative, providing either the input to the
first machine or the input the second, executing the corresponding machine,
and obtaining as output either the output of the first machine or the output
of the second.

  * •

They allow a graphical representation as state diagrams, which could help to
understand how a machine actually works also for non-technical people.

  * •

They can be implemented as a function depending just on the _input_ and the
_state_. The simplicity of this mental model helps the implementor considering
all the possible cases which need to be considered and uncovering potential
edge cases.

For example, the _Cart_ aggregate of the previous section could be implemented
along these lines; see Figure 2.

$\begin{array}[]{@{\hspace{0mm}}r@{\hspace{1mm}}c@{\hspace{1mm}}l}\lx@intercol{\textbf{data}}~{}\mathit{CartCommand}\hfil\lx@intercol\\\
\hskip 2.84526pt&=\hfil\hskip 2.84526pt&\mathit{PayCart}\\\ \hskip
2.84526pt&|\hfil\hskip 2.84526pt&\mathit{MarkCartAsPaid}\\\\[5.69054pt]
\lx@intercol{\textbf{data}}~{}\mathit{CartEvent}\hfil\lx@intercol\\\ \hskip
2.84526pt&=\hfil\hskip 2.84526pt&\mathit{CartPaymentInitiated}\\\ \hskip
2.84526pt&|\hfil\hskip 2.84526pt&\mathit{CartPaymentCompleted}\\\\[5.69054pt]
\lx@intercol{\textbf{data}}~{}\mathit{CartState}\hfil\lx@intercol\\\ \hskip
2.84526pt&=\hfil\hskip 2.84526pt&\mathit{WaitingForPayment}\\\ \hskip
2.84526pt&|\hfil\hskip 2.84526pt&\mathit{InitiatingPayment}\\\ \hskip
2.84526pt&|\hfil\hskip 2.84526pt&\mathit{PaymentComplete}\\\\[5.69054pt]
\lx@intercol\mathit{cart}::\mathit{Mealy}~{}\mathit{CartState}~{}\mathit{CartCommand}~{}[\mathit{CartEvent}]\hfil\lx@intercol\\\
\lx@intercol\mathit{cart}=\mathit{Mealy}\hfil\lx@intercol\\\ \hskip
2.84526pt&\\{\hfil\hskip
2.84526pt&\mathit{initialState}=\mathit{WaitingForPayment}\\\ \hskip
2.84526pt&,\hfil\hskip 2.84526pt&\mathit{action}=\backslash{\textbf{case}}\\\
\hskip 2.84526pt&\hfil\hskip
2.84526pt&\quad\mathit{WaitingForPayment}~{}\mathit{PayCart}\to\\\ \hskip
2.84526pt&\hfil\hskip
2.84526pt&\qquad([\mathit{CartPaymentInitiated}],\mathit{InitiatingPayment})\\\
\hskip 2.84526pt&\hfil\hskip
2.84526pt&\quad\mathit{WaitingForPayment}~{}\mathit{MarkCartAsPaid}\to\\\
\hskip 2.84526pt&\hfil\hskip
2.84526pt&\qquad([],\mathit{WaitingForPayment})\\\ \hskip
2.84526pt&\hfil\hskip
2.84526pt&\quad\mathit{InitiatingPayment}~{}\mathit{PayCart}\to\\\ \hskip
2.84526pt&\hfil\hskip 2.84526pt&\qquad([],\mathit{InitiatingPayment})\\\
\hskip 2.84526pt&\hfil\hskip
2.84526pt&\quad\mathit{InitiatingPayment}~{}\mathit{MarkCartAsPaid}\to\\\
\hskip 2.84526pt&\hfil\hskip
2.84526pt&\qquad([\mathit{CartPaymentCompleted}],\mathit{PaymentComplete})\\\
\hskip 2.84526pt&\hfil\hskip
2.84526pt&\quad\mathit{PaymentComplete}~{}\mathit{PayCart}\to\\\ \hskip
2.84526pt&\hfil\hskip 2.84526pt&\qquad([],\mathit{PaymentComplete})\\\ \hskip
2.84526pt&\hfil\hskip
2.84526pt&\quad\mathit{PaymentComplete}~{}\mathit{MarkCartAsPaid}\to\\\ \hskip
2.84526pt&\hfil\hskip 2.84526pt&\qquad([],\mathit{PaymentComplete})\\\ \hskip
2.84526pt&\\}\hfil\hskip 2.84526pt&\\\ \end{array}$ Figure 2. Cart
Implementation, Simplified

This is a very simplified version, which does not perform any sophisticated
logic on duplicate or unexpected messages, but still it gives the idea of how
the domain logic could be implemented.

In real systems, one will have to deal with multiple aggregates, handling
different kinds of commands. Since there will be only one aggregate to deal
with a given command, we can compose several aggregates in parallel to obtain
a bigger component able to deal with multiple kinds of commands. Then, when we
receive a command, we will need to route it to the correct component to be
dealt with.

Similarly, we can compose multiple policies or projects to put ourselves back
in the case when we have a single policy or projection.

##  4\. Crem

The architecture we described in the Domain-Driven Design section could be
implemented as a composition of state machines. Aggregates, policies and
projections get implemented as state machines, which then get composed into a
unique state machine which describes the whole domain of the application.

To benefit from the above described perks of both the architecture and state
machines we need a way to implement a domain with state machines which is
compositional and allows synchronising a graphical representation of the state
machines with the actual implemented code.

_Crem_ is a Haskell library for defining and executing state machines in such
a way that the theoretical benefits of state machines, as compositionality and
representability, are practically preserved.

It allows to:

  * •

Compose state machines in multiple ways.

  * •

Generate a graphical representation out of the implementation of a state
machine.

  * •

Impose invariants on the allowed transitions.

_Crem_ is based on two main ideas: tracking the set of the allowed transitions
at the type level and using a free-like structure to restore compositionality.

Let’s see how these two ideas play really well together and why both have a
relevant role in the implementation.

A simple definition of a state machine that is parametric over the type of its
state $s$, as well as input and output types $a$ and $b$, respectively, could
look like the following:

$\begin{array}[]{c@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l}\lx@intercol{\textbf{data}}~{}\mathit{Mealy}~{}s~{}a~{}b=\mathit{Mealy}\hfil\lx@intercol\\\
\quad\\{\hfil\hskip 2.84526pt&\mathit{initialState}\hfil\hskip
2.84526pt&::\hfil\hskip 2.84526pt&s\\\ \quad,\hfil\hskip
2.84526pt&\mathit{action}\hfil\hskip 2.84526pt&::\hfil\hskip 2.84526pt&s\to
a\to(b,s)\\\ \quad\\}\hfil\hskip 2.84526pt\\\ \end{array}$

By making the state type implicit, one ends up with $\mathit{Mealy}$ as is
defined in the _machines_ library (Kmett et al., 2012):333This transformation
can be perceived as two separate steps:  (1) First turn the $s$ into an
existentially quantified type variable:
$\begin{array}[]{c@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l}\lx@intercol{\textbf{data}}~{}\mathit{Mealy^{\prime}}~{}a~{}b={\textbf{forall}}~{}s.~{}\mathit{Mealy^{\prime}}\hfil\lx@intercol\\\
\quad\\{\hfil\hskip 2.84526pt&\mathit{initialState}\hfil\hskip
2.84526pt&::\hfil\hskip 2.84526pt&s\\\ \quad,\hfil\hskip
2.84526pt&\mathit{action}\hfil\hskip 2.84526pt&::\hfil\hskip 2.84526pt&s\to
a\to(b,s)\\\ \quad\\}\hfil\hskip 2.84526pt\\\ \end{array}$ (2) Then use
recursion to eliminate the state variable altogether (see
$\mathit{unfoldMealy}$ from the _machines_ library (Kmett et al., 2012)):
$\begin{array}[]{l}\mathit{unfoldMealy}::\mathit{Mealy^{\prime}}~{}a~{}b\to\mathit{Mealy}~{}a~{}b\\\
\mathit{unfoldMealy}~{}(\mathit{Mealy^{\prime}}~{}\mathit{initial}~{}\mathit{action})=\mathit{go}~{}\mathit{initial}~{}{\textbf{where}}\\\
\quad\mathit{go}~{}s=\mathit{Mealy}~{}\$~{}\backslash
a\to{\textbf{case}}~{}\mathit{action}~{}s~{}a~{}{\textbf{of}}\\\
\qquad(b,t)\to(b,\mathit{go}~{}t)\end{array}$

$\begin{array}[]{c@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l}\lx@intercol{\textbf{newtype}}~{}\mathit{Mealy}~{}a~{}b=\mathit{Mealy}\hfil\lx@intercol\\\
\quad\\{\hfil\hskip 2.84526pt&\mathit{runMealy}\hfil\hskip
2.84526pt&::\hfil\hskip 2.84526pt&a\to(b,~{}\mathit{Mealy}~{}a~{}b)\\\
\quad\\}\hfil\hskip 2.84526pt\\\ \end{array}$

This allows improving the compositionality of the data type, since now there
is no need to keep track of the state type variable, and it is possible to
implement instances for common type classes like $\mathit{Category}$,
$\mathit{Profunctor}$ and $\mathit{Arrow}$.

On the other hand, these simple implementations do not allow to extract any
information about how the state machine works, without actually executing the
state machine itself. Being just functions, the only thing we can do with them
is running them.

In particular, we have no way to extract information about which transitions
are allowed or not by the state machine, and therefore we are not able to
generate a graphical representation which describes how the machine works.

To be able to enforce which state transitions are actually allowed and to
generate a graphical representation of the state space, we need to track the
list of allowed transitions, which we call $\mathit{Topology}$.

$\begin{array}[]{c@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l}\lx@intercol{\textbf{newtype}}~{}\mathit{Topology}~{}\mathit{vertex}=\mathit{Topology}\hfil\lx@intercol\\\
\quad\\{\hfil\hskip 2.84526pt&\mathit{edges}\hfil\hskip
2.84526pt&::\hfil\hskip 2.84526pt&[(\mathit{vertex},[\mathit{vertex}])]\\\
\quad\\}\hfil\hskip 2.84526pt\\\ \end{array}$

The $\mathit{Topology}$ is a list of edges, grouped by their initial vertex.

Coming back to our example, the $\mathit{Topology}$ of the _Cart_ aggregate
could look as follows:

$\begin{array}[]{@{\hspace{0mm}}r@{\hspace{1mm}}c@{\hspace{1mm}}l}\lx@intercol{\textbf{data}}~{}\mathit{CartVertex}\hfil\lx@intercol\\\
\hskip 2.84526pt&=\hfil\hskip 2.84526pt&\mathit{WaitingForPaymentVertex}\\\
\hskip 2.84526pt&\mid\hfil\hskip 2.84526pt&\mathit{InitiatingPaymentVertex}\\\
\hskip 2.84526pt&\mid\hfil\hskip 2.84526pt&\mathit{PaymentCompleteVertex}\\\
\hskip 2.84526pt\\\
\lx@intercol\mathit{cartTopology}::\mathit{Topology}~{}\mathit{CartVertex}\hfil\lx@intercol\\\
\lx@intercol\mathit{cartTopology}=\hfil\lx@intercol\\\ \hskip
2.84526pt&[\hfil\hskip
2.84526pt&(\mathit{WaitingForPaymentVertex},[\mathit{InitiatingPaymentVertex}])\\\
\hskip 2.84526pt&,\hfil\hskip
2.84526pt&(\mathit{InitiatingPaymentVertex},[\mathit{PaymentCompleteVertex}]\\\
\hskip 2.84526pt&,\hfil\hskip
2.84526pt&[\mathit{PaymentCompleteVertex},[]])\\\ \hskip
2.84526pt&]\hfil\hskip 2.84526pt&\\\ \end{array}$

By storing the $\mathit{Topology}$ at the type level we are able to use it for
enforcing at compile time that forbidden transitions are never executed.
Having an explicit $\mathit{Topology}$ allows to retrieve the information
later on to create a graphical representation of the state machine out of it.
In this way, we are sure that the generated graphical representation is always
in sync with the implemented logic of the state machine.

One possible way to implement such a mechanism is depicted in Figure 3.

$\begin{array}[]{l}{\textbf{data}}~{}\mathit{InitialState}~{}(\mathit{state}::\mathit{vertex}\to\mathit{Type})~{}{\textbf{where}}\\\
\quad\mathit{InitialState}::\mathit{state}~{}\mathit{vertex}\to\mathit{InitialState}~{}\mathit{state}\\\\[5.69054pt]
{\textbf{data}}~{}\mathit{ActionResult}\\\
\qquad(\mathit{topology}::\mathit{Topology}~{}\mathit{vertex})\\\
\qquad(\mathit{state}::\mathit{vertex}\to\mathit{Type})\\\
\qquad(\mathit{initialVertex}::\mathit{vertex})\\\ \qquad\mathit{output}\\\
\quad{\textbf{where}}\\\ \quad\mathit{ActionResult}\\\
\qquad::\mathit{AllowedTransition}~{}\mathit{topology}~{}\mathit{initialVertex}~{}\mathit{finalVertex}\\\
\qquad\Rightarrow(\mathit{output},\mathit{state}~{}\mathit{finalVertex})\\\
\qquad\to\mathit{ActionResult}~{}\mathit{topology}~{}\mathit{state}~{}\mathit{initialVertex}~{}\mathit{output}\\\\[5.69054pt]
{\textbf{data}}~{}\mathit{BaseMachine}\\\
\qquad(\mathit{topology}::\mathit{Topology}~{}\mathit{vertex})\\\
\qquad\mathit{input}\\\
\qquad\mathit{output}={\textbf{forall}}~{}\mathit{state}.\\\
\quad\mathit{BaseMachine}\\\
\quad\\{~{}\mathit{initialState}::\mathit{InitialState}~{}\mathit{state}\\\
\quad,~{}\mathit{action}\\\
\qquad::{\textbf{forall}}~{}\mathit{initialVertex}.\\\
\qquad\mathit{state}~{}\mathit{initialVertex}\\\ \qquad\to\mathit{input}\\\
\qquad\to\mathit{ActionResult}~{}\mathit{topology}~{}\mathit{state}~{}\mathit{initialVertex}~{}\mathit{output}\\\
\quad\\}\end{array}$ Figure 3. State Machines, Revisited

$\mathit{AllowedTransition}$ $\mathit{topology}$ $\mathit{initialVertex}$
$\mathit{finalVertex}$, which is implemented as in Figure 4, is a type class
which checks that a transition from $\mathit{initialVertex}$ to
$\mathit{finalVertex}$ is allowed by the $\mathit{topology}$. It searches
through all the edges of the $\mathit{Topology}$ whether there is one starting
from $\mathit{initialVertex}$ and ending at $\mathit{finalVertex}$, and it
constructs a proof of it using the $\mathit{AllowTransition}$ data type.

$\begin{array}[]{l}{\textbf{data}}~{}\mathit{AllowTransition}\\\
\qquad(\mathit{topology}~{}::~{}\mathit{Topology}~{}\mathit{vertex})\\\
\qquad(\mathit{initial}~{}::~{}\mathit{vertex})\\\
\qquad(\mathit{final}~{}::~{}\mathit{vertex})\\\ \quad{\textbf{where}}\\\
\quad\mathit{AllowIdentityEdge}\\\
\qquad::~{}\mathit{AllowTransition}~{}\mathit{topology}~{}\mathit{a}~{}\mathit{a}\\\
\quad\mathit{AllowFirstEdge}\\\
\qquad::~{}\mathit{AllowTransition}~{}(\prescript{\prime}{}{\mathit{Topology}}{}{}~{}(\prescript{\prime}{}{(}{}{}\mathit{a},~{}\mathit{b}~{}\prescript{\prime}{}{:}{}{}~{}\mathit{l1})~{}\prescript{\prime}{}{:}{}{}~{}\mathit{l2}))~{}\mathit{a}~{}\mathit{b}\\\
\quad\mathit{AllowAddingEdge}\\\
\qquad::~{}\mathit{AllowTransition}~{}(\prescript{\prime}{}{\mathit{Topology}}{}{}~{}(\prescript{\prime}{}{(}{}{}\mathit{a},~{}\mathit{l1})~{}\prescript{\prime}{}{:}{}{}~{}\mathit{l2}))~{}\mathit{a}~{}\mathit{b}\\\
\qquad\to~{}\mathit{AllowTransition}~{}(\prescript{\prime}{}{\mathit{Topology}}{}{}~{}(\prescript{\prime}{}{(}{}{}\mathit{a},~{}\mathit{x}~{}\prescript{\prime}{}{:}{}{}~{}\mathit{l1})~{}\prescript{\prime}{}{:}{}{}~{}\mathit{l2}))~{}\mathit{a}~{}\mathit{b}\\\
\quad\mathit{AllowAddingVertex}\\\
\qquad::~{}\mathit{AllowTransition}~{}(\prescript{\prime}{}{\mathit{Topology}}{}{}~{}\mathit{topology})~{}\mathit{a}~{}\mathit{b}\\\
\qquad\to~{}\mathit{AllowTransition}~{}(\prescript{\prime}{}{Topology}{}{}~{}(\mathit{x}~{}\prescript{\prime}{}{:}{}{}~{}\mathit{topology}))~{}\mathit{a}~{}\mathit{b}\end{array}$

$\begin{array}[]{l}{\textbf{class}}~{}\mathit{AllowedTransition}\\\
\qquad(\mathit{topology}~{}::~{}\mathit{Topology}~{}\mathit{vertex})\\\
\qquad(\mathit{initial}~{}::~{}\mathit{vertex})\\\
\qquad(\mathit{final}~{}::~{}\mathit{vertex})\\\ \quad{\textbf{where}}\\\
\quad\mathit{allowsTransition}~{}::~{}\mathit{AllowTransition}~{}\mathit{topology}~{}\mathit{initial}~{}\mathit{final}\\\
\\\ {\textbf{instance}}\\{-\\#~{}\mathit{INCOHERENT}~{}\\#-\\}\\\
\qquad\mathit{AllowedTransition}~{}\mathit{topology}~{}\mathit{a}~{}\mathit{a}\\\
\quad{\textbf{where}}\\\
\quad\mathit{allowsTransition}~{}=~{}\mathit{AllowIdentityEdge}\\\ \\\
{\textbf{instance}}\\{-\\#~{}\mathit{INCOHERENT}~{}\\#-\\}\\\
\qquad\mathit{AllowedTransition}~{}(\prescript{\prime}{}{\mathit{Topology}}{}{}~{}(\prescript{\prime}{}{(}{}{}\mathit{a},~{}\mathit{b}~{}\prescript{\prime}{}{:}{}{}~{}\mathit{l1})~{}\prescript{\prime}{}{:}{}{}~{}\mathit{l2}))~{}\mathit{a}~{}\mathit{b}\\\
\quad{\textbf{where}}\\\
\quad\mathit{allowsTransition}~{}=~{}\mathit{AllowFirstEdge}\\\ \\\
{\textbf{instance}}\\{-\\#~{}\mathit{INCOHERENT}~{}\\#-\\}\\\
\qquad\mathit{AllowedTransition}~{}(\prescript{\prime}{}{\mathit{Topology}}{}{}~{}(\prescript{\prime}{}{(}{}{}\mathit{a},~{}\mathit{l1})~{}\prescript{\prime}{}{:}{}{}~{}\mathit{l2}))~{}\mathit{a}~{}\mathit{b})~{}\Rightarrow\\\
\qquad\mathit{AllowedTransition}~{}(\prescript{\prime}{}{\mathit{Topology}}{}{}~{}(\prescript{\prime}{}{(}{}{}\mathit{a},~{}\mathit{x}~{}\prescript{\prime}{}{:}{}{}~{}\mathit{l1})~{}\prescript{\prime}{}{:}{}{}~{}\mathit{l2}))~{}\mathit{a}~{}\mathit{b}\\\
\quad{\textbf{where}}\\\
\quad\mathit{allowsTransition}~{}=~{}\mathit{AllowAddingEdge}~{}\mathit{allowsTransition}\\\
\\\ {\textbf{instance}}\\{-\\#~{}\mathit{INCOHERENT}~{}\\#-\\}\\\
\qquad\mathit{AllowedTransition}~{}(\prescript{\prime}{}{\mathit{Topology}}{}{}~{}\mathit{topology})~{}\mathit{a}~{}\mathit{b}~{}\Rightarrow\\\
\qquad\mathit{AllowedTransition}~{}(\prescript{\prime}{}{Topology}{}{}~{}(\mathit{x}~{}\prescript{\prime}{}{:}{}{}~{}\mathit{topology}))~{}\mathit{a}~{}\mathit{b}\\\
\quad{\textbf{where}}\\\
\quad\mathit{allowsTransition}~{}=~{}\mathit{AllowAddingVertex}~{}\mathit{allowsTransition}\\\
\end{array}$

Figure 4. $\mathit{AllowedTransition}$ implementation

The $\mathit{InitialState}$ and $\mathit{ActionResult}$ data types are
respectively ways to store a $\mathit{state}$ and a pair of a $\mathit{state}$
and an $\mathit{output}$, given the fact that the state does not have kind
$\mathit{Type}$ but kind $\mathit{vertex}\to\mathit{Type}$.

With these new data types, the _Cart_ aggregate could be adjusted accordingly.
The updated implementation is shown in Figure 5.

$\begin{array}[]{c@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l}\lx@intercol{\textbf{data}}~{}\mathit{CartState}~{}(\mathit{cartVertex}~{}::~{}\mathit{CartVertex})~{}{\textbf{where}}\hfil\lx@intercol\\\
\hfil\hskip 2.84526pt&\mathit{WaitingForPayment}\hfil\hskip
2.84526pt&::\hfil\hskip
2.84526pt&\mathit{CartState}~{}\mathit{WaitingForPaymentVertex}\\\ \hfil\hskip
2.84526pt&\mathit{InitiatingPayment}\hfil\hskip 2.84526pt&::\hfil\hskip
2.84526pt&\mathit{CartState}~{}\mathit{InitiatingPaymentVertex}\\\ \hfil\hskip
2.84526pt&\mathit{PaymentComplete}\hfil\hskip 2.84526pt&::\hfil\hskip
2.84526pt&\mathit{CartState}~{}\mathit{PaymentCompleteVertex}\\\ \end{array}$

$\begin{array}[]{@{\hspace{0mm}}r@{\hspace{1mm}}c@{\hspace{1mm}}l@{\hspace{1mm}}l}\lx@intercol\mathit{cart}::\mathit{BaseMachine}~{}\mathit{CartTopology}~{}\mathit{CartCommand}~{}[\mathit{CartEvent}]\hfil\lx@intercol\\\
\lx@intercol\mathit{cart}=\mathit{BaseMachine}\hfil\lx@intercol\\\ \hskip
2.84526pt&\\{\hfil\hskip
2.84526pt&\mathit{initialState}=\mathit{InitialState}~{}\mathit{WaitingForPayment}\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&,\hfil\hskip
2.84526pt&\mathit{action}=\backslash{\textbf{case}}\hfil\hskip 2.84526pt\\\
\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
2.84526pt\mathit{WaitingForPayment}~{}\mathit{PayCart}\to\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
8.53581pt\mathit{ActionResult}~{}([\mathit{CartPaymentInitiated}],\mathit{InitiatingPayment})\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
2.84526pt\mathit{WaitingForPayment}~{}\mathit{MarkCartAsPaid}\to\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
8.53581pt\mathit{ActionResult}~{}([],\mathit{WaitingForPayment})\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
2.84526pt\mathit{InitiatingPayment}~{}\mathit{PayCart}\to\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
8.53581pt\mathit{ActionResult}~{}([],\mathit{InitiatingPayment})\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
2.84526pt\mathit{InitiatingPayment}~{}\mathit{MarkCartAsPaid}\to\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
8.53581pt\mathit{ActionResult}~{}([\mathit{CartPaymentCompleted}],\mathit{PaymentComplete})\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
2.84526pt\mathit{PaymentComplete}~{}\mathit{PayCart}\to\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
8.53581pt\mathit{ActionResult}~{}([],\mathit{PaymentComplete})\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
2.84526pt\mathit{PaymentComplete}~{}\mathit{MarkCartAsPaid}\to\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\hfil\hskip 2.84526pt&\hskip
8.53581pt\mathit{ActionResult}~{}([],\mathit{PaymentComplete})\hfil\hskip
2.84526pt\\\ \hskip 2.84526pt&\\}\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt\\\ \end{array}$

Figure 5. Cart Implementation, Revisited

Even though the implementation looks completely analogous to the previous
version using the $\mathit{Mealy}$ data type, we are now ensuring at compile
time that the machine will never use a transition which is not allowed by the
$\mathit{Topology}$.

The $\mathit{BaseMachine}$ data type allows us to track at the type level the
information regarding the $\mathit{Topology}$ of the machine.

On the other hand, that $\mathit{topology}$ type parameter makes composition
harder, since composing two machines would require computing at the type level
the topology of the composed machine. Moreover, just the presence of that
third type parameter does not allow us to us common type classes as
$\mathit{Category}$, $\mathit{Profunctor}$ or $\mathit{Arrow}$.

To restore compositionality, we define a free-like structure which adds
composition operations on top of the $\mathit{BaseMachine}$ data type, which
is presented in Figure 6.

$\begin{array}[]{l}{\textbf{data}}~{}\mathit{StateMachine}~{}\mathit{input}~{}\mathit{output}~{}{\textbf{where}}\\\
\quad\mathit{Basic}\\\
\qquad::{\textbf{forall}}~{}m~{}\mathit{vertex}~{}\mathit{topology}~{}\mathit{input}~{}\mathit{output}.\\\
\qquad\quad(~{}\mathit{Demote}~{}\mathit{vertex}\sim\mathit{vertex}\\\
\qquad\quad,~{}\mathit{SingKind}~{}\mathit{vertex}\\\
\qquad\quad,~{}\mathit{SingI}~{}\mathit{topology}\\\ \qquad\quad)\\\
\qquad\Rightarrow\mathit{BaseMachine}~{}\mathit{topology}~{}\mathit{input}~{}\mathit{output}\\\
\qquad\to\mathit{StateMachine}~{}\mathit{input}~{}\mathit{output}\\\
\quad\mathit{Sequential}\\\ \qquad::\mathit{StateMachine}~{}a~{}b\\\
\qquad\to\mathit{StateMachine}~{}b~{}c\\\
\qquad\to\mathit{StateMachine}~{}a~{}c\\\ \quad\mathit{Parallel}\\\
\qquad::\mathit{StateMachine}~{}a~{}b\\\
\qquad\to\mathit{StateMachine}~{}c~{}d\\\
\qquad\to\mathit{StateMachine}~{}(a,c)~{}(b,d)\\\ \quad\mathit{Alternative}\\\
\qquad::\mathit{StateMachine}~{}a~{}b\\\
\qquad\to\mathit{StateMachine}~{}c~{}d\\\
\qquad\to\mathit{StateMachine}~{}(\mathit{Either}~{}a~{}c)~{}(\mathit{Either}~{}b~{}d)\\\
\quad\mathit{Feedback}\\\
\qquad::\mathit{StateMachine}~{}\mathit{a}~{}[\mathit{b}]\\\
\qquad\to\mathit{StateMachine}~{}\mathit{b}~{}[\mathit{a}]\\\
\qquad\to\mathit{StateMachine}~{}\mathit{a}~{}[\mathit{b}]\\\
\quad\mathit{Kleisli}\\\
\qquad::\mathit{StateMachine}~{}\mathit{a}~{}[\mathit{b}]\\\
\qquad\to\mathit{StateMachine}~{}\mathit{b}~{}[\mathit{c}]\\\
\qquad\to\mathit{StateMachine}~{}\mathit{a}~{}[\mathit{c}]\\\ \end{array}$
Figure 6. State Machine Representation

This way, it becomes trivial to implement type classes like
$\mathit{Category}$, $\mathit{Strong}$ and $\mathit{Choice}$, in terms of the
constructors.

The $\mathit{Sequential}$ constructor allows restoring sequential categorical
composition. The $\mathit{Parallel}$ allows implementing $\mathit{Arrow}$ and
$\mathit{Strong}$, while the $\mathit{Alternative}$ constructor allows
implementing $\mathit{ArrowChoice}$ and $\mathit{Choice}$.

The $\mathit{Feedback}$ constructor is used to loop two state machines,
respectively feeding the output of one as input of the other.

The $\mathit{Kleisli}$ constructor allows composing sequentially two state
machines which produce multiple outputs, while they process single inputs.

The $\mathit{StateMachine}$ data type helps us construct an abstract syntax
tree where the leaves are $\mathit{BaseMachine}$s and the other nodes describe
how we are composing the subtrees.

Considering our running example, if we suppose now to have implemented the
_Cart_ aggregate, the _PaymentGateway_ policy and the _PaymentStatus_
projection, like so

$\begin{array}[]{@{\hspace{0mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{\hspace{0mm}}}\mathit{cart}\hfil\hskip
2.84526pt&::\hfil\hskip
2.84526pt&\mathit{StateMachine}~{}\mathit{CartCommand}~{}[\mathit{CartEvent}]\\\
\mathit{paymentGateway}\hfil\hskip 2.84526pt&::\hfil\hskip
2.84526pt&\mathit{StateMachine}~{}\mathit{CartEvent}~{}[\mathit{CartCommand}]\\\
\mathit{paymentStatus}\hfil\hskip 2.84526pt&::\hfil\hskip
2.84526pt&\mathit{StateMachine}~{}\mathit{CartEvent}~{}[\mathit{CartView}]\\\
\end{array}$

we can compose them together to create an implementation for the whole domain:

$\begin{array}[]{l}\mathit{wholeCartDomain}::\mathit{StateMachine}~{}\mathit{CartCommand}~{}[\mathit{CartView}]\\\
\mathit{wholeCartDomain}=\mathit{Kleisli}\\\
\quad(\mathit{Feedback}~{}\mathit{cart}~{}\mathit{paymentGateway})\\\
\quad\mathit{paymentStatus}\\\ \end{array}$

A whole implementation could be found in the _examples_ folder inside the
_Crem_ repository (Perone, 2023).

From this definition, _Crem_ is able to generate a diagram that shows how the
application is structured, presented in Figure 7.

Figure 7. Architecture diagram of the cart payment system

From the picture, it’s easy to understand how the _cart_ aggregate is
connected in a loop with the _paymentGateway_ policy and how the outputs of
the loop are then fed as inputs into the _cartState_ projection.

Inside every box we can also see the topology of the state space of the state
machine controlling that specific component.

When we interpret the $\mathit{StateMachine}$ abstract syntax tree, we need to
define how to process the leaves, i.e. the $\mathit{BaseMachine}$s, and how to
interpret the composition of substrees.

For example, when we want to run a $\mathit{StateMachine}$, we need to
describe how to run a $\mathit{BaseMachine}$, and this is provided by the
$\mathit{action}$ included in the $\mathit{BaseMachine}$ definition, and how
to run a composition of sub-$\mathit{StateMachine}$s. This depends on the
specific constructor; for example, for the $\mathit{Sequential}$ constructor,
we first recursively run the first $\mathit{StateMachine}$, and we use the
output as input to run the second $\mathit{StateMachine}$.

Similarly, when we want to create a graphical representation of a
$\mathit{StateMachine}$, we need to be able first to create a graphical
representation of its leaves, which are $\mathit{BaseMachine}$s. We are able
to do that because we have the $\mathit{Topology}$ information stored at the
type level. Then, we also need to be able to create a graphical representation
of a composed $\mathit{StateMachine}$ given a graphical representation of its
sub-$\mathit{StateMachine}$s. Depending on the used constructor, and on the
graphical representation that we would like to obtain, we can decide how to
represent the composed machine.

##  5\. Extending the architecture

In real-life projects an application is rarely composed by only one aggregate,
one policy, and one projection. To understand how we can compose multiple
aggregates, policies and projections together to model more complex workflows,
we can use the interface provided by $\mathit{Arrow}$ and
$\mathit{ArrowChoice}$, or, alternatively, the $\mathit{Profunctor}$,
$\mathit{Strong}$, and $\mathit{Choice}$ type classes. Effectively, this means
that the composition does not depend on our use of state machines; composition
using another data type satisfying these type classes would also work in
pretty much the same way.

Let’s continue with our running example and consider that we would like to
automatically start the delivery process once a payment is completed. As a
first step, we introduce a new aggregate that we implement as a “Basic” state
machine:

$\begin{array}[]{@{\hspace{0mm}}l}{\textbf{data}}~{}\mathit{ShippingCommand}=\ldots\\\
\\\ {\textbf{data}}~{}\mathit{ShippingEvent}=\ldots\\\ \\\
\mathit{shipping}::\mathit{StateMachine}~{}\mathit{ShippingCommand}~{}[\mathit{ShippingEvent}]\\\
\mathit{shipping}=\mathit{Basic}\ldots\\\ \end{array}$

To connect this new aggregate with the rest of the application, we want to
execute it as an alternative to the current write model, meaning that we want
to handle either a _CartCommand_ or a _ShippingCommand_ and route it to the
appropriate machine. We can achieve this using the
($\mathbin{+\mkern-5.0mu+\mkern-5.0mu+}$) operator from $\mathit{ArrowChoice}$
(or, equivalently, $\mathit{splitChoice}$ from the $\mathit{Choice}$ type
class).

$\begin{array}[]{l}\mathit{writeModelWithShipping}::\mathit{StateMachine}\\\
\quad(\mathit{Either}~{}\mathit{CartCommand}~{}\mathit{ShippingCommand})\\\
\quad[\mathit{Either}~{}\mathit{CartEvent}~{}\mathit{ShippingEvent}]\\\
\mathit{writeModelWithShipping}=\mathit{rmap}\\\
\quad(\mathit{fmap}~{}\mathit{Left}\mathbin{|\mkern 0.0mu|\mkern
0.0mu|}\mathit{fmap}~{}\mathit{Right})\\\
\quad(\mathit{writeModel}\mathbin{+\mkern-5.0mu+\mkern-5.0mu+}\mathit{shipping})\\\
\end{array}$

Now we have a way to process both commands concerning the cart payment and the
shipping, but there is still no automatic connection between the two
components. We would like to connect them by specifying that whenever a
payment is completed the shipping process must start. The word _“whenever”_
indicates that we need to use a policy, specifically one that consumes
_CartEvent_ s and produces _ShippingCommand_ s.

$\begin{array}[]{l@{\hspace{1mm}}c@{\hspace{1mm}}l}\lx@intercol\mathit{paymentCompletePolicy}\hfil\lx@intercol\\\
\lx@intercol\quad::\mathit{StateMachine}~{}\mathit{CartEvent}~{}[\mathit{ShippingCommand}]\hfil\lx@intercol\\\
\lx@intercol\mathit{paymentCompletePolicy}=\mathit{stateless}~{}\$~{}\backslash{\textbf{case}}\hfil\lx@intercol\\\
\quad\mathit{CartPaymentInitiated}\hfil\hskip 2.84526pt&\to\hfil\hskip
2.84526pt&[]\\\ \quad\mathit{CartPaymentCompleted}\hfil\hskip
2.84526pt&\to\hfil\hskip 2.84526pt&[\mathit{StartShipping}]\\\ \end{array}$

We now need to connect our new _paymentCompletePolicy_ policy to our
$\mathit{writeModelWithShipping}$ machine. Policies are always connected via
the $\mathit{Feedback}$ constructor of the $\mathit{StateMachine}$ data type.
To use it, we need to align the types by ignoring some inputs and enlarging
the return type:

$\begin{array}[]{l}\mathit{writeModelWithShipping^{\prime}}::\mathit{StateMachine}\\\
\quad(\mathit{Either}~{}\mathit{CartCommand}~{}\mathit{ShippingCommand})\\\
\quad[\mathit{Either}~{}\mathit{CartEvent}~{}\mathit{ShippingEvent}]\\\
\mathit{writeModelWithShipping^{\prime}}=\\\
\quad\mathit{Feedback}~{}\mathit{writeModelWithShipping}~{}\$\\\
\qquad\mathit{rmap}~{}(\mathit{fmap}~{}\mathit{Right})~{}\mathit{paymentCompletePolicy}\\\
\qquad\quad\mathbin{|\mkern 0.0mu|\mkern
0.0mu|}~{}\mathit{stateless}~{}(\mathit{const}~{}[])\\\ \end{array}$

Next, we need another projection to provide the user with some queryable
information about the status of the shipping. It is a process which consumes
_ShippingEvent_ s and produces some new _ShippingInfo_ value:

$\mathit{shippingInfo}::\mathit{StateMachine}~{}\mathit{ShippingEvent}~{}[\mathit{ShippingInfo}]$

The only thing that remains to be done is connecting the machine
($\mathit{writeModelWithShipping^{\prime}}$) and the two projections
(_paymentStatus_ and _shippingInfo_). We first pair up the projections to set
up our read model and then we link it to our write model in a sequential
fashion:

$\begin{array}[]{l}\mathit{readModel}::\mathit{StateMachine}\\\
\quad(\mathit{Either}~{}\mathit{CartEvent}~{}\mathit{ShippingEvent})\\\
\quad[\mathit{Either}~{}\mathit{CartView}~{}\mathit{ShippingInfo}]\\\
\mathit{readModel}=\mathit{rmap}\\\
\quad(\mathit{fmap}~{}\mathit{Left}~{}\mathbin{|\mkern 0.0mu|\mkern
0.0mu|}~{}\mathit{fmap}~{}\mathit{Right})\\\
\quad(\mathit{paymentStatus}\mathbin{+\mkern-5.0mu+\mkern-5.0mu+}\mathit{shippingInfo})\\\
\\\ \mathit{cartAndShipping}::\mathit{StateMachine}\\\
\quad(\mathit{Either}~{}\mathit{CartCommand}~{}\mathit{ShippingCommand})\\\
\quad[\mathit{Either}~{}\mathit{CartView}~{}\mathit{ShippingInfo}]\\\
\mathit{cartAndShipping}=\\\
\quad\mathit{Kleisli}~{}\mathit{writeModelWithShipping^{\prime}}~{}\mathit{readModel}\\\
\end{array}$

##  6\. Future work

Some possible directions for future work on the subject could be:

  * •

The $\mathit{Feedback}$ constructor of the $\mathit{StateMachine}$ data type
is used to implement looping behaviour. Classically, such behaviour is
implemented in terms of the $\mathit{ArrowLoop}$ or $\mathit{Costrong}$ type
classes. It would be interesting to investigate the relation between
$\mathit{Feedback}$ and such type classes, potentially removing the
$\mathit{Feedback}$ constructor from the $\mathit{StateMachine}$ data type and
replacing it with a constructor more similar to the $\mathit{loop}$ or
$\mathit{unfirst}$ functions coming from the aforementioned type classes.

  * •

The $\mathit{Sequential}$ and $\mathit{Kleisli}$ constructors both deal with
sequential composition of state machines. It would be interesting to find a
way to unify them.

  * •

With the current implementation, we are tracking at the type level only a list
of the allowed state transitions. There is no connection between the allowed
transitions and the inputs which trigger them. In other words, we are not
restricting in any way the inputs that we could receive in a given state. It
would be interesting to implement a way to express that in a certain state
only certain inputs are valid.

This would allow stating explicitly which are the expected inputs in a given
state when implementing a state machine, avoiding the need to implement error
handling for such unwanted cases.

  * •

The current implementation of _Crem_ does not take advantage of any
concurrency or parallelism. In cases where a state machine is actually
composed of multiple sub-machines in parallel, it could be interesting to
allow running them on separate threads to improve the execution time.

  * •

In the spirit of parallelising as much as possible a given machine, or anyway
optimizing it in other ways, it could make sense to introduce an optimization
step which would restructure the abstract syntax tree which constitutes a
$\mathit{StateMachine}$. Simple optimizations could be given by the algebraic
structure provided by the categorial structure; for example any identity
machine composed sequentially could be removed; or it would be possible to use
the distributive law between sequential and parallel composition to improve
the parallelisability of a machine.

Another potential area of future development concerns how to test systems
built with _Crem_ and/or with the architecture described in the _Domain-Driven
Design_ section.

Some potential aspects to investigate in that area could be:

  * •

Using a compositional library like _Crem_ , the Domain-Driven Design
architecture described above could be implemented as a single state machine
receiving commands as inputs and emitting views as outputs.

One way to test such a system would be to proceed with unit testing, treating
the whole domain as a unit, feeding commands to it and asserting the expected
state on the view observed by the user.

  * •

Another way to test such a system would be to use property-based testing,
generating commands randomly and making assertions on the invariants of the
views.

A potential direction on investigation could be using something like linear
temporal logic to provide a language to express system invariants, along the
lines to what has been done with Quickstrom (O’Connor and Wickström, 2022).

  * •

Pushing it even further, we can notice that our domain and the user (in fact,
any external system interacting with our system) together form a cycle.
Therefore, if we implement our user as a state machine (potentially an
effectful or probabilistic one) receiving views and producing commands, we
could close the loop and let our application run as long as we like. At this
point we could use this new complete system to test the invariants of the
domain.

  * •

Another way in which such a system could potentially be tested would be to use
languages like TLA+ or Alloy. A model could be exported using the information
stored in the topology of the machine. Then it could be tested and verified
using the chosen specification language.

##  7\. Conclusion

We believe that compositionality and representability constitutes two
extremely important aspects for the success of a software architecture. The
former because it allows tackling simpler problems and then composing back
their solutions to obtain solutions for more complex problems. The latter
because it allows an easier interaction between business and domain experts
and software developers.

Crem makes it easy to keep the graphical representation synchronised with the
implementation, providing a reliable source of graphical documentation.

Inspired by Domain-Driven Design and thanks to the Haskell type system we were
able to create the _Crem_ library, which allows architecting systems in a
composable and representable way, without sacrificing the developer experience
while implementing such systems.

Moreover, the architecture we propose helps to clarify the role of the various
components commonly used in a Domain-Driven Design architecture, describing
more precisely which is their role inside the domain.

###### Acknowledgements.

We would like to thank the reviewers of FUNARCH ’23 for their constructive
comments, and especially Michael Sperber for shepherding the editing process;
our paper is all the better for their thorough feedback and suggestions. The
initial development of the _Crem_ library happened while both authors were
employed by Tweag. The first author would also like to thank his former
colleagues Richard Eisenberg, Alexis King, Sjoerd Visscher, Alexander Esgen,
Nicolas Frisby and Daniele Palombi for the fruitful discussions and the
feedback on the _Crem_ library. Moreover, he would like to thank his former
colleague Alexei Drake for the fruitful collaboration in setting up a
development environment for _Crem_ using _Nix_.

## References

  * (1)
  * Brandolini (2015) Alberto Brandolini. 2015\.  _Introducing EventStorming_.  Leanpub, 1321 Blanshard Street, Suite 301, Victoria, British Columbia, Canada, V8W 0B6.
  * Evans (2003) Eric Evans. 2003\.  _Domain-Driven Design_.  Addison-Wesley, Reading, MA.
  * Kmett et al. (2012) Edward A. Kmett, Rúnar Bjarnason, and Josh Cough. 2012\.  machines: Networked stream transducers.  https://hackage.haskell.org/package/machines
  * Mealy (1955) George H. Mealy. 1955\.  A Method for Synthesizing Sequential Circuits.  _Bell System Technical Journal_ 34, 5 (1955), 1045–1079.
  * O’Connor and Wickström (2022) Liam O’Connor and Oskar Wickström. 2022.  Quickstrom: property-based acceptance testing with LTL specifications.  _PLDI 2022: Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation_ (2022), 1025–1038.
  * Perone (2023) Marco Perone. 2023\.  A Cart example with Crem.  https://github.com/marcosh/crem/tree/main/examples/Crem/Example/Cart
  * Ploch (2022) Thomas Ploch. 2022\.  DDD Aggregates: Processes, State Machines and Transducers.  https://t-pl.io/ddd-aggregates-processes-state-machines-and-transducers
  * Stopford (2018) Ben Stopford. 2018\.  _Designing Event-Driven Systems_.  O’Reilly, 1005 Gravenstein Highway North, Sebastopol, CA 95472.
  * Verraes (2021) Mathias Verraes. 2021\.  What is Domain-Driven Design.  https://verraes.net/2021/09/what-is-domain-driven-design-ddd/
  * Wickström (2019) Oskar Wickström. 2019\.  motor: Type-safe effectful state machines in Haskell.  https://hackage.haskell.org/package/motor
  * Young (2007) Greg Young. 2007\.  The Architecture of a Large Transaction System.  https://www.infoq.com/interviews/Architecture-Eric-Evans-Interviews-Greg-Young/
  * Young (2010) Greg Young. 2010\.  CQRS Documents.  https://cqrs.files.wordpress.com/2010/11/cqrs_documents.pdf


* [11] Z.A. Wang, M. Winkler, D. Wrzosek, Global regularity versus infinite-time singularity formation in a chemotaxis model with volume-filling effect and degenerate diffusion, SIAM Journal on Mathematical Analysis. 44(5), 3502-3525, 2012.
  * [12] Y. Tao, M. Winkler, A chemotaxis-haptotaxis model: the roles of nonlinear diffusion and logistic source, SIAM Journal on Mathematical Analysis. 43(2), 685-704, 2011.
  * [13] Y. Tao, M. Winkler, Large time behavior in a multidimensional chemotaxis-haptotaxis model with slow signal diffusion, SIAM Journal on Mathematical Analysis. 47(6), 4229-4250, 2015.
  * [14] A. Chakraborty, M. Singh, D. Lucy, et al., Predator-prey model with prey-taxis and diffusion, Mathematical and computer modelling. 46(3-4), 482-498, 2007.
  * [15] S.N. Wu, J.P. Shi, B.Y. Wu, Global existence of solutions and uniform persistence of a diffusive predator-prey model with prey-taxis, Journal of Differential Equations. 260(7), 5847-5874, 2016.
  * [16] B.E. Ainseba, M. Bendahmane, A. Noussair, A reaction-diffusion system modeling predator-prey with prey-taxis, Nonlinear Analysis: Real World Applications. 9(5), 2086-2105, 2008.
  * [17] J.P. Wang, M.X. Wang, The diffusive Beddington-DeAngelis predator-prey model with nonlinear prey-taxis and free boundary, Mathematical Methods in the Applied Sciences. 41(16), 6741-6762, 2018.
  * [18] H.H. Qiu, S.J. Guo, S.Z. Li, Stability and bifurcation in a predator-prey system with prey-taxis, International Journal of Bifurcation and Chaos. 30(02), 2050022, 2020.
  * [19] J.I. Tello, D. Wrzosek, Predator-prey model with diffusion and indirect prey-taxis, Mathematical Models and Methods in Applied Sciences. 26(11), 2129-2162, 2016.
  * [20] Y.V. Tyutyunov, L.I. Titova, I.N. Senina, Prey-taxis destabilizes homogeneous stationary state in spatial Gause-Kolmogorov-type model for predator-prey system, Ecological Complexity. 31, 170-180, 2017.
  * [21] J.P. Wang, M.X. Wang, The dynamics of a predator-prey model with diffusion and indirect prey-taxis, Journal of Dynamics and Differential Equations. 32(3), 1291-1310, 2020.
  * [22] Y. Lou, X.Q. Zhao, P. Zhou, Global dynamics of a Lotka-Volterra competition-diffusion-advection system in heterogeneous environments, Journal de Mathématiques Pures et Appliquées. 121, 47-82, 2019.
  * [23] D. Tang, P. Zhou, On a Lotka-Volterra competition-diffusion-advection system: Homogeneity vs heterogeneity, Journal of Differential Equations. 268(4), 1570-1599, 2020.
  * [24] S.S. Chen, Y. Lou, J.J. Wei, Hopf bifurcation in a delayed reaction-diffusion-advection population model, Journal of Differential Equations. 264(8), 5333-5359, 2018.
  * [25] S.S. Chen, J.J. Wei, X. Zhang, Bifurcation analysis for a delayed diffusive logistic population model in the advective heterogeneous environment, Journal of Dynamics and Differential Equations. 32(2), 823-847, 2020.
  * [26] J.P. Shi, C.C. Wang, H. Wang, Diffusive spatial movement with memory and maturation delays, Nonlinearity. 32(9), 3188, 2019.
  * [27] Y.L. Song, S.H. Wu, H. Wang, Spatiotemporal dynamics in the single population model with memory-based diffusion and nonlocal effect, Journal of Differential Equations. 267(11), 6316-6351, 2019.
  * [28] Y.L. Song, S.H. Wu, H. Wang, Memory-based movement with spatiotemporal distributed delays in diffusion and reaction, Applied Mathematics and Computation. 404, 126254, 2021.
  * [29] Y.L. Song, J.P. Shi, H. Wang, Spatiotemporal dynamics of a diffusive consumer-resource model with explicit spatial memory, Studies in Applied Mathematics. 2021.
  * [30] Y.L. Song, Y.H. Peng, T.H. Zhang, The spatially inhomogeneous Hopf bifurcation induced by memory delay in a memory-based diffusion system, Journal of Differential Equations. 300(5), 597-624, 2021.
  * [31] P. Ghosh, S. Sen, D.S. Ray, Reaction-cattaneo systems with fluctuating relaxation time, Physical Review E. 81(2), 026205, 2010.
  * [32] P. Ghosh, Control of the Hopf-Turing transition by time-delayed global feedback in a reaction-diffusion system, Physical Review E. 84(1), 016222, 2011.
  * [33] Y.H. Lv, Z.H. Liu, Turing-Hopf bifurcation analysis and normal form of a diffusive Brusselator model with gene expression time delay, Chaos, Solitons and Fractals. 152, 111478, 2021.
  * [34] X.D. Li, J.D. Cao, Delay-dependent stability of neural networks of neutral type with time delay in the leakage term, Nonlinearity. 23(7), 1709, 2010.
  * [35] M. Kot, Elements of Mathematical Ecology, Cambridge University Press, Cambridge, 2001.
  * [36] N. Mcdonald, Time Lags in Biological Models, Springer-Verlag, Berlin, 1978.
  * [37] H.L. Smith, An Introduction to Delay Differential Equations with Applications to the Life Sciences, Springer-Verlag, New York, 2011.
  * [38] T. Faria, Normal forms and Hopf bifurcation for partial differential equations with delays, Transactions of the American Mathematical Society. 352(5), 2217-2238, 2000.
  * [39] T. Faria, L.T. Magalh$\tilde{a}$es, Normal forms for retarded functional differential equations with parameters and applications to Hopf bifurcation, Journal of Differential Equations. 122(2), 181-200, 1995.
  * [40] S.N. Chow, J.K. Hale, Methods of Bifurcation Theory, Springer-Verlag, New York, 1982.
  * [41] H.B. Shi, Y. Li, Global asymptotic stability of a diffusive predator-prey model with ratio-dependent functional response, Applied Mathematics and Computation. 250, 71-77, 2015.


# Disarranged Zone Learning (DZL): An unsupervised and dynamic automatic
stenosis recognition methodology based on coronary angiography

Yanan Dai111The authors contributed equally to this work. School of
Management, Fudan University. No.220 Handan Road, Shanghai, China  Pengxiong
Zhu222The authors contributed equally to this work. Department of Cardiac
Surgery, Shanghai East Hospital, Tongji University. No.150, Jimo Road,
Shanghai, China  Bangde Xue  Department of Cardiac Surgery, Shanghai East
Hospital, Tongji University. No.150, Jimo Road, Shanghai, China  Yun Ling
Department of Cardiac Surgery, Shanghai East Hospital, Tongji University.
No.150, Jimo Road, Shanghai, China  Xibao Shi  Department of Cardiovascular
Medicine, Ruijin Hospital, Shanghai Jiao Tong University School of Medicine.
No.197, Ruijin er Road, Shanghai, China  Liang Geng  Department of Cardiology,
Shanghai East Hospital, Tongji University. No.150, Jimo Road, Shanghai, China
Qi Zhang  Department of Cardiology, Shanghai East Hospital, Tongji University.
No.150, Jimo Road, Shanghai, China  Jun Liu  Department of Cardiac Surgery,
Shanghai East Hospital, Tongji University. No.150, Jimo Road, Shanghai, China

###### Abstract

We proposed a novel unsupervised methodology named Disarranged Zone Learning
(DZL) to automatically recognize stenosis in coronary angiography. The
methodology firstly disarranges the frames in a video, secondly it generates
an effective zone and lastly trains an encoder-decoder GRU model to learn the
capability to recover disarranged frames. The breakthrough of our study is to
discover and validate the Sequence Intensity (Recover Difficulty) is a measure
of Coronary Artery Stenosis Status. Hence, the prediction accuracy of DZL is
used as an approximator of coronary stenosis indicator. DZL is an unsupervised
methodology and no label engineering effort is needed, the sub GRU model in
DZL works as a self-supervised approach. So DZL could theoretically utilize
infinitely huge amounts of coronary angiographies to learn and improve
performance without laborious data labeling. There is no data preprocessing
precondition to run DZL as it dynamically utilizes the whole video, hence it
is easy to be implemented and generalized to overcome the data heterogeneity
of coronary angiography. The overall average precision score achieves 0.93,
AUC achieves 0.8 for this pure methodology. The highest segmented average
precision score is 0.98 and the highest segmented AUC is 0.87 for coronary
occlusion indicator. Finally, we developed a software demo to implement DZL
methodology.

###### keywords:

Disarranged Zone Learning, Unsupervised Learning , Dynamic , Automatic
Stenosis Recognition, Coronary Angiography

††journal: Journal of LaTeX Templates

##  1 Introduction

Deep learning has achieved great success in computer vision, among which in
the field of medical, the first application of deep learning is medical image
processing. For example, magnetic resonance images of the brain, ultrasound
images of breast nodules, CT and X-ray images of the lungs, these images
reflect the structure of organs and the attributes of lesions through
continuous groups of pictures from different angles.[Miotto et al., 2018] Each
image is a static reflection of the lesion under a certain angle. In cardiac
imaging research, deep learning is applied to the segmentation of LV and CCS
based on CMR, CT, ultrasound images and to the extraction of coronary artery
and its centerlines mainly based on CCTA. However, as far as we know,
discussion of deep learning in coronary angiography which is regarded as the
golden rule for coronary artery disease diagnostics is very limited, mainly
for two reasons:

1) Coronary angiography(CAG) is a video, which records the dynamic process of
contrast agent flowing in the blood vessel. For the part that is not able to
be developed by contrast agent, it is the location of suspected lesions. The
methodology of reflecting the lesions causes the analysis of coronary
angiography extended to the three-dimensional space, by adding the extra
dimension of time. For each lesion, adjacent images are no longer independent.
The strong dependence makes the analysis of coronary angiography be based on
the whole of the video. The correlation between adjacent images makes the
frame sequence unable to maintain Markov property, which further increases the
complexity of modeling. There are several studies of deep learning based on
coronary angiography, but they only select the certain frame from the
angiogram to do the further analysis. This is a static assessment of the
lesion and can only get anatomical feature. After all, anatomic stenosis does
not necessarily mean true ischemia. Our methodology is based on dynamic
changes in the lesion assessment, the results are from an functional point of
view. Results from functional method are more correlated with
ischemia.[Kumamaru et al., 2020]Therefore, the research difficulty of deep
learning in coronary angiography, especially in a dynamic perspective, is
higher than that in other fields while such research results are more
beneficial.

2) The annotation of medical images needs to consume huge medical resources,
especially where such annotation can only be completed by professional
doctors. Coronary angiography is a video, each has several frames, so the
annotation will consume even more. This could be the reason that the previous
studies, even based on coronary angiography, only select key frames from the
whole video to annotate and analysis. Such static methods lose the tremendous
information advantage of coronary angiography. Other related studies just use
CCTA instead of CAG and are constrained to the very small sample size probably
due to the huge consumption of labeling engineering. Our proposed methodology
is totally label-free and overcomes the laborious difficulty. Therefore it is
very easy to be implemented and generalized.

In this paper, a methodology (DZL) is originally designed to overcome the two
research bottlenecks mentioned above. Sequence Intensity is defined and used
as an indicator for evaluating the stenosis. In order to establish the link
between the two, we creatively define Reorder Difficulty to measure the
Sequence Intensity. That is to say, the stronger the Sequence Intensity is,
the easier it is to be restored after the sequence is disrupted, and the lower
the Reorder Difficulty is. Then a recurrent neural network(RNN) model is
designed to imitate human’s capability to recover the disordered frames
sequence. The model prediction accuracy is creatively used as an approximator
for Reorder Difficulty. The higher the model accuracy is, the lower Reorder
Difficulty is. Finally, the relationship between Sequence Intensity and
coronary artery stenosis status is discovered and validated via using the
approximator measure of Sequence Intensity.

To sum up, our study is the first to deliver the definition of Sequence
Intensity and Reorder Difficulty of coronary angiography, also we are the
first to approximate Reorder Difficulty using deep learning model prediction
accuracy. Last but not least, we are the first to discover and validate the
relationship between Sequence Intensity and Coronary Artery Stenosis Status.
Amazingly, the overall process even does not need any manual labeling.

We evaluate the contributions of the proposed methodology from the two major
challenges of coronary angiography data, that is, how the methodology
overcomes the difficulties in these two dimensions:

Time dependency: coronary angiography is a video, there is a strong dependence
between frames, if we use the conventional modeling method, since the lack of
Markov property and the model will be extremely complex and hard to
generalize. The novel methodology designed by this paper makes full use of the
time dependence between frames and essentially establishes the relationship
between the time dependence and the lesion status. Time dependence is no
longer a challenge to the methodology, but has become the core principle of
the methodology, which is an idea of turning waste into treasure.

Heterogeneity: coronary angiography is patient based. Coronary angiography
from different patients show different dynamic process in terms of speed,
position, vessels thickness, heart size, heart rate, spinal occlusion status
which are hard to generalize, especially in dynamic perspective. The
methodology captures the implicit relationship between the Sequence Intensity
and Coronary Artery Stenosis Status, this is a high-level intrinsic
relationship regardless of left or right dominance, proximal occlusion or
distal stenosis, size, shape and rate of heart, error from instruments etc..
Also, it is totally label-free. Hence the methodology is possible to be
generalized in various videos of different patients with strong robustness and
cross-platform migration capability.

The overall system architecture of the methodology is shown in Figure 1:

Figure 1: Overall System Architecture. The overall methodology can be divided
into three parts: disarranged, zone and learning. The disarranged part is
functional to disorder the frames of angiography segment. The zone part is
functional to generate an effective optical flow zone to capture the sequence
information of segments. The learning part is to learn how to recover the
disarranged order accordingly.

The sections are organized as follows. Section 1 is the overall introduction
of our study including background introduction and main contributions. Section
2 is the theory development. Section 3 is the methodology specification.
Section 4 is the analysis results. Section 5 is the discussion about
advantage, extension and potential of this methodology. Section 6 is the
limitations to further provide a future work direction.

##  2 Theory

In this section, we proposed the main theorem of DZL.

###### Definition 2.1

_Sequence Intensity_. It measures the correlation strength of the adjacent
frames in a video. It is defined as the cumulative counts if the true next
frame is with biggest probability regarded as the corresponding next frame
given its previous frames for all the frames.

$Tindex_{t}=\begin{cases}1&\text{\emph{t} =
$\mathop{\arg\max}\limits_{t^{\prime}}$}\frac{P{\left({F_{t^{\prime}}\left|F_{t-1},F_{t-2}...,F_{0}\right.}\right)}}{(\sum_{t^{\prime-}}P{\left({F_{t^{\prime-}}\left|F_{t-1},F_{t-2}...,F_{0}\right.}\right)})+P{\left({F_{t^{\prime}}\left|F_{t-1},F_{t-2}...,F_{0}\right.}\right)}}\\\
0&\text{Otherwise}\end{cases}$ (1)

$SequenceIntensity=\sum_{t}Tindex_{t}$ (2)

###### Definition 2.2

_Reorder Difficulty_. It measures the correlation strength of the adjacent
frames in a sequence-shuffled video. It is defined as the cumulative counts if
the shuffled next frame is with biggest probability regarded as the
corresponding next frame given its previous frames for all the frames.

$Findex_{s}=\begin{cases}1&\text{\emph{s} =
$\mathop{\arg\max}\limits_{s^{\prime}}$}\frac{P{\left({F_{s^{\prime}}\left|F_{s-1},F_{s-2}...,F_{0}\right.}\right)}}{(\sum_{s^{\prime-}}P{\left({F_{s^{\prime-}}\left|F_{s-1},F_{s-2}...,F_{0}\right.}\right)})+P{\left({F_{s^{\prime}}\left|F_{s-1},F_{s-2}...,F_{0}\right.}\right)}}\\\
0&\text{Otherwise}\end{cases}$ (3)

$ReorderDifficulty=\sum_{s}Findex_{s}$ (4)

From the above definitions, Sequence Intensity and Reorder Difficulty are two
negative correlated variables and we have the following relationship:

###### Lemma 2.1

_Complementary Order Index_.

$SequenceIntensity=T-\alpha-ReorderDifficult$ (5)

In which, T is the total frames number in a video and $\alpha$ is the counts
of the positions that are not shuffled during the random shuffling process.

###### Proof of Lemma 2.1 1

For the position $t$ that is shuffled, if $Tindex_{t}=1$, then we must have:
$Findex_{t}=0$ and vise versa. $Tindex_{t}=1$ means the true next frame
$F_{t}$ is regarded as the next frame with biggest probability while
$Findex_{s}=1$ means the shuffled next frame $F_{s}$ is regarded as the next
frame with biggest probability. The two statements is exclusive when the
position t is shuffled. For the position that is not shuffled, then we have
$Tindex_{t}=Findex_{t}$ correspondingly.

The contrast agent injection process of a normal coronary artery is a clear
time-sequential dynamic process and each frame is an evolutionary step towards
the dynamic process. The abnormal coronary artery, due to vascular stenosis or
occlusion which affects the smooth injection of contrast agent, results in the
dynamic process more blurred and not easy to be distinguished. We originally
discover the Sequence Intensity as an indicator of Coronary Artery Stenosis
Status in terms of normal/abnormal. And Theorem2.1 is established.

###### Theorm 2.1

Sequence Intensity of coronary angiography is an indicator of Coronary Artery
Stenosis Status.

Stenosis and occlusion will hinder the dynamic contrast agent injection
process and make some adjacent frames with less sequence information. Hence,
two propositions are proposed as follows:

###### Proposition 2.1

Sequence Intensity of coronary angiography is negatively correlated with
Coronary Artery Stenosis Status. The higher probability there is stenosis
with, the weaker the Sequence Intensity is.

From Lemma2.1, we have the following proposition:

###### Proposition 2.2

Reorder Difficulty of coronary angiography is positively correlated with
Coronary Artery Stenosis Status. The higher probability there is stenosis
with, the greater the Reorder Difficulty is.

##  3 Methodology

The contrast agent injection process of a normal coronary artery is a clear
time-sequential dynamic process and each frame is an evolutionary step towards
the dynamic process. The abnormal coronary artery, due to vascular stenosis or
occlusion which affects the smooth injection of contrast agent, results in the
dynamic process more blurred and not easy to be distinguished. Hence we argue
the Sequence Intensity, defined in Section 2 could be an indicator of Coronary
Artery Stenosis Status in terms of normal/abnormal. The intuition of the
methodology is illustrated in Figure 2

Figure 2: The Intuition. The sub-left figure is the illustration of a sequence
of frames from a video of normal coronary vessels. For example, the first and
third frames are exchanged and the second frame is not moved. Hence, such
disarranging cause the first and third frames labeled as 1 and the second
frame labeled as 0. For the sub-right figure, the settings are the same except
that it is an abnormal and occluded right coronary artery. We argue the normal
coronary angiography is with higher Sequence Intensity and high model
prediction accuracy. The example shows that the sub-left output-label pairs
are consistent, indicating a high model prediction accuracy. Meanwhile, the
sub-right output-label pairs are different, indicating a comparatively low
model prediction accuracy. The methodology is developed in details in the
subsequent subsections.

###  3.1 Step 1: Disarranging Sequence Order of Coronary Angiography

A coronary angiography video is composed of many frames and each frame is an
image which records development state of the vessels at a certain time when
the contrast agent is injected. We first shuffle the frames sequence of the
video. We set $\theta$, the shuffling percentage, equal to 50%. Half of the
frames in a video is shuffled while the other half is not shuffled. If the
total number of frames of the video is odd, we round the half to be shuffled.

###  3.2 Step 2: Zone Generating

We are concerned about the dynamic imaging process of blood vessels during
contrast injection. In order to overcome the difficulty of high dimension, we
use optical flow technology to extract sequence features and form an effective
zone to calculate on.

Optical flow is the instantaneous motion speed of the pixels of a spatially
moving object in the observed imaging plan. Optical flow uses the change of
pixels in the image sequence in the time domain and the correlation between
adjacent frames to find the corresponding relationship between frames, so as
to calculate the motion information of objects between adjacent frames.
Optical flow can be generally divided into two categories: sparse optical flow
and dense optical flow. Lucas and Kanade [1981] is a typical method to
calculate the sparse optical flow. This method needs to use some methodology
to locate the corner points as the initial points of the optical flow. We used
Shi and Tomasi [1994] method to locate the corner points but find these points
are less related to vessels due to various disturbances such as spinal pixels,
heartbeat, angle transformation etc. That is, the corner points are not
generated on the vessel, so the generated optical flow fails to represent the
dynamic effect of the contrast agent injection process. So we chose to compute
the dense optical flow proposed by Farneback [2003]. It is to compute the
optical flow of all pixels between frames. It is mainly through polynomial
expansion and the assumption of pixel displacement invariance to reach the
optimal optical flow. Figure 3 is a representation of the Farneback dense
optical flow mechanism in 2 dimensions perspective.

Figure 3: 2-dimension Farneback Illustration. The principle of dense optical
flow is to find the optimal flow direction and magnitude through the
polynomial expansion in the pixel field based on the assumption of pixel
displacement invariance. We reduce the high dimension description in Farneback
into 2 dimensional conditions. The x-axis in the figure is the spatial
position of the pixel point, f(x) is the corresponding second polynomial
expansion of pixel value. Based on the assumption of displacement invariance,
the movement of the pixel is illustrated as moving from the left star to the
right star, keeping f(x) as the same, and the polynomial expansion can be
changed from the dark blue quadratic curve to either the light green quadratic
curve or the light blue quadratic curve or other quadratic curve passing
through the second star. However, different quadratic curve (second polynomial
expansion) corresponds to different optical flow direction and magnitude, the
objective is to find the optimal most satisfies the displacement invariance
constraint.

The Farenback optical flow calculation is based on (6),(7). (6) is the second
polynomial expansion of pixel point x. (7) is the second polynomial expansion
of pixel point x plus a displacement. According to the displacement variance,
$f_{1}(x)=f_{2}(x-d)$, and we have coefficient constraints (8)$-$(11):

$f_{1}(x)=a_{1}x^{2}+b_{1}x+c_{1}$ (6)

$f_{2}(x-d)=a_{2}(x-d)^{2}+b_{2}(x-d)+c_{1}$ (7)

$a_{1}=a_{2}$ (8)

$b_{1}=b_{2}-2a_{2}d$ (9)

$c_{1}=a_{2}d^{2}-b_{2}d+c_{2}$ (10)

$\triangle b=-\frac{1}{2}(b_{1}+b_{2})$ (11)

Our objective is to select the optimal optical flow that satisfies the above
constraints most.

We then encounter the problem of further selection of effective feature points
and form an active zone to enforce the disarranging function on. Because dense
optical flow calculates the optical flow of all pixels in a frame, only a
small part of which is related to blood vessels. If all the pixels are
analyzed, a compensation mechanism will work which puts a negative impact on
the analysis of the results. Since coronary angiography also records the
movement of part of the spine, heartbeat as well as some movement of the
camera angles. Such additional dynamics are easier to generate strong Sequence
Intensity, so it may make it easier to recover the disorder via using such
additional information though the vascular visualization part is not easy to
be recognized. Bias may correspondingly be generated.

Hence, it is necessary to develop a screening mechanism to select an
“effective zone” from where the optical flows are generated from the pixels of
vessel.

Figure4 is a dense optical flow calculation process, from which we get such a
view that the points associated with blood vessels generally change sharply in
color and brightness. From the visualization process, different color and
brightness express different magnitudes and angles of optical flow.

Figure 4: Dense Optical Flow Calculation Process. The first row is from a
normal coronary angiography, the second row is from an abnormal coronary. The
orange arrow is the time axis. The dense optical flow is developed along the
time axis.

Figure5 is a vessel in polar coordinate plane. We finally select the point
whose flow magnitude variance is above 80 percentile as effective. Moreover,
we aggressively and randomly select 100 points from the 52428 effective points
as the final zone. A final zone and its optical flow trace are illustrated in
Figure 6. The above hyperparameters are selected based on try and error.

Figure 5: Polar Coordinate Plane View Figure 6: Effective Zone Generation.The
first row is from a normal coronary angiography, the second row is from an
abnormal coronary. Column (A) is from the original angiography. Column (B) is
the calculation results of Farneback optical flow of a frame in the segment.
Column (C) is the randomly selected 100 optical flow points from the optical
flow point sets above 80% percentile of magnitude variance. Column (D) is the
optical flow trace from 100 points selected.

###  3.3 Step 3: Learning

The objective of the learning model is to be trained so as to learn the
capability to recover disordered frames like human. To simplify the model, we
design the model as a two-class classification model, that is, we train the
model to tell if the specific frame is disarranged or not. The labels guiding
the training process are generated automatically comparing to the original
order. Once the model is trained to learn the recovering capability, its
accuracy is used as an approximate to Reorder Difficulty and therefore be an
indicator of Coronary Artery Stenosis Status. The model training process
doesn’t require any label engineering, in other words, it is not necessary to
know the ”answer” of Coronary Artery Stenosis Status beforehand, the model
intrinsically works in an unsupervised learning approach.

In terms of the learning of recovery capability, as our input is the sequence
of disarranged optical flow from the final effective zone, we chose the
recurrent neural network (RNN) which is specifically used to learn and predict
the sequence. Sutskever et al. [2014] found that using two separate RNN can be
very good realization of the sequence-to-sequence prediction. In our model,
the RNN we chose is GRU (Gate Recurrent Unit) invented by Cho et al. [2014]
Such architecture can handle variable-length inputs corresponding to variable-
frames-counts of different angiography videos. One RNN is for the encoder that
receives variable-length sequence inputs (max length×batch size) and transfers
the inputs into a fix length vector (max length×batch size×hidden size). The
input to each GRU module is a sequence element, the output is an output vector
and a hidden state (n layers×batch size×hidden size). The other RNN is the
decoder, its each GRU module takes a sequence element and the fixed length
vector from encoder as input and outputs a prediction of the next sequence
element (batch size×class counts) and the hidden state to be passed to its
next GRU (n layers×batch size×hidden size). The overall Encoder-Decoder GRU
architecture is illustrated as Figure 7.

Figure 7: Encoder-Decoder GRU Model.The bottom block is effective zone of
disarranged frames as the input of the Encoder-Decoder GRU model. The X block
is the encoder module, each node is a GRU unit. The green circle C is the
fixed length vector output by the encoder. The y block is the decoder module,
each node is also a GRU unit. The loss of the model is calculated through the
output of the Y block and the binary label generated automatically via the
disarranging status of the input frames. If the specific frame is disarranged,
it is correspondingly labeled as 1, otherwise, labeled as 0.

##  4 Results

We train the Encoder-Decoder GRU model described in Section3.3 to gain the
capability to recover the disarranged frames. The training set consists of
1320 Right Coronary Artery(RCA) videos and the test set consists of 100 RCA
videos. The average model prediction accuracy, the corresponding average
precision score and AUC is listed in Table 1, Figure 8, Figure 9.

Table 1: Overall and Segmented Results Stenosis |  Average Test Accuracy |  Average Precision Score |  AUC
---|---|---|---
all |  0.84 |  0.93 |  0.8
$\geq$ 80% |  - |  0.94 |  0.79
$\geq$ 90% |  - |  0.97 |  0.85
$\geq$ 95% |  - |  0.98 |  0.86
$\geq$ 99% |  - |  0.98 |  0.87

To highlight, the average precision score for stenosis $\geq$ 99$\%$ is up to
0.98, the corresponding AUC is up to 0.87. The results validate the intuition.
Since the severe stenosis cause occlusion, hence the contrast agent injection
process is blocked and similar adjacent frames are generated which increase
the Reorder Difficulty significantly. Hence, the model is less able to
distinguish and recover the disorder and hence generate significantly low
prediction accuracy. The average prediction accuracy between positive and
negative samples is most significantly different in this group so that the
classification performance is enhanced most.

Figure 8: Overall ROC Curve Figure 9: Segmented ROC Curve

From the iteration process data of Average Test Accuracy and AUC trends
(Figure 10), we can see that they reach peak simultaneously. Generally, the
higher average test accuracy is, the higher AUC it achieves. In our study, the
highest average test accuracy is 0.84, leaving huge potential for the future
work to improve the AUC via improving average test accuracy.

Figure 10: Average Test Accuracy V.S. AUC

Table 2 is the performance comparison of several typical researches related to
automatic recognition of coronary artery disease and ours. Moon et al. [2021]
achieves the highest AUC of 0.92. However, their method is a supervised
learning method which need laborious efforts to label engineering, so their
sample size is severely constrained due to the huge labeling efforts needed.
Besides, their method needs certain amounts of data preprocessing efforts such
as segmentation [Zana and J.-C.Klein, 2001, Huang et al., 2018, Yang et al.,
2019] and centerline extraction[Gulsun et al., 2016, Wolterink et al., 2019].
Cho et al. [2019] study is totally based on traditional machine learning and
needs heavy feature learning efforts. Our methodology, without any typical
data preprocessing, no need to label the data, even without convolution neural
network, achieves overall average precision score of 0.93 and AUC of 0.8. The
highest segmented average precision score reaches 0.98 and AUC reaches 0.87.

Table 2: Performance Comparison Study |  Sample Size |  Device |  Accuracy |  AUC |  Need Label |  Convolution Used |  Segmentation Used |  Centerline Extrac. Used |  Feature Engi. Used
---|---|---|---|---|---|---|---|---|---
Cho et al. [2019] |  1501 |  CCTA |  |  0.87 |  YES |  YES |  NO |  NO |  YES
Moon et al. [2021] |  452 |  CAG |  |  0.92 |  YES |  YES |  YES |  YES |  NO
Zreik et al. [2019] |  163 |  CCTA |  0.8 |  |  YES |  YES |  NO |  YES |  NO
Kumamaru et al. [2020] |  1052 |  CCTA |  0.76 |  0.78 |  YES |  YES |  NO |  NO |  NO
Proposed |  1320 |  CAG |  |  0.8 |  NO |  NO |  NO |  NO |  NO

##  5 Discussion

There are many cardiac related researches based on machine learning,
especially deep learning. Isensee et al. [2017] use 2D and 3D CNN to extract
the time series features of sequential images and the deep learning and random
forest model are integrated to predict heart diseases. Xu et al. [2017]
construct a parallel neural network model of CNN and RNN (LSTM) to predict the
lesion area of myocardial infarction. Lin et al. [2020] infer the probability
of coronary heart disease via facial recognition.

###  5.1 Dynamic Based

In terms of coronary heart disease diagnostics, as far as we know, all the
existing researches are static based on anatomy. That is, the analysis is
totally based on separate medical image typically generated from Coronary
Computed Tomography Angioplasty (CCTA). Zreik et al. [2019] use semi-
supervised learning based on CCTA images to evaluate if the patient needs
further invasive coronary angiography. Fischer et al. [2020] use RNN to
predict the calcification fraction of coronary vessels based on CCTA. Shadmi
et al. [2018] use deep CNN to calculate the calcification fraction based on
CCTA. Zreik et al. [2018] use recurrenct CNN to classify coronary stenosis
also based on CCTA. There are few deep learning research based on coronary
angiography. Moon et al. [2021] use CNN to achieve the automatic recognition
of coronary lesion based on coronary angiography. However, the preprocessing
technique of their method is to select key frames instead of utilize the whole
angiography video. Besides, their method is a purely supervised learning which
needs data manual label efforts a lot. Analysis based on static image
corresponds to anatomy diagnostic while a stenosis found in a static image
doesn’t necessarily mean ischemia.[Tonino et al., 2009] Our methodology is
based on analysis of the whole coronary angiography video instead of separate
image which is theoretically dynamic in a functionally perspective.

###  5.2 Label Free

There are many mature annotation libraries in image recognition, the most
famous one is ImageNet[J.Deng et al., 2009], and there are some other
annotation libraries in video recognition such as Kinetics[Kay et al., 2017].
These databases cover general scenarios. However, in the field of medical
imaging, especially coronary angiography, there is no mature annotation
library developed. For studies using deep learning techniques in this field,
researchers need to complete the label engineering work by themselves which is
highly costly since the annotation work must be finished by professional
doctors.[Cho et al., 2019, Zreik et al., 2018, 2019, Moon et al., 2021,
Fischer et al., 2020, Kumamaru et al., 2020] This makes the development of
deep learning, especially supervised learning in medical field greatly
limited. According to statistics by May 2020 from OECD (Organization for
Economic Cooperation and Development), the average annual income of a
specialist in hospitals of United States is 350300 dollars, and for a GP is
242400 dollars. That is to say, a specialist earns up to $168 an hour and a GP
earns up to $116 an hour, even without taking into account national holidays.
Doctors estimate that it takes about 15 to 20 minutes to fully evaluate a
coronary angiography, so even if a more junior GP to do the annotation, the
cost is as high as $30 for each coronary angiography. For deep learning, a lot
of labeled angiographies are needed. For example, in this paper, 1320 videos
of RCA angiography were used for training and 100 for testing, and the cost of
manual labeling alone was at least as high as $44080, not to mention some
larger training program. This may be an important bottleneck restricting deep
learning in coronary angiography.

This methodology links Sequence Intensity with Coronary Artery Stenosis Status
and finally demonstrates a significant relationship between them. However,
there is no need to manual labeling at all so that the training cost is
greatly saved and large-scale training becomes possible.(Figure 11)

Figure 11: The Laborious Efforts Saved Before and After.From the Syntax Score
scoring process, in the right coronary artery(RCA), there are 8 positions to
potentially have lesions. Hence there are 256 combination possibilities to be
diagnosed as an abnormal vessel. That is to say, to label the RCA, doctors
need to exclude the 256 possibilities so as to make a final decision of a
normal vessel. Hence the labeling efforts are laborious. On the other hand,
the methodology in this study is 100$\%$ label free and can be generalized
very easily.

###  5.3 Potential of the Methodology

From the performance of final results, we can see that the methodology still
has great potential to improve. The test accuracy of this methodology is 0.84,
the corresponding AUC can reach 0.8. As you can see from the iterations in the
Figure 10, there is a significant positive correlation between test accuracy
and AUC. If test accuracy is further improved, AUC is possible to be further
increased.

The methodology uses optical flow technology to represent sequence feature
between frames which is an idea of dimension reduction. The dimension of the
model input reduces by 2621.44 times which is very considerable while the
performance of the methodology is maintained in a good level. However,
dimension reduction will eventually bring about the loss of information and
indirectly affect the final test accuracy and AUC. If we can enhance the
parallel computing power of computers, such as using GPU instead of CPU
(Figure 12) to design and implement the methodology, it will improve the
accuracy of model prediction to a certain extent, thus improving the final
evaluation of lesions.

Figure 12: Potential Improvements. The current implementation is GPU-off. The
potential to improve the performance of the methodology is huge if GPU is
implemented.

###  5.4 Software Implementation

We implemented DZL methodology and developed a software to generate SCOREs for
any right coronary angiography in DICOM, AVI and MP4 forms. The software
interface is as Figure 13. From Figure 14, the left side RCA coronary
angiography uploaded in our example is an abnormal video with occlusion while
the right side RCA coronary angiography uploaded in our example is a normal
segment. The final SCOREs are calculated as Figure 14, the occlusion video
gets 0.77 and the normal video gets 0.85. You can find the DZL calculator on
http://47.103.11.61/DisarrangedZoneLearningCalculator/

Figure 13: Software Interface Figure 14: Scores Generation. The left RCA
coronary angiography uploaded in our example is an abnormal video with
occlusion while the right RCA coronary angiography uploaded in our example is
a normal video. The final SCOREs are calculated: the occlusion video gets 0.77
and the normal video gets 0.85.

###  5.5 Conclusion

This study originally proposed a novel unsupervised and dynamic methodology
(DZL) to automatically recognize coronary artery stenosis. DZL is labe-free,
with no precondition for inputted coronary angiography and takes advantage of
the whole coronary angiography video information. DZL is easy to be
generalized and migrated. Finally, we developed a software to implement the
DZL for clinical practice.

##  6 Limitation

In this study, only the Right Coronary Artery (RCA) Coronary Angiography data
is used to train and test the DZL. However, the methodology is general and not
constrained to any coronary artery parts. It can also be applied to Left
Artery Coronary (LCA). Future work can further validate, improve and extend
the methodology. As illustrated in Table 2, in this study, we skip all the
traditional data preprocessing procedures in order to demonstrate the pure
power of our methodology, however, it also constrained the performance of the
methodology. Future work can gradually add the typical preprocessing
procedures such as segmentation, centerline extraction etc..

## References

  * Cho et al. [2019] Cho, H., et al., 2019.  Angiography-based machine learning for predicting fractional flow reserve in intermediate coronary artery lesions.  Journal of the American Heart Association 8, 1–10.  doi:10.1161/JAHA.118.011685.
  * Cho et al. [2014] Cho, K., et al., 2014.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  Proceediings of the 2014 Conference on Empirical Methods in Natural Language Processing(EMNLP) , 1724–1734.
  * Farneback [2003] Farneback, G., 2003.  Two-frame motion estimation based on polynomial expansion.  Scandinavian Conference on Image Analysis , 363–370.
  * Fischer et al. [2020] Fischer, A.M., et al., 2020.  Accuracy of an artificial intelligence deep learning methodology implementing a recurrent neural network with long short-term memory for the automated detection of calcified plaques from coronary computed tomography angiography.  J Thorac Imaging 35, S49–S57.  doi:10.1097/RTI.0000000000000491.
  * Gulsun et al. [2016] Gulsun, M.A., et al., 2016.  Coronary centerline extraction via optimal ﬂow paths and cnn path pruning.  International Conference on Medical Image Computing and Computer Assisted Intervention , 317–325.
  * Huang et al. [2018] Huang, W., et al., 2018.  Coronary artery segmentation by deep learning neural network on computed tomographic coronary angiographic images.  Annu Int Conf IEEE Eng Med Biol Soc , 608–611.
  * Isensee et al. [2017] Isensee, F., et al., 2017.  Automatic cardiac disease assessment on cine-mri via time-series segmentation and domain specific features.  Computer Science doi:10.1007/978-3-319-75541-0.
  * J.Deng et al. [2009] J.Deng, et al., 2009.  Imagenet: A large-scale hierarchical image database.  2009 IEEE Conference on Computer Vision and Pattern Recognition , 248–255doi:10.1109/CVPR.2009.5206848.
  * Kay et al. [2017] Kay, W., et al., 2017.  The kinetics human action video dataset.  Computer Science .
  * Kumamaru et al. [2020] Kumamaru, K.K., et al., 2020.  Diagnostic accuracy of 3d deep-learning-based fully automated estimation of patient-level minimum fractional flow reserve from coronary computed tomography angiography.  Eur Heart J Cardiovasc Imaging 21, 437–445.  doi:10.1093/ehjci/jez160.
  * Lin et al. [2020] Lin, S., Li, Z., Fu, B., et al., 2020.  Feasibility of using deep learning to detect coronary artery disease based on facial photo.  Eur Heart J. doi:10.1093/eurheartj/ehaa640.
  * Lucas and Kanade [1981] Lucas, B.D., Kanade, T., 1981\.  An iterative image registration technique with an application to stereo vision.  Proceedings of DARPA Image Understanding Workshop , 121–130.
  * Miotto et al. [2018] Miotto, R., et al., 2018.  Deep learning for healthcare: review, opportunities and challenges.  Briefings in Bioinformatics 19, 1236–1246.  doi:10.1093/bib/bbx044.
  * Moon et al. [2021] Moon, J.H., et al., 2021.  Automatic stenosis recognition from coronary angiography using convolutional neural networks.  Computer Methods and Programs in Biomedicine 198\.  doi:10.1016/j.cmpb.2020.105819.
  * Shadmi et al. [2018] Shadmi, R., et al., 2018.  Fully-convolutional deep-learning based system for coronary calcium score prediction from non-contrast chest ct.  2018 IEEE 15th International Symposium on Biomedical Imaging , 24–28doi:10.1109/ISBI.2018.8363515.
  * Shi and Tomasi [1994] Shi, J., Tomasi, 1994.  Good features to track.  1994 Proceedings of IEEE Conference on Computer Vision and Pattern Recognition , 593–600doi:10.1109/CVPR.1994.323794.
  * Sutskever et al. [2014] Sutskever, I., et al., 2014.  Sequence to sequence learning with neural networks.  Proceedings of the 27th International Conference on Neural Information Processing Systems 2, 3104–3112.
  * Tonino et al. [2009] Tonino, P.A., et al., 2009.  Fractional ﬂow reserve versus angiography for guiding percutaneous coronary intervention.  N Engl j Med 360, 213–224.  doi:10.1056/NEJMoa0807611.
  * Wolterink et al. [2019] Wolterink, J.M., et al., 2019.  Coronary artery centerline extraction in cardiac ct angiography using a cnn-based orientation classiﬁer.  Med Image Anal. 51, 46–60.  doi:10.1016/j.media.2018.10.005.
  * Xu et al. [2017] Xu, C., Xu, L., et al., 2017\.  Direct detection of pixel-level myocardial infarction areas via a deep-learning algorithm.  MICCAI 2017 , 240–249doi:10.1007/978-3-319-66179-728.
  * Yang et al. [2019] Yang, S., et al., 2019.  Deep learning segmentation of major vessels in x-ray coronary angiography.  Nature 9.  doi:10.1038/s41598-019-53254-7.
  * Zana and J.-C.Klein [2001] Zana, F., J.-C.Klein, 2001.  Segmentation of vessel-like patterns using mathematical morphology and curvature evaluation.  IEEE Transactions on Image Processing 10, 1010–1019.  doi:10.1109/83.931095.
  * Zreik et al. [2018] Zreik, M., et al., 2018.  A recurrent cnn for automatic detection and classification of coronary artery plaque and stenosis in coronary ct angiography.  IEEE Trans Med Imaging 38, 1588–1598.  doi:10.1109/TMI.2018.2883807.
  * Zreik et al. [2019] Zreik, M., et al., 2019.  Deep learning analysis of coronary arteries in cardiac ct angiography for detection of patients requiring invasive coronary angiography.  IEEE Trans Med Imaging 39, 1545–1557.  doi:10.1109/TMI.2019.2953054.