# MC Sharp

Paradigm Concurrent programming 2009 3.0 / 17 июля 2015 http://www.mcsharp.net/

MC# programming language is an extension of the C# language and is intended for developing of concurrent and distributed programs. A concurrent program is a program which is intended for running on multicore/multiprocessor machines with shared memory. A distributed program is a program for running on the network of (possibly, multicore/multiprocessor) machines with separate memories. The clusters and Grids are the examples of systems for running of distributed programs.

## Introduction

MC# programming language is based on the asynchronous parallel programming model which originally was introduced in the Polyphonic C# language (http://research.microsoft.com/en-us/um/people/nick/polyphony/). The given model proposes the high-level, concurrent constructions which turn the object-oriented С# language to parallel programming language. In particular, they provide all needed features which are required for parallel programming, namely, tools for

1. creating,
2. interaction (message passing) and
3. synchronizing

of concurrent processes. Such high-level constructs fit well into the object-oriented programming model and, in fact, free the programmer from the need to use the additional libraries (such as System.Threading library from .NET Framework, Microsoft Parallel Extensions for .NET and others). The mentioned above libraries have such shortcomings as, first of all, they introduce additional process-like notions as “thread” or “task”, and, secondly, they doesn’t support a distributed programming. In the given manual, novel constructs of MC# language are described and complete examples of their usage to develop concurrent and distributed programs are provided. The compilation and running rules for both types of programs can be found in “User’s Guide” which has been included into the install package of MC# programming system.

## Asynchronous methods

In any traditional object-oriented language, conventional methods are synchronous: the caller always waits until the callee is completed and only then continues its work. The one of the key features of MC# is the introduction of so called asynchronous methods in addition to conventional synchronous ones. Asynchronous (and also movable − see below) methods are the only way to create concurrent and distributed processes in MC# programs. (The traditional tools to create concurrent processes and threads are accessible in C# programs through library function calls). The general syntax of asynchronous method declaration in MC# is the following:

 modifiers async method_name ( arguments )
{
< method body >
}

Note that the keyword async defining a method as asynchronous is placed instead the return type of the method. Correspondingly, we have the following rule which defines the syntax of return type in MC# language:

 return_type ::= type | void | async | movable

So the keyword movable defining corresponding method is placed also instead of the return type. Declaring a method with async keyword means that given method will be running locally in a separate thread. The differences of async-method from conventional synchronous method are the following:

• async-method call completes almost immediately; i.e., after the call of it, a control is passing to the following statement without waiting of the former;
• async-methods never return a result (for interaction and message passing among them see Section 3 “Channels and handlers”).

By the rule of correct definition, async-methods in MC#

• may not have a static modifier
• never use a return statement
• ref, out and params modifiers can’t be applied to the formal parameters of such methods.

Example 1. The example below demonstrates the using of asynchronous methods in the concurrent program for matrix multiplication. The program is intended for running on two processors (its extension to arbitrary number of processors can be a simple exercise for the reader). An object of ManualResetEvent type serves as a tool to determine termination of asynchronous methods.

 using System;
public class MatrixMultiplier {
public static int N = 1000;
public static int count = 2;
public static void Main ( String[] args ) {
double[] a, b, c;
a = new double [ N, N ];
b = new double [ N, N ];
c = new double [ N, N ];
Random r = new Random();
for ( int i = 0; i < N; i++ )
for ( int j = 0; j < N; j++ ) {
a [ i, j ] = r.NextDouble();
b [ i, j ] = r.NextDouble();
c [ i, j ] = 0.0;
}
MatrixMultiplier mm = new MatrixMultiplier();
using ( ManualResetEvent mre = new ManualResetEvent ( false ) )
{
mm.multiply ( 0, N/2, a, b, c, mre );
mm.multiply ( N/2, N, a, b, c, mre );
mre.WaitOne();
}
}
public async multiply ( int from, int to, double[,] a, double[,] b, double[,] c, ManualResetEvent mre )
{
for ( int i = from; i < to; i++ )
for ( int j = 0; j < N; j++ )
for ( int k = 0; k < N; k++ )
c [ i, j ] += a [ i, k ] * b [ k, j ];
if ( Interlocked.Decrement ( ref count ) == 0 )
mre.Set()
}
}

Indeed, MC# language has its own high-level tools to support both an interaction of asynchronous methods (namely, data and signals transferring) and synchronization between them. Channels and handlers are such tools and they are considered in the next Section.

## Channels and handlers

Channels and channel message handlers (or, simply, handlers) are the tools to support an interaction between concurrent or distributed processes. The second role of them is to serve as a synchronization tool for the processes. Syntactically, channels and handlers are declared using the special constructs − the chords. For example, the channel sendInt for transferring single integers is declared along with corresponding handler getInt as

 handler getInt int() &amp; channel sendInt ( int x ) {
return x;
}

