In the first part of this series we have looked at a conceptual overview of the Abra specification, which describes how data flow is achieved within the Qubic Computation Model. In the second, third, fourth, and fifth parts we used the Abra specification to implement Qupla, a higher level programming language for Qubic. Now it is time to introduce the Qubic Supervisor and the way it interacts with Qupla functions to be able to create even more complex behavior.  

As a reminder: we advise readers who finish this series to re-read it in its entirety for deeper understanding. What seems complex at first reading will become clearer at the second or even the third reading. There is a huge amount of new concepts and paradigms that we are conveying. We are doing our best to keep the explanation as clear as possible, but your best tools for learning and understanding are repetition and experimentation. So check out theQupla repositorythat we created and play around with the language.

Qubics are strictly event-driven, meaning that they depend on the Tangle and other sources for input data, and run whenever that input data becomes available or changes. This behavior requires an agent that can wait for these input events to happen, gathers the new input data, schedules a qubic to run its computations with this input data, and then passes on the output data of the qubic. Because this entity supervises the dispatching of data to and from qubics we call it theQubic Supervisor, or Supervisor for short.

The Supervisor has a plug-in design that allows any kind of data source to function as a source of input data or output data. Possible data sources that come to mind are messages posted on the Tangle, HTTP GET and POST urls, or hardware I/O ports.

With qubics being packaged as intermediate trit-code, it also falls on the Supervisor to find/load the qubics on demand and prepare them for running on the target processing device.

Remember how we explained the reactive data flow in part 1as consisting of computational entities that send effects to environments. Any computational entity can generate data and send that as an effect to one or more environments. The effect data is subsequently passed on to any computational entity that has joined these environments. Any entity that processes an effect can in turn send results as effect data to one or more environments.  

The indirection that is created by sending effects between entities through environments allows for very flexible combinations of events to trigger all kinds of computations. Entities do not necessarily have to be aware of each other. They simply send effects to environments, and any entity can join these environments and get delivered the effect data for processing.

This is how we can implement oracles that deliver external data to the Qubic system. Any source of data can package this data as an effect and ask the Supervisor to send it to an environment. If a qubic entity has joined that environment, it will be triggered to process the effect data. Once the qubic has processed the effect data, its result data can in turn be sent as effect data to an environment, which causes the Supervisor to pass it to entities that have joined that environment for further processing. One such entity could be yet another oracle, which then can function as the data provider for further external processing.

Note that it is entirely possible for a qubic entity to be triggered by the effect data generated by another qubic entity instead of data generated by an oracle entity. That’s why we have always maintained that there is no clear demarcation line between classical, external oracles and (internal) qubics functioning as oracles. There are only processing entities generating and consuming effect data via environments. Some entities happen to lie on the boundary of the system and the outside world. Others are entirely within the system and are constructed in such a way that they can process data in complex ways by a divide-and-conquer technique that combines many small, easy to understand processing entities into more complex processing behaviors.

The processing entities aren’t necessarily only qubics, either. Effect data can be processed by an oracle by passing it on as external data outside the system. Or a processing entity could be a view that displays the effect data. You can mix and match in a very flexible way.

Imagine for example a special monitor entity that can join any environment and just displays what effect data passes through. You could hook a separate monitor entity to each environment that you are interested in to see what is going on internally. Or even to provide that environment with effect data for processing, for that matter. This would allow us to test entities in isolation.

Another way that oracles can be used is as gateways between Q-nodes, passing effect data over external connections of any type. Such oracles would function as simple communication adapters, and all they have to do is pass the effect data to the correct environment on their counterpart’s Q-node. To the local Q-node this is practically invisible. All it does as far as it is concerned is send effect data to a local environment, and the oracle that joined that environment sends it to the other Q-node, where it gets picked up by its counterpart, which then forwards it to a local environment on own system.

It is up to the Supervisor to integrate all the different entities in the system and keep track of what environments they have joined, so that it can pass any effect data arriving at these environments to the correct joined entities. In addition it will make sure that the effects are processed in a deterministic way, so that when the same data is processed by different Q-nodes the resulting order of processing is the same for any Q-node, no matter how many effects arrive or how many environments get triggered simultaneously.

