Concurrent programming is the use of several programs, running together in the same application. It is opposed to traditional sequential programming, in which there is one unique program, which thus coincides with the whole application. Concurrent programming is usually considered to increase modularity, as one can often naturally decompose a complex application in several cooperating programs which can be run concurrently. This is for example the case of servers in which each user request can quite logically be mapped to a specific program processing it. With concurrent programming there is no more need to code a complex application made of many distinct parts in one single program, as it is the case in sequential programming. There are two main variants of concurrent programming: the one in which the programs, called threads, are sharing a common memory; and the one in which programs are basically processes which have their own memory. The presence of a shared memory eases communication between threads, as threads can directly use shared data to communicate, while processes have to use specialized means, for example sockets, for the same purpose. But, the counterpart is that shared data may have to be protected from concurrent accesses from distinct threads. Of course, this is not necessary with processes in which, by definition, data are fully protected from being accessed by other processes. Parallelism is the possibility to simultaneously use several computing resources. It is available with multiprocessor machines, or more generally, when several machines are distributed over a network. It is well-known that parallelism is not the best solution in all cases, and there are systems which are more efficiently run by a single processor machine than by a multiprocessor one. Parallelism is now directly available, with no special effort, in standard OS such as Linux which can operate hardware mapped on Symmetric Multi-Processor (SMP) architectures. Parallelism appears quite natural in concurrent programming, as generally there is no logical need that concurrent programs should be run by one unique processor. Concurrent programming is largely recognized as being, in the general case, much more difficult than sequential programming. Some problems, such as deadlocks, are specific to it. Moreover, concurrent programs are most of the time nondeterministic, and thus more difficult to debug. For these reasons, concurrent programming is often considered as an activity which must be left to specialists. This seems of course largely justified in domains such as the programming of OS kernels. But the question remains of designing a set of concurrent primitives that can be not too difficult or painful to use, and to provide general users with it.

In sequential programming, a program is basically a list of instructions run by the processor. The program has access to the memory in which it can read and write data. Amongst the instructions are tests and jumps which are the way to control the execution flow. In this standard computing model, a program-counter points to the current instruction executed by the processor. The model of threads extends the previous sequential model by allowing the presence of several programs, the threads, sharing the same memory. There are thus several program counters, one by thread, and a new component, the scheduler, which is in charge of dispatching the processors to the threads. The transfer of a processor from one thread to another is called a context-switch, because it implies that the program-counter of the thread which is left must be saved, in order to be restored later, when the thread will regain the processor. When several threads can be executed, the scheduler can choose arbitrarily between them, depending on implementation details, and it is thus generally unpredictable to determine which one will finally get the processor. This is a source of nondeterminism in multi-threaded programming. The strategy of the scheduler is said to be preemptive when it is able to force a running thread to release a processor executing it, in which case one says that the thread is preempted. With a preemptive scheduler, situations where a non-cooperative thread prevents the others from any execution, are not possible. A preemptive scheduler can withdraw a processor from a running thread because of priority reasons (there exist threads with higher priorities in the system), or for other reasons. This is also a source of nondeterminism. In a preemptive context, to communicate or to synchronize generally implies the need to protect some shared data involved in the communication or in the synchronization. Locks are often used for this purpose, but they have a cost and are error-prone as they introduce possibilities of deadlocks, that are situations where two threads cannot progress because each one owns a lock needed by the other. Preemptive threads are generally considered to be well adapted for systems made of heavy-computing tasks and needing few communications and synchronizations. This is typically the case of Web servers, in which a thread (usually picked out from a pool of available threads) is associated to each new user request. Advantages are clear: first, modularity is increased, because requests do not have to be split in several small parts, as it would be the case with sequential programming. Second, servers can be run by multiprocessor machines without any change, and for example they can immediately benefit from SMP architectures. Finally, blocking I/Os, for example reading from a file, do not need special attention. Indeed, as the scheduler is preemptive, there is no risk that a thread blocked forever on an I/O operation will also block the rest of the system. The strategy of the scheduler is said to be cooperative if the scheduler has no way to force a thread to release the processor it owns. With this strategy, a running thread must cooperate and release by itself the processor from time to time, in order to let the other threads the possibility to get it. Cooperation is of course absolutely mandatory if there is only one processor: a running thread which would never release the processor would indeed forbid any further execution of the other threads. Cooperative threads, sometimes called green-threads, are threads that are supposed to run under the control of a cooperative scheduler. Cooperative threads are adapted for tasks that need a lot of communications between them. Indeed, data protection is no more needed, and one can thus avoid to use locks. Cooperative threads can be efficiently implemented at user level, but they cannot benefit from multiprocessor machines. Moreover, they need special means to deal with blocking I/O. Thus, purely cooperative threads are not sufficient to implement important applications such as servers.

