# Modeling Composable Systems

We are on a quest to compose complex *systems* from simple ones. The
character of a system is determined by its *observable behaviors,
internal states and the dynamics* that generates the behaviors from
states.

## Systems: Interfaces, States and Dynamics

We will build our core ideas behind `metals`

in this section.

### Systems

A **system** in our world is anything that we are trying to model and build.
In its most simplistic form, it can be just a function. But it can be a
type that implements an interface, a process, a user interface (UI), a
service, an entire application programming interface (API), an application
with all its layers (frontend, backend, data etc.) of functionality or a
collection of subsystems that work together. Any unit of software
regardless of its size or form, really!

See `section on dynamics`

below for a formal
characterization of systems.

### Interfaces

We characterize the behaviors of *systems* through their **interfaces**.
An *interface* is the atomic building block in `metals`

. The time honored
way to specify an interface is as a *map* from an *input* to an *output*.

```
f: (A) → B // interface f as a map from A to B
```

Here we have the specification of an interface *f* that transforms *A
inputs* into *B outputs*. This conforms to our concept of functions in
programming. This describes the observable behavior of a system as
an obligation to engage in an interaction specified by the interface.

It is even more important to understand what an interface specification does not say.

- It does not say anything about the actual dynamics of this transformation
of
*A's*into*B's*. - It does not say anything about the internal states. By looking at this
interface, we can't tell if this is a stateful or stateless system. We don't
know if this represents a pure computation or one with side effects. There
is no
*referential transparency*guarantee that the same inputs shall produce same output. - The interface says nothing about the
*space*, whether this computation is local or remote. It works with*A*and*B*types as per the representations supported by the runtime used by the consumers of this interface. - It hardly says anything about time either. is it synchronous or
asynchronous?
Interface is silent on the subject. This interface only guarantees to
produce the output
*A*eventually, if the consuming system is willing to wait for it.

We need to build all these notions on top of this starting model while
preserving the simplicity of interface specification. Our goal is to create
a model framework to provide such extensions. We will do this systematically
from ground up using, you guessed right, **composition**.

### States and Dynamics

While interfaces specify the observed behavior, we need *states* to
model the **dynamics** of the system. A complete specification of the
**system** is achieved by mapping a **state** to an **interface**.

*A system in our discussions refers to this mapping from a state to an
interface.*

```
system: (S) → I // A system as a map from state S to Interface I
```

An implementation of a *system* is the realization of this mapping. It
represents a *unit of computation*.

### Notational Conventions

Since we are building a meta language for such specifications, using *Rust*
to build it and finally be used from other programming languages,
we will need a few notational conventions.

- A generic abstract notation that is independent of any programming language.
- Their concrete specifications in Rust.
- The mapping of the abstract notation to other programming languages. We will not be covering this in this document.

Let us look at some of the basic conventions. We will refine them as we go along.

## Interfaces, Interface Types and States

We write <Input, Output> to represent an *interface* from *Input* to
*Output*.

```
<Input, Output> // An interface from Input to Output
```

We use the capital letters A and B with or without numbers for input
output types respectively. For example, A, A_{1} or A1 for inputs
and B, B_{1} or B1 for outputs.

An *interface type* I<A, B> represents any interface from A to B. It is the
family of all interfaces from A to B. We will also use I, I_{1} or
I1 or capitalized names to denote to *interface types*.

```
I<A, B>: Type of interfaces from input type A to output type B
Handlers<HttpRequest, HttpResponse>: Interfaces from HttpRequest to HttpResponse
```

Some of the key ideas we use in characterizing the systems and their
behaviors come from the area of *Polynomial Functors*, especially from
the groundbreaking work of `David I. Spivak`

and his collaborators.
We highly encourage readers to read the books on `Polynomial functors`

and `Dynamical systems theory`

. There are several educational videos and
even a complete `Polynomial Functors course`

on YouTube.

