Archive for the 'Programming model' Category

Start with mathematics

Tuesday, September 14th, 2010

The purpose of this post is to introduce main concepts of array programming in Zonnon. Mathematical constructs in Zonnon make it possible to combine Matlab-like notation with efficiency of compiled code, what is especially essential in applications implementing linear algebra algorithms. Zonnon mathematical extension is a full part of the language currently and described in Zonnon language report in detail.

All the mathematical operations are available only for mathematical arrays. To define such an array, the user has to declare it with the {math} modifier. In the example below A and B are mathematical arrays, C1 and C2 are simple arrays.

module Main;
  A: array {math} 2,3 of integer;
  B: array {math} *,* of integer;
  C1, C2: array *,* of integer;

Assignment of two simple arrays means just a reference copy. If at least one array in the assignment statement is mathematical, the compiler will allocate memory if it is needed and create a deep copy. Besides, it is allowed to assign a constant array into a mathematical one. Constant arrays should be declared from the first dimension to the last using []. In the following example matrix

  1 2 3
  4 5 6

is assigned to the array A. Arrays B and C1 are deep copies of A, array C2 is a reference copy of C1.

  A := [[1, 2, 3], [4, 5, 6]];
  B := A;
  C1 := A;
  C2 := C1;
end Main.

Modification of elements of a mathematical array can be done using simple indices, ranges, integer or boolean vector indices. The following example demonstrates it:

  x : array {math} * of integer;
  b: array {math} * of boolean;
  A[0,0] := 100;
  x := [111, 222];
  A[.., 1] := x; (*assign x to the 1.column of A*)
  i := [2, 1];
  A[0, i] := x; (*assign x[0] to A[0, i[0]]; x[1] to A[0, i[1]]*)
  b := [false, true, true];
  A[1, b] := x; (*assign x[0] to A[0, 1]; x[1] to A[1, 2]*)

There is a set of basic operators and functions available for mathematical arrays. However, to use arrays in mathematical operations corresponding operators should be defined or overloaded for the base types. For example, to sum two mathematical arrays (or apply operator “+”), their base type should be either integer, cardinal, real, or other types for which operator “+” is overloaded. The example below demonstrates using mathematical arrays with a user-defined base type.

module Main;
(*defining new complex numbers type*)
type {public, ref} complex = object(r, i: real)
var {public}
  re, im: real;

procedure {public} print;
  writeln(re, " + ", im, "i");
end print;

  re := r; im := i;
end complex;

