2.4.3.2 The Expansion of Distributors

Unlike the old expander, the new expander cannot expand the distributors directly because the distributor is represented by a subtree instead of a substring. According to the Theorem 3.4 (given in [JL92]p.267), every distributor can be replaced by a concatenator. So, we need to create a function called transform in order to transform all distributor subtrees into concatenator subtrees before expansion.

For example, we declare an array as following:

If the distributor has the form ;[a], we have the following steps to transform it into a concatenator:

1)

in order to use normal form to define the concatenator, we assign ini = inc = 1, and then, find out array a's lower bound, upper bound and increase step from the array table, use the formula m = (fi-ini) div inc + 1 to calculate m, use the formula i = ini+(j-1)*inc to calculate the value of the range variable, check how many dimensions are in the array;

2)

according to the information we just got, we can construct a concatenator which corresponds to the distributor:

where ``1'' is a index variable and it indicates the sequence of the separators.

Let's consider the other example, we have the distributor:

where the outer-most separator ``;'' is ``1'', the middle separator ``,'' is ``2'', the last separator ``;'' is ``3''. So, we will have the concatenator:

If the distributor has the form ;1[,[;[b]]], we will change it as follows:

If the distributor has the form , we will change it as follows:

If the distributor has the form , we will change it as follows:

We will discuss the function transform later. Now let's see how the syntax tree is changed after transformation. For instance, if we have a Macro COSY program as follows:

After parsing, we have the syntax tree as follows:

  Program
    (Programbody4
     (Array
      (Arraybody1
       (Simpleardecl
        (Name1 (Name "a"),Simpleardeclbody1 (Iexpr1 (Integer 3))))),
      Programbody1
       (Path
        (Sequence1
         (Orelement1
          (Gelement3
           (Distributor4
            (Simicol ";",
             Sequence1
              (Orelement1
               (Gelement1
                (Nostar
                 (Element (Event2 (Name "a"))))))))))))))

After transformation, the distributor is changed to a concatenator:

  Program
    (Programbody4
     (Array
      (Arraybody1
       (Simpleardecl
        (Name1 (Name "a"),Simpleardeclbody1 (Iexpr1 (Integer 3))))),
      Programbody1
       (Path
         (Orelement1
          (Gelement2
           (Sreplicator1
            (Range_spec
             (Indexvariable (Name "1"),Iexpr1 (Integer 1),
              Iexpr1 (Integer 3),Iexpr1 (Integer 1)),
             Concseq
              (Sequence1
               (Orelement1
                (Gelement1
                 (Nostar
                  (Element
                   (Event3
                    (Name "a",
                     Meventbody1
                      (Plus
                       (Iexpr1 (Integer 1),
                        Iexpr4
                         (Mult
                          (Iexpr4
                           (Plus
                            (Iexpr2
                             (Rangevariable
                              (Name
                               "1")),
                               Iexpr4
                                (Iexpr1
                                 (Integer
                                  ~1)))),
                                  Iexpr1
                                   (Integer
                                    1))))))))))), Simicol ";")))))))))

Now, we need to prove the new expansion is equivalent to the old expansion:

where parser is a function which translates the Macro COSY program from a string to a syntax tree according to the Macro COSY grammar, pathfirst is a function which puts all the paths in front of the processes, transform is a function which transforms all distributor subtrees into replicator subtrees, csr is a function which checks whether the syntax tree satisfies all context-sensitive restrictions, is a function which expands the syntax tree into a string which is in the form of the Basic COSY program, is a function which expands a Macro COSY program from a string into a string which is in the form of the Basic COSY program, o denotes a composition of two functions.