The article presents a markup domain-specific language (DSL) for concurrent programming. Runtime libraries and language extensions are the usual ways to implement parallel execution. However, their using often requires a special programming skill. The modern languages with build-in parallel constructs are more convenient for programming, but they are poorly integrated with existing high performance computing infrastructure. We propose a compromise solution which uses DSL together with C++ programming language. The article discusses syntax, programming model, and some practical applications of the language.
The Templet language is a domain-specific language (DSL). It is designed to be used
together with a sequential procedural or an object-oriented programming language.
The new property of the language is an implicit specification of the actor's
computation semantics with a marked serial code. The language detailed description first
appeared as arXiv preprint [
The article focuses on a design of the markup language. The design of the language
basically follows the concept of the language-oriented programming [
The second one is a programming model. We introduce a diffusive (with no locking)
programming model that describes concurrent activity as a message exchange
between parallel processes. They are activated by incoming messages. The channels
define message exchange protocols. The model avoids concurrent data access, hence
it is easier to use when multithreading. The model is a specialization of the actor
formalism [
The third concept is based on description of concurrent activity with sequential code. This method is derived from formal theories that consider parallel process as set of behaviors (sequences of system states and/or atomic actions). We simulate the sequences with random number generator.
The following paragraphs illustrate these concepts with syntax and code examples. The article ends with an overview of related works. The experimental preprocessor for the Templet language and code samples in marked C++ are available at http://github.com/templet-language. 1
To describe the syntax, an extended Backus-Naur Formalism called EBNF is used. The following EBNF rules describe the block structure of a module. The module here is a unit of code that can include one or several files. module = {base-language|user-block} module-scheme {base-language|user-block}. user-block = user-prefix base-language
user-postfix. module-scheme = scheme-prefix
{ channel | process } scheme-postfix.
The code of a module consists of the single module scheme section and multiple code sections in C++ language with highlighted user blocks. These sections are distinguished from the rest of the code by means of C++ comments. For example, the marked C++ code may look as follows. The blocks’ names according to the markup language syntax are shown on the right side. #include <runtime.h> /*templet$$include*/
#include <iostream> /*end*/ /*templet*
*hello<function>. *end*/ <-- base-language <-- user-prefix <-- base-language <-- user-postfix <-- scheme-prefix <-- module-scheme <-- scheme-postfix <-- base-language <-- user-prefix <-- base-language <-- user-postfix <-- base-language Lexical analyzer defines the boundaries of the blocks by signatures, recognizing specific sub-strings in a character stream. For example, the module scheme may be preceded by a combination of characters /*templet*, and finish by *end*/. User block prefixes include identifiers for binding the blocks with module scheme: /*templet$hello$*/ bound with *hello<function>. The module scheme defines a structure of the program skeleton and user blocks are extension points of the skeleton. The markup language implies a mapping algorithm. The mapping is a module transformation carried out by rewriting the module code. The mapping is applied only to a module with syntactically correct scheme. As a result of this transformation the code and the scheme becomes isomorphic meaning that the code can be reproduced from the scheme and vice versa. New user blocks may appear. Existing user blocks may move to new positions or turn into comments. 2
The module scheme includes definitions of the two DSL classes: channel and process. The channel describes communication, while the process describes data processing. Any DSL class inherits its behavior from BaseChannel or BaseProcess runtime classes. The classes should be implemented in a way that the following behavior is possible. class Channel: public BaseChannel{ public: // test whether the channel it accessible bool access_client(){...} // at client side bool access_server(){...} // at server side // client sends entire channel to server void send_client(){...} // server sends entire channel to client void send_server(){...} ... }; class Process: public BaseProcess{ public: // receive data on the channel virtual void recv(BaseChannel*); // bind a channel to the process as client bool bind_client(BaseChannel*){...} // .. or server bool bind_server(BaseChannel*){...} ... } The BaseChannel has the following behavior. The access to the channel alternately belongs to pair of processes called client and server. The client process has access right to the channel in the beginning of computations. The methods access_client() and access_server() allow client or server to check for access. The methods send_client() and send_server() can be used to grant access from client to server or from server to client respectively.
The BaseProcess has the following behavior. The methods bind_client() and bind_server() establish connection between a process (as a client or as a server) and a channel. The method recv() is called at the moment getting access to the channel. The channel is passed as recv() argument.
The implementation also carries out the rules below. If the process gets access to multiple channels, it takes several consecutive calls to recv() in random order. If some process sends the channel access to another process, the other process will sooner or later get the access. 3
The program implementation in C++ language should provide the opportunity for a non-deterministic performance. The non-determinism of program execution is simulated by means of pseudo-random numbers. void TempletProgram::run() { size_t rsize; // while message queue is not empty while(rsize=ready.size()){ //select random channel which //is currently sending message //then exclude this channel //from the message queue //and move it to not sending state int n=rand()%rsize; auto it=ready.begin()+n; BaseChannel*c=*it;ready.erase(it); c->sending=false; //extract the process to which the message //was sent from the channel //run message handling method recv() //for the channel and //pass the channel as //the argument to this method c->p->recv(c); }
} Appropriate runtime libraries are provided for truly parallel execution of a code. Some modifications to mapping algorithm may also be required. 4
This is a complete EBNF description of module scheme in the Templet language. channel = '~' ident [params]
['=' state {';' state}] '.'. state = ['+'] ident [ ('?'|'!') [rules] ]. rules = rule { '|' rule }. rule = ident { ',' ident } '->' ident. process = '*' ident [params] ['=' ((ports [';' actions])
| actions) ] '.'. ports = port {';' port}. port = ident ':' ident ('?'|'!')[(rules ['|' '->' ident]) |( '->' ident)]. actions = action {';' action}. action = ['+'] [ident ':'] disjunction ['->'
([ident] '|' ident) | ident]. disjunction = conjunction { '|' conjunction}. conjunction = call {'&' call}. call = ident '(' [args] ')'. args = ident ('?'|'!') ident
{',' ident ('?'|'!') ident }. params = '<' ident {',' ident} '>'.
For example, there is a program that checks the trigonometric identity sin2x+cos2x=1 in parallel. The process of Master class sends x values to working processes of Worker class via channels of Link class. The Master gets the squares of trigonometric functions and calculates their sum in return. The protocol Link to verify the trigonometric identity may be coded in Templet DSL like shown below. ~Link = +BEGIN ? ArgCos -> CALCCOS |
ArgSin -> CALCSIN; CALCCOS ! Cos2 -> END;
CALCSIN ! Sin2 -> END.
The Master and Worker processes for checking the trigonometric identity can be defined as follows. *Master = p1:Link ! Sin2 -> join; p2:Link ! Cos2 -> join; +fork(p1!ArgSin,p2!ArgCos);
join(p1?Sin2,p2?Cos2). *Worker = p : Link ? ArgSin -> sin2 | ArgCos -> cos2; sin2(p?ArgSin,p!Sin2); cos2(p?ArgCos,p!Cos2).
Any Templet program is a network of objects. Objects are instances of C++ classes generated from the DSL. These C++ classes are in turn derived from BaseChannel class or BaseProcess class. The network of objects is coded manually in C++. 5
The current implementation includes another three samples to illustrate the practical use of the Templet language for various applications.
The Gauss-Seidel method for solving the Laplace equation is the first one. This example illustrates the use of the language in the field of high performance scientific computing. It also shows how the Templet simulation runtime can help to predict program performance without an explicit mathematical model or parallel execution. An example from the field of linear algebra is the second one. This is an illustration of distributed matrix multiplication algorithm. It shows that the Templet implementation of the actor model is well suited both for shared and distributed parallel architectures. The business process model example is the third one. The Templet DSL can be used to model and analyze concurrency in non-technical systems, for example, in the area of business process modeling. We studied a business scenario written in a human language and composed a formal specification for the scenario in the Templet language. The static type analysis, debugging, and testing of the program were used to verify the correctness of the specification. In particular, we compared programmatically generated event sequences with expected sequences for the studied business process. This example illustrates that in our approach much of model verification is done by C++ compiler and the Templet runtime.
The experimental implementation of the domain-specific language toolkit showed the following benefits of our approach.
Additional language constructions are not required to explain the meaning of an
algorithm with concurrent control. This is similar to approach based on object-oriented
libraries STL [
More reliable protection against programming errors is provided. This feature is
compatible with modern concurrent programming languages Go [
Behavior of the Templet program can be investigated in more detail by means of problem-oriented debugger. The mapping algorithm can add code to provide information to the debugger. The performance prediction of a parallel program is also possible. Discrete event simulation library can easily replace standard execution mechanism for the performance analysis.
The markup language is a mean of skeleton programming and code reuse [
The markup language defines concurrent execution with sequential code. A number
of well-known [
The DSL language can be applied to different general-purpose programming
languages. It is compatible with a number of modern industrial process control software
development technologies [
Our research shows a practical interest of the DSL-based approach for parallel actororiented programming. We got a fully working but relatively compact implementation of the actor language. This implementation had been deployed online as a part of the web service TempletWeb (http://template.ssau.ru/templet).
The research was supported by the Ministry of Education and Science of the Russian Federation within the framework of the Program designed to increase the competitiveness of Samara National Research University among the world's leading scientific and educational centers over the period from 2013 till 2020. This work was partially supported by the RFBR grant 15-08-05934 A.