(*overloading operator '+' for complex numbers*)
operator {public} '+' (z1, z2: complex): complex;
var res: complex;
  res := new complex( +, +;
  return res;
end '+';

(*overloading operator '*' for complex numbers*)
operator {public} '*' (z1, z2 : complex) : complex;
var res : complex;
  res := new complex( * - *, * + *;
  return res;
end '*';

(*overloading operator '<' as squared modulus comparison*)
operator {public} '<' (z1, z2: complex): boolean;
var res: boolean;
  res := * + * < * + *;
  return res;
end '<';

  c1, c2, c3: array {math} 3 of complex;
  b: array {math} 3 of boolean;
  z: complex;
  i: integer;

  c1[0] := new complex(1.2, 4.5); c2[0] := new complex(2.3, 3.1);
  c1[1] := new complex(0.3, 2.1); c2[1] := new complex(-1.5, -3.2);
  c1[2] := new complex(-5.3, 4.5); c2[2] := new complex(4.4, 0.1);

  c3 := c1 + c2;
  writeln("c1 + c2 = ");
  for i := 0 to len(c3) - 1 do c3[i].print end;
  (* c1 + c2 =
    3,500000E+000 + 7,600000E+000 i
    -1,200000E+000 + -1,100000E+000 i
    -9,000000E-001 + 4,600000E+000 i*)

  z := c1 +* c2;
  write("c1 +* c2 = ");
  (* c1 +* c2 = -2,869000E+001 + 2,923000E+001 i *)

  b := c1 .< c2;
  write("c1 < c2 = ");
  for i := 0 to len(c3) - 1 do
    write(b[i]) end;
  (* c1 < c2 = false true false *)

end Main.

Note that in this example we overload only necessary operators. For instance, when using operator “+*” for arrays of complex type, it is essential to overload operators “+” and “*” for complex numbers.

Nina Gonova

A note on activities, protocols and communication

Monday, September 6th, 2010

The purpose of this post is to explain by example the concurrency model in Zonnon. The description of this model one can find in the Zonnon Language report.

The primary building block for concurrency is activities. Activities are used both for adding behavior to objects and for implementing interobject communication. Syntactically activities resemble procedures and are encapsulated in their host object. However, the difference lies in the runtime model. When a procedure is called, possibly with some parameters, it blocks the caller and runs on account of the caller’s thread. Upon completion it returns both return parameters and control to the caller. When an activity is called, possibly with some initial parameters according to its signature, a separate execution thread is created, and the caller is not blocked. Each activity implements a communication protocol (a kind of “contract”) that defines an exchange of tokens (a “dialog”) in terms of a formally defined syntax in EBNF.

In the following example, the body of module Main creates an instance a of a local activity of type A within its scope and interacts according to protocol P.

object {actor} Main;

protocol P = ( N,F,
  prot = ({N ?integer} | F)

activity A implements P;
var i: integer; cmd: P;
  i := 0;
  accept cmd;
  while cmd # P.F do
  return i;
  accept cmd
end A;

var i, next: integer;
    a: activity{P};
  a := new A;
  for i:=1 to 10 do
  next := a(P.N);
end Main.

The caller uses a method call notation to send data (“messages”) to the callee and assignment logic to receive data. Statements accept and return are used on the callee side. In principle, the caller (client) is anonymous for the callee.

Protocols for activities correspond to signatures for procedures. A procedure can be regarded as an activity that accepts parameters only once in the beginning and returns results only once at the end. Both synchronous and asynchronous procedure calls can be modelled, where in the second case a “future” variable is used instead of the assignment logic.

Within a parent scope a full hierarchy of child activities may be created. If the parent scope is marked with a fence modifier, then its end by definition takes the role of an execution barrier that must not be crossed before all child activities have terminated. The scope of the calling routine is an implicit fence.

Objects and modules with at least one activity must be marked with modifier ‘actor’ or ‘protected’. If object is marked with ‘actor’ then it cannot have public procedures. In other words the (interoperability) interface of an actor replaces the method table interfaces of ordinary objects. It is the set of protocol-based activities that it exposes. Protected objects may mix activities and public methods.

The following example shows two communicating actors. Whenever a dialog is created by some caller actor, an activity (a kind of an agent) in the partner actor is launched. Actor Car features an intrinsic activity that implements driving into ParkingLot. This activity instantiates an agent activity within the scope of ParkingLot. An agent activity is defined within the scope of ParkingLot and therefore has access to the fields of ParkingLot. The two activities run in separate threads and communicate via message passing in the clothes of a dialog and using the tokens of protocol Service as messages.

protocol Service = (
  Request, Allow, Reject, Enter, Leave, Wait,
  park = [Enter] Leave,
  waitorleave = Wait ?Allow park | Leave,
  dialog = Request (?Allow park | ?Reject waitorleave)

module {actor} ParkingLot;
import Service;

var capacity: integer;

activity {public} Serve implements Service;
var cmd: Service;
  enter: boolean;
  accept cmd; (*Request*)
  enter := true;
  if capacity=0 then
    return Service.Reject;
    accept cmd; (*Wait or no wait*)
    if cmd = Service.Wait then
      await capacity > 0
      enter := false;
  if enter then
    dec(capacity); (* Book *)
    return Service.Allow;
    accept cmd; (* Enter or Leave *)
    if cmd = Service.Enter then
      (* car stays in the lot *)
      accept cmd (* Leave *)
end Serve;

  capacity := 2;
end ParkingLot.

object {ref, protected} Car;
import ParkingLot as PL, Service;

activity {public} Drive;
var parking: PL.Serve;
    ans: Service;
  parking := new PL.Serve;
  ans := parking(Service.Request);
  if ans # Service.Allow then
    (* Ask to wait forever *)
    writeln("try again");
    ans := parking(Service.Wait);
  (*stay in the parking lot*)
  await 100; (*sleep*)
  parking(Service.Leave);   writeln("left")
end Drive;

  new Drive;
end Car.

module Main;
import Car;
var i: integer;
  for i:= 1 to 5 do new Car end
end Main.

Note that caller activities refer to callees via their instance name, while callers are anonymous from the callee`s point of view. In our example, a reference ans to activity Serve is used by the caller to identify the communication.

The caller and the callee exchange tokens according to the protocol/ syntax specified by the callee. It is said that activity Serve implements a “parser” for protocol Service.

In the example above protocol Service defines an enumeration of tokens Request, Allow, Reject, Enter, Wait and Leave which are used as tokens or messages in the communication. In turn, the communication protocol is defined via three EBNF productions: park, waitorleave and dialog. Note that the question mark used in front of a token changes the direction of the message. Production park defines optional sending of token Enter and then mandatory sending of token Leave from caller to callee. Production dialog obliges the caller to send a Request token and then the callee to reply either with Allow or with Reject. If the callee replies with Allow then the continuation of the dialog is defined with production park. If the callee replies with Reject then the continuation of the dialog is defined with production waitorleave.

Note that in protocol definitions

  • Protocol syntaxes must be deterministic and context-free.
  • Recursion of productions is not allowed.
  • In repetitions there must be at least one message in both directions. Since send operations are non blocking, this is needed to calculate buffer sizes statically and also to prevent buffer overflows. As an example, messages like {string} are not allowed, where {string ?OK} and {string string ?OK} are.
  • Alternatives can start with transmissions in one direction only. For example, (A | ?B) is not allowed. At each point in the protocol it must be clear whether the callee or the caller makes the decision. Our example can be rewritten as (A | C ?B) if the decision is to be made by the caller or as (?C A | ?B) if the callee decides. By the same reason, (string [string] ?OK) is not allowed, whereas (string [string] END ?OK) is perfectly fine.

Compliance of the transmitted data with the protocol is checked at runtime with a finite state automata and an exception can be raised in case of any deviation. As we emphasize again that validating of a communication protocol with respect to its formal declaration in a way corresponds to signature type checking in the case of procedure calls compiler tries to enforce protocol statically. Unfortunately a full protocol validation is not feasible in the general case, and it would require sophisticated model checking concepts. However without this one would not be able to write code productively.

This static validation procedure is the main reason why references of protocol types are limited to local variables and it is impossible to create a copy of this reference. There is one exception to that. It is allowed to pass a protocol reference in a procedure call. This does not affect the analysis as it can be replaced with inlining of the called procedure. Recursion of this calls in not allowed.

It is also allowed to pass a protocol reference to another activity within some dialog. This operation is allowed only for references to activities that have been assigned but not yet launched. It is necessary to ensure that the state of the protocol is known. The transfer operation works as destructive reading that is, the variable becomes unassigned and its value becomes invalid.

Local variables that are used for protocols in the language can be of some protocol type or of a concrete activity type. References of some protocol type can refer to any activity that implements this protocol type.

Instead of a conclusion a few words about the consistency model. Activities express potential parallelism. However it does not always makes sense to actually run them in parallel. Our aim is to provide two options: expressing desirable concurrency (on a very fine grain level) and to express unconstrained concurrency on coarse grain level. Activities that belong to different active objects can always run in parallel. Activities declared within one active object share the object state and may conflict.

We use a simple consistency rule to specify the “visible” behavior based on the notion of atomic sequences. We define atomic sequence as a trace in the control flow of the program (possibly including method calls) that does not contain any blocking instructions (e.g. receiving a message, waiting for a condition or sleeping for a certain period of time).

Then we use a simple sequential consistency rule saying that for any execution order of a group of atomic sequences within one active object there is a sequential exclusive execution order that leads to the same result.

Atomic sequences may have been assigned a precondition that schedules the execution.

In ParkingLot example discussed before we can find, for example, following atomic sequences.

In the following example after receiving a message and until the next blocking statement the code is executed exclusively:

  accept cmd; (* Blocking receive *)
  enter := true;
  if capacity = 0 then
    return Service.Reject;
    (* The next instruction is blocking *)

Since there is a branch the other trace when condition is false is also an atomic sequence:

  accept cmd; (*Blocking receive *)
  enter := true;
  if capacity # 0 then
    return Service.Reject;
  if enter then
    dec(capacity); (* Book *)
    return Service.Allow;
    (* The next instruction is blocking *)

For example this trace is also atomic:

  await capacity > 0; (* Blocking until condition is true *)
  if enter then
    dec(capacity); (* Book *)
    return Service.Allow;
    (* The next instruction is blocking *)

which ensures that capacity will be decremented only when it is greater than 0. If condition becomes eventually true then the activity eventually will be rescheduled. These were examples of conditional atomic sequence.

A body of objects and modules is always scheduled first, so it is safe to use the beginning of the body (before the first blocking statement) for initialization as a constructor. This is an unconditional atomic sequence:

  capacity := 2;
end ParkingLot.

The following atomic sequence will be scheduled not earlier than 100 milliseconds after the call of await:

await 100; (*sleep*)

Roman Mitin

Program composition in the small

Saturday, August 7th, 2010

The purpose of this post is to clarify one aspect of compositional model in Zonnon and in particular the use of import directive in the context of object construction. There are four kinds of building blocks: definition, implementation, object and module. And there are four types of relations between them: import, aggregation, implementation and refinement. Both import and aggregation are represented with keyword import.

We will use a simple example to illustrate how objects are composed.

A definition defines an abstract interface possibly comprising variable declarations, method signatures, and syntactically defined protocols. For example the following declaration defines an interface containing one procedure.

definition {public} A.D;
  procedure P;
end D.

An object may implement any number of definitions.

Before continuing, I want to clarify the use of namespaces. Definition D is defined within namespace A. Identifier D should be always used with qualifying namespace unless renamed by an import clause. In other words if there is another unit defined also within namespace A uses D it needs to qualify D with A anyway.

In the example below object A.B.O implements definition A.D and procedure P within object A.O.O implements procedure A.D.P.

object {ref} A.B.O implements A.D;
  var {public}
    a: object{A.D};
  procedure {public} P implements A.D.P;
  end P;
end O.

Implements clause implies an implicit import of A.D. in the example above. However we still can write an explicit import. Explicit import allows to give a local nickname for the imported unit. Example below is an equialen to the example above.

object {ref} A.B.O implements D;
  import A.D as D;
  var {public}
    a: object{D};
  procedure {public} P implements D.P;
  end P;
end O.

Module units can import declarations from other modules. The import clause shows explicit dependencies between modules. This also applies to the standalone definition, implementation and object units.

As you can see from the example below the transitivity rule does not apply here. Both the object type and the definition must be imported if they are used in the module.

module Main;
  import A.B.O, A.D;
    o: object{A.D};
  o := new A.B.O;
end Main.

To clarify the case with ‘topmost’ level definitions, objects and implementation note that a standalone object declaration is equivalent to the type being declared in an anonymous module.

object T;
  . . . .
end T.

is shorthand for

module ;
  type T = object . . . end T;
end .

A definition can refine another definition by adding services. Originally refinement also meant ability to omit and modify services, but this no not supported.

In the example below a definition K is a refinement of definition D. It adds a new procedure U.

definition {public} B.K refines A.D;
  procedure U;
end K.

Any object that implements definition B.K must implement both procedures P and U.

object {ref} A.B.O2 implements B.K;
  procedure {public} P implements B.K.P;
  end P;
  procedure {public} U implements B.K.U;
  end U;
end O2.

Note that procedure P implements B.K.P; and not A.D.P as P is visible in the scope of definition K and definition D is not visible in O2 at all.

An implementation defines an aggregation of variable and method implementations intended for reuse. In the example below there is a pair of definition and implementation. Implementation

definition {public} A.T;
  procedure S;
  procedure L;
end T.

implementation A.T;
  procedure S implements A.T.S;
  end S;
end T.

Implementation A.T provides a default implementation for method S which can be reused. The following example illustrates an implicit aggregation. Object O3 implements definitions B.K and A.T and implicitly aggregates implementation A.T which contains procedure S.

object {ref} A.B.O3 implements B.K, A.T;
var {public}
  procedure {public} P implements B.K.P;
  end P;
  procedure {public} U implements B.K.U;
  end U;
  procedure {public} L implements A.T.L;
  end L;
end O3.

An interface is a type for a postulated object composed from one or more definitions. In the example below the construct
t: object{A.T};
declares a variable of a generic object type with a specifier that it implements the definition A.T.
The other example
object{A.T, B.K};
defines an interface type that implements both definitions A.T and B.K.

module Main;
import A.B.O3, B.K, A.T;
  o: A.B.O3;
  kt: object{A.T, B.K};
  t: object{A.T};
  o := new A.B.O3;
  t := o;
end Main.

Roman Mitin