====== ACT Introduction ======

The Asynchronous Circuit Toolkit (ACT) is a suite of programs that can be used to design, verify, and test asynchronous circuits.  The tools share a common input language (specified in a text ''.act'' file) which can be used to describe circuits at different levels of detail. In what follows, we assume that the reader is familiar with asynchronous design  methodologies and terminology.

ACT is a hierarchical, lexically scoped circuit description language. A single ACT file can be used to describe the transistor implementation of a circuit as well as a high-level functional description of the same circuit.

There are three steps used to process an ACT file:
   * reading in an ACT file;
   * an expansion/elaboration phase where parameters are expanded; and 
   * a circuit construction and instantiation phase.
In the parsing phase, the input is converted into internal data structures. In the expansion phase, parameters are substituted, creating a concrete hierarchical netlist. In the instantiation phase, data structures are created for every circuit element specified in the ACT file. Errors may be reported in any of these stages. As a rule of thumb, errors are reported as soon as there is sufficient information to determine the error.


===== A simple example =====

To get a feel for how a circuit is described in ACT, we begin with a simple example circuit. The purpose of this circuit is to create a dual rail channel (called ''a1of2'' for a one-of-two encoded data channel and an acknowledge) and attach a bit-bucket to it.

<code act>
/* my first act program */
defchan a1of2 <: chan(bool) (bool d0,d1,a)
{
  spec {
    exclhi(d0,d1)  // exclusive high directive
  }
  // channel description omitted
}
  
defproc bitbucket (a1of2 d)
{
  prs {
    d.d0 | d.d1  -> d.a+
   ~d.d0 & ~d.d1 -> d.a-
  }
}

bitbucket b;
a1of2 c;

b.d = c;
</code>

''defchan a1of2'' is used to create a new channel type named ''a1of2'' with a port list that consists of three Boolean values named ''d0'', ''d1'', and ''a''. A ''bool'' is a Boolean-valued electrical node in the circuit, and is a built-in type. Identifier names such as ''d0'' and ''a1of2'' conform to the C naming convention. The //body// of the type  ''a1of2'' is enclosed in braces.

The ''defchan'' construct specifies that ''a1of2'' is a channel type, and the signature ''<: chan(bool)'' is used to specify that ''a1of2'' is an implementation of a channel of type ''chan(bool)''. Boolean-valued variables can be sent or received on this channel since the type of the value communicated on the ''chan'' that it implements is ''bool''. ''chan'' is also a built-in type that is used for communication channels.

The definition of type ''a1of2'' consists of a ''spec'' body. The construct ''name { ... }'' is used to specify a //language-specific body// within a type definition. A type can have any number of these language-specific bodies. A program using the ACT library typically will examine a subset of all possible language bodies. In our example, the word ''spec'' is recognized to be a //specification// body.

The specification body contains an assertion indicating that the nodes ''d0'' and ''d1'' are exclusive high, meaning that at most one of them can be true at any time (a form of an invariant). Whenever a circuit element of type ''a1of2'' is created, this specification  will be automatically attached to it. Tools that read ACT files can use this information for a variety of purposes, and can also check if this invariant is violated in case of an error in the design of a circuit that uses this channel.

The process ''bitbucket'' is defined to take a variable ''d'' of type ''a1of2'' as its argument. ''bitbucket'' is a process rather than a channel because it was created using ''defproc'' instead of ''defchan''. The body of ''bitbucket'' contains a different language-specific body, namely a ''prs'' body. ''prs'' bodies correspond to //production rule set// descriptions of the process. In the example, the production rules for ''bitbucket'' corresponds to what is commonly  referred to as a ``bit-bucket'' or a ``token sink'' for a four phase dual rail channel. 

The statement ''bitbucket b'' creates an //instance// of type ''bitbucket'' named ''b''. The statement is said to be an
//instantiation//. Execution of this statement creates variable ''b'' of type ''bitbucket'', production rules corresponding to the body of a ''bitbucket'', and the specification body for the ''a1of2'' variable ''b.d''. Similarly, the statement ''a1of2 d'' creates an instance of type ''a1of2''. ACT uses the standard dot-notation to access the names that are in port lists, since they are analogous to the fields of types/structures in conventional programming languages.

The final statement ''b.d=c'' //connects// the two ''a1of2'' types ''b.d'' and ''c''. The effect of connecting two types is to make the two instances aliases for each other. Therefore, the connect statement also specifies that the Booleans ''b.d.d0'', ''b.d.d1'', ''b.d.a'' are the same as the Booleans ''d.d0'', ''d.d1'', ''d.a'' respectively. Electrically, those Booleans correspond to the same circuit node.