Any function in Qupla can operate as an entity that can receive effects from environments as well as generate effects for environments. To facilitate this we have added two special statements to the language that can be used to indicate this: join and affect.  

The join statement is used to join an environment. Join statements are always the first group of statements declared in a function. There are two forms:   

func Int entity (Int val) {join myEnvironmentjoin myOtherEnvironment limit 3return val}

The functionentity() specifies that it joins 2 separate environments. The environments joined are my Environment and my OtherEnvironment. As you can see, the second join statement specifies alimitof 3 invocations of this entity function through my OtherEnvironment within a single quant. The first join statement does not specify a limit, in which case the invocation limit defaults to 1. This means that the only way to have an entity function be invoked multiple times within the same quant is to explicitly specify an invocation limit. This limit guarantees that entities that cause an invocation loop can never cause an infinite invocation loop within a single quant.  

Whenever effect data is sent to my Environment or my OtherEnvironment the functionentity() will be called and the effect data gets passed in as the valargument. When the size of the effect data trit vector is smaller than the size of the function argument, it will be padded with zero trits until it has equal size. When it is larger than the size of the function argument it will be truncated to the correct size. It is up to the creator of the entity()function to make sure that the effect data trit vector is interpreted in the way it was defined for the environment. Note that you can see an environment as an interface definition and the entities that join it as implementations of that interface.  

The affect statement is used to send effect data to an environment. This will trigger invocation of the entities that have joined that environment by passing the effect data to them. Affect statements are always the second group of statements declared in a function (after any join statements). There are again two forms:   

func Int entity (Int val) {affect myEnvironmentaffect myOtherEnvironment delay 5return val}

The functionentity() here specifies that it affects 2 environments. The environments affected are my Environment and my OtherEnvironment. As you can see, the second affect statement specifies a delay of 5 quants before it takes effect. The first affect statement does not specify a delay, in which case the delay defaults to 0 (zero). A delay of zero means that the effect data is sent to the environment within the current quant. Note that this does not necessarily mean that it gets processed within the current quant. If an entity in that environment has reached its invocation limit, processing of the effect for that entity will be delayed until the next quant instead.  

The actual effect data that is sent to my Environment or my OtherEnvironment is the return value of the functionentity(). When the return value is a null trit vector, this means that no environments will be affected. In any other case the return value will be sent to the specified environments. Any null trits in the trit vector will be replaced with zero trits before the effect data is sent to any environments. It is up to the creator of the entity()function to make sure that the effect data trit vector is structured in the way it was defined by these environments.  

We will be using the original Proof of Concept application for the QCM as a study case. That application is an implementation of Conway’s Game of Life. This cellular automaton ‘game’ displays the evolution of generation after generation of cells on a grid that live or die according to a very simple set of rules:  

  1. A live cell with less than 2 neighbors starves and dies.
  2. A live cell with more than 3 neighbors suffocates and dies.
  3. A dead cell with exactly 3 neighbors spawns a new live cell.

It turns out that with these simple rules very complex behaviors can occur that are highly fascinating to watch and experiment with. Starting with a grid that contains a number of random cells is already very entertaining. But figuring out what cell patterns exhibit special behaviors makes for such nice puzzles that an entire online community has formed around the Game of Life that explores its intricacies and shares their results.  

So what do we need to be able to implement the Game of Life (GoL) in terms of EEE? Only a handful of entities are necessary:

  • Of course, you want to be able to display the current grid state, so you need a view entity that can display the grid.
  • Another entity is responsible for handling user interaction and translating that into operations on the grid.
  • And finally, we need an entity for which Qupla is extremely well-suited, namely one that can calculate the next generation of the grid from a starting grid. This is a large computation, that would be very well-suited to parallelization and execution on an FPGA.

You can see the Game of Life in action and play with it yourself when you run the Qupla interpreter with the GameOfLife module as parameter. The GoL will run with a fixed 81x81 grid. Qupla comes with a Java Game Of Life Entity that doubles as both the view entity and the user interaction entity. We will start our explanation with the simplest version: a single user that has a single single view of the grid.  

