Tutorial

From Céupédia
Jump to: navigation, search

This version is obsolete and will not be updated for new releases of Céu.

Check out the new interactive tutorial in http://www.ceu-lang.org/try.php.


This is a tutorial on the Céu programming language.

We assume some knowledge in C, as most of the basic functionality of Céu derives from it (constants, operators, declarations, etc).

Contents

1 Hello World!

Follows a reactive Hello World! in Céu that prints the infamous message every 250 milliseconds:

   loop do
       await 250ms;
       _printf("Hello World!\n");
   end
   
   // (try online!)

The await statement halts the running line of execution until the referred event occurs (in this case, the elapsing of 250 milliseconds).

In Céu, external C symbols like printf must be preceded with an underscore.

The loop statement in the example repeats its body indefinitely.

  • Timers are integrated with the language!

2 Input Events

Céu supports events that represent external input, allowing programs to interact with the environment:

   // input event identifiers begin in uppercase
   input int MyEvt;              // `MyEvt' is an input event of integers
   loop do
       int v = await MyEvt;      // `v' gets the next triggered value of `MyEvt'
       _printf("MyEvt=%d\n", v);
       if v == 0 then
           break;                // escapes the loop when v==0
       end
   end
   return 0;
   
   // (try online!)

  • The await statement accounts for the reactive nature of Céu.

An input event in Céu represents a correspondent event in the underlying platform. The availability of external events depend on the platform in use.

For example, in an Arduino binding for Céu, a change in an input pin on the microcontroller might trigger a correspondent input event in Céu. In higher-level platforms (e.g. operating systems), more abstract events might be available, such as keyboard presses, or the arrival of network packets.

3 Parallel Compositions

If only a single line of execution were allowed, a program could not wait for multiple events at the same time, and Céu would be the most worthless language in the World.

A line of execution is known as a trail, and Céu allows multiple trails to coexist.

The parallel statements of Céu (par/and,   par/or,   par) splits the running trail in two:

   loop do
       par/and do
           await 100ms;
           _printf("Hello ");
       with
           await 250ms;
           _printf("World!\n");
       end
   end
   
   // (try online!)

The par/and stands for parallel and, meaning that the trails spawned in parallel rejoin after both terminate (restarting the loop, in the example).

Conversely, a par/or rejoins after any spawned trail in parallel terminates, killing the other.

So, if we change the par/and to a par/or, the second _printf is never reached:

   loop do
       par/or do
           await 100ms;
           _printf("Hello ");
       with
           await 250ms;
           _printf("World!\n");    // never reached
       end
   end
   
   // (try online!)


We can change the original par/and example to terminate on the occurrence of the input event TERM. We just need to enclose the whole code with another par/or that awaits the termination event in parallel:

   input void TERM;
   par/or do
       loop do                     // the original loop never terminates
           par/and do
               await 100ms;
               _printf("Hello ");
           with
               await 250ms;
               _printf("World!\n");
           end
       end
   with
       await TERM;                 // but the whole par/or terminates on TERM
                                   // and kills the original loop
   end
   return 1;
   
   // (try online!)

Note that we don't need to change a single line in the original par/and loop.

  • Parallel compositions in Céu are very powerful!

Finally, the par statement is used when all trails in parallel are supposed to run forever. In this case, using par/and or par/and would also have the same effect, but could lead to confusion, as the composition is not intended to terminate:

   input void Hello;
   input void World;
   par do      // par/and, par/or would behave the same
       loop do
           await Hello;
           _printf("Hello!\n");
       end
   with
       loop do
           await World;
           _printf("World!\n");
       end
   end
   
   // (try online!)

4 Execution Model

The existence of a parallel statement raises several questions regarding how trails are scheduled during execution. Nonetheless, the concurrency properties of Céu are quite simple and easy to grasp.

  • Céu doesn't require semaphores, locks, or any other synchronization primitive!

The following rules are respected during the execution of programs:

4.1 Synchronous Execution

A program execution is synchronous with respect to input events. This means that while trails are reacting to the current input event, no further events are handled.

The period in which trails are reacting to a given input event is named as a reaction chain. A trail only halts (i.e. stops to react) when it awaits again or terminates.

In the following example, suppose the event A occurs just before B:

   input void A, B;
   int v = 0;
   par/and do
       await A;        // first trail
       v = v + 1;
   with
       await B;        // second trail
       v = v * 2;
   end
   return v;
   
   // (try online!)

Initially, both trails in parallel are awaiting. The occurrence of A awakes the first trail that performs the increment on v. If the event B occurs in the middle of the increment operation, it is delayed until the running reaction chain terminates. Hence, there is no possible race condition on accessing v and, given the sequence A->>B, the only possible result for the program is <tt>2 ((0+1)*2).

  • Reactions to input events do not overlap.

But what if a trail executes endlessly and never halts, how further input events could be handled? (see #2)

And what if multiple trails react to the same input event and access the same variables? (see #3, #4)

4.2 Bounded Execution

Céu ensures at compile time that a trail never runs forever, and hence, that reaction chains always run in bounded time.

The compiler detects the only way a trail could run in unbounded time: loops that do not await, the so called tight loops.

In the following examples, which are all refused at compile time, the loop bodies have at least one path that does not await:

   loop do                 // a tight loop
       nothing;            // `nothing' is a valid statement :)
   end

or

   loop do                 // a tight loop
       par/or do
           await A;
       with
           nothing;        // this path does not await
       end
   end

or

   loop do                 // a tight loop
       if a == 0 then
           await A;
       end                 // the omitted else does not await
   end

or

   // calculates fat of 10
   int fat = 1;
   int i = 10;
   loop do             // a tight loop
       if i == 0 then
           break;
       end
       fat = fat * i;
       i = i - 1;
   end
   return fat;
   
   // (try online!)


  • Céu detects tight loops at compile time!

The last example is actually useful and it would be a shame if it couldn't be written in Céu. (see #Asynchronous Execution)

The tight loop analysis is not extended for external C code. Hence, it is the responsibility of the programmer to ensure that external functions run in bounded time.

4.3 Deterministic Execution

Céu is designed to be deterministic in the sense that a given program should always yield the same outcome for the same sequence of input events executed multiple times.

However, as trails share variables, it is easy to write non-deterministic programs. In the following example, the variable v is accessed concurrently on the occurrence of A:

   input void A;
   int v;
   par/and do
       await A;
       v = 1;              // non-deterministic access
   with
       await A;
       v = 2;              // non-deterministic access
   end
   return v;               // returns 1 or 2
   
   // (try online!)

Céu performs a static analysis to detect non-deterministic access to variables, raising a warning if it is the case.

In the next example, although v is accessed in both trails on the occurrence of A, they never happen at the same time:

   input void A;
   int v;
   par/and do
       await A;
       v = 1;              // deterministic access
   with
       await A;
       await A;
       v = 2;              // deterministic access
   end
   return v;               // returns 2
   
   // (try online!)

The static analysis takes into account any combinations of events, timers, loops, parallel statements, etc, as the following examples illustrate:

   int v = 0;
   par/or do
       loop do
           await 10ms;
           v = v + 1;      // non-deterministic access (on 10th iteration)
       end
   with
       await 100ms;
       v = v * 2;          // non-deterministic access
   end
   return v;               // returns 19 or 20
   
   // (try online!)
   input void A,B;
   int v;
   par/and do
       par/and
           await A;
       with
           await B;
       end
       v = 1;              // non-deterministic access
   with
       await A;
       await B;
       v = 2;              // non-deterministic access
   end
   return v;               // returns 1 or 2
   
   // (try online!)
  • Céu detects non-deterministic access to variables at compile time!

4.4 Atomic Execution

Some applications are inherently non-deterministic and require the deterministic property of Céu to be relaxed. (That's why the static analysis raises a warning instead of an error.)

For these situations, Céu ensures that the concurrent trails' segments that access the same variables execute atomically, i.e., they are never interrupted:

   input void A, B, C;
   int v = 0;
   par/and do
       await A;
                           // atomic begin: trail awakes
       v = v + 1;          //      non-deterministic access
                           // atomic end: trail halts
       await B;
       v = v + 1;          // deterministic, no need to be atomic
   with
       await A;
                           // atomic begin: trail awakes
       v = v * 2;          //      non-deterministic access
                           // atomic end: trail halts
       await C;
       v = v * 2;          // deterministic, no need to be atomic
   end
   return v;
   
   // (try online!)
  • Céu prevents race conditions on concurrent access to shared variables!

4.5 Glitch-free Execution

In the following example, both trails in the par/or terminate at the same time:

    1:  int v1=0, v2=0;
    2:  par/or do
    3:      v1 = 1;         // priority=2
    4:  with
    5:      v2 = 2;         // priority=2
    6:  end
    7:  return v1 + v2;     // priority=1 (returns 3)
   
   // (try online!)

Once one of the trails (e.g. line 3) terminate, the par/or composition could proceed to its join point (line 7). However, the trail in parallel (e.g. line 5) is also executing, what would make the par/or terminate again and re-execute the join point, characterizing a glitch.

In order to avoid glitches, Céu assigns different priorities to statements at compile time, so that they execute in the expected order. In the example, both assignments execute before the return statement.

  • Céu is glitch-free!

5 Internal events

Internal events are used as a signaling mechanism among trails.

A program can await for changes in internal events, which can be signaled through the emit statement:

   // internal event identifiers begin in lowercase
   event int i = 1;
   par do
       loop do
           _printf("Hello World: %d!\n", i);
           await i;        // waits for changes
       end
   with
       loop do
           await 250ms;
           emit i(i+1);    // assigns a new value and triggers `i'
       end
   end
   
   // (try online!)

The current value of an internal event can be queried just like variables. Actually you can think of internal events as a kind of reactive variables.

The next example holds the constraint that v1 is always v2+1:

   input int Start;
   event int v1, v2;
   par/or do
       loop do
           await v2;
           v1 = v2 + 1;
       end
   with
       loop do
           await v1;
           v2 = v1 - 1;
       end
   with
       // tests the constraint
       await Start;
       emit v1(2);         // use `emit' instead of simply `='
       _printf("v1=%2d   v2=%2d\n", v1, v2);
       emit v2(12);
       _printf("v1=%2d   v2=%2d\n", v1, v2);
       emit v1(0);
       _printf("v1=%2d   v2=%2d\n", v1, v2);
       return 0;
   end
   
   // (try online!)
  • Variables in Céu can be reactive!

5.1 Stacked Execution

A running trail that emits an internal event may cause another trail to awake. This way, Céu must specify how the communicating trails interact.

In Céu, when a trail emits an internal event, it immediately halts, resuming only after the complete reaction to it terminates:

   input int Start;
   event void e;           // an internal event that carries no value
   int v = 0;
   par do
       loop do             // a simple loop that
           await e;        // when `e' occurs
           v = v + 1;      // increments `v'
       end
   with
       await Start;
   
       // 1st trail is awaiting `e'
       emit e;             // halts and resumes after 1st trail halts
                           // v=0+1 => 1
   
       // 1st trail is awaiting `e' again
       emit e;             // halts and resumes after 1st trail halts
                           // v=1+1 => 2
   
       return v;
   end
   
   // (try online!)

The way internal events execute is analogous to conventional call/return routines. When a routine is invoked, the statement following it only executes after the routine returns. Also, just like routines, internal events can nest to a deep level of emits.

  • Internal events execute similar to routines!

6 Asynchronous Execution

The factorial example previously shown contains a tight loop and cannot be written that way.

The asynchronous blocks (asyncs) of Céu are the way to perform time consuming computations that require a tight loop:

   int ret = async do
       // calculates fat of 10
       int fat = 1;
       int i = 10;
       loop do                 // a tight loop
           if i == 0 then
               break;
           end
           fat = fat * i;
           i = i - 1;
       end
       return fat;
   end;
   
   // (try online!)

Code that runs in async blocks is suspended whenever there is a pending input event to the synchronous side. This way, you never know if/when an async executes.

Asyncs cannot await, cannot use parallel compositions, and cannot nest. Nonetheless, they can still be used in conjunction with the synchronous side of the application:

   int ret;
   par/or do
       ret = async do
           // calculates fat of 10
           // (copy of the previous fat)
       end;
   with
       await 1s;       // watchdog to kill the async if it takes too long
       ret = 0;
   end
   return ret;
   
   // (try online!)
  • Asynchronous blocks allow programs to perform long computations!

7 Simulation

Asyncs are allowed to trigger input events and the passage of time towards the synchronous side of a program, providing a way to test programs in the own language:

   input int A;
   
   // tests a program with a simulation in parallel
   par do
   
       // original program
       int v = await A;
       loop do
           await 10ms;
           _printf("v = %d\n", v);
           v = v + 1;
       end
   
   with
   
       // input simulation
       async do
           emit A(0);      // initial value for `v'
           emit 1s35ms;    // the loop executes 103 times
       end
       return 0;
   end
   
   // (try online!)

When the program starts, the par/or spawns the original program together with the input simulation. As synchronous code has higher priority, the program immediately awaits the event A. Then, the async emits the event A, awaking the synchronous code, which enters the loop, prints the message, and awaits 10ms. Then, the async resumes and emits 1s35ms, what makes the synchronous side to resume, increment v, restart the loop, print the message, and await 10ms again. However, 1s25ms remains from the previous emit, what makes the synchronous side to resume again, and again (the loop iterates and prints the message exactly 103 times).

  • Céu supports the simulation of programs in the own language!

8 C Definitions

Céu has no support for functions or new types, which can be defined inside C blocks:

   C do
       int soma (int a, int b) {
           return a+b;
       }
   
       typedef struct {
           int a;
           int b;
       } mystruct;
   end
   
   _mystruct s;
   int v = _soma(s.a, s.b);
   
   // (try online!)

As previously stated, C symbols must be preceded with an underscore when used in Céu programs.

C blocks can only be used for global definitions.

  • Céu integrates well with C!

9 Abstractions with m4

Céu source files can be optionally preprocessed with m4, which offers similar functionality to the C preprocessor.

Moreover, m4 can be used to substitute arbitrary code, providing a powerful mechanism for creating abstractions in Céu.

The following example defines the macro AWAIT_COND that loops until the value of an event satisfies a condition. The event name, condition operator, and expected value should be passed as arguments to the macro:

   @define(AWAIT_COND, `          // name of the macro
       loop do
           int v = await $1;      // $1 is the event name (1st macro argument)
           if v $2 $3 then        // $2 is the operator, $3 is the expected value
               break;
           end
       end
   ')
   
   input int A, B;
   par/or do
       loop do
           @AWAIT_COND(A, `>=', 5);   // terminates when A>=5
           _printf("A >= 5\n");
       end
   with
       @AWAIT_COND(B, `==', 0);       // terminates when B==0
   end
   return 0;
   
   // (try online!)

The two occurrences AWAIT_COND in the source code are expanded to the macro definition.

In m4, the command define is used to define a new macro. The symbols ` and ' are used to enclose tokens that contain spaces and special characters.

In Céu, the token @ is ignored by the parser and is used to highlight the use of macros.

  • High-level abstractions can be created with m4!


Personal tools