ACT recognizes both C and C++ style comments, and they are treated as white space along with spaces, tabs, and new lines. A C-style comment begins with the characters ''/*'' and ends with ''*/''. Everything between the beginning and end of the  comment is treated as whitespace. A C++ style comment begins with two forward slashes, and continues till the end of line.


===== Variables and expressions =====

Variables in ACT fall into two basic categories: //parameters//
and //circuit elements//. A parameter is a variable that is used to
parameterize a circuit element in some way and must be of type integer
(''pint'' for unsigned integer or ''pints'' for signed integer),
real (''preal''), or Boolean (''pbool''). Circuit elements
consist of Booleans (''bool''), integers (''int''), or channels
(''chan'').

A variable identifier can be a sequence of digits, letters, and
underscores. The following declarations are
legal:

<code act>
bitbucket b;
a1of2 x1;
a1of2 _2;
bool x5;
</code>

On the other hand, the following declaration is incorrect.

<code act>
pbool 5;
</code>
<code>
-[ERROR]-> Expecting bnf-item `instance_id', got `5'
</code>


Errors use names from the ACT BNF to describe the item that the
parser was expecting. Error messages are accompanied by the file name,
line number, and column number of the item that resulted in the error.

The names in the port list of a user-defined type are the only parts of
the type that are visible externally. Other parts of the defined type
cannot be accessed outside the body of the type itself. For example,
consider the following definition of ''bitbucket''.

<code act>
defproc bitbucket(a1of2 d)
{
  bool p;
  prs {
    d.d0 | d.d1  -> d.a+
   ~d.d0 & ~d.d1 -> d.a-
  }
}
</code>

If we had used this definition, then although ''b.p'' is a ''bool''
within the bit-bucket ''b'', we cannot access it by statements
outside the body. Therefore, a statement such as ''b.p=c.d0'' would
result in the following message:

<code act>
bitbucket b;
a1of2 c;
b.p = c.d0;
</code>
<code>
-[ERROR]-> `p' is not a port for `bitbucket'
</code>

Expressions look very much like C expressions. Expressions can be of two
types: numeric or logical. Numeric expressions can be constructed from
identifiers, numeric constants, parentheses for grouping, and the
arithmetic operators ''+'', ''-'', ''*'', and ''/'' for
addition, subtraction, multiplication, and division respectively. The
unary minus operator is also supported. The operator ''%'' is used
for computing the remainder. Logical expressions can be constructed from
logical variables, the logical constants ''true'' and ''false'',
and the logical operators ''&'', ''|'', and ''~'' denoting
the and, or, and negation operations respectively.  Numeric expressions
can be compared using ''<'', ''< ='', ''>'', ''>='',
''='', and ''!='' for the operators less than, less than or equal
to, greater than, greater than or equal to, equal to, and not equal to
respectively.

===== Arrays =====

Most circuits contain a set of components that are replicated a number
of times. This is especially common in datapath circuits. ACT has a
very flexible array mechanism that can be used to construct complex
circuits. The simplest way to create an array is shown below.

<code act>
bool x[10];
a1of2 y[5][3];
</code>

The first statement creates an array of ten ''bool''s named ''x'' whose
elements are ''x[0]'', ''x[1]'', ..., ''x[9]''. The
second statement creates a two-dimensional array of ''a1of2''
variables named ''y'' whose elements are ''y[0][0]'',
''y[0][1]'', ..., ''y[4][2]''. The entire array range can also
be specified as shown below

<code act>
bool w[4..7]; // create Booleans w[4], ..., w[7]
</code>

ACT also contains a mechanism for constructing //sparse arrays//. A
sparse array is one that has 'holes' in it; in other words, valid
indices of the array do not form a contiguous, rectangular
block. Consider the following instantiation:

<code act>
bool x[10];
bool x[12..14];
</code>

The first statement creates ''x[0]'', ..., ''x[9]''; the
second creates ''x[12]'', ..., ''x[14]''. This is a valid
sequence of statements, and it makes ''x'' a sparse array. The
following, on the other hand, is not valid.

<code act>
bool x[10];
bool x[9..14];
-[ERROR]-> Sparse array: overlap in range in instantiation
           Original: [10]; adding: [9..14]
</code>
Each index of an array can only be created once.