At startup the Game Of Life Entity will join the GolViewenvironment, where updates to the game grid will be sent as an effect that contains the entire 81x81 grid as effect data. When the Game Of Life Entity receives such an effect it will store a copy of the grid data in its local memory and display the current grid state in its view.  

User interaction comes in the form of mouse input. You can use the left mouse button to click or draw directly on the view. The state of the cell under the mouse pointer determines whether clicking/drawing creates or removes live cells. Clicking first inverts the state of the cell under the mouse pointer and then copies that state along the mouse path as it draws. The changes are sent directly as an effect to the GolViewenvironment, so that the view can update itself automatically and you can see the effect of your mouse input taking place in real time.  

The right mouse button performs a special function. Each time it is clicked the current grid is sent as an effect to theGolGenenvironment. This will cause a Qupla entity to calculate the next generation of the grid, which is then sent as effect data to theGolViewenvironment so that it can be displayed in the view.

Note how the Java Game Of Life Entity functions as both an input oracle and an output oracle in the QCM. It will provide the external data for the Quplagame Of Life() function entity that calculates the next generation, and also processes the changes to the grid meant for external display purposes.  

From the rules of GoL it is clear that to calculate the new generation of the grid we need two things: a count of neighbors of a cell and a decision based on that count that results in the new state of the cell. And of course we need to do this for every cell in the 81x81 grid, preferably in parallel. This means we take the input grid, calculate the new state for each cell, and construct a new grid from those new cells to be returned as the next generation grid.

Since any cell that has >3 neighbors is doomed, we can use a special counter that only keeps track of 0–3 and >3 neighbors. This is easily done with a LUT. Whether that LUT counts binary or trinary does not really matter. For historic reasons we use a binary count here. This is what the LUT looks like: 

// input trit 1 & 2: current binary amount of neighbors (-- when >3)// input trit 3: next neighbor cell state (0 = dead, 1 = alive)// output: new binary amount of neighbors (-- when >3)lut binSum {0,0,0 = 0,0//0 + 0 =0 neighbors0,0,1 = 1,0//0 + 1 =1 neighbor1,0,0 = 1,0//1 + 0 =1 neighbor1,0,1 = 0,1//1 + 1 =2 neighbors0,1,0 = 0,1//2 + 0 =2 neighbors0,1,1 = 1,1//2 + 1 =3 neighbors1,1,0 = 1,1//3 + 0 =3 neighbors1,1,1 = -,-//3 + 1 = >3 neighbors-,-,0 = -,-// >3 + 0 = >3 neighbors-,-,1 = -,-// >3 + 1 = >3 neighbors}

Now all we need to do is start with a binary amount of zero and feed the running tally of the amount plus the state of each of the 8 neighbor cells through the bin SumLUT. Note how each combination where the next cell is dead simply outputs the original binary input value. And each combination where the next cell is alive outputs the next higher binary number, until it becomes more than 3, in which case we return a special overflow indicator:-,-. Any neighbor we try to add after that simply returns the overflow indicator again.  

The next step is to use the rules of the game on the calculated number of neighbors in combination with the current state of the current cell. Again, we can use a simple LUT to decide: 

// input trit 1 & 2: binary amount of neighbors (-- when >3)// input trit 3: old cell state (0 = dead, 1 = alive)// output: new cell state according to GoL ruleslut newCellState {0,0,0 = 0//0 neighbors + dead-> stay dead0,0,1 = 0//0 neighbors + alive -> starve cell1,0,0 = 0//1 neighbor+ dead-> stay dead1,0,1 = 0//1 neighbor+ alive -> starve cell0,1,0 = 0//2 neighbors + dead-> stay dead0,1,1 = 1//2 neighbors + alive -> stay alive1,1,0 = 1//3 neighbors + dead-> spawn cell1,1,1 = 1//3 neighbors + alive -> stay alive-,-,0 = 0// >3 neighbors + dead-> suffocate cell, stay dead-,-,1 = 0// >3 neighbors + alive -> suffocate cell}

