In the paper, we present foundations of a new object-oriented programming language for Physarum polycephalum computing. Both, theoretical foundations and assumptions for a language speci cation are considered. Physarum polycephalum is a one-cell organism. In the phase of plasmodium, its behavior can be regarded as a biological substrate that implements the Kolmogorov-Uspensky machine which is the most generalized and nature-oriented version of a mathematical machine. The proposed language will be used for developing programs for Physarum polycephalum by the spatial con guration of stationary nodes (inputs).
Physarum polycephalum is a one-cell organism belonging to Physarales,
subclass Myxogastromycetidae, class Myxomycetes and division Myxostelida. In
the phase of plasmodium, it looks like an amorphous giant amoeba with
networks of protoplasmic tubes. It feeds on bacteria, spores and other microbial
creatures (substances with potentially high nutritional value) by propagating
towards sources of food particles and occupying these sources. A network of
protoplasmic tubes connects the masses of protoplasm. As a result, the plasmodium
develops a planar graph, where the food sources or pheromones are considered
as nodes and protoplasmic tubes as edges. This fact allows us to claim that
plasmodium behavior can be regarded as a biological implementation of
KolmogorovUspensky machines [
One of the paths of our research in this area concerns creating a new programming language that simulates plasmodium behavior. The following main tasks can be distinguished in the rst step of this path: 1. Constructing the programming language on the basis of storage machines.
The static storage structure is represented by a two-dimensional con guration of point-wise sources of chemo-attractants and chemo-repellents. 2. Constructing the programming language on the basis of the KolmogorovUspensky machine (KUM), where edges are represented by protoplasmic strands. 3. Developing programs represented by the spatial con guration of stationary nodes (treated as inputs of the programs). Outputs of the programs may be recorded optically.
The rest of the paper is organized as follows. In Section 3, we give foundations of speci cation of a new language. Assumptions of speci cation are preceded by a theoretical background of Physarum automata (see Section 2). 2
Plasmodium's active zones of growing pseudopodia interact concurrently and in a parallel manner. At these active zones, three basic operations stimulated by nutrients and some other conditions can be observed: fusion, multiplication, and direction operations. The fusion F use means that two active zones A1 and A2 both produce new active zone A3 (i.e. there is a collision of the active zones). The multiplication M ult means that the active zone A1 splits into two independent active zones A2 and A3 propagating along their own trajectories. The direction Direct means that the active zone A is not translated to a source of nutrients but to a domain of an active space with a certain initial velocity vector v. These operations, F use, M ult, Direct, can be determined by the following stimuli: { The set of attractants fN1; N2; : : :g. Attractants are sources of nutrients or pheromones, on which the plasmodium feeds. Each attractant N is characterized by its position and intensity. It is a function from one active zone to another. { The set of repellents fR1; R2; : : :g. Plasmodium of Physarum avoids light and some thermo- and salt-based conditions. Thus, domains of high illumination (or high grade of salt) are repellents such that each repellent R is characterized by its position and intensity, or force of repelling. In other words, each repellent R is a function from one active zone to another.
Such plasmodium behavior can be presented as an implementation of some abstract automata. Recall that a cellular automaton is a 4-tuple A = hZd; S; u; f i, where (1) d 2 N is a number of dimensions, and the members of Zd are referred to as cells, (2) S is a nite set of elements called the states of an automaton A, the members of Zd take their values in S, (3) u Zd n f0gd is a nite ordered set of n elements, u(x) is said to be a neighborhood for the cell x, (4) f : Sn+1 ! S that is f is the local transition function (or local rule). As we see an automaton is considered on the endless d-dimensional space of integers, i.e., on Zd. Discrete time is introduced for t = 0; 1; 2; : : : For instance, the cell x at time t is denoted by xt. Each automaton calculates its next state depending on states of its closest neighbors. The cellular automata thus represent locality of physics of information and massive-parallelism in space-time dynamics of natural systems.
In abstract cellular automata, cells are physically identical. They can di er just by one of the possible states of S. In case of Physarum, cells can possess di erent topological properties. This depends on intensity of chemo-attractants and chemo-repellents. The intensity entails the natural or geographical neighborhood of the set's elements in accordance with the spreading of attractants or repellents. As a result, we obtain Voronoi cells. Let us de ne what they are mathematically. Let P be a nonempty nite set of planar points and jPj = n. For points p = (p1; p2) and x = (x1; x2) let d(p; x) = p(p1 x1)2 + (p2 x2)2 denote their Euclidean distance. A planar Voronoi diagram of the set P is a partition of the plane into cells, such that for any element of P, a cell corresponding to a unique point p contains all those points of the plane which are closer to p in respect to the distance d than to any other node of P. A unique region vor(p) =
\ m2P;m6=p
fz 2 R2: d(p; z) < d(m; z)g assigned to a point p is called a Voronoi cell of the point p. Within one Voronoi cell a reagent has a full power to attract or repel the plasmodium. The distance d is de ned by the intensity of reagent spreading. A reagent attracts or repels the plasmodium and the distance, on which it is possible, corresponds to the elements of a given planar set P. When two spreading wave fronts of the two reagents meet, this means that on the board of meeting the plasmodium cannot choose its one further direction and splits (see Figure 2).
The direction of protoplasmic tubes is de ned by concentrations of chemoattractants or chemo-repellents in Voronoi neighborhood. Each dynamics of protoplasmic tube can be characterized at time step t by its current position xt and the angle t. Let be an alphabet, k a natural number. We say that a tree is ( ; k)-tree, if one of nodes is designated and is called root and all edges are directed. Each node is labeled by one of the signs of and each edge from the same node is labeled by di erent numbers f1; : : : ; kg (so, each node has not more than k edges). We see that by this de nition of ( ; k)-tree, the pseudopodia growing from the one active zone, where all attractants are labeled by signs of , and protoplasmic tubes are labeled by numbers of f1; : : : ; kg, is a ( ; k)-tree.
Let r be the maximal possible path of ( ; k)-tree. We can always design Physarum Voronoi diagrams (using attractants and repellents) for inducing different numbers r and appropriate local properties. The ( ; k)-tree limited by r is called ( ; k)-complex. Programming in Kolmogorov-Uspensky machines is considered as transforming one ( ; k)-complex to another with the same r by changing nodes and edges using some rules. In case of Physarum implementation of Kolmogorov-Uspensky machines programming is presented as transforming one Voronoi diagram into another with the same r by dynamics of Physarum (e.g. when some attractants become eaten by Physarum).
The simpler version of the Kolmogorov-Uspensky machines is presented by Schonhage's storage modi cation machines. 2.3
Physarum Schonhage's Storage Modi cation Machines These machines consist of a xed alphabet of input symbols, , and a mutable directed graph with its arrows labeled by . The set of nodes X, identi ed with attractants is nite, as well. One xed node a 2 X is identi ed as a distinguished center node of the graph. It is the rst active zone of growing pseudopodia. The distinguished node a has an edge x such that x (a) = a for all 2 . That is, all pointers from the distinguished center node point back to the center node. Each 2 de nes a mapping x from X to X. Each word of symbols in the alphabet is a pathway through the machine from the distinguished center node.
Schonhage's machine modi es storage by adding new elements and redirecting edges. Its basic instructions are as follows: { Creating a new node: new W . The machine reads the word W , following the path represented by the symbols of W until the machine comes to the last symbol in the word. It causes a new node y, associated with the last symbol of W , to be created and added to X. Adding a new node means adding a new attractant within a Physarum Voronoi diagram. { A pointer redirection: set W to V . This instruction redirects an edge from the path represented by word W to a former node that represents word V . It means that we can remove some attractants within a Physarum Voronoi diagram. { A conditional instruction: if V = W then instruction Z. It compares two paths represented by words W and V and if they end at the same node, then we jump to instruction Z, otherwise we continue. This instruction serves to add edges between existing nodes. It corresponds to the splitting or fusion of Physarum. 3
Foundations of Speci cation of an Object-Oriented
Programming Language for Physarum Polycephalum
The plasmodium of Physarum polycephalum functions as a parallel amorphous
computer with parallel inputs and parallel outputs. Data are represented by
spatial con gurations of sources of nutrients. Therefore, we can generally
assume that a program of computation is coded via con gurations of repellents
and attractants. The plasmodium of Physarum polycephalum is a computing
substrate. In [
In this section, we deal with foundations of speci cation of a new
objectoriented programming language for Physarum polycephalum computing on the
basis of using a Voronoi diagram for implementing Kolmogorov-Uspensky
machines. In an object-oriented programming (OOP) paradigm, concepts are
represented as objects that have data elds (properties describing objects) and
associated procedures known as methods. The OOP approach assumes that properties
describing objects are not directly accessible by the rest of the program. They are
accessed by calling special methods, which are bundled in with the properties.
This approach has been implemented in our new language. Moreover, we have
referred to conventions used in the JavaBeans API [
Our new language has been proposed as a prototype-based programming
language like, for example, Self [
The main objects identi ed in Physarum polycephalum computing are collected in Table 1. We assume that a computational space is divided into twodimensional computational layers on which Physarum polycephalum, as well as attractants and repellents, can be scattered. Our approach allows interaction between elements placed on di erent layers. This property enables us to use, in the future, the multi-agent paradigm in Physarum polycephalum computing. The user can de ne, in the computational space, as many computational layers as needed. For each layer, its size can be determined individually. We apply the point-wise con guration of elements scattered on the layers. Therefore, for each element (Physarum, attractant, repellent), its position can be determined using two integers (coordinates). As it was mentioned in Section 2, attractants and repellents are characterized by the property called intensity. This property plays an important role in creation of the Voronoi cells. For each attractant and repellent, the intensity is a fuzzy value from the interval [0; 1], where 1 denotes the maximal intensity, while 0 the minimal intensity, i.e., a total lack of impact of a given attractant or repellent on Physarum polycephalum. The force of attracting (repelling) of Physarum is a combination of intensity of attractants (repellents) and distances between plasmodium and attractants (repellents), respectively.
Let p = (p1; p2) and x = (x1; x2) be points on the layer where Physarum and attractant (repellent), respectively, are located. To create the Voronoi cells, we can use the following measure modyfying a distance, which is commonly used: f (p; x) =
1 "(x) p(p1 x1)2 + (p2 x2)2; where "(x) is the intensity of attractant (repellent) placed at x. It means that the Voronoi cells cover the force of attracting (repelling) of plasmodium instead of simple distances between it and attractants (repellents). In the current version of the language, the Voronoi cells are built within layers only.
Analogously to layers, the user can create and scatter on layers as many elements as needed.
Below, we present an exemplary fragment of a code in our language responsible for creating the layer and elements, setting individual properties of elements and scattering elements on the layer. l1=new Layer; p1=new Physarum; a1=new Attractant; a2=new Attractant; a3=new Attractant; a4=new Attractant; l1.add(p1); p1.setPosition(800,200); l1.add(a1); a1.setPosition(500,150); a1.setIntensity(0.7); l1.add(a2); a2.setPosition(500,350); a2.setIntensity(0.5); l1.add(a3); a3.setPosition(400,250); a3.setIntensity(0.6); l1.add(a4); a4.setPosition(600,250); a4.setIntensity(0.5);
For experiments with Physarum polycephalum computing, a specialized
computer tool (PhyChip Programming Platform) is being developed using the Java
environment. The tool consists of two main modules:
1. Code creation and compilation module. For generating the compiler of our
language, the Java Compiler Compiler (JavaCC) tool [
In Figure 3, we have shown the Voronoi cells generated in our computer tool for 4 attractants (a1, a2, a3, a4) with di erent intensity assigned to them, de ned in the exemplary program. Attractants are marked with dots whereas Physarum with a square. The measure de ned earlier has been used to create cells. It is easy to see that Physarum is attracted rst of all by the most right attractant. 4
In the paper, we have outlined theoretical foundations as well as assumptions
for a new object-oriented programming language for Physarum polycephalum
computing. The next mile steps in our research are the following: implementation
of operations based on the -calculus model [
Acknowledgments This research is being ful lled by the support of FP7-ICT-2011-8.