Dataflow Graphs as Matrices
and Programming with Higher-order Matrix Elements

arXiv:1601.01050v1 [cs.PL] 6 Jan 2016

Michael Bukatin1 and Steve Matthews2
1 Nokia Corporation
Burlington, Massachusetts, USA
bukatin@cs.brandeis.edu
2 Department of Computer Science
University of Warwick
Coventry, UK
Steve.Matthews@warwick.ac.uk

Abstract
We consider dataflow architecture for two classes of computations which admit taking linear combinations of execution runs: probabilistic sampling and generalized animation. We improve the earlier
technique of almost continuous program transformations by adopting a discipline of bipartite graphs
linking nodes obtained via general transformations and nodes obtained via linear transformations
which makes it possible to develop and evolve dataflow programs over these classes of computations by continuous program transformations. The use of bipartite graphs allows us to represent the
dataflow programs from this class as matrices of real numbers and evolve and modify programs by
continuous change of these numbers.
We develop a formalism for higher-order dataflow programming for this class of dataflow graphs
based on the higher-order matrix elements. Some of our software experiments are briefly discussed.

1

Introduction

Because probabilistic sampling and generalized animation are both stream-based, dataflow programming is a natural framework for this situation. Earlier we were able to leverage the ability to take linear
combinations of execution runs to obtain the notion of almost continuous transformation of dataflow
programs [1].
There were three main sources of benign discontinuities in [1]: addition of new subgraphs via an
operation of limited deep copy, insertion of a new vertex and an edge during the first stage of S-insert,
and insertion of an edge during the second stage of S-insert.
We now allow to decorate subgraphs with weights and require that new subgraphs created by limited
deep copy appear initially with zero weight subject to subsequent continuous evolution.
We also introduce the discipline of arranging and linking vertices as a bipartite graph, namely that
general transforms of fixed arity must point only at linear transforms of unlimited arity, and vice versa.
This allows to eliminate the benign discontinuities mentioned above and obtain continuous program
transformations.

1.1

Dataflow Graphs as Matrices

It is convenient to have a situation where for any trajectory of program development or evolution all
parts of the program which might emerge preexist in a silent way.
The discipline of bipartite graphs actually makes this possible. We fix a particular signature by
taking a finite number of operations, each with its own fixed finite non-negative arity.
1

Dataflow Graphs as Matrices

Bukatin and Matthews

We take a countable number of copies of each template operation from the signature. Then we have
a countable set of inputs of those operations, Y j , and a countable set of their outputs, Xi .
Associate with each Y j a linear combination of all Xi with real coefficients ai j . We require that no
more than finite number of elements of the matrix (ai j ) are nonzero.
We often impose additional conditions, e.g. we often require that all ai j are nonnegative, and that
the sum of elements ai j associated with a particular matrix column Y j does not exceed 1.
Thus we have a countable-sized program, namely a countable dataflow graph, all but a finite part of
which is suppressed by zero coefficients. Any finite dataflow graph over a particular signature can be
embedded into a universal countable dataflow graph over this signature in this fashion.
Hence we represent programs over a fixed signature as countable-sized real-valued matrices with no
more than finite number of nonzero elements, and any program evolution would be a trajectory in this
space of matrices.

1.2

Multiple Types of Data Streams

Originally this construction was envisioned for the situation when each node Xi and Y j has a data stream
of the same type, and all these streams are equipped with the same meaningful addition operation [1].
The most important case here is when these are streams of real numbers which can be considered as
one-point generalized animations.
However, we might want to consider situations when there are multiple stream types associated with
nodes. Consider a situation when Y j and Xi are of different types. If ai j = 0, this is fine, because then
ai j · Xi does not affect Y j . If there is a default adapter Ti j between these types, then other values of ai j are
allowed, and ai j · Ti j (Xi ) is contributed to the sum. Otherwise the condition ai j = 0 has to be enforced
(ai j are clamped at zero).

1.3

Multiple Types of Addition

One might want to also consider a situation where more than one meaningful addition operation is
possible within the same program (e.g. point-wise addition of generalized animations and stochastic
sum of the streams of probabilistic samples).
(Note that these additions are different from template operations: additions have unlimited arity and
map infinite tuples of X’s to Y ’s, and template operations have finite fixed nonnegative arity and map
finite tuples of Y ’s to X’s.)
In the case of multiple types of addition, each input Y j of a template operation from the signature
needs to be marked with the type of the addition operation it uses. If necessary, similar template operations with different addition types should be included in the signature separately.
One would typically include an identity transform for every type of data stream and for every type
of addition applicable to this particular type of data stream in order to provide a capability to group the
sums hierarchically.

