Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
language:langs:chp [2022/08/02 16:27]
rajit [Conditionals]
language:langs:chp [2023/04/09 19:28] (current)
rajit [Arrays: dynamic v/s non-dynamic indices]
Line 45: Line 45:
 This corresponds to setting ''x'' and ''y'' to true in parallel. Only after both are complete, ''z'' is set to false. This corresponds to setting ''x'' and ''y'' to true in parallel. Only after both are complete, ''z'' is set to false.
  
-==== Conditional execution ====+===== Conditional execution =====
  
 The selection statement uses the guarded command syntax. The statement The selection statement uses the guarded command syntax. The statement
Line 87: Line 87:
 In the published literature, non-deterministic selections are usually written using a thin bar ''|'' rather than the thick bar ''[]''. However, this can create some ambiguities in parsing. For example, consider the statement ''[ a -> y:=b | c | d -> skip ]''. This can be parsed in a number of ways, and it is not clear which one was the intended option. In the published literature, non-deterministic selections are usually written using a thin bar ''|'' rather than the thick bar ''[]''. However, this can create some ambiguities in parsing. For example, consider the statement ''[ a -> y:=b | c | d -> skip ]''. This can be parsed in a number of ways, and it is not clear which one was the intended option.
  
-==== Loops ====+===== Arrays: dynamic v/s non-dynamic indices ===== 
 + 
 +Suppose an array ''x'' has been declared as: 
 +<code act> 
 +int x[10]; 
 +</code> 
 + 
 +Now when ''x'' is accessed in CHP, it could be accessed with an array index that is a run-time constant, or an index that is computed at run-time. For example, the CHP program 
 +<code act> 
 +chp { 
 +   ... 
 +   x[0] := x[0] + 1; 
 +   ... 
 +
 +</code> 
 +uses ''x'' with a constant index. As opposed to this, the program 
 +<code act> 
 +chp { 
 +   ... 
 +   x[i] := x[i] + 1; 
 +   ... 
 +
 +</code> 
 +uses ''x'' with an index that is computed using the run-time value of ''i''. This second category of arrays are referred to as //dynamic arrays//---not because the array size is dynamic, but because the element of the array accessed depends on a value that is computed by the circuit.  Such dynamic arrays have to be translated into memory structures, or other circuits where the element being accessed has to be specified at run-time. Arrays with constant references can be directly mapped to circuit implementations of asynchronous registers, since the element to be accessed can be determined statically. 
 + 
 + 
 +===== Loops =====
  
 Loops/repetitions use a syntax similar to selections, with the addition of the Kleene star.  Loops/repetitions use a syntax similar to selections, with the addition of the Kleene star. 
Line 128: Line 154:
  
 Loop guards can only use local variables. Hence, it is an error if a variable appearing in a loop guard is either (i) a global variable; or (ii) accessible via the port list of the process; or (iii) involves a channel probe. This ensures that loop guards cannot include any shared variables. Loop guards can only use local variables. Hence, it is an error if a variable appearing in a loop guard is either (i) a global variable; or (ii) accessible via the port list of the process; or (iii) involves a channel probe. This ensures that loop guards cannot include any shared variables.
 +
 +===== Advanced expression syntax =====
  
 ==== Channels in expressions ==== ==== Channels in expressions ====
Line 158: Line 186:
 If ''A'' is an input port, then ''A'' can participate in a //channel expression//. For example, we can write: If ''A'' is an input port, then ''A'' can participate in a //channel expression//. For example, we can write:
 <code act> <code act>
-*[[A=3 -> X!true;A?+[A=3 -> X!true;A?
- []A!=3 -> X!false;A?+[]A!=3 -> X!false;A?
- ]+]
 </code> </code>
 Here, ''A=3'' is a channel expression. This has the following meaning: first, wait for a value to be pending on the input channel ''A''; then compare it to 3. In other words, this expression includes an //implicit// probe. It also permits the pending value on ''A'' to be inspected. Note that ''A!=3'' //also includes waiting for a value to be pending on the input channel//, and is not the literal negation of the condition corresponding to ''A=3''. In other words, in the program fragment above, the selection statement should be read: wait for a value to be pending on input channel ''A''; if the value is 3, do the first set of statements; otherwise pick the second set of statements. Here, ''A=3'' is a channel expression. This has the following meaning: first, wait for a value to be pending on the input channel ''A''; then compare it to 3. In other words, this expression includes an //implicit// probe. It also permits the pending value on ''A'' to be inspected. Note that ''A!=3'' //also includes waiting for a value to be pending on the input channel//, and is not the literal negation of the condition corresponding to ''A=3''. In other words, in the program fragment above, the selection statement should be read: wait for a value to be pending on input channel ''A''; if the value is 3, do the first set of statements; otherwise pick the second set of statements.
Line 221: Line 249:
  
 Essentially every channel variable ''V'' can be translated into ''(#V ? V : ERR)''. Note that this is a different translation compared to guards. Note that since probes are only allowed in guards of selection statements, negated probes are not possible in other contexts.  Essentially every channel variable ''V'' can be translated into ''(#V ? V : ERR)''. Note that this is a different translation compared to guards. Note that since probes are only allowed in guards of selection statements, negated probes are not possible in other contexts. 
 +
 +===== Advanced channels =====
  
 ==== Exchange channels ==== ==== Exchange channels ====
Line 233: Line 263:
 Four-phase handshake channels involve two synchronizations. If you need to make this explicit in the CHP, the ''!'' (send) and ''?'' (receive) operators can be replaced with ''!+'' (first half of send), ''!-'' (second half of send), or ''?+'' (first half of receive), ''?-'' (second half of receive). The second half is purely synchronization and should not have any data. Four-phase handshake channels involve two synchronizations. If you need to make this explicit in the CHP, the ''!'' (send) and ''?'' (receive) operators can be replaced with ''!+'' (first half of send), ''!-'' (second half of send), or ''?+'' (first half of receive), ''?-'' (second half of receive). The second half is purely synchronization and should not have any data.
  
-=== The chp-txt sublanguage ===+===== Syntactic replication ===== 
 + 
 +There are three common uses of syntactic replication in CHP, and the language has syntactic support for them. The first two correspond to scenarios where you have a number of items separated by semicolon or comma. The syntax for this follows the generic template for [[language:controlflow|syntactic replication]]: 
 + 
 +<code act> 
 +(; i : 4 : x[i] := 0) 
 +</code> 
 + 
 +corresponds to 
 + 
 +<code act> 
 +x[0] := 0; x[1] := 0; x[2] := 0; x[3] := 0 
 +</code> 
 + 
 +Note the missing trailing semicolon. Following this with another statement in sequence would be written 
 + 
 +<code act> 
 +(; i : 4 : x[i] := 0 ); 
 +x[0] := 1 - x[1] 
 +</code> 
 + 
 +Similarly, the semicolon can be replaced with a comma to specify parallel execution. 
 + 
 +Syntactic replication is also supported for guarded commands.  The statement 
 + 
 +<code act> 
 +[ v = 0 -> x := x  - v 
 +[] ( [] i : 3 : v = i+2 -> x := x + i 
 +
 +</code> 
 + 
 +is the same as 
 + 
 +<code act> 
 +[ v = 0 -> x := x - v 
 +[] v = 0+2 -> x := x + 0 
 +[] v = 1+2 -> x := x + 1 
 +[] v = 2+2 -> x := x  + 2 
 +
 +</code> 
 + 
 +This construct can be used to work around one of the current restrictions of CHP. A natural way to write a merge process in ACT is: 
 +<code act> 
 +*[ C?c; I[c]?d; O!d ] 
 +</code> 
 +This will error out because the CHP has a //dynamic// channel access---i.e. the channel accessed is computed at run-time. While this is supported for int arrays, for example, that is because there is an efficient compilation mechanism for large int arrays (via memory macros). To work around this restriction, one can use: 
 +<code act> 
 +*[ C?c; [ ([] i : N : c = i -> I[i]?d) ]; O!d ] 
 +</code> 
 +where ''N'' is the number of channels in the ''I'' array. This approach ensures that index for the array ''I[]'' is always a constant. 
 + 
 +====== The chp-txt sublanguage ======
  
 Since the CHP syntax is quite different from commonly used programming languages, we have provided a variation called ''chp-txt'' that uses notation that may be a bit more familiar to programmers. Note that ''chp-txt'' is viewed internally as exactly the same as ''chp'', so only one ''chp''/''chp-txt'' block can be used in a process. Since the CHP syntax is quite different from commonly used programming languages, we have provided a variation called ''chp-txt'' that uses notation that may be a bit more familiar to programmers. Note that ''chp-txt'' is viewed internally as exactly the same as ''chp'', so only one ''chp''/''chp-txt'' block can be used in a process.
Line 241: Line 322:
 } }
 </code> </code>
-The basic statements, expression syntax, etc. remains unchanged from the CHP language. What is different is the syntax for loops, selection statements, and short-cuts.+The basic statements, expression syntax, etc. remains unchanged from the CHP language. What is different is the syntax for loops, selection statements, and short-cuts, plus additional syntax for baseline send and receive operations. 
 +==== Send and receive ==== 
 + 
 +In addition to the syntax 
 +<code act> 
 +X!e 
 +</code> 
 +for a send operation, ''chp-txt'' also supports 
 +<code act> 
 +send (X, e) 
 +</code> 
 +In addition to the syntax 
 +<code act> 
 +X?v 
 +</code> 
 +for a receive operation, ''chp-txt'' also supports 
 +<code act> 
 +recv (X, v) 
 +</code> 
  
 ==== Conditionals  ==== ==== Conditionals  ====
Line 259: Line 359:
 </code> </code>
 The ''else'' clause can be written ''else : Sn'' as the last item in the list of cases.  The ''else'' clause can be written ''else : Sn'' as the last item in the list of cases. 
 +
 +A non-deterministic statement is written the same way, except the keyword ''arb_select'' is used instead of ''select''.
 +
 +Waiting for a condition is a commonly used operation. This was written in chp as ''[cond]''; in ''chp-txt'', this is written
 +<code act>
 +wait-for (condition)
 +</code>
 +
 +==== Loops ====
 +
 +A simple while loop written in CHP as
 +<code act>
 +*[ G -> S ]
 +</code>
 +is written in ''chp-txt'' as:
 +<code act>
 +while (G) {
 +   S
 + }
 +</code>
 +A while loop with multiple guards of the form
 +<code act>
 +*[ G1 -> S1 [] G2 -> S2 ... [] Gn -> Sn ]
 +</code> 
 +is written as 
 +<code act>
 +while { 
 + case G1 : S1;
 + case G2 : S2;
 +  ...
 + case Gn : Sn
 +}
 +</code>
 +A do-loop is written:
 +<code act>
 +do {
 +  S 
 +} while (G)
 +</code>
 +Finally, an infinite loop is written:
 +<code act>
 +forever {
 +   S
 +}
 +</code>
 +
 +==== An example ====
 +
 +The CHP program:
 +<code act>
 +chp {
 +   *[ L?x; R!x ]
 +}
 +</code>
 +would be written in ''chp-txt'' as
 +<code act>
 +chp-txt {
 +   forever {
 +      recv (L, x); send (R, x)
 +   }
 +}
 +</code>
 +
 +The CHP program:
 +<code act>
 +chp {
 +   *[ L?x; [ x > 0 -> R!x [] else -> skip ] ]
 +}
 +</code>
 +would be written
 +<code act>
 +chp-txt {
 +   forever {
 +      recv (L, x);
 +      select {
 +        case x > 0 : send (R, x);
 +        else : skip
 +      }
 +   }
 +}   
 +</code>