Professional

Home
Learn Shen
Videos
Community 
Wiki
Community
OS Kernel
OS Library
Shen Professional

Concurrency
Shen Professional contains two models for concurrency which are closely related. The first model is the special or restricted theory of concurrent processes which allows the creation of non-communicating parallel processes.

The second is the general theory of concurrent processes which allows the creation of communicating concurrent processes with local state.

Both theories are based on a simple and straightforward extension of the Kl instructions set. The basic Kl instruction extension to create concurrent Shen is to create a thread and to kill it. Both models are loaded by clicking on the concurrency menu option and downloading the concurrency plugin.

1. The Restricted Theory of Concurrent Processes

2. Examples of Simple Concurrent Processes

3. Timing Results on an 8 Core Desktop

4. The General Theory of Concurrent Processes

5. A Simple Communicating Concurrent Program

1. The Restricted Theory of Concurrent Processes

The special or restricted theory of concurrent processes deals with non-communicating processes. In this document non-communicating processes are referred to as simple processes (SPs). SPs are essentially suitable for straightforward parallelism.

A thread is created by taking a lazy expression and passing it as an argument to the function thread. The type of this function is
(lazy A) --> thread. The function terminate takes a thread and terminates it returning the thread. If the thread is already terminated no error is raised. The type of this function is thread --> thread. Threads do not return any computed result and hence are suitable only for event loops.

An SP can return a result. The function
proc-> takes an expression of type A and returns an expression of type (sproc A). The function <-proc receives a simple process and returns the result of its computation. The type of this function is (sproc A) --> A. Thus (<-proc (proc-> (* 2 3))) returns 6. If the process has not terminated then <-proc will return an error. The function terminated? will return true for any simple process that has terminated and false otherwise. The type of terminated? is (sproc A) --> boolean. <-proc! of type (sproc A) --> A will return a result only if the process has terminated and will recurse until it does. The function thread-in will extract the thread from a process and has the type (sproc A) --> thread. end will terminate any simple process whether or not it has terminated already.

The following type secure parallel functions exist within the concurrency plugin.

Function Type Description
p-and boolean ..... boolean --> boolean Polyadic. Takes a series of booleans and and-parallelises them.
p-anycases As cases Works as cases except the tests are computed in parallel and the first case that applies is used irrespective of its order in the list of cases.
p-apply F : A1 ...An --> B;
X1 : A1;
...;
Xn : An;
______________________
(p-apply F X1...Xn) : B;
Applies a function to a series of arguments computing the arguments in parallel.
p-cases As cases Works as cases except the tests are computed in parallel.
p-let As let Parallel local assignments. Local assignments are computed in parallel and result returned. Two restrictions.

a. there can be no data dependencies between assignments (variable sharing).
b. the final expression must consist of a function applied to a series of local variables
p-map (A --> B) --> (list A) --> (list (sproc B)) Constructs a list of simple processes by mapping a function over a list.
p-or boolean ..... boolean --> boolean Polyadic. Takes a series of booleans and or-parallelises them.

2. Examples of Simple Concurrent Processes

(10+) (proc-> (* 7 8))
?56? : (sproc number)

(11+) (<-proc (proc-> (* 7 8)))
56 : number

(12+) (<-proc! (proc-> (* 7 8)))
56 : number

(13+) (p-or false false true)
true : boolean

(14+) (p-let X (* 3 3)
Y (* X X)
(* X Y))
(* X X) is data dependent

(15+) (p-map (+ 1) [1 2 3 4 5])
[?2? ?3? ?4? ?5? ?6?] : (list (sproc number))

The evaluation in (14+) fails because X and Y have to be evaluated in series.

3 Timings Results on an 8 Core Desktop

Some of these functions were timed using a 4.3 GHz 8 core AMD desktop using Willi Riha's prime library function. The first test was on parallel local assignments. The program was identical in the serial and parallel cases apart from the use of p-let and let. Here are the programs 1 p-let for parallel case, let for serial.

(time (p-let/let A (prime? (* 18014398241046527 16769023))
                  B (prime? (* 18014398241046527 16769023))
                  C (prime? (* 18014398241046527 16769023))
                   ........................
                  [A B C ...................]))) 

The second test anded a positive prime number test (prime? 18014398241046527) n times. p-and for parallel case, and for serial.

(and/p-and (prime? (* 18014398241046527 16769023)) ... (prime? (* 18014398241046527 16769023)))      

The results are given below.

serial vs parallel let

  serial  parallel
n = 3 47.64 21.4
n = 8 126 32
 
serial vs parallel and
  serial parallel
n = 2 16.5 10
n = 3 25 11
n = 4 34 12.7
n = 5 42 13.5
n = 6 50 14.4
n = 7 62.78 14.9
n = 8 66 16.8

4. The General Theory of Concurrent Processes

Complex processes (CPs) are concurrent processes that can communicate with each other, have local state and are based on a general theory of concurrent processes. CPs have reflection built into them and can interrogate their own local state.

The way to invoke a CP is through the @. notation. Either

(@. <variable> <process description>)

or

(@. <variable> <process description> <local state>)

invokes a complex process which is designated by the bound <variable>. The function <-state retrieves the local state of a CP. The function state-> takes a CP and a value and stores the value in the local state of the CP returning the CP.

An example;
(@. P (count-down P 100))

(define count-down
P 0 -> (state-> P 0)
P N -> (count-down P (- N 1)))

describes a process which counts down from a 100 and then stores zero in the local state. The result returned is a CP with the local state set to zero.

The type theory of CPs is based on the idea that a CP is rather similar to a function in having a channel that allows the local state to be updated and a result which is returned when the process terminates. The type of a CP is (A ! B) where A is the type of the local state and B is the type of the result. The type rules for @. are

P : (A ! B) >> D : B;
(@. P D) : (A ! B);

S : A;
P : (A ! B) >> D : B;
(@. P D S) : (A ! B);

The count-down function has the following type.

(define count-down
  {(number ! B) --> number --> (number ! B)}
  P 0 -> (state-> P 0)
  P N -> (count-down P (- N 1)))

(@. P (count-down P 100)) has no type. However if we arrange for count-down to return say true and not a process then things change.

(10+) (define count-down
        {(number ! B) --> number --> boolean}
         P 0 -> (do (state-> P 0) true)
         P N -> (count-down P (- N 1)))
count-down : ((number ! B) --> (number --> boolean))

(11+) (@. P (count-down P 100))
?complex process? : (number ! boolean)

CPs inherit the functions applicable to SPs (simple processes). The inheritance rule is.

P : (A ! B);
P : (sproc B);

<-proc and <-proc! will return solutions from CPs. end will terminate CPs and SPs.

(12+) (<-proc! (@. P (count-down P 100)))
true : boolean

5. A Simple Communicating Concurrent Program

To conclude here is a simple program using two CPs, A and B, which are embedded in an SP C. A begins by incrementing its local state while B simply spins its wheels doing nothing in particular. When the local state of A has risen by at least 106 , C prints switch and then instructs A to spin its wheels and B increments its state until it rises by at least 106 and C then repeats the cycle. When this cycle is repeated 100 times, C ends both A and B and prints done as the returned value thus ending itself.

(let \\ start a complex process counting setting the local state to (@p 0 true)
     A (@. P (count P) (@p 0 true)) 
     \\ start a complex process counting setting the local state to (@p 0 false)
     B (@. P (count P) (@p 0 false)) 
     \\ start a simple process to monitor the two running 
     C (proc-> (regulate A B 0))
     done) 
     
(define count
  {((number * boolean) ! A) --> B}
   \\ if flag set to false just spin wheels
    P -> (count P) where (not (snd (<-state P)))
    \\ otherwise increment numeric part of local state 
    P -> (count (state-> P (@p (+ 1 (fst (<-state P))) true)))) 

(define regulate
  {((number * boolean) ! A) --> ((number * boolean) ! A) --> number --> symbol}
  \\ after 100 turns terminate A and B 
  A B 100 -> (do (end A) (end B) (print done))
  \\ flip roles 
  A B Turn -> (do (output "switch ") 
                  (regulate (start B) (pause A) (+ Turn 1))) 
                                      where (> (fst (<-state A)) (* (+ Turn 1) 1e6))
  \\ otherwise keep checking
  A B Turn -> (regulate A B Turn)) 

(define pause
  {((number * boolean) ! A) --> ((number * boolean) ! A)} 
  Process -> (state-> Process (@p (fst (<-state Process)) false)))

(define start
  {((number * boolean) ! A) --> ((number * boolean) ! A)} 
  Process -> (state-> Process (@p (fst (<-state Process)) true)))

Here is a script.

(14+) (let A (@. P (count P) (@p 0 true)) 
           B (@. P (count P) (@p 0 false)) 
           C (proc-> (regulate A B 0)) 
           running)
running : symbol

(15+) switch switch switch switch switch switch switch switch switch switch switch switch switch
 switch switch switch switch switch switch switch switch switch switch switch switch switch switch 
switch switch switch switch switch switch switch switch switch switch switch switch switch switch 
switch switch switch switch switch switch switch switch switch switch switch switch switch switch 
switch switch switch switch switch switch switch switch switch switch switch switch switch switch 
switch switch switch switch switch switch switch switch switch switch switch switch switch switch 
switch switch switch switch switch switch switch switch switch switch switch switch switch switch 
switch switch switch done