1.4

String-based Indices

Rather than indexing our countable sets {Xi } and {Y j } with numbers we are going to fix an alphabet
and to index them with strings from that alphabet. Of course, letters can be considered as digits in an
appropriate base, and strings as the corresponding natural numbers, but by indexing with strings we
are trying to de-emphasize the order associated with this natural-numbers-based interpretation and to
encourage an implementation of sparse arrays based on dictionaries (hash tables), with the expectation
that zero elements of arrays and matrices would typically be omitted from their respective dictionaries.
2

Dataflow Graphs as Matrices

Bukatin and Matthews

In order to maintain our convention that the association between a particular X j and its template operation is fixed, and that the association between X j and its corresponding arguments Yk1 , . . . ,Ykn j (n j >= 0)
is fixed and that all flexibility is concentrated solely in the values ai j we adopt the following naming
conventions.
We call a multiset (bag) of strings prefix-free if none of the strings in that multiset is a prefix of
another string in that multiset. (Note that a prefix-free multiset cannot have multiple occurrences of the
same string.) All template operations are given string names in such a way that the multiset consisting
of all these names and the string ′ arg′ is prefix-free. A node Y j is indexed with a string j which starts
with the name of the template operation associated with this node. We say that the string j is the name
of Y j . A node Xi which is one of the arguments for Y j is indexed with the string i which is obtained by
concatenating the prefix ′ arg1 ′ (′ arg2 ′ etc.) with the name of Y j . We say that the string i is the name of
Xi .

1.5

Higher-order Programming

Because matrices, their columns, and their elements are vectors themselves, this is a platform with a
variety of opportinuties to create techniques for higher-order programming.
In this text we focus on one particular avenue for doing so, and this approach is centered around
making elements ai j higher-order (see Section 2).
To quote from Section 1.1 of [2] “A lot of expressive power of this architecture comes from the
ability to have non-standard secondary structures on the set of points. Points can be associated with
vertices or edges of a graph, grammar rules, etc. One should be able to formulate mechanisms of
higher-order animation programming via variable illumination of elements of such structures.”
What is being done in the present paper is an instance of this approach.
A more precise mathematical description of the way this kind of computational engine functions is
in Section 3.
Our first series of exercises in matrix-based dataflow programming which have been open-sourced
simultaneously with the release of this preprint is described in Section 4.

2
2.1

Higher-order Matrix Elements
Degrees of Order

Here we classify varieties of ai j .
2.1.1 Not Properly Higher-order Elements
A not properly higher-order element ai j is not associated with a stream of any particular node Xk .
Zero elements (zero-order). These coefficients are zero and are not typically included in the dictionaries implementing the matrix or its columns.
First-order elements. Constant elements of the matrix (ai j ) are called first-order elements.
Variable elements (first-and-a-half order, sesquialteral-order elements). Elements of the matrix
(ai j ) which vary with time belong to this class. Our exercises in higher-order dataflow have belonged to
this class so far.
3

Dataflow Graphs as Matrices

Bukatin and Matthews

2.1.2 Properly Higher-order Elements
A properly higher-order element is associated with a datastream of a particular node Xk . The three types
above are still representable with higher-order elements. When a node is not turned on (and typically is
not in the appropriate dictionary), this is the case of zero-order element. When a node is constant value
with no arguments, this is the case of first-order matrix element. When a node is a variable stream, but
does not have argument nodes (so we are talking about a predefined/external variable stream), this is the
case of sesquialteral-order element.
Specialized higher-order elements. When a node Xk is computed by a template operation with at least
one argument, this is the case of a higher-order element. We call it specialized, because the operation
which computes this element is fixed, although it can be controlled via its argument(s). Evaluation of
such an operation is immediately effective, i.e. the newly computed coefficient is then immediately used
to compute the appropriate linear combination.
Fully higher-order elements. In this case the node Xk is computed by a template operation which is
the identity transform (one of the identity transforms, if multiple types of addition of streams of reals are
included in the signature). In this case, the value in question can be computed in a very flexible manner
from any linear combination of any transformations. However, the value is essentially computed on
the “downswing” using the previous values of (ai j ), and becomes the new effective value of the matrix
only after the identity transform is applied to it. So if one needs to implement changing the ai j via a
particular specialized template operation, a one-cycle delay is involved before the new value of ai j goes
via a linear combination and via an identity transform and becomes effective.