In general, the chords (and, correspondingly, channels and handlers) are declared in MC# programs according to the following syntactical rules:

 chord-declaration ::= [ handler-header &amp; ] channel-header
handler-header ::= attributes modifiers handler handler-name
return-type ( formal parameters )
channel-header ::= attributes modifiers channel channel-name
( formal parameters )

In above rules, the non-terminals body, attributes, modifiers, return-type and formalparameters are defined by C# standard syntactical rules. The non-terminals handlername and channel-name are the simple (non-qualified) identifiers. Channel and handler declarations are subject to the following restrictions:

1. channels and handlers cannot be defined as static
2. modifiers ref, out and params cannot be applied to formal parameters of channels and handlers
3. if a handler has defined with return-type else than void in the chord, then every return statement in the chord body must return a value of return-type
4. all identifiers for channel and handler parameters in the chord must be unique.

The important key feature of MC# language is that channels and handlers can be passed as arguments to methods (in particular, to async- and movable methods) separately from the object to which they belong (in other words, from the object within which they has been defined). In this sense, channels and handlers are similar to the pointers to functions in C/C++, or, in C# terms, to delegates. Accordingly, the type system of MC# language includes the types for channels and handlers:

 type ::= chanel-type | handler-type | …
channel-type ::= channel ( type-list )
handler-type ::= handler retur-type ( type-list )
type-list ::= // empty list
| type [ , type ]*

The difference between channels and handlers and other types (both scalar and reference) is in that they can be declared only within the chords with obligatory defining of the chord’s body. As a consequence, channels and handlers cannot be declared similar to the convenient types; for example, a declaration as

 public channel с1;

is not allowed. Correspondingly, there are no ways to declare both channel and handler arrays directly and to use an assignment statement for channels and handlers. But it should be noted that due to that channels and handlers are always parts of objects within which they has been declared , all mentioned above operations can be implemented by using such objects indirectly. For example, to declare an array of channels it’s enough to declare an array of objects, which, in turn, contains the corresponding channels. The syntax of statement to send value through the channel in much is similar to invoke an ordinary method:

 [ qualified-object-name. ] channel-name ! ( argument-list );

Thus, we may send an integer x by the channel sendInt as

 a.sendInt ! ( n );

where a is an object for which the channel sendInt has been defined. The syntax of statement to call a handler has the dual form:

 [ qualified-object-name.] handler-name ? ( argument-list );

For handler which returns a value, we need to cast this value before assigning it to the some variable. For example, to receive an integer value by the handler getInt we need to write

 int x = (int) a.getInt ? ();

If, by the time a handler is called, the corresponding channel is empty (i.e. if there have been no calls to this channel at all or all of the values sent through this channel before were absorbed during previous calls to the handler), then the call blocks and the program passes to wait state. If a handler is tied with few channels in the chord, a blocking state comes in the case when there is some empty channel. After receiving a value from the channel (or, in general case, all channels have values), body of the chord executes and returns a result value through the handler. Conversely, if a value is sent on a channel when there are no pending calls to the handler, the value is simply saved in the internal queue of channel, where all the values coming with multiple sendings over the channel are accumulated. After invoking the handler and under condition that all channels from the chord contain the values, the first values from the channels queues will be selected for handling. It is worth to note that triggering of the chord consisting from the handler and a few channels is possible principally due to they are called typically from the different threads.

Example 2. The current example illustrates the running of several async-methods where each of them takes the channel sendStop as one of the arguments. After termination, each of the asyncmethods sends a stop signal to the main program through the call

 sendStop ! ( );

The main program receives a corresponding number of stop signals from the asyncmethods in the for loop:

 for ( i = 0; i < N; i++ )
atc.getStop ? ();
using System;
public class AsyncTerminationClass {
public static int N = 10;
public static void Main ( String[] args ) {
int i;
AsyncTerminationClass atc = new AsyncTerminationClass();
for ( i = 0; i < N; i++ )
atc.a_method ( i, atc.sendStop );
for ( i = 0; i < N; i++ )
atc.getStop ?();
}
public async a_method ( int myNumber, channel () sendStop )
{
Console.WriteLine ( “Process “ + myNumber );
sendStop ! ();
}
public handler getStop void() &amp; public channel sendStop () {
return;
}

Example 3. The example below demonstrates the using of chords as a synchronization tool. The body of the chord