From the point of view of *polynomials*, an interface <A, B> can be
thought of as a *monomial* of the form By^{A}. We will use this
notation sparingly, but the fact that dynamic systems and their interfaces
can be represented as polynomials and their interactions can be understood
in terms of polynomial arithmetic is both fascinating and critical to
understanding our approach. Whenever necessary, we will use the polynomial
representation to clarify such ideas. We will write a monomial as,

By^{A}.

We also write it as,

```
I = By[A]: A monomial representing interface from input type A to output type B
```

When we deal with multiple interfaces, we will use labels to distinguish individual interfaces. A labelled interface is written as below.

```
I<A, B>: I is the interface type representing any interface from A to B
i<A, B>: i is a labelled interface, a specific instance of type I<A, B>
// This means i has type I
i: I<A, B>
I<(i32, i32), i32> //Interface type specifying any interface from 2-tuple (pair) of i32's to i32
add<(i32, i32), i32> // A specific interface labelled add of type pair of i32's to i32
sub<(i32, i32), i32> // Another interface labelled subtract of type pair of i32's to i32
add, sub: I<(i32, i32), i32> // Both add and sub have type I
Handlers<HttpRequest, HttpResponse> // An interface type for HttpHandlers
handler<HttpRequest, HttpResponse> // A specific handler of type Handler
handler: Handlers<HttpRequest, HttpResponse> // handler has type Handlers
```

We use lowercase letters to represent labels of *interfaces* and uppercase
letters for *interface types*.

A system with a *state* s and an interface i is written as,

```
[s, i<A, B>] // Interface labelled i from type A to type B with state s
s: S // State s is of type S
```

We use capitalized names, *S* for example, to denote *types* of states.
They are usually encoded as some type implementing the interface and
refer to them as *implementing type*. We will redefine them in terms of
interfaces soon.

We have to combine an interface with a state to get an *executable or
runnable* system.

We also use `_`

when we are specifying generic types. For example,

```
[_, i<A, B>]: Refers to any system implementing interface from A to B
[S, i<_, B>]: Refers to an interface from any type to B implemented by S
[S, i<A, _>]: Refers to an interface from A to any type implemented by S
```

## Multiple Interfaces

Systems have multiple interfaces. A calculator, for example, has interface for addition, subtraction, multiplication, division, etc. Let us consider two interfaces,

```
add<(i32, i32), i32>
sub<(i32, i32), i32>
// Both have the same interface type
add, sub: I<(i32, i32), i32>
```

An interface that supports both add and sub behaviors can be constructed by combining individual interfaces,

```
Calc: add<(i32, i32), i32> | sub<(i32, i32), i32>
// Or we may write this in short as,
Calc<add | sub>
```

We just added two *monomials* to get a *polynomial*.

Calc = (i32) y^{(i32, i32)} + (i32) y^{(i32, i32)}

This is an *algebraic sum* or *disjoint union* of two interfaces. This is
defining a *sum type* for those of you familiar with _Algebraic Data
Types (ADT).

Generalizing to a system with multiple interfaces i1<A1, B1>, i2<A2, B2>, ..., in<An, Bn>, we write,

```
// In our notation
I: i1<A1, B1> | i2<A2, B2> | ... | in<An, Bn>
// In polynomial notation
I = B1 y[A1] + B2 y[A2] + ... + Bn y[An]
```

Polynomial notation in full glory,

I = (B1) y^{A1} + (B2) y^{A2} + ... + (Bn) y^{An}.

A calculator (the system) implementing this interface can be written as,

```
Calculator[(), add<(i32, i32), i32> | sub<(i32, i32), i32>]
// () indicates unit type for state
// Or shorter
Calculator[(), add | sub]
// Or even shorter
Calculator[(), Calc]
// Above, Calc is the sum interface defined as before Calc<add | sub>
// We may even write this by combining state and system together
[Calculator, Calc]
```

Please note that `Calc`

is the interface type, `()`

is the unit state and
`Calculator`

is an implementing system.

A system with state S implementing the generalized interface i can be written as,

```
[S, i1<A1, B1> | i2<A2, B2> | ... | in<An, Bn>]
// Or shorter
[S, i1 | i2 | ... | in]
// Or even shorter
[S, I]
```

S is the type of state and I is the interface type in the above.

At this point, we have recovered the standard definition of an *interface*
that we are all familiar with as programmers - a group of named
(labels) functions (interfaces) with input/output signatures
(interface type).

Let us translate this to *Rust*.

`#![allow(unused)] fn main() { // The trait is what is equivalent to an interface type in Rust // This defines Calc as the sum interface, add + sub. trait Calc { fn add(i: (i32, i32)) -> i32; //labelled interface with type (i32, i32) → i32 fn sub(i: (i32, i32)) -> i32; //labelled interface with type (i32, i32) → i32 } // The system implementing the interface // In this case, it has no internal state struct Calculator; // The actual implementation details impl Calc for Calculator { // x-- snip the implementation details fn add((m, n): (i32, i32)) -> i32 { m + n } fn sub((m, n): (i32, i32)) -> i32 { m - n } } }`

A general interface or sum type maps to a `trait`

in Rust. An implementing
type with unit state is defined using a `unit struct`

.

A general interface in

`metals`

is equivalent to a`trait`

in Rust. But we don't use the term`trait`

outside of Rust implementation discussions.

We refer to a general interface simply as anInterfaceor aFrame.It is because we use the concept of interface to model and compose systems and their states, not just interfaces.

It is for the same reasons we use

`|`

to denote our disjoint union instead of`+`

as in Rust. In our composition of systems, we go intoproducts and concurrent productsin addition tosums.

## Understanding Sum of Interfaces in `metals`

It may appear that we have just managed to duplicate a basic programming language feature using a new set of notations.

In `metals`

, we are **composing systems**. In addition to composing
two interfaces using sum, I = I1 | I2, to define a new composite interface,
we can compose two systems implementing those interfaces,

[S, I] = [S1, I1] | [S2, I2].

The composite system on the left has the interface type I = I1 | I2.
Moreover, we are constructing a system that can operate in two **modes**,
*either as a system with interface I1 or as a system with interface I2,
each of which may have a different underlying system implementing it
with different state (S1 and S2 above)*. We are incorporating
the context of systems implementing the interfaces into the composition.

For example, consider two interfaces,

```
I1: <A1, B1> // Interface type A1 to B1
I2: <A2, B2> // Interface type A2 to B2
I: I1 | I2 // Sum of interfaces
```

Consider the systems implementing these interfaces,

```
Y1: [S1, I1] // Y1 is the system with state type S1 implementing interface type I1
Y2: [S2, I2] // Y2 is the system with state type S2 implementing interface type I2
Y: [S, I] // Y is the system with state type S implementing combined interface
```

Here there is no relationship between the three systems, even though there is a relationship between their interface types. The systems are independent of each other. Interface I is composed of I1 and I2, but Y is a completely independent implementation of this combined interface. You can picture the situation as follows,

```
y1: (s1, a1) → b1 // When invoked with input a1 (type A1), produces b1 (type B1) using its state s1
y2: (s2, a2) → b2 // When invoked with input a2 (type A2), produces b2 (type B2) using its state s2
y: (s, a1) → b1 // When invoked with input a1 (type A1), produces b1 (type B1) using its state s
Or (s, a2) → b2 // When invoked with input a2 (type A2), produces b2 (type B2) using its state s
// s1 != s2 != s (!= means not equal)
```

The composition is only skin deep! **You are just defining a new interface
type.**

Now, consider different kind of composition of systems,

```
Y1 = [S1, I1] // System Y1 implementing interface I1
Y2 = [S2, I2] // System Y2 implementing interface I2
Y = Y1 | Y2 // Y is a system composed of Y1 and Y2
```