2.2

Embedding the Set of Matrix Coefficient Indices into the Set of Column Indices

An interesting question is whether one can have all matrix elements to be properly higher-order elements. The answer is “yes”, and it is essentially based on the countability of the union of countable sets.
This countability allows us to take the set of indices of matrix coefficients, (i j), and embed it into the
set of indices of matrix columns, j.
Here we are going to give an example of such an embedding which is sufficiently detailed to enable
computer implementation.
Without properly higher-order matrix elements, it was possible to avoid giving unique names for
matrix elements. For example, one could represent matrix columns as separate dictionaries and then
just use the row names for matrix elements, like we do in the example of Section 4.
With properly higher-order matrix elements one needs unique names for matrix elements. We start
with the naming scheme for columns and rows given in Section 1.4 and given the name N j for column j and the name Mi for row i, we define the name for the matrix element (i j) as concatenation
′ (′ +N +′ )#(′ +M +′ )′ . Now we should just reserve parentheses for the use within the names of matrix
j
i
elements only, but not within the “originally present names”, and this should be enough to avoid the
name clashes.

3

A More Precise Description of the Abstract Machine

We only describe the machine for the situation where all nodes are streams of reals, and where one kind
of addition operation exists with the sum being component-wise addition. It is not difficult to generalize
appropriately.
4

Dataflow Graphs as Matrices

Bukatin and Matthews

Define an alphabet Σ which does not contain parentheses and the number sign, ′ ()#′ .
Denote the set of all finite strings over Σ as Σ∗ .
Define an operation as a tuple F containing name (a string NF ∈ Σ∗ ), arity (a non-negative integer
AF ), and a mathematical function fF : RAF → R (if AF is zero, fF is simply a real number).
Define a signature as a finite set of operations, S = {F1, . . . , Fn }.
We require that the multiset {NF1 , . . . , NFn ,′ arg′ } is prefix-free per Section 1.4.
We take F1 to be the identity operation, h′ id ′ , 1, x 7→ xi.

3.1

Abstract Machine Without Properly Higher-order Matrix Elements