 public handler Get2 long () &amp; channel c1 ( long x )
&amp; channel c2 ( long y )
{
return ( x + y );
}

can be triggered and the handler Get2 will return a value only both channels c1 and c2 have the values. In general, one handler can be joined with an arbitrary number of channels. A chord of the above mentioned form is used typically

1. to detect a termination of async-methods, and
2. to take the values from them.

In the sample shown below − a program to compute Fibonacci numbers, a computation of nth Fibonacci number is reduced to the recursive computation of n-1th and n-2th Fibonacci numbers asynchronously. The corresponding chord allows to detect the termination of recursively called methods and to take the result values from them.

using System;
public class Fib
{
public handler Get2 long() &amp; channel c1( long x ) &amp; channel c2( long y ) {
return x + y;
}
public async Compute( long n, channel( long ) c )
{
Console.WriteLine( "Compute: n=" + n );
if ( n <= 1 )
c ! ( 1 );
else
{
new Fib().Compute( n-1, c1 );
new Fib().Compute( n-2, c2 );
c ! ( (long)Get2 ? () );
}
}
public class ComputeFib
{
handler Get long() &amp; channel c( long x ) {
return x;
}
public static void Main( string[] args )
{
if ( args.Length < 1 )
{
Console.WriteLine( "Usage: Fib.exe <number>" );
return;
}
int n = System.Convert.ToInt32( args [ 0 ] );
ComputeFib cf = new ComputeFib();
Fib fib = new Fib();
fib.Compute( n, cf.c );
Console.WriteLine( "For n = " + n + " value is " + cf.Get?() );
}

## Distributed programming in MC#

By “distributed programming” we mean a writing of programs which intended to run on 2 or more computers (for example, on computational cluster having one main and many work nodes). The distinctive feature of MC# language is that it preserves a single programming model both for the concurrent (local) and distributed cases: async-methods are used to create local asynchronous threads, while movable methods are used to create threads which can be scheduled to execute on remote machines. The syntax rules to declare the movable methods are similar to the rules for asyncmethods with that exception that movable methods may have only public modifier:

 [ public ] movable method_name ( arguments )
{
< method body >
}

The distinctions of movable methods from conventional methods and the rules of correct definition of the former coincide with the ones for async-methods (see Section 2 “Asynchronous methods”). During development of distributed programs in MC# language it is necessarily to take into account some properties of performing of distributed programs. These properties follow from the rules of object passing between the machines which perform a distributed MC# program. First of all, the objects created during of MC# program execution are static by their nature: once created, they remain bound to the place (machine) where they were created and don’t move further. But when we invoke a movable method, all necessary data, namely

1. the object itself to which the given movable method belongs, and
2. arguments of call (both scalar and reference values)

are only copied (but not moved) to the remote machine. As a consequence, changes made afterwards to the copy at remote machine will not affect the original object.

Example 4. In the code below, an invoke of movable method Compute, which alters the field x, doesn’t change that field of object b in the main program.

class A {
public static void Main ( String[] args ) {
B b = new B ();
b.x = 1;
Console.WriteLine ( “Before movable method call: x = “ + b.x );
b.Compute ();
Console.WriteLine ( “After movable method call: x = “ + b.x );
}
}
class B {
public int x;
public B () { }
movable Compute () {
x = 2;
}
}

A running of that program gives the output

 Before movable method call: x = 1
After movable method call: x = 1

Example 5. For the program from Example 3 it is easy to make its distributed version by replacing async keyword by movable in the declaration of Compute method:

using System;
public class Fib
{
public handler Get2 long() &amp; channel c1( long x ) &amp; channel c2( long y ) {
return x + y;
}
movable Compute( long n, channel( long ) c )
{
Console.WriteLine( "Compute: n=" + n );
if ( n <= 1 )
c ! ( 1 );
else
{
new Fib().Compute( n-1, c1 );
new Fib().Compute( n-2, c2 );
c ! ( (long)Get2 ? () );
}
}

public class ComputeFib
{
handler Get long() &amp; channel c( long x ) {
return x;
}
public static void Main( string[] args )
{
if ( args.Length < 1 )
{
Console.WriteLine( "Usage: Fib.exe <number>" );
return;
}
int n = System.Convert.ToInt32( args [ 0 ] );
ComputeFib cf = new ComputeFib();
Fib fib = new Fib();
fib.Compute( n, cf.c );
Console.WriteLine( "For n = " + n + " value is " + cf.Get?() );
}

Recall (see Section 3) that channels and handlers can be passed as arguments to the movable methods separately from the object to which they belong. One of the key feature of execution of distributed MC# programs is that if channels and handlers were copied to a remote machine autonomously or as part of some object, then they become proxy objects, or intermediaries for the original channels and handlers. This replacement is hidden from the applied programmer − he can use the passed channels and handlers (in fact, their proxy objects) on the remote machine as the original ones: as usual, all actions over the proxy objects are redirected to the original channels and handlers by the Runtime-system. In this sense, channels and handlers are different from convenient objects: modifications of the latter on a remote machine are not passed to the original objects.

Note. During development of distributed applications, a programmer must seek to minimize as far as possible a creation of proxy-objects for channels and, especially, for handlers. Sometimes it is possible to build an equivalent variant of the program in which proxyobjects for handlers are absent that allows to avoid a reading from remote machines.