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₁ or A1 for inputs and B, B₁ 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₁ 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 an Interface or a Frame.

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 into products and concurrent products in addition to sums.

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 (∑_iI_i<A_i,B_i> using a shorter notation and ∑_iB_i y^A_i in polynomial notation)
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 a generalized interface of the form I1 | I2 | ... | In or ∑_iI_i<A_i,B_i>. It is a polynomial ∑_iB_i y^A_i

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 functors as well as profunctors here.

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 Unit interface represents a pure 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⁰. Translating it to an interface type,

A: <0, A>

A data type A represented by interface <0, A> describes a behavior of read only access to value 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 pure panic behavior of the system.

A data type A with a power polynomial of the form 1y^A or simply y^A has interface,

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¹ 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 a state transition system with 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 that states are interfaces and interfaces can be represented as data types is 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 = ∑_iI_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₀ ∈ 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₀ ∈ 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
1. Use the update map to updates its state,
2. 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 = ∑_iI_i<A_i,B_i>.

THIS SECTION IS STILL WORK IN PROGRESS

Metals - Meta Programming Language System