The first case we consider is the case of sesquialteral-order matrix elements, which will be further
illustrated by the example in Section 4.
We introduce the partially defined map Op from Σ∗ to S (operations) and two partially defined maps
X and Y from Σ∗ to N → R (data streams).
We denote string concatenation with + and string representation of a non-negative integer k as str(k).
For w ∈ Σ∗ and for every Fm ∈ S introduce i = NFm +′ ′ + w. For all such i, Op(i) and X(i) (denoted
as Xi ) are defined and Op(i) = Fm .
For all such i, for all k ∈ {1, . . . , AFm }, introduce j = ′ arg′ + str(k) +′ ′ + i. For all such j, Y ( j)
(denoted as Y j ) is defined.
Now we have a dataflow graph representing the machine, and we need to define the values of data
streams N → R associated with graph nodes Xi and Y j , which will define how the machine works.
Time starts with value 0 and increases by 1 at each machine step. For every i and j defined above
there is a stream of values N → R associated with ai j . Given that we are considering the case of
sesquialteral-order matrix elements, we assume that streams associated with ai j are external to the program and are just generated by their externally programmed generators.
At time 0 we start with all Xi and Y j being the streams of one element, which equals to 0 for all
those streams. The values of ai j at the moment 0 are not important at this level of consideration, because we only give a mathematical definition in this section and ignore the question of sparseness as an
implementation detail (of course, nothing would even fit a finite machine without this implementation
detail).
Then given streams Xi , Y j , and ai j of length t, here is how the components t + 1 are defined (that
is, computed by the abstract machine; so this is a definition by induction with respect to time, and this
definition describes how the machine works).
Step 1. First, for all i, the value of Xi at time t + 1 is computed as follows. One considers Op(i), and
for all k ∈ {1, . . ., AOp(i) } and jk = ′ arg′ + str(k) +′ ′ + i one takes the value y jk as being the value of the
).
stream Y jk at moment t. The value of Xi at time t +1 then is computed (defined) as fOp(i) (y j1 , . . . , y jA
Op(i)

Step 2. Then the values of streams corresponding to ai j at the moment t + 1 are externally generated.
The condition that only a finite number of those are different from 0 at the moment t + 1 is observed.
Step 3. Finally, for all j, the values of streams associated with Y j at the moment t + 1 are computed as
the linear combinations Σi ai j · Xi , where ai j and Xi are the values of the corresponding data streams at
the moment t + 1.
5

Dataflow Graphs as Matrices

3.2

Bukatin and Matthews

A More Abstract View

Here is a more abstract way to describe what is going on in the previous subsection.
There are two (in general, countably dimensional) vector spaces X and Y . There is a fixed non-linear
function F : Y → X induced by the signature. There is a family of linear transformations Lt : X → Y
parametrized with time (this corresponds to sesquialteral-order of L).
We define streams of vectors xt , yt from X,Y parametrized with time by induction over time. We
define x0 and y0 to be zero vectors and L0 is irrelevant.
At time t + 1, first we take xt+1 = F(y(t)), then we note the current Lt+1 and take yt+1 = Lt+1 (xt+1 ).
In the subsection which follows we use the embedding from Section 2.2 to incorporate L into X.
Then at time t + 1 we take xt+1 = F(y(t)) and among other things this yields Lt+1 . Then we take
yt+1 = Lt+1 (xt+1 ).
We occasionally parametrize F as Ft as well, to allow the dynamic tuning of the system and to
account for the stochastic factors in randomized template operations.

3.3

Abstract Machine with all Fully Higher-order Matrix Elements

Here we modify the construction of Section 3.1 in order to deliver what was promised at the end of the
previous subsection.We start with sets of names I = {i} and J = { j} defined in Section 3.1.
Then we define I0 = I and J0 = J, and organize the induction as follows.
Given In and Jn we first use the scheme from Section 2.2 to define set of names of matrix elements:
An+1 = {′ (′ + j+′ )#(′ +i+′ )′ |i ∈ In , j ∈ Jn }.
S
Then we use the fact that our signature has the identity operation and define In+1 = I {′ id ′ + a|a ∈
S ′
An+1 } and Jn+1 = J { arg1 id ′ + a|a ∈ An+1 }.
S
S
Now consider the limit of this process, I∞ = In and J∞ = Jn .
Then this limits is the fixed point of this process, namely that if we define
S
S
A∞ = {′ (′ + j+′ )#(′ +i+′ )′ |i ∈ I∞ , j ∈ J∞ }, then I∞ = I {′ id ′ + a|a ∈ A∞ } and J∞ = J {′ arg1 id ′ + a|a ∈
A∞ }.
Now the steps at the end of Section 3.1 are modified as follows. Performing Step 1 yields values
of streams corresponding to ai j at the moment t + 1. If only finite number of those values are different
from 0 at the moment t, then only a finite number of them would be different from 0 at the moment t + 1
(for the detailed explanation of the reasons for that see the last paragraph of the next subsection).
Then we can go ahead and perform Step 3.

3.4

Sparseness Considerations

The discussion of the abstract machines would not be complete without discussing how to keep the
amount of computations at each step finite (as, if possible, minimal).
For the setup of Section 3.1, the requirement is that if a matrix element ai j is nonzero, then its linear
combination needs to be evaluated and the template operation computing Xi and the template operation
using Y j as an argument both need to be evaluated, so the appropriate nodes should be included into the
dictionaries in question. When for a template operation with inputs Y1 , . . . ,Yk and output Xi all matrix
elements related to nodes Y1 , . . . ,Yk and output Xi are zero, it is not recommended to evaluate such a
template operation or to include the nodes in question into dictionaries (although doing so is legal).
This means that when ai j becomes nonzero for the first time, the Y j node and the template operation
using this node as an input together with the other vertices of this template operation must be added to
the appropriate dictionaries, if it is not already there. Similarly, the Xi node and the template operation
computing it together with the other vertices of that template operation must be added to the appropriate
dictionaries, if it is not already there, and moreover, it needs to be retroactively computed (by evaluating
6

Dataflow Graphs as Matrices

Bukatin and Matthews

the corresponding template operation with zero values of its arguments) before the linear combination
using ai j can be evaluated.
The same considerations are valid for the setup of Section 3.3. At any given moment of time we
only have a finite number of operations computing ai j being in the dictionaries and subject to being
evaluated. So only finite number of them might become nonzero for the first time at any given time
moment. Hence no more than a finite number of new nodes need to be added to the dictionaries on each
time step.

4

A Simple Example

This architecture is applicable to probabilistic sampling and to generalized animation. We created an
open source software prototype demonstrating the use of those techniques for streams of real numbers
implementing a family of continuous cellular automata.
The software and associated videos have been released simultaneously with this preprint as
aug 20 15 experiment in the Project Fluid repository [3].
Note that we cannot make these video previews quite faithful; video compression software introduces some distortion at the initial stage of uploading a video, then it notices the problems with quality
and offers to automatically fix lighting, the overall result might be worse in some aspects and better in
some other aspects than the video natively produced by the software.
This is an example of a situation when a matrix-based dataflow program is used in combination
with other software. In this particular case, the video output from the dataflow program is being passed
through an external lighting-enhancing software.
The set of template operations for this series of experiments is very simple: zero-arity constants,
black and white (-1 and 1), and a unary randomized propagator, copying the value of its input Y j to its
output Xi with probability p (a typical value of which in this series of experiments is 0.995) and setting
the output to zero otherwise. The setup is essentially that of Section 3.1, except that we allow several
copies of a template operation to share an input when convenient (mathematically this is equivalent to
constraining several columns of a matrix to be the same).
In this series of experiments we use the dynamic nature of matrix elements very sparingly, first
having the weights concentrated on the output of the constants (initialization phase) and then switching it
(continuously, or, as in this series of experiments, abruptly) to the output of the randomized propagators
forming a structure determining the connectivity of the continuous cellular automaton in question. This
architecture also allows to continuously morph between a variety of connectivity structures, but we have
left this as a simple exercise to the reader.
We are observing a variety of emerging Turing structures with interesting dynamics in this series of
experiments, depending mostly on the connectivity pattern, and also on the initialization configuration.
In the spirit of non-equilibrium thermodynamics, even when one starts with a uniform initial pattern
(all black or all white), the structures first emerge driven by the randomized propagators and by the
connectivity pattern, and then fade out to gray (zero value, the thermodynamic equilibrium). If one
includes the amplification during the visualization stage (scaling the brightness of the image so that
the maximal absolute value of a rendered point reaches 1), then one can observe that the meaningful
fine structures of the dynamic patterns tend to persist indefinitely (in some cases the main motive is
preserved, in other cases the pattern is shifting and evolving unpredictably).
See the Fluid repository for further details.
7

Dataflow Graphs as Matrices

4.1

Bukatin and Matthews

An Example with Properly Higher-order Matrix Elements

The aug 24 15 experiment implements the same example using fully higher-order elements (all but
two matrix elements in that experiment are fully higher-order, while two of its elements are not properly
higher-order, and their change is controlled from the outside).
This experiment also features pause/resume facility controlled by the mouse key and the space bar,
improved brightness amplification, and an adjustment mechanism to stabilize the values and prevent
their relaxation to zero.
We recommend that the reader uses this experiment to further explore the system.

5

Conclusion

This architecture allows us to evolve dataflow programs in continuous fashion while those evolving
programs are running. This makes it possible to sample continuous trajectories in the space of dataflow
programs, in addition to the usual practices of sampling the syntax trees of programs.
The representation of programs as matrices of real numbers makes the task of program learning
more similar to the task of machine learning for more narrow and conventional classes of models.
One way to introduce some higher-order mechanisms in dataflow programming (and in neural networks) is via letting any particular data stream to propagate along multiple directions in the graph, and to
dynamically control the actual directions of propagation by setting the multipliers along some of those
paths to zero.
A somewhat unexpected result of the present preprint is that this particular higher-order mechanism
seems to be universal: all higher-order programming for a given class of dataflow graphs over datastreams with linear combinations of execution runs built on top of a fixed signature of template operations
seems to be expressible via setting multipliers along the paths of data propagation (in particular, setting
all but the finite number of them to zero).
Acknowledgments. We would like to thank Ralph Kopperman, Lena Nekludova, and Josh Tenenbaum for helpful discussions and to acknowledge collaboration with Lena Nekludova on software experiments.

References
[1] M. Bukatin and S. Matthews. Almost continuous transformations of software and higher-order dataflow programming, Preprint (2015). http://www.cs.brandeis.edu/~ bukatin/HigherOrderDataFlow.pdf.
[2] M. Bukatin and S. Matthews. Linear models of computation and program learning, Preprint (2015).
http://www.cs.brandeis.edu/~ bukatin/LinearModelsProgramLearning.pdf.
[3] Fluid. Project “Fluid” github repository, 2015. https://github.com/anhinga/fluid.

8