Arrays can be connected to others using the ''='' operation. If two
arrays have the same size, the same type, and the same number of
dimensions, the connection is valid. Conceptually, connections are
performed by converting each array into an ordered list of individual
elements, where the order is specified by the lexicographic ordering
on their indices (the leftmost index has precedence). Finally, an
element-by-element connection is performed. This is illustrated
below.

<code act>
bool x[10];
bool x[12..14];
bool y[2];
x=y;
-[ERROR]-> Types `bool[ [10]+[12..14] ]' and `bool[2]' are not compatible
</code>

Note the syntax used to report the sparse array type as a combination
of two sub-arrays.

The dimensionality of the two arrays must match for a connection to
succeed, and their shapes also have to be compatible.

<code act>
bool x[12];
bool w[4][3];
x=w;
</code>
<code>
-[ERROR]-> Type-checking failed in connection
           Types `bool[12]' and `bool[4][3]' are not compatible
</code>

The following are examples of valid connections:

<code act>
bool x[10];
bool x[10..12];
bool y[13];
x=y; // success!

bool u[4][3];
bool v[4][3];
u=v; // success!
</code>

===== Loops and conditionals =====

Loops and conditionals can be used to describe complex circuit
structures in a compact manner. Loops are useful when creating array
structures, or connecting arrays in a regular manner. For example,
suppose ''fulladder'' is a process that contains channels ''ci''
and ''co'' as its carry-in and carry-out. The following connects the
carry chain for a ten bit ripple-carry adder.

<code act>
fulladder fa[10];
(i : 9 : fa[i].co=fa[i+1].ci; )
</code>

The parentheses are used to group the body of the loop. ''i'' is
the dummy variable, and it ranges from zero to eight in this
example. The '';'' is a separator, and separates each instance of
the body of the loop.  In general if only one integer is specified for
the range, the variable ranges from zero to one less than the integer.

The conditional statement uses the guarded command notation. They are
used for describing the edge of repetitive structures, during
recursive constructions, or for creating special versions of processes
based on parameters. The following is an example where odd-numbered
indices of ''x'' are connected to ''y'', and even-numbered
indices are connected to ''z''.

<code act>
bool x[10], y[10], z[10];

( i : 10 : 
   [ (i%2) = 0 -> x[i] = y[i];
   [] (i%2) = 1 -> x[i] = z[i];
   ]
)
</code>

===== Scoping =====

In the second definition of ''bitbucket'', the variable ''p'' was
defined within the body of the type definition. Therefore, this variable
is local to the type, and cannot be accessed by any construct outside
the body of the type. Different instances of ''bitbucket'' get
different copies of ''p'', since it is a local variable. If we had
created a dualrail channel ''p'' after the bitbucket, this ''p''
has no relation to the ''p'' in the body of ''bitbucket''.

The ACT language has two scopes: the global scope, and the scope
within the entity being defined. Ports of types have the same scope as
items defined within the body of the type. However, ports are special
in that they can also be accessed from outside the type using
dot-notation.


ACT does not have a special 'global' keyword. Global nodes can
be created by simply defining them in the outer-most scope. For
instance, ACT files will tend to begin with

<code act>
bool Reset,Reset_;
</code>

This permits the names ''Reset'' and ''Reset_'' to be used
throughout the ACT file. 

===== Namespaces =====
Complex projects involve a large number of ACT files, including
shared libraries and blocks designed by different people. One could
easily envision a situation where a particular identifier name is used by
multiple designers to describe different processes.

To keep names of processes, channels, and types separate for different
parts of a design, ACT provides the notion of a
//namespace//. Every instantiation and type definition resides in a
specific namespace. In all our examples so far, this was the
(implicit) global namespace (named ''Global'').

The following example creates a namespace ''lib'' and defines types
within the namespace.

<code act>
namespace lib {
  export defchan a1of2 <: chan(bool) (bool d0,d1,a) { ... }
}

lib::a1of2 d;
</code>

We have created a channel definition of type ''a1of2'' within the
''lib'' namespace. There are a few items that should be noted.
First, the directive ''export'' indicates that the ''a1of2''
type is in fact visible outside the namespace scope. This is why we
can use the notation ''lib::a1of2'' to access this type. The
rationale for this is that one might have created a library, but might
only want a few types exposed (e.g. top-level cells). By default, a
type is not visible outside a namespace unless it is explicitly
''export''ed. Second, a user-defined namespace cannot contain any
global instances of processes. This means that the only legal items
within a namespace are namespace directives, type definitions, and
global data/channel types.