Loft basically gives users the choice of the context, cooperative or preemptive, in which threads are executed. More precisely, Loft defines schedulers which are cooperative contexts to which threads can dynamically link or unlink. All threads linked to the same scheduler are executed in a cooperative way, and at the same pace. Threads which are not linked to any scheduler are executed by the OS in a preemptive way, at their own pace. An important point is that Loft offers programming constructs for linking and unlinking threads. The main characteristics of Loft are:

• It is a language, based on C and compatible with it.
• Programs can benefit from multiprocessor machines. Indeed, schedulers and unlinked threads can be run in real parallelism, on distinct processors.
• Users can stay in a purely cooperative context by linking all the threads to the same scheduler, in which case systems are completely deterministic and have a simple and clear semantics.
• Blocking I/Os can be implemented in a very simple way, using unlinked native threads.
• There exist instants shared by all the threads linked to the same scheduler. Thus, all threads linked to the same scheduler execute at the same pace, and there is an automatic synchronization at the end of each instant.
• Events can be defined by users. They are instantaneously broadcast to all the threads linked to a scheduler; events are a modular and powerful means for threads to synchronize and communicate.
• It can be efficiently implemented on various platforms. Implementation of the whole language needs the full power of native threads. However, the cooperative part of the language can be implemented without any native thread support. This leads to implementations suitable for platforms with few resources (PDAs, for example).

Loft is strongly linked to an API of threads called FairThreads[12]: actually, Loft stands for Language Over Fair Threads. This API mixes threads with the reactive approach, by introducing instants and broadcast events in the context of threads. Loft can be implemented in a very direct way by a translation into FairThreads (this implementation is described in section Implementation in FairThreads7.1).

Section The Language LOFT2 contains the description of the language. First, an overview of Loft is given. Then, modules and threads are considered. Atomic and non-atomic instructions are described. Finally, native modules are considered. A first serie of examples is given in section Examples - 13. Amongst them is the coding of a small reflex-game which shows the reactive programming style. The case of data-flow programming is also considered. Various sieves are coded, showing how the presence of instants can benefit to code reuse. Section Programming Style4 contains a discussion on the programming style implicitly supposed by Loft. Section Semantics5 contains the formal semantics of the cooperative part of Loft by means of a set of rewriting rules. FairThreads is described in section FairThreads in C6. Several implementations of Loft are described in section Implementations7. One consists in a direct translation in FairThreads. Another is a direct implementation of the semantics rules of section Semantics5. One implementation is suited for embedded systems. Section Examples - 28 contains a second serie of examples. Amongst them are some example which can benefit from multiprocessor architectures. A prey/predator demo running on an embedded system (the Game Boy Advance of Nintendo) is also described. Related work is described in section Related Work9 before the conclusion. A first annex gives the API of FairThreads. A second one is the Reference Manual of Loft. The third one is a quick description of the compiling command.

Modules are templates from which threads are created. A thread created from a module is called an instance of it. A thread is always created in a scheduler which is initially in charge of executing it. Modules are made from atomic and non-atomic instructions that are defined in the next sections. A module can have parameters which define corresponding parameters of its instances. Arguments provided when an instance is created are associated to these parameters. A module can also have local variables, new fresh instances of which are automatically created for each thread created from it. The syntax of Loft is based on C and modules are defined in files that can also contain C code. The syntax of modules is:

module <kind> <name> ( <params> )
<locals>
<body>
<finalizer>
end module

• <kind> is the optional native keyword. The case of native modules is considered in section Native Modules2.5.
• <name> is the module name; it can be any C identifier.
• <params> is the list of parameters; it is empty if there is no parameter at all.
• <locals> is the optional list of local variables declarations. This list begins with the keyword local.
• <body> is a sequence of instructions defining the module body.
• <finalizer> is an optional atomic instruction executed in case of forced termination (instruction stop). This part begins with the keyword finalize.

As example, consider the module trace defined by:

module trace (char *s)
while (1) do
   printf ("%s\n",local(s));
   cooperate;
end
end module

This module is a non-native one and it has a parameter which is a character string. The body is reduced to a single while loop (actually, an infinite one) considered in section Loops2.4.4. At each instant, the loop prints the message in argument and cooperates. Note the presence of the do and end keywords around the loop body; indeed, as in Loft "{" and "}" are used to delimit atomic instructions (see C Statements2.3.4), one needs a different notation for loop bodies. The parameter s is actually a local variable which is passed at creation to the instances of trace. In Loft, all accesses to local variables, and thus also to parameters, must be of the form local(...) (local is actually a macro).

2.2.1 Local variables

Threads can have local variables which keep their values across instants. These are to be distinguished from static variable which are global to all the threads, and from automatic variables which loose their values across instants. Let us return to the previous module trace and suppose that one wants to also print the instant number. A first idea would be to define a variable inside the atomic instruction:

module trace (char *s)
while (1) do
   {
      int i = 0;
      printf ("%s (%d)\n",local(s),i++);
   }
   cooperate;
end
end module

This is not correct because the variable i is allocated in the stack at the beginning of the atomic instruction, and vanishes at the end of it. Thus, a new instance of the variable is used at each instant. A solution would be to declare a global C variable to store the instant number:

int i = 0;

module trace (char *s)
while (1) do
   printf ("%s (%d)\n",local(s),i++);
   cooperate;
end
end module

This solution produces a correct output. However, i is a global variable shared by all instances of trace. A local variable should be used if one wishes that each instance owns a distinct variable:

module trace (char *s)
local int i;
{local(i) = 0;}
while (1) do
   printf ("%s (%d)\n",local(s),local(i)++);
   cooperate;
end
end module

Note that local variables must always be accessed using the form local(...). This allows one to access in the same context a local variable and a global or automatic one having the same name.

2.2.2 Threads

Threads are instances of modules. Threads which are instances of a module m are created using the function m_create which returns a new thread. Threads are of the pointer type thread_t. Note that, as in many C APIs, all types defined in Loft have their name terminated by "_t". Arguments given to m_create are passed to the created instance (as in C, arguments are passed by value). For example, the following atomic instruction creates two instances of the previous module trace:

{
   trace_create ("first thread");
   trace_create ("second thread");
}

The output is:

first thread (0)
second thread (0)
first thread (1)
second thread (1)
first thread (2)
second thread (2)
...

Several points are important:

• Threads are created in the implicit scheduler which is automatically created and started in all program (see Schedulers7.2.4).
• Threads are automatically started. This is a difference with Java in which threads have to be explicitly started.
• Threads are always executed in the same order, which is the order of their creation. Thus, the previous output is the only one possible.

It is possible to create a thread in a specific scheduler using a creation function of the form create_in. For example, an instance of trace is created in the scheduler sched by:

trace_create_in (sched,"a thread");

Threads are always incorporated in the scheduler at the beginning of an instant, in order to avoid interferences with already running threads. Moreover, if the current scheduler and the one in which the thread is created are the same, then this instant is the next one. The running thread is returned by the function self().

2.2.3 Finalizer

The finalizer of a module is an atom executed when an instance of the module is forced to terminate by a stop instruction (defined in Control over Threads). The finalizer is only executed if the stopped thread is not already terminated. A typical use of finalizer is for deallocation purposes, as in:

module m (...)
local resource_type resource;

{local(resource) = allocate ();}
...
{deallocate (local(resource));}

finalization
{deallocate (local(resource));}
end module

The allocated resource is deallocated in case of normal termination, at the end of the module body. It is also deallocated if termination is forced, as in this case the finalizer is executed. An important point to note is that the thread executing a finalizer is unspecified, as the instance considered is stopped. This means that self cannot be safely used in finalizers.

2.2.4 Main Module

The entry point of a program is a module with name main. An instance of it is automatically created in the implicit scheduler. For example, the previous output could be produced by the execution of a program with the following module main:

module main ()
trace_create ("first thread");
trace_create ("second thread");
end module

As in C, arguments can be given to the module main, following the standard argc/argv convention. The global program does not terminate when the main thread terminates: it is the programmer's responsibility to end the program (typically, by calling the exit function of C).

scheduler_t sched = scheduler_create ();

scheduler_react (sched);

scheduler_t implicit = implicit_scheduler ();
scheduler_t current  = current_scheduler ();

event_t evt1 = event_create ();
event_t evt2 = event_create_in (sched);

generate (evt);
generate_value (evt,val);

stop (self ());

suspend (main_thread);
resume (other_thread);

suspend (thread);
resume (thread);

module main ()
{
   trace_create ("first thread");
   trace_create ("second thread");
}
end module

await (event);

await (e,10);

await (e,1);
{
   if (return_code () == ETIMEOUT) 
      printf ("was absent");
   else 
      printf ("is present"); 
}

await (e,1);
await (f,1);
{
   if (return_code () == ETIMEOUT) 
      printf ("f was absent");
   else 
      printf ("f is present");
}

join (th1);
join (th2,10);

while (1) do
   printf ("loop!");
   cooperate;
end

{local(i) = 1;}
while (local(i)) do
   {local(i) = 0;}
   cooperate;      
   printf ("loop!");
   cooperate;
   {local(i) = 1;}   
end

while (1) do
   printf ("loop!");
end

repeat (10) do
   printf ("loop!");
   cooperate
end

if (<expression>) then <instruction> else <instruction> end

await (e,1);
if (return_code () == ETIMEOUT) then 
   printf ("was absent");
else 
   printf ("is present"); 
end