So once we have calculated the total number of neighbors of a cell by using the bin SumLUT we can immediately decide on the new state of the cell by using the new CellStateLUT. Now all we need is a mechanism to iterate over each row of the grid, and within each row iterate over each cell in the row.  

The problem we encounter here is that in Qupla it is not possible to use a flexible index that points directly at the current cell in the grid. We need another way to achieve this. And the way we do this is by shifting each row 1 cell at a time, each time using the first cell in the row as the current cell. Then we determine the new state for that cell and append that new state at the end of the row. Once we have done this for each cell in the row, we have a new row consisting of all new cells in the correct sequence.

We can use the same trick in an outer loop for each row, by shifting out one row at a time from the grid, creating the new row cell by cell, and then appending the new row at the end of the grid. Once we have done this for each row in the grid, we have a new grid consisting of all new rows in the correct sequence.

There’s only one additional thing left to do and that is to take care of the cells at the edges of the grid. They don’t have any neighbors. There are usually 2 ways of dealing with this in game environments. The first way is to add an empty border around the grid and only iterate over the grid within that border. The second way is to treat the grid as ‘wrap-around’ so that the cells at the far ends are seen as neighbors of each other. In our PoC we use the first approach, an empty border around the grid. Here is the final Qupla implementation, which has been turned into a grid-size-independent template already: 