Namespaces can be nested. For instance, we could have:

<code act>
namespace processor {

  namespace lib {
       export defchan a1of2 <: chan(bool) (bool d0,d1,a) { ... } 
  }

  lib::a1of2 d;
}
</code>

In this example, ''d'' is instantiated from namespace ''lib''
within namespace ''processor''. This brings up another subtlety of
the ''export'' directive. An exported definition is only exported
one level up in the namespace hierarchy. Hence, although the channel
''processor::lib::a1of2'' exists, it cannot be accessed outside the
''processor'' namespace.

<code act>
namespace processor {

  namespace lib {
       export defchan a1of2 <: chan(bool) (bool d0,d1,a) { ... }
  }

}

processor::lib::a1of2 d;
</code>
<code>
-[ERROR]-> Type is not exported up the namespace hierarchy:
           processor::lib::a1of2
</code>

If this channel needs to be visible
outside the ''processor'' namespace, this can be accomplished by
exporting the namespace itself.

<code act>
namespace processor {

  export namespace lib {
       export defchan a1of2 <: chan(bool) (bool d0,d1,a) { ... }
  }

}
processor::lib::a1of2 d;
</code>

In this approach, every element that is exported from namespace
''lib'' is also exported out of namespace ''processor''.

Something that is a little unusual is that a type cannot be accessed
within a sub-namespace unless it is exported. For instance, in the
example above, if ''a1of2'' was defined within the
''processor'' namespace, then it will not be visible within the
''processor::lib'' namespace unless it is exported. An
''export'' directive is needed to permit a type to be used in other
namespaces apart from the one in which the type was defined.

A namespace can have global variables. The global variables described
earlier were simply a special case corresponding to the namespace
''Global''. For instance, a collection of process definitions within
a namespace might have a reset signal that is global to the namespace
only, and which is generated using some logic defined within the
namespace. 

===== Importing ACT files =====

The keyword ''import'' is used to include other design files. An
ACT file can begin with a sequence of ''import'' statements.
If the same file is imported twice within the same scope, chances are
that some types would be multiply defined. To avoid such problems,
imports of files which have already been imported within the same
scope or an outer scope are ignored. Therefore, always use
''import'' to include type definitions defined elsewhere.

<code act>
import "channel.act";
...
</code>

''import'' searches for the file in the current directory
first, then in the colon-separated path specified by ''$ACT_PATH'',
and finally in ''$ACT_HOME/act''.

A typical project would contain multiple files, each possibly having
their own namespace. Namespaces can also have global variables, so
importing a namespace automatically creates an instance of the global
variables from that namespace, and from any sub-namespace that was also
imported. 

There are a few things that might create issues in such a situation.
First, duplicate namespaces might exist, especially when re-using old
files. For instance, suppose we have two files: ''lib1.act'' and
''lib2.act'' both containing namespace ''lib'', but having
definitions that are useful. Importing both would result in the union of
the namespaces, and could create naming conflicts (e.g. multiple
definition of types having the same name---an error). To solve this
problem, one can do the following: 

<code act>
import "lib1.act";
open lib -> lib1;
import "lib2.act";
open lib -> lib2;
</code>

The ''open'' construct enables one to rename a namespace. Once this
has occured, there cannot be any naming conflicts. This version of
''open'' is a renaming construct. The old name for the namespace is
eliminated.

A second issue is one that is more about convenience. Consider a
project that has many different people working on it, each in their
own namespace to avoid naming conflicts. This situation can result in
very long type names. Plus it would be more bookkeeping to have to
create a test environment for the types within, say,
''processor::lib''---not just because of the long type names, but
because not all types might be exported! In this case we can say:

<code act>
import "lib.act";
open processor::lib;

a1of2 d;
</code>

This version of the ''open'' directive has two
functions: (i) it adds ''processor::lib'' to the search path for
types, and (ii) it allows one to access all types within the
namespace, not just the ones that are exported (including types within
nested namespaces). Note that this ''open'' statement will fail if
all types cannot be uniquely resolved.

The sequence of ''open'' and ''import'' statements can only be
at the beginning of an ACT file.

A second version of import uses namespaces directly, but requires that
ACT files be placed in locations that match the namespace
hierarchy. The import statement

<code act>
import processor::lib;
</code>

is equivalent to the following:

<code act>
import "processor/lib/_all_.act";
</code>

It assumes that the file ''_all_.act'' in the directory
''processor/lib'' contains all the definitions corresponding to the
''processor::lib'' namespace.