Y has the interface type I: I1 | I2 as before. But it is composed of two subsystems where it operates S1 with inputs of type A1 and S2 with inputs of type A2. In terms of state, the situation now is,

```
y1: (s1, a1) → b1 // When invoked with input a1 (type A1), produces b1 (type B1) using its state s1
y2: (s2, a2) → b2 // When invoked with input a2 (type A2), produces b2 (type B2) using its state s2
y: (s1, a1) → b1 // When invoked with input a1 (type A1), produces b1 (type B1) using s1
Or (s2, a2) → b2 // When invoked with input a2 (type A2), produces b2 (type B2) using s2
```

It is true composition of two systems! **We are constructing a new system.**

We want both, an ability to combine systems or create a new system that implements a combined interface.

A sum or polynomial interface represents a composed system that can act as any one of its subsystems, one at a time.

It is as though we have a box with a mode selector button. Anywhere we need
to make B_{i}'s out of A_{i}'s, we jut have to set the mode
to *i* position first and then run it with A_{i}.

The system represented by a sum interface has acquired a state, even if the underlying system implementing the behavior represented by the interfaces has state or not. We need to pick the right interface before we can call it with the right input. In our calculator example, we have to select add or subtract operation first and then pass the pair of numbers.

## Interface Maps and Representation of General Interfaces and Systems

Let us summarize our discussion so far.

- Simplest form of
*Interface*is <A, B> where A is the input type and B is the output type. - An
*Interface Type*I<A, B> defines a type of any interface with input A and output B. - A
*System*implementing an interface, Y: [S, I] associates a*State*type S with an*Interface Type*I. - The general form of an interface is a disjoint sum of single
interfaces, I = I1 | I2 | ... | In
(
**∑**using a shorter notation and_{i}I_{i}<A_{i},B_{i}>**∑**in polynomial notation)_{i}B_{i}y^{Ai} - In
`metals`

, we can not only compose interfaces to form a combined interface, but also compose systems implementing those interfaces to form a new system. - A general interface introduces
*modality*to the system's interface where by introducing an additional step in the interaction with the system.

From this point onwards, when we refer to an

interface, we mean ageneralized interfaceof the formI1 | I2 | ... | Inor∑. It is a polynomial_{i}I_{i}<A_{i},B_{i}>∑_{i}B_{i}y^{Ai}

### Introducing Interface Maps

As we saw above, an interaction with a system with a general interface
is no longer a simple `call with an input`