template gameOfLife<T> {type Cell [Trit]type Col [T]type Row [T]type Grid [Row * Col]type BorderedGrid [Row + Grid + Row]type BorderedRow [Cell + Row + Cell]type NeighborRows [BorderedRow * 3]func Grid gameOfLife<T> (Grid grid) {// sandwich grid between two dummy zero border rowsborderRow = as<Row>(0)borderedGrid = borderRow & grid & borderRow// loop over all grid rows, rowShifter starts at first positionnewBorderedGrid = golLoopRows<T>(borderedGrid, all<Row>(1))// extract new grid from tail endreturn newBorderedGrid[BorderedGrid - Grid : Grid]}func BorderedGrid golLoopRows<T> (BorderedGrid grid, Row rowShifter) {// check if row shifter is donerowShifterIsDone = isZero[rowShifter[0]]return rowShifterIsDone ? grid : golProcessRows<T>(grid, rowShifter)}func BorderedGrid golProcessRows<T> (BorderedGrid grid, Row rowShifter) {// extract current row and neighbor rows// and sandwich them between dummy zero border cellsborderCell = as<Cell>(0)rows = borderCell & grid[Row * 0 : Row] & borderCell & borderCell & grid[Row * 1 : Row] & borderCell & borderCell & grid[Row * 2 : Row] & borderCell// loop over all row columns, colShifter starts at first positionnewRows = golLoopCols<T>(rows, all<Col>(1))// extract new row from tail of newRowsnewRow = newRows[NeighborRows - Row : Row]// shift grid one row and append new row at end.// when done iterating (shifter runs out) the// tail end of newGrid will hold the new gridnewGrid = grid[Row : BorderedGrid - Row] & newRow// one more row iteration donenewRowShifter = lshift<Row>(rowShifter)return golLoopRows<T>(newGrid, newRowShifter)}func NeighborRows golLoopCols<T> (NeighborRows rows, Col colShifter) {// check if col shifter is donecolShifterIsDone = isZero[colShifter[0]]return colShifterIsDone ? rows : golProcessCols<T>(rows, colShifter)}func NeighborRows golProcessCols<T> (NeighborRows rows, Col colShifter) {// calculate number of alive neighbours for current cellalive0 = binSum[0, 0, rows[0 * BorderedRow + 0]]alive1 = binSum[alive0[0], alive0[1], rows[0 * BorderedRow + 1]]alive2 = binSum[alive1[0], alive1[1], rows[0 * BorderedRow + 2]]alive3 = binSum[alive2[0], alive2[1], rows[1 * BorderedRow + 0]]alive5 = binSum[alive3[0], alive3[1], rows[1 * BorderedRow + 2]]alive6 = binSum[alive5[0], alive5[1], rows[2 * BorderedRow + 0]]alive7 = binSum[alive6[0], alive6[1], rows[2 * BorderedRow + 1]]alive8 = binSum[alive7[0], alive7[1], rows[2 * BorderedRow + 2]]// determine new cell state for current cellnewCell = newCellState[alive8[0], alive8[1], rows[1 * BorderedRow + 1]]// shift rows 1 cell and append new cell at end.// when done iterating (shifter runs out) the tail// end of newRows will hold the new row of cellsnewRows = rows[Cell : NeighborRows - Cell] & newCell// one more col iteration donenewColShifter = lshift<Col>(colShifter)return golLoopCols<T>(newRows, newColShifter)}}

We use a trick here to determine the number of iterations in a loop. We set a shifter parameter of the same size as a row or column toall(1). We now shift this parameter at each iteration to the left. As long as we’re not done the first trit will contain a one. The moment we’re done we have successively shifted out all the ones and are left with zeroes, so the first trit will be a zero. This way, we only need to check a single trit instead of the entire shifter value, and instead of doing a much more costly decrement operation we use a cheap shift operation.

Note how we separate the loop control mechanism from the loop contents by using separate functions. This is a good practice to keep the functions simple and clear. It does not matter for the quality and speed of the generated code anyway.

Another optimization we chose to implement is that, because we are only interested in the direct neighbors of a cell, we don’t pass the entire game grid around constantly, but only the rows that contain the direct neighbors of the current row we operate on.

Now that we can use Qupla to generate the next generation grid from an input grid it is time to start putting things together with EEE.

The way that we integrate a function as an entity in EEE with Qupla is by wrapping that function in another function that joins and/or affects specific environments. It may sound like an unnecessary extra step to wrap a function within a function, but in this way we are decoupling the functionality of the function implementation from its integration as a function entity within EEE. That in turn means that we can use the same function (which could even be derived from a template) in other function entities without change.   

type GolSize [81]type GolGrid [GolSize * GolSize]func GolGrid golGen(GolGrid grid) {join GolGenaffect GolViewreturn gameOfLife<GolSize>(grid)}

In this case we define the grid size for GoL to be 81x81. We also define a GolGridtype that will contain the game grid and that we can send around as effect data. Now all we need to do is create an entity function golGen()that joins the GolGenenvironment so that it will receive game grids from the Game Of Life Entity that we defined earlier whenever the user right-clicks the view. The golGen()entity function calls the game Of Life () function version for the correct size of the game grid and the result will affect theGolViewenvironment. This in turn will cause the Game Of Life Entity to receive the new generation of the game grid and display it.  

So to recap, this simple example has 2 entity components that interact with each other through 2 separate environments:  

  1. Any 81x81 grid that is sent to the GolViewenvironment will be displayed somehow.
  2. Any 81x81 grid that is sent to the GolGenenvironment will cause the next generation of the grid to be calculated and displayed somehow.

The 2 entities that work together are:

  1. The Java Game Of Life Entity that joins the GolViewenvironment to display any grid that is received from that environment in its view.
  2. The QuplagolGen()function entity that joins theGolGenenvironment to calculate the next generation of the grid.

The effects being sent by the entities are:

  1. The Java Game Of Life Entitys ends any grid it wants to be displayed to the GolViewenvironment, and sends any grid it wants to use as basis for a new generation to the GolGenenvironment.
  2. The QuplagolGen()function entity sends any new generation grid it has calculated to theGolViewenvironment to be displayed.

You can see all this in action when you run the GameOfLife demo that we have provided with the Qupla interpreter.  

We introduced the Qubic Supervisor and how it provides the Environment, Entity, Effect event model as defined by the QCM that allows application components to communicate with each other in intricate ways. We then showed how to integrate a Qupla function into the EEE model and next proceeded to implement Conway’s Game of Life as a simple Proof of Concept example application to demonstrate how it all works together.

In the next part of this series we will explore in what kinds of interesting ways we can expand on this simple Proof of Concept example.

Follow us on our official channels for the latest updates:
Discord | Twitter | LinkedIn | Instagram | YouTube |

Tags

IOTA Foundation

Official posts from the IOTA Foundation, and migrated posts from old platforms.

Recommended for you

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.