if (exp) then
   cooperate;
   printf ("true!");
else
   cooperate;   
   printf ("false!");
end

module m ()
while (1) do
   if (exp) then return; end
   cooperate;
end
end module

module bug ()
while (1) do
   {if (exp) return;} 
   cooperate;
end
end module

while (1) do cooperate; end

if (!exp) then
   generate (error);
   halt;
end
...

get_value (evt,0,res);
{
   if (return_code () == ENEXT) printf ("there was no value! ");
   else printf ("first value is %d ", (int)(*res));
}

module print_all_values (event_t evt)
local int i,int res;
await (local(evt));
{local(i) = 0;}
while (1) do
   get_value (local(evt), local(i), (void**)&local(res));
   if (return_code () == ENEXT) then return;
   else
      {
         printf ("value #%d: %d\n", local(i), local(res));
         local(i)++;
      }
   end
end
end module

run mod1 ();
run mod2 ("mod2 called");

module play ()
while (1) do
   link (sched1);
   await (evt1);
   printf ("Ping ");
   link (sched2);
   await (evt2);
   printf ("Pong\n");
end
end module

module native pr (char *s)
unlink;
while (1) do
   printf (local(s));
end
end module

module main ()
pr_create ("hello ");
pr_create ("world!
");
end module

module native AnalyseInput ()
unlink;
...
while (1) do
   {
      switch (getchar ()){
         ...
      }
   }
end
end module

module native read_module (int fd,void *buf,size_t count,ssize_t *res)
local scheduler_t sched;
{local(sched) = current_scheduler ();}
unlink;
{(*local(res)) = read (local(fd),local(buf),local(count));}
link (local(sched));
end module

thread_t fast, slow;
event_t  start_fast, start_slow;

module fast_variant ()
await (start_fast);
stop (slow);
< fast service >
end module

module slow_variant ()
await (start_slow);
stop (fast);
< slow service >
end module

  ....  
  fast = fast_variant_create ();
  slow = slow_variant_create ();  
  start_fast = event_create ();
  start_slow = event_create ();
  ....

int condition = 0;

void notify (int *condition)
{
   (*condition) = 1;
}

module wait (int *cond)
while ((*local(cond)) == 0) do
   cooperate;
end
{(*local(cond)) = 0;}
end module

typedef struct condition_t
{
   int condition;
   event_t satisfied;
}
*condition_t;

void notify (condition_t cond)
{
   cond->condition = 1;
   generate (cond->satisfied);
}

module wait (condition_t cond)
while (local(cond)->condition == 0) do
   await (local(cond)->satisfied);
   if (local(cond)->condition == 0) then cooperate; end
end
{local(cond)->condition = 0;}
end module

void notify_one (condition_t cond)
{
   event_t event = get (cond);
   if (event == NULL) return;
   cond->condition = 1;
   generate (event);
}

void notify_all (condition_t cond)
{
   int i, k = cond->length;
   for (i = 0; i < k; i++) notify_one (cond);
}

module wait (condition_t cond)
local event_t event;
while (local(cond)->condition == 0) do
   {
      local(event) = event_create_in (current_scheduler ());
      put (local(cond),local(event));
   }
   await (local(event));
   if (local(cond)->condition == 0) then cooperate; end
end
{local(cond)->condition = 0;}
end module

typedef struct sync_point_t
{
   int sync_count;
   int threshold;
   event_t go;
}
*sync_point_t;

module sync (sync_point_t cond)
if (local(cond)->threshold > local(cond)->sync_count) then
   {local(cond)->sync_count++;}
   await (local(cond)->go);
else
   {
      local(cond)->sync_count = 0;   
      generate (local(cond)->go);
   }
end
end module

typedef struct rwlock_t
{
   int lock_count;
   int waiting_writers;
   event_t read_go;
   event_t write_go;
}
*rwlock_t;

module write_lock (rwlock_t rw)
{local(rw)->waiting_writers++;}
while (local(rw)->lock_count) do
   await (local(rw)->write_go);
   if (local(rw)->lock_count) then cooperate; end
end

{
   local(rw)->lock_count = -1;
   local(rw)->waiting_writers--;
}
finalize
{
   local(rw)->waiting_writers--;
}
end module

void write_unlock (rwlock_t rw)
{
   rw->lock_count = 0;
   if (!rw->waiting_writers) generate (rw->read_go);
   else generate (rw->write_go);
}

module read_lock (rwlock_t rw)
while ((local(rw)->lock_count < 0) || (local(rw)->waiting_writers)) do
   await (local(rw)->read_go);
end
{local(rw)->lock_count++;}
end module

void read_unlock (rwlock_t rw)
{
   rw->lock_count--;
   if (!rw->lock_count) generate (rw->write_go);
}

channel buffer;
event_t new_input;

module process ()
local int v;
while (1) do
   while (buffer->length == 0) do
      await (new_input);
      if (buffer->length == 0) then cooperate; end
   end
   {local (v) = get (buffer);}
   if (local(v) == 0) then return; end
   < processing the value >
   {local(v)--;}
   put (buffer,local(v));
   generate (new_input);
end
end module

channel in, out;
scheduler_t in_sched, out_sched;
event_t new_input, new_output;

module process ()
while (1) do
    if (in->length > 0) then
      run process_value (get (in));
    else 
      await (new_input);
      if (in->length == 0) then cooperate; end
    end
end
end module

module process_value (int v)
< processing the value >
link (out_sched);
put (out,local(v));
generate (new_output);
end module

module killer (event_t event,thread_t thread)
await (local(event));
stop (local(thread));
end module

module until (thread_t thread,event_t event)
local thread_t kill;
{local(kill) = killer_create (local(event),local(thread));}
join (local(thread));
stop (local(kill));
end module

run until (t,e);

int pause_length, limit_time, total_time, measure_numbers;
void print_out (char*);
event_t coin_evt, ready_evt, end_evt, display_evt, tilt_evt;

module beep_on (event_t event)
while (1) do
  await (local(event));
  print_out ("\07");
  cooperate;
end
end module

module phase1 ()
local thread_t beeper;
print_out ("press r when ready\r\n");   
{local(beeper) = beep_on_create (end_evt);}
await (ready_evt,limit_time);
stop (local(beeper));
if (return_code () == ETIMEOUT) then
   generate (tilt_evt);
   halt;
end
end module

module detector (event_t trigger,event_t produced,thread_t thread)
await (local(trigger));
stop (local(thread));
generate (local(produced));
end module

module phase2 ()
local thread_t cheat_detector;
print_out ("wait...\r\n");
{local(cheat_detector) = detector_create (end_evt,tilt_evt,self ());} 
repeat (myrandom ()) do cooperate; end
print_out ("GO!\r\n");
stop (local(cheat_detector));
end module

module increm (int *where)
while (1) do
   {(*local(where))++;}
   cooperate;
end
end module

   
module phase3 ()
local int count, thread_t counter, thread_t beeper;
{
   local(count) = 0;
   local(counter) = increm_create (&local(count));
   local(beeper)  = beep_on_create (ready_evt);
}
await (end_evt,limit_time);
stop (local(counter));
stop (local(beeper));
if (return_code () == ETIMEOUT) then
   generate (tilt_evt);
   halt;
else
   {total_time += local(count);}
   generate_value (display_evt, (void*)local(count));
end
end module

module final_display ()
repeat (pause_length) do cooperate; end
print_out ("**** final ");
generate_value (display_evt, (void*)(total_time / measure_number));
end module

module list_of_measures ()
repeat (measure_number) do
   run phase1 ();
   run phase2 ();
   run phase3 ();
end
run final_display ();
end module

module reflex_game ()
print_out ("A reflex game ... press c to start, q to stop.\r\n");
print_out ("You must press `e' as fast as possible after GO!.\r\n");
while (1) do
   {total_time = 0;}
   await (coin_evt);
   run until (list_of_measures_create (),tilt_evt);
   print_out ("game over. Press c to restart, q to stop.\r\n");
end
end module

void the_beginning (void){
   system ("stty raw -echo");
}

void the_end (void){
   print_out ("It's more fun to compete ...\r\n");
   system ("stty -raw echo");
   exit (0);
}

module native analyze_input ()
unlink;
the_beginning ();
while (1) do
   {
      switch(getchar()){
         case 'c': generate (coin_evt); break;
         case 'r': generate (ready_evt); break;

         case 'e': generate (end_evt); break;
         case 'q': the_end ();
      }
   }
end
end module

module analyze_display ()
local int res;
while (1) do
   await (display_evt);
   get_value (display_evt,0, (void**)&local(res));
   fprintf (stdout,"score: %d\r\n",local(res));
   cooperate;
end
end module

module analyze_tilt ()
while (1) do
   await (tilt_evt);
   print_out ("\07TILT!!\r\n");
   cooperate;
end
end module

module analyze_output ()
analyze_display_create ();
analyze_tilt_create ();
end module

   
module main ()
{
   ready_evt      = event_create ();
   coin_evt       = event_create ();
   end_evt        = event_create ();
   display_evt    = event_create ();
   tilt_evt       = event_create ();
   analyze_input_create ();
   reflex_game_create ();
   analyze_output_create ();
}
end module

int main ()
{
   list_t primes = init_list ();
   int current = 3, create = 1;
   while (1) {
      cell_t cell = primes->first;
      while (cell != NULL) {
         if (multiple_of (current,cell->val)) {
            create = 0; break;
         }
         cell = cell->next;
      }
      if (create) {
         add_list (primes,current);
         output (current);
      } else create = 1;
      current += 2;
   }
   return 0;
}

module producer (event_t start)
local int i;
{local(i) = 1;}
while (1) do
   {local(i) += 2;}
   generate_value (local(start), (void**)local(i));
   cooperate;
end
end module

#define get_first_val(evt,res) await(local(evt));get_value(local(evt),0, (void**)&local(res))

module filter_prime (event_t me)
local int prime, int res, event_t next;
   get_first_val(me,prime);
   {
      output (local(prime));
      filter_prime_create (local(next = event_create ()));
   }
   while (1) do
      cooperate;
      get_first_val(me,res);
      {
         if (local(res) % local(prime))
              generate_value (local(next), (void**)local(res));
      }
   end
end module 

module main ()
{
   event_t start = event_create ();
   producer_create (start);
   filter_prime_create (start);
}
end module

 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73
79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167
173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263
269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367
373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541 547 557 ...

module filter_lucky (int i,event_t trigger,event_t out)
local int base, int res, int k, event_t next;
   get_first_val(trigger,base);
   {
      generate_value (local(out), (void**)local(base));
      filter_lucky_create (local(k)= local(i)+1,
                           local(next) = event_create (),
                           local(out));
   }
   while (1) do
      cooperate;
      get_first_val(trigger,res);
      {
         local(k)++;
         if (local(k) % local(base)) 
            generate_value (local(next), (void**)local(res));
      }

   end
end module

module main ()
{
   event_t go = event_create ();
   event_t result = event_create ();

   out1_create (result);
   producer_create (go);
   filter_lucky_create (1,go,result);
}
end module

 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87
93 99 105 111 115 127 129 133 135 141 151 159 163 169 171 189 193 195
201 205 211 219 223 231 235 237 241 259 261 267 273 283 285 289 297
303 307 319 321 327 331 339 349 357 361 367 385 391 393 399 409 415
421 427 429 433 451 463 475 477 483 487 489 495 511 517 519 529 535
537 541 553 559 577 579 583 591 601 613 615 619 ...

module out2 (event_t event)
local int k, int res, int all;
while (1) do
   await (local(event));
   {local(k) = 0; local(all) = 0;}
   while (!local(all)) do
      get_value (local(event),local(k), (void**)&local(res)); 
      {
         if (return_code () == ENEXT) {
            local(all) = 1;
            if (local(k) == 2) output (local(res));
         }
         local(k)++;
      }
   end 
end
end module

module main ()
{
   event_t go = event_create ();
   event_t result = event_create ();

   out2_create (result);
   producer_create (go);
   filter_lucky_create (1,go,result);
   filter_prime_create (go,result);
}
end module

3 7 13 31 37 43 67 73 79 127 151 163 193 211 223 241 283
307 331 349 367 409 421 433 463 487 541 577 601 613 619 631 643 673
727 739 769 787 823 883 937 991 997 1009 1021 1039 1087 1093 1117 1123
1201 1231 1249 1291 1303 1459 1471 1543 1567 1579 1597 1663 1693 1723
1777 1801 1831 1879 1933 1987 2053 2083 2113 2221 2239 2251 2281 2311
2467 2473 2557 2593 2647 2671 2689 2797 2851 2887 2953 2971 3037 3049
3109 3121 3163 3187 3229 3259 3301 3307 3313 ...

typedef struct channel_t {
   cell_t   first;
   cell_t   last;
   int      length;
   event_t  new_value;
} *channel_t;

void put (channel_t chan,value_t v)
{
   if (chan->length == 0) {
      chan->last = cell_create (v);
      chan->first = chan->last;
      generate (chan->new_value);
   } else {
      chan->last->next = cell_create (v);
      chan->last = chan->last->next;
   }
   chan->length++;
}

value_t extract (channel_t chan)
{
   cell_t head;
   value_t res;
   if (chan->length == 0) return NULL;
   head = chan->first;
   chan->first = head->next;
   res = head->val;
   free (head);
   chan->length--;
   return res;
}

module get (channel_t in,value_t *res)
while (local(in)->length == 0) do
   await (local(in)->new_value);
   if (local(in)->length == 0) then cooperate; end
end
{(*local(res)) = extract (local(in));}
end module

#define GET(chan) \
   while (chan->length == 0) do\
      await (chan->new_value);\
      if (chan->length == 0) then cooperate; end\
   end

module producer_process (value_t from,value_t incr,channel_t out)
local value_t val;
{local(val) = local(from);}
while (1) do
   if (local(out)->length < 10) then
   {
      put (local(out),local(val));
      local(val) += local(incr);
   }
   end
   cooperate;
end
end module

module out_process (channel_t in)
while (1) do
   GET (local(in))
   printf ("%d ",extract (local(in)));
   fflush(stdout);
end
end module

module main()
{ 
   channel_t c = channel_create ();
   producer_process_create (0,1,c);
   out_process_create (c);
}
end module

module filter_process (int index,int base,channel_t in,channel_t out,filter_t filter)
while (1) do
   GET (local(in))
   {
      int v = extract (local(in));
      local(index)++;
      if (local(filter) (local(index),local(base),v)) 
            put(local(out),v);
   }
end
end module

module sift_process (channel_t in,channel_t out,filter_t filter)
local int k;
{local(k) = 1;}
while (1) do
   GET (local(in))
   {
      channel_t intern = channel_create_in (current_scheduler ());
      int v = extract (local(in));
      put(local(out),v);
      local(k)++;
      filter_process_create (local(k),v,local(in),intern,local(filter));
      local(in) = intern;
   }

end
end module

int primes (int index,int base,int value)
{
   return value%base;
}

module main()
{ 
   channel_t c1 = channel_create ();
   channel_t c2 = channel_create ();
   producer_process_create   (3,2,c1);
   sift_process_create       (c1,c2,primes);
   out_process_create        (c2);
}
end module

while (1) do 
   printf ("loop!"); 
end

while (1) do
   await (evt);
   printf ("loop!"); 
end

while (1) do
   await (evt1);
   await (evt2);
   { ... }
end

while (search) do
   get_value (evt,i,&res);
   {
      if (return_code () == ENEXT) {
         search = 0;
      } else {
         printf ("value #%d: %d ", i,res);
         i++;
         generate_value (evt,i);
      }
   }
end

{
   for (;;) {}
}

module m ()
m_create ();
end module

module m ()
m_create ();
halt
end module

module m ()
run m ();
end module

{
   int i;
   for (i=0; i<2*N; i++) {
      f ();
   }
}

{
   int i;
   for (i=0; i<N; i++) {
      f ();
   }
}
cooperate;
{
   int i;
   for (i=0; i<N; i++) {
      f ();
   }
}

repeat (2*N) do
   f ();
   cooperate
end

module processing_thread ()
   while (!X) do cooperate end;
   ....
end

module processing_thread ()
   await (X);
   ....
end

generate (X);
processing_thread_create ();

{
   while (!X) {}
   Y=1;
}

{
   while (!Y) {}
   X=1;
}

while (!X) do cooperate; end
{Y=1;}

while (!Y) do cooperate; end 
{X=1;}

await (X);
generate (Y)

await (Y);
generate (X)

scheduler_t move_scheduler, paint_scheduler;

main ()
{
   move_scheduler = scheduler_create ();
   paint_scheduler = scheduler_create ();
   ....
   while (1) {
        scheduler_react (move_scheduler);
        scheduler_react (paint_scheduler);
   }
}

void object_creation (graphical_object obj)
{
   move_create_in (move_scheduler,obj);
   paint_create_in (paint_scheduler,obj);
}

inst =
   inst ... inst
|  atomic
|  non-atomic

atomic =
   {<c-code>}
|  stop (exp)
|  suspend (exp)
|  resume (exp)
|  generate (exp)
|  generate (exp, exp)

exp =
   special_exp
|  <c-exp>

special_exp =
   <module>_create (exp, ..., exp)
|  return_code ()
|  self ()

non-atomic =
   cooperate
|  halt
|  return
|  await (exp)
|  await (exp, exp)
|  join (exp)
|  join (exp,exp)
|  get_value (exp, exp, exp)
|  if (exp) then inst else inst end
|  while (exp) do inst end
|  repeat (exp) do inst end
|  run <module> (exp, ..., exp)
|  extensions

extensions =
   nothing
|  repeat* (n, inst) do inst end
|  while* (exp, inst) do inst end
|  await* (event)
|  await* (event, n)
|  get_value* (event, n, v)

fireable (thread)
   return thread.suspended = false and thread.state = CONT

stable (sched)
   forall thread in sched.linked
       if (fireable (thread)) return false
   return true

make_decision (sched)
   if (sched.move = true) return sched<move = false>
   else return sched<eoi = true>

start_instant (sched,env)
   sched.eoi = false
   sched.move = false
   transfer_events (sched)
   process_orders (sched,env)
   reset_threads (sched)
   finalize_stopped_threads (sched)

transfer_events (sched)
    sched.events = get_events (to_broadcast)
    sched.val = get_values (to_broadcast)
    sched.to_broadcast = Ø

process_orders (sched,env)
    forall order in previous
       if (order.kind = SUSPEND_ORDER) 
           order.thread.suspended = true
       else if (order.kind = RESUME_ORDER)  
           order.thread.suspended = false
       else if (order.kind = STOP_ORDER)    
           sched.to_finalize += thread
           thread.state = TERM
       else if (order.kind = LINK_ORDER)
           sched.linked += order.thread
    sched.orders = Ø

reset_threads (sched)
    forall thread in sched.linked
       if (thread->state = TERM)
          sched.linked -= thread
       else if (thread->suspended = false and thread->state = COOP)
          thread.state = CONT

finalize (sched,env,thread)
   if (thread.state = TERM) return
   thread.state = TERM
   sched.events += thread.signal
   sched = sched'
   env = env'
   if (thread.called != NULL) finalize (sched,env,thread.called)

finalize_stopped_threads (sched)
   forall thread in sched.to_finalize
      finalize (thread)
   sched.to_finalize = Ø

repeat3 (5) do 
   seq0 (
       awaite (event),
       cooperatetrue
   )
end

repeat (5) do 
   seq(
      await (event),
      cooperate
   )
end

awake_all (sched, event) 
    forall thread in sched.waiting (event)
       awake (sched,thread,event)
    return sched

awakeable (thread)
   return thread.suspended = false and thread.state = WAIT

awake (sched,thread,event)
   if (awakeable (thread)) 
       thread.state = CONT,
       sched.waiting(event) -= thread
       sched.timer -= thread

start_instant (sched,env)
   sched.eoi = false
   sched.move = false
   timer_processing (sched)
   transfer_events (sched)
   process_orders (sched,env)
   reset_threads (sched)
   finalize_stopped_threads (sched)

timer_processing (sched)
   sched.instant = sched.instant + 1
   forall thread in sched.timer
     if (awakeable (thread) and thread.deadline ≤ sched.instant) 
        awake (thread),

#include "fthread.h"
#include <stdio.h>

void h (void *id)
{
   while (1) {
      fprintf (stderr,"Hello ");
      ft_thread_cooperate ();
   }
}

void w (void *id)
{
   while (1) {
      fprintf (stderr,"World!\n");
      ft_thread_cooperate ();
   }
}

int main (void)
{
  ft_scheduler_t sched = ft_scheduler_create ();
  ft_thread_create (sched,h,NULL,NULL);
  ft_thread_create (sched,w,NULL,NULL);
  ft_scheduler_start (sched);
  ft_exit ();
  return 0;
}

DEFINE_AUTOMATON (switch_aut)
{
   void       **args    = ARGS;
   ft_event_t   event   = args[0];
   ft_thread_t  thread1 = args[1];
   ft_thread_t  thread2 = args[2];
   BEGIN_AUTOMATON
     STATE (0)
     {
        ft_scheduler_resume (thread1);
     }
     STATE_AWAIT (1,event)
     {
        ft_scheduler_suspend (thread1);
        ft_scheduler_resume  (thread2);
        GOTO(2);
     }
     STATE_AWAIT (2,event)
     {
        ft_scheduler_suspend (thread2);
        ft_scheduler_resume  (thread1);
        GOTO(1);
     }
   END_AUTOMATON
}

void switch_aut (void *arg)
{
   void       **args    = arg;
   ft_event_t   event   = args[0];
   ft_thread_t  thread1 = args[1];
   ft_thread_t  thread2 = args[2];
   ft_scheduler_resume (thread1);
   while (1) {
      ft_thread_await (event);
      ft_scheduler_suspend (thread1);
      ft_scheduler_resume  (thread2);
      ft_thread_cooperate ();    
      ft_thread_await (event);
      ft_scheduler_suspend (thread2);
      ft_scheduler_resume  (thread1);
      ft_thread_cooperate ();
   }
}

module switch_aut (ft_event_t event,ft_thread_t thread1,ft_thread_t thread2)
resume (local(thread1));
while (1) do
   await (local(event));
   suspend (local(thread1));
   resume (local(thread2));
   cooperate;
   await (local(event));
   suspend (local(thread2));
   resume (local(thread1));
   cooperate;
end
end module

void sum_aux (int n)
{
   if (n == 0) { printf ("0"); return; }
   ft_thread_cooperate_n (n);
   sum_aux (n - 1);
   printf ("+%d",n);
}

 
void sum (void *k)
{
   sum_aux ((int)k);
   printf (" = instant number\n");
   exit(0);
}

void trace_instants (void *n)
{
   int i = 0;
   while (1){
      printf ("\ninstant %d: ", i++);
      ft_thread_cooperate();
   }
}

int main(int argc, void** argv)
{
  ft_scheduler_t sched = ft_scheduler_create ();
  ft_thread_create (sched,trace_instants,NULL,NULL);
  ft_thread_create (sched,sum,NULL,argv[1]);
  ft_scheduler_start(sched);
  ft_exit();
  return 0;
}

instant 0:
instant 1:
instant 2:
instant 3:
instant 4:
instant 5:
instant 6:
instant 7:
instant 8:
instant 9:
instant 10: 0+1+2+3+4 = instant number