. We have to pick a specific
component system with one of the component interfaces (one of the
I_{i}'s) first and then call it with the input. We have a mode
selector interface of the form <Mode, I>.

```
I = I1 | I2 | ... | In
InterfaceSelector: <Mode, I> //Interface selection interface type
// Interface selector accepts some input of type Mode and returns a value
// of the _Interface Type_ I, which is one of I1, I2, ...or In.
```

It appears that we need a way to translate this interaction pattern in
terms of our language of *interfaces*. The key lies in looking at the
interface definition with our understanding that *interfaces* themselves
are types.

Let us revisit our original definitions

```
<A, B> // Interface from type A to type B
I: <A, B> // Interface Type from type A to type B
```

Since interfaces are types, let us replace A and B with some other interface types. We have 3 cases.

__Case 1:__ A is an interface type, I1<A1, B1>

```
I1: <A1, B1> // Interface Type from type A1 to type B1
A = I1 // A in I is an interface of type I1
I: <I1, B> // I takes an interface type I1, returns a value of type B
```

This is the interface description for evaluating or running an interface I1 with input A1, then converting B1 values to B values. That means the interface describes a system converting A1's to B's.

We can capture this idea of turning an interface <A1, B1> into a <A1, B> as map of interfaces, an IMAP as follows,

```
I:= <A1, B>
IMAP: <(<A1, A1>, <B1, B>), <A1, B>>
```

IMAP takes two interfaces, one from A1 to A1 (an identity map) and one that converts B1 into B and returns an interface from A1 to B.

__Case 2:__ B is an interface type, I1<A1, B1>

```
I1: <A1, B1> // Interface Type from type A1 to type B1
B = I1 // B in I is an interface of type I1
I: <A, I1> // I takes an input of type A and returns an interface type I1
```

This system turns an interface from A1 to B1 into an interface from A to B1.

This can be expressed as an IMAP as follows,

```
I:= <A, B1>
IMAP: <(<A, A1>, <B1, B1>), <A, B1>>
```

IMAP takes a map from A to A1 and a second one from B1 to B1 (an identity map) and returns an interface from A, B1.

__Case 3:__ Both A and B are interface types, I1<A1, B1> and I2<A2, B2>

```
I1: <A1, B1> // Interface Type from type A1 to type B1
I2: <A2, B2> // Interface Type from type A2 to type B2
A: I1 // A in I is an interface of type I1
B: I2 // B in I is an interface of type I2
I: <I1, I2> // I takes an interface type I1 and returns an interface type I2
```

This is a more general form of mapping between interfaces. This converts an interface from A1 to B1 into an interface from A2 to B2.

As an IMAP, this is,

```
I:= <A2, B2>
IMAP: <(<A2, A1>, <B1, B2>), <A2, B2>>
```

Please note that the two maps that IMAP uses goes in opposite directions. On inputs, it goes from A2 to A1 while on outputs it goes from B1 to B2.

We can think of <A1, B1> as the inner interface type and <A2, B2> as the outer interface type.

Readers familiar with functional programming will recognize the relation to

contravariant and covariant functorsas well asprofunctorshere.

We will generalize the IMAP we defined above to the general interface case, those with multiple interfaces.

Before we do that, let us talk about the types and states that appear in our definition of interfaces, those A's and B's on interfaces and S's in the definition of systems.

### Data Types and States as Interfaces

We already introduced `Interface Types`

as types representing interfaces.
All data types can be represented as interfaces as well. *There is a
duality between interfaces and data types*.

This ideas of *sum and product types* must be very familiar to those who
have some background in *Algebraic Data Types (ADT)*. Here are some
references that provide simple introduction to algebraic data types for
programmers in [Javascript][adt-js], [Rust][adt-rust] and in
[Swift][adt-swift].

There are two special data types we will start with, a zero type and a
unit type. In Rust, they translate to the types *never ! and unit ()*
respectively. They represent types that can take

*no value*and exactly

*one value*. They are represented by constant polynomials

*0 and 1*.

We can translate them to interface types **Zero** and **Unit** as follows.

```
Zero: <0, 0> // Interface Type from never type to never type
Unit: <1, 1> // Interface Type from unit type to unit type
```

The data types 0 and 1 are translated to an appropriate data type in the target language. In Rust, they translates to,

```
Zero: <!, !>
Unit: <(), ()>
```

As one would expect, adding *Zero* interface type to an interface type
*I* returns *I* and adding *Unit* interface type to a type *I + Unit*.

```
I + Zero = I
I + Unit = I | Unit
```

A

Unitinterface represents apure side effect, a system behavior with no observable input or output.

*Note: To fully understand the statements we are making about a system
behavior, we need the machinery of interface maps and the concept of
a system as a map from state to an interface type, S → I as
well as the idea that a state has an interface type <S, S>. It will
become clearer by the end of next section*

Any data type *A* is a constant polynomial of the form *Ay ^{0}*.
Translating it to an interface type,

```
A: <0, A>
```

A data type A represented by

interface <0, A>describes a behavior ofread onlyaccess tovalue of of type A.

We can extend the above definitions to other combinations of A, 0 and 1.

A data type *A* with a power polynomial of the form *0y ^{A}* has
interface,

```
Panic: <A, 0> // Interface Type from type A to never type
```

An

interface <A, 0>represents a purepanicbehavior of the system.

A data type *A* with a power polynomial of the form *1y ^{A}* or
simply

*y*has interface,

^{A}```
UpdateInternalState: <A, 1> // Interface Type from A to Unit
```

An

interface <A, 1>represents a side effect or unobserved internal state changing behavior of the system based on the values of type A.

A data type *A* with a linear polynomial of the form *Ay ^{1}*
or simply

*Ay*has interface,

```
UpdateRead: <1, A> // Interface Type from Unit to A
```

An

interface <1, A>represents an update followed by read of values of A. The update is completely internal to the system.

A state *S* is represented by a monomial of the form *Sy ^{S}*
with interface,

```
State: <S, S> // Interface Type from S to S
```

An

interface <S, S>represents astate transition systemwith states from values of S.

A state transition system or **state system** for short, takes the
current state and returns a new state.

The idea thatstates are interfacesandinterfaces can be represented as data typesis a central concept in`metals`

.

### Putting It All Together

In last three sections, we introduced the idea of general interfaces and systems, discussed the concept of maps between interface types and established that there is a duality between data types and interfaces.

We described a system as a map from states to a set of observable behaviors
encoded as an interface, (S) → I. We used a special notation [S, I], to
represent a system with state S and interface I where
I = ∑_{i}I_{i}<A_{i},B_{i}>.

Since a state system S, has interface type <S, S> (Sy^{S}), the
above system definition translates to an interface type with interface
types as input and output,

```
System: [S, I]
System: <<S, S>, I> // System has an interface type from <S, S> to I
```

If I is an interface <A, B> then, the system has interface type,

```
System: <<S, S>, <A, B>>
```

The behavior of the system can be described as follows,

- Uninitialized: An uninitialized system shall accept initial state
s
_{0}∈ S. System is not ready to accept inputs A yet. - Initialized: Once initialized, the system shall turn into an <A, B> system and ready to accept input A.
- On Input: The system shall return the output of type B.

Someone interacting with an *initialized system*, can't distinguish it
from another system implementing interface <A, B> without a state.

There are many ways to implement the above interface and the behavior. One way to do this is to use an IMAP we defined earlier. Our system as an IMAP,

```
System: IMAP<(<A, S>, <S, B>), <A, B>>
```

The system has inner state S with interface <S, S> representing the state
transitions and outer interface <A, B>, which is the
observable behavior of the system. The maps <A, S> and <S, B> are referred
to as the *update* and *read* maps respectively.

If we implement the system using an IMAP, it will simulate the behavior we described earlier as follows,

- Uninitialized: An uninitialized system shall accept initial state
s
_{0}∈ S. System is not ready to accept inputs A yet. - Initialized: Once initialized, the system shall turn into an <A, B> system and ready to accept input A.
- On Input: The system shall
- Use the update map to updates its state,
- Use the read map to generate output and return it.

Again, an *initialized* system is indistinguishable from any other system
with interface <A, B>.

The IMAP implementation is reminiscent of most state management systems out there with update and read functions,

update: S x A → S

read: S → B

In Redux, one of the most popular state management frameworks used by
user interface (UI) developers, the update signature is exactly that of
a *reducer*.

But the subtle difference is that our interface definition is a prescription for turning a state system S into a <A, B> system,

(s) → ((a) → b).

The state management system is a prescription for the conversion

(s, a) → (s, b).

It is converting a (state, input) tuple into a (state, output) tuple. It is a different behavior. It is possible for us to translate this to our interface language. We will have a lot more to say later about systems with states especially regarding mutability, locality and synchronization of state.

Let us focus our attention to a system with state S and general interface
I = ∑_{i}I_{i}<A_{i},B_{i}>.

THIS SECTION IS STILL WORK IN PROGRESS

Copyright 2022 Weavers @ Eternal Loom. All rights reserved.