Firstly, let's introduce the old expander.
Let MT, MNT stand for macro notation
terminal symbols and macro notation non-terminal symbols
respectively.
Let 
denote the initial non-terminal of macro notation.
Let 
mean that there exists a production of macro
notation grammar (including context-sensitive constraints) which
transforms a string x into a string y, where 
.
Define:
where 
is a transitive closure of
, i.e., 
(and 
respectively) means that there
exists a production sequence of length one or more starting
from x and resulting in y.
The elements of MPROGRAM are called macroprograms, the elements of MGEN are called macro expressions or macro generators.
Consider the following three mappings:
We now extend as and val to: 
and
. Let 
denote the set of all
integer expressions of our macro notation without range variables,
i.e.,
and let RVAR denote the set of all range variables, i.e.,
Every 
can be represented as
where 
, 
, 
and no substring of 
belongs to . We
define:
For example,
.
Similarly, every can be represented as
where , 
,
and no substring of belongs to RVAR.
The context-sensitive restriction Irest1 guarantees uniqueness of
the above representation. We define:
In the sequel we shall use the symbol as to denote both as and
, and val to denote both val and 
.
Throughout the following sections we will be representing macro programs schematically to facilitate the statement of definitions, theorems and their proofs. Capitalized names of basic or macro non-terminals will stand for the set of strings which may be generated from that non-terminal. Thus:
The subscript ``0'' will indicate that all strings of the set
contain no range variable.
Thus:
To obtain the schematic representations of macro programs we now define:
The complete expansion of a macro program mprog is given by expand(mprog), where the lower case names corresponding to the upper case names defined above represent arbitrary elements of the sets denoted by the corresponding upper case name. The function expand is defined as follows:
An auxiliary mapping pathsfirst
works
in the following way. If a string x is a sequence of
paths and processes, say 
, where
, 
, 
are
paths, 
are processes, then
This means that it moves all paths before processes as required by the basic COSY grammar. If the string x is not a sequence of paths and processes then pathsfirst(x) is not defined.
For every string x, let 
, where y is a string and
, denote the string obtained from x by replacing each
occurrence of t by y. If x contains no t then
equals to x.
To define exprepl
and
expdist let us first define the
operator 
which transforms strings into strings,
where j,k,m are parameters, j is the name (of an integer
variable), k,m are integer values, x is an argument and x is
a string from 
. The result of this operator is
the following:
For example:
We need also two operators LSTRIP
and FSTRIP which strip off the last and
first separators of a given string respectively. We assume that
, and for every 
and 
, let:
For instance:
