This is an old revision of the document!
Types and Variables
Variables are the basic data objects in ACT. Instantiations specify which variables are created, and state what type they have. The type of an object completely specifies what the object is and how it can be used.
Types come in two flavors: parameters and circuit elements. Parameters
are variables whose types are pint
, preal
,
pbool
, or arrays thereof. All other types refer to circuit
elements. The basic circuit element is a Boolean value
bool
. Circuit element types are broken down into three
categories: processes (created with defproc
), channels (created
with defchan
), and data (created with deftype
).
There are some restrictions on variable names. Ordinarily a variable
identifier can be constructed as an arbitrary sequence of underscores,
letters, and digits. Identifier names are case sensitive, so case
and Case
are different identifiers.
Basic types
The following basic types are supposed by ACT:
- Parameter types
pint
, for integer parameters.preal
, for real-valued parameters.pbool
, for Boolean-valued parameters.ptype
, for type parameters.
- Data types
bool
, for Boolean circuit signals.int
, for unsigned integer-valued data.enum
, for enumerations.chan
, for channels.
The first group of types (and arrays of them) are referred to as
parameter types or meta-language types, and they begin with
the character p
. This is because they do not represent physical
entities in the circuit itself, but rather values that are used to
construct the circuit or specify circuit parameters.
The bool
type corresponds to an electrical node in the
circuit. Eventually all types get implemented using circuit elements and
bool
s.
The int
, enum
, and chan
types are used for
higher-level representations of the circuit. These types support
parameters, and are described in more detail later.
Variables of these basic types can be created by specifying the type name followed by a comma-separated list of identifier names.
bool a,b,c,n1,n1x2; pint x,y,z; preal w2,w_3;
The statements above are referred to as instantiations, since they create variables that are instances of the basic types. It is an error to have more than one instantiation of a variable in the same scope.
bool a; pint a; -[ERROR]-> Duplicate instance for name `a'
A parameter instantiation can be accompanied by a single initializer which initializes the value of a variable.
pint a=5, c=8; preal b=8.9;
The order of initialization of variables is left to right. Using constructs such as
pint a=c, c=5; -[ERROR]-> The identifier `c' does not exist in the current scope
should be avoided, as this leads to the error shown above indicating
that ACT does not know about variable c
in the initialization
of a
. Constructs where the two instances and initializers are
listed in an order that does not lead to an error are deprecated even
they are well-defined.
Array types
An array of a basic type or user-defined type can be created using ACT's array syntax. The syntax is based on C-style arrays, and examples of creating arrays are shown below:
int ar1[4] preal ar2[7] bool ar3[1..6]
The number in square brackets specifies the range of the array. In the first two examples, valid array indices range from zero to three and zero to six respectively. The third example specifies the array indices to range from one to six. In general, if the array index range is specified by a single integer, the lower bound of the range is zero, and the upper bound is the specified integer minus one. Instead of simple integers, arbitrary integer expressions can also be used as array range specifications, as shown below.
int ar4[5*3] preal ar5[7*x+(y%2)-p] // here x, y, and p must be integer parameter types
Expressions used to specify array ranges must be of integer
type. Variables used must always be parameter types (typically pint
).
preal a = 4.3; bool ar6[7*a+5]; -[ERROR]-> Expression must be of type int
Multidimensional arrays are specified by additional square brackets. Two
and three-dimensional arrays of bool
s are specified as shown in
the example below.
bool x[5,3]; bool y[1..6][9][2..10];
ACT provides a mechanism for constructing sparse arrays, i.e., those whose range need not be a single contiguous block. It is possible to create an array of nodes whose elements exist only at, say, positions 4 and 6 of the array. The syntax for creating the aforementioned array is shown below.
bool n[4..4], n[6..6];
These sparse array instantiations can be mixed with ordinary instantiations, permitting the definition of arrays which can be dynamically extended in ACT.
bool n[5]; bool n[10..12]; // n is now defined at positions 0 to 4, 10 to 12
The definition below specifies an instantiation of elements of array
m
at positions [6][5]
, [6][6]
, …, [6][10]
.
bool m[6..6][5..10]
Note that this is quite different from the statement
bool m[6][5..10];
which indicates that array m
is to be instantiated at positions
[0][5]
, …, [5][10]
.
Unlike ordinary instances, array instantiations cannot be followed by initializers.
bool x[10]; bool y[10] = x; -[ERROR]-> Connection can only be specified for non-array instances
For type-checking purposes, an array is defined by its base type
(bool
in the example above), number of dimensions, and the
shape of the array in each dimension.
User-defined types
User-defined type can be used to create complex circuit structures. A
new user-defined type name is introduced by using defproc
,
defcell
, defchan
, or deftype
statements. All user-defined types have the same basic structure:
- a type signature, that provides information about the interface to the type and the ports that are externally visible; and
- a body, contained in braces, that specifies the detailed definition of the user-defined type.
The type chosen for each port must be the most specific type used by that port in the body (see the implementation relation section).
User-defined types can also be parameterized, and this is covered in detail later.
Processes and cells
A process is a user-defined type that corresponds to a circuit entity. Other hardware description languages sometimes call it a module or a subcircuit. The basic syntax of a process definition is shown below.
defproc test (bool n, m; bool p, q) { ... }
The definition above creates a new process, called test
, that has
a port list consisting of four bool
s. This port list cannot
contain any parameter types (pint
, etc).
If the body of the user-defined type is replaced by a single
semi-colon or is empty, the statement corresponds to a type
declaration. Declarations are typically used when defining
mutually recursive types. The declaration corresponding to type
test
is:
defproc test (bool n, m; bool p, q);
If the process is never defined, ACT assumes that it has an empty body. If a process declaration is followed by a definition, the type signature must match exactly.
defproc test (bool n, m; bool p, q); defproc test (bool n, m; bool p) { } -[ERROR]-> Name `test' previously defined as a different process
A type can only have one definition in a given scope.
defproc test (bool n) { ... } defproc test (bool n) { ... } -[ERROR]-> Process `test': duplicate definition with the same type signature
The body of a process specifies its implementation. This can use a combination of instances of other processes, connections, and other languages like production rules. Loops and conditional statements can also be used to construct a process.
Port lists have a syntax similar to instantiations. A type specifier can be followed by a list of identifiers rather than just a single identifier, similar to an instantiation. Semicolons are used to separate parameters of differing types, as shown in the example below.
defproc test2(bool n,m; d1of2 p,q) { ... }
In this example we assumed that there was a user-defined type (or
channel) called d1of2
that was used in the port list. Any
user-defined type in the port list must be either a data or channel
type. Processes are supposed to correspond to circuit blocks, and so
cannot be port parameters to other circuit blocks.
Square brackets can also be used following the identifier names to specify array ports. The meaning of these square brackets is identical to the ordinary array instantiation. However, the arrays in port lists are restricted to be dense arrays indexed at zero. This restriction is enforced by syntax, and will be reported as a parse error.
defproc test1 (bool a,b,c, d[10]) { } // success! defproc test2 (bool a,b,c, d[0..9]) { } -[ERROR]-> Expecting token `]', got `.'
The ports themselves cannot be converted to sparse arrays within the body of a definition. This means that the following is illegal:
defproc test1 (bool a, b, c, d[10]) { bool d[11..12]; ... } -[ERROR]-> Array instance for `d': cannot extend a port array
Type names and variable names do not share the same name space. Creating a type definition with the same name as an instance variable or vice versa is allowed, but deprecated.
Cells follow the same rules for definition as processes, except the
keyword defcell
is used in place of defproc
. The reason
for separating cells from processes is that processes are supposed to
correspond to logical entities that are meaningful semantic
objects. For example, a process ordinarily has its origins in a CHP
language description. Cells, on the other hand,
can be fragments of logical processes. Examples of cells are standard
gates like C-elements, NAND, or NOR gates, or commonly used circuit
structures like completion detection logic. Cells are distinguished
from processes to make it easier to write automation tools.
Data types
A data type is defined using deftype
. A data type corresponds
to an integer or Boolean value, although it could also be a composite
construct like a record or structure (from software programming
languages). The syntax is similar to a process, and the constraints
about declarations/etc. apply here as well.
Data types have some additional structure that is not required for a process. In particular, the body of the data type and its type signature provide information that relates a user-defined data type to a previously defined or built-in data type. When a user-defined data type is specified, a method for setting the value of the data type and reading its value must also be specified. If omitted, certain features of data types will not be enabled for the defined type.
The following is a simple example of a datatype that creates a dual-rail
representation for a Boolean variable. The first line specifies that
d1of2
is a new data type, and it implements the built-in type
int<1>
—a one-bit integer.
deftype d1of2 <: int<1> (bool d0,d1) { spec { exclhi(d0,d1) } }
The body of the type is similar to a process, except it can only contain
connections, spec
bodies, and special methods. The
following would result in an error:
deftype d1of2 <: int<1> (bool d0,d1) { bool p; spec { exclhi(d0,d1) } } -[ERROR]-> Expecting bnf-item `methods_body', got `bool'
There are two methods that can be specified for a data type:
- a set method, used to write a value to the type;
- a get method, used to read the value of the type.
One can think of these as type conversion methods invoked automatically to read or write the data type.
deftype d1of2 <: int<1> (bool d0,d1) { spec { exclhi(d0,d1) } methods { set { [self=1->d1-;d0+ [] self=0->d0-;d1+] } get { [d0->self:=1 [] d1->self:=0] } } }
In the example above, the set
method says that the way to set a
d1of2
data type to the value 0
is to set d0
to
false
and d1
to true
. The special variable
self
is used to specify the int<1>
value of the type, and
the methods specify conversion operations.
The selection statement in the get
method uses the deterministic
selection operator []
(see languages). This is an implicit check
that when the get
method is invoked, signals d0
and d1
cannot both be true
. We have also made this explicit in the
specification body. Also, if both d0
and d1
are false
(i.e. an illegal state in which to execute a get operation), the
variable self
is not assigned; the operation waits for at least
one of d0
or d1
to be true. This is viewed as an error for a
data type. (This is different in the case of a channel, where the
semantics of the channel permit waiting.)
Port lists for data types can be either built-in data types or user-defined data types. Channels (built-in or user-defined) and processes are not valid types for ports of a data type, since a data type is supposed to represent a circuit structure that is used to represent a data value.
Channels
Channels are similar to data types. Instead of relating a user-defined channel to built-in data, we relate them to a built-in channel types instead. The methods required for supporting the full functionality of a channel are operations necessary to send and receive data on the channel, rather than a read and write operation on a data value.
There are six possible methods that can be defined for a channel type:
- Methods for sending and receiving values on the channel
set
,send_rest
: together these two operations implement a send operation on the channel. The send operation consists of two parts: (i) setting the data value to be sent (set
); and (ii) completing the synchronization operation (send_rest
).get
,recv_rest
: together these two operations implement a receive operation on the channel. The receive operation consists of two parts: (i) getting the value that has been transmitted along the channel (get
); and (ii) completing the synchronization operation.
- Methods for probing a channel to determine if there is synchronization operation being attempted.
send_probe
: this is the probe operation for the sending end of the channel. It corresponds to the receiver being ready to communicate.recv_probe
: this is the probe operation for the receiving end of the channel. It corresponds to the sending being ready to communicate.
The send operation X!e
in the CHP language corresponds to two
parts: setting the data value, followed by the synchronization
operation. Setting the data value also indicates that the sender is
ready to communicate. It is illegal to set the data value multiple
times without an intervening synchronization operation. Finally,
attempting to set the data value might block if the previous channel
operation has not completed as yet. Whether or not this could occur
depends on the channel protocol.
The receive operation X?v
in the CHP language corresponds to
two parts: receiving the data value, followed by the synchronization
operation. Attempting to get the data value from the channel will
block if the sender has not provided any value. Once a value has been
extracted from the channel, the synchronization operation can be
executed. Prior to the synchronization, multiple get operations can be
executed; the channel must be designed so that subsequent get
operations will return the same value as the first one, and will be
guaranteed not to block. The get operation is used to implement a CHP
value probe, where the receiver can peek at the value pending in the
channel without attempting a synchronization operation.
An example definition of a Boolean channel where the channel has an lazy-active send and passive receive is below.
defchan e1of2 <: chan(bool) (bool d0,d1,e) { spec { exclhi(d0,d1) } methods { set { [e];[self->d1+[]~self->d0+] } send_rest { [~e];d0-,d1- } get { [d0->self-[]d1->self+] } recv_rest { e-;[~d0&~d1];e+ } recv_probe = (d0|d1); } }
In the example above, the set
and send_rest
methods
specify the sequence of operations on the channel variables that are
invoked for a send action. The get
and recv_rest
methods
specify the sequence of operations used to perform a receive. The
special variable self
is used to specify the bool
value
that is being either sent or received on the channel.
This channel has an active send and passive receive, and hence probes
are only supported at the receiver. The recv_probe
method
expression specifies the Boolean expression corresponding to the probe
at the receiver end of the channel. A send_probe
can be
specified in a similar way when the sender is passive and receiver is
active.
The e1of2
channel has been specified to perform a four-phase
handshake protocol. If the channel were to correspond to a two-phase
protocol, a different sequence of actions can be specified instead.
Port lists for channel types can be data types (built-in or user-defined) or channels. Processes are not valid types for ports of a channel type.
Instantiating user-defined types
User-defined type variables can be instantiated in much the same manner as ordinary type variables.
defproc test(bool N, n) { ... } test x; // x.N and x.n refer to the ports of ''x''
The ACT description above creates an instance of type test
named
x
. Creating an instance of a type creates instances of all the
ports listed as well as creating whatever is specified by the body of
the type definition. The list of ports of a user-defined type can be
accessed from the scope outside the type definition by using
dot-notation. These externally visible ports are analogous to the
fields of structures or record types in standard programming
languages.
This analogy to records can be used to build complex data types, albeit with slightly different syntax compared to traditional programming languages. The following is a simple example that illustrates this.
deftype mystruct <: int<16> (int<4> f1, f2; int<8> f3) { methods { set { f1:=self >> 12; f2:=(self >> 8) & 0xf; f3:=self & 0xff } get { self:=(f1 << 12) | (f2 << 8) | f3 } } }
Parameterized types
Parameterized types give ACT considerable flexibility in type definitions. Parameterized types come in two flavors: built-in types, and user-defined types. For user-defined types, ACT guarantees that the order in which parameters are created and initialized is from left to right. Therefore, one can use the value of one parameter in the definition of another one.
Built-in integers and channels
Although we have been describing the types int
and chan
as simple types, they are in fact paramterized. Omitting the
parameters makes ACT use implicit default parameters for both of
them.
The int
type is parameterized by the number of bits used to
specify the integer. This bit-width can be specified using angle
brackets, as shown below:
int<1> x; // x is a one bit integer int<37> y; // y is a thirty-seven bit integer
When interpreting these bits as integers, ACT assumes an unsigned binary representation. The default bit-width is thirty-two.
The channel type chan
can be parameterized by the type that is
being sent and received on the channel.
chan(bool) x; // x is a Boolean channel chan(int<16>) y; // y is a 16-bit integer channel
The default data type for a channel is assumed to be the default
int
, namely int<32>
.
Another built-in data type is the enumeration type. An enumeration type corresponds to integer-valued variables with a restricted range.
enum<5> x; // x can take on values 0, 1, 2, 3, 4
For convenience, these values are treated as integers for the purposes
of expressions. Also, enumerations that have power-of-two ranges are
type-equivalent to the approprate int
type. For instance,
enum<2>
@ is equivalent to int<1>
. Enumerations are
useful when specifying a data value that is a one-hot code.
User-defined types
Processes, channels, and datatypes created using defproc
,
defchan
, and deftype
all support
parameterization. Parameters are specified using the template
keyword.
Since the syntax for all three is the same, we use a process definition to illustrate this. To create a parameterized type, the definition of the type is preceeded by a template specifier as shown below.
// A generic adder block template<pint N> defproc adder (e1of2 a[N], b[N]; e1of2 s[N]) { ... }
This example defines an adder
that takes N
as a
parameter. Note that the value of N
determines the size of the
arrays in the port list for the process. Instances of this
adder
can be created in the following way:
adder<4> a1; // a1 is a 4-bit adder adder<16> a2; // a2 is a 16-bit adder
The value of a1.N
is 4, while the value of a2.N
is
16. To illustrate how one might define this adder block, assume we
have processes fulladder
, zerosource
, and
bitbucket
already defined that implement a full-adder, a
constant source of zeros, and a constant sink respectively. One
possible definition of the adder would be:
template<pint N> defproc adder (e1of2 a[N], b[N]; e1of2 s[N]) { fulladder fa[N]; ( i : N-1 : fa[i].a = a[i]; fa[i].b = b[i]; fa[i].s = s[i]; fa[i].co = fa[i+1].ci; ) zerosource z; bitbucket w; fa[0].ci=z.x; fa[N-1].co = w.x; }
This creates a parameterized ripple-carry adder. Notice the use of
loops and arrays to connect the carry chain for the adder, and the
inputs and outputs of the process to the fulladder
ports.
As shown in the example above, the arguments in the template parameter list are specified by listing them next to the type name. Trailing arguments can be omitted from the parameter list attached to the type as shown in the example below.
template<pint N; preal w[N]> defproc test (bool n[N]) { ... } test<5> x;
Channels and data types can also be parameterized in the same way. For example, the following might be an N-bit dual rail definition.
template<pint N> deftype d1of2 <: int<N> (bool d0[N], d1[N]) { ... }
Since the body of the type can use loops and selection statements in
arbitrary ways, changing the parameters for the type can completely
change the structure of the circuit. It can also change the ports for
the type. Hence, when checking for type compatibility, the values of
parameters are also taken into account. Hence, the full type for
instance a2
above is in fact adder<5>
, not just
adder
. Types such as fulladder
that do not have
parameters are more completely specified as fulladder<>
,
although the angle brackets can be omitted. Arrays can only correspond
to instances of the same type—so an array cannot contain a three-bit
adder and five-bit adder.
Directional types
Data and channel types also support access permissions in terms of valid
operations on the types. To illustrate this, consider the simplest data
type, namely a bool
. There are three different ways a bool
type can be defined, and they are shown below:
bool x; // Boolean that may be read or written bool! y; // Boolean that must be written, and may be read bool? z; // Boolean that must be read, and cannot be written
The !
and ?
suffixes constrain the way in which the type
can be accessed. The primary use of this is in port lists, where one can
specify what variables are read and written by a process. The same
syntax can be used (with the same meaning) for user-defined data types.
The following example shows a possible definition for a two-input nand
gate that takes two inputs a
and b
, and produces its
output on c
.
defcell nand2 (bool? a, b; bool! c) { ... }
Channels support a similar syntax, but the meaning is slightly different.
chan(int) x; // Sends or receives are permitted chan!(int) y; // Only sends permitted chan?(int) z; // Only receives permitted
Again, the same syntax is valid for user-defined channels. These constructs are useful in libraries for additional error checking, and conveying more information to the user of the library.
Interaction with user-defined types
Direction specifications can be used for built-in data and channel
types, as well as user-defined types. Consider the e1of2
user-defined channel type that we saw earlier:
defchan e1of2 <: chan(bool) (bool d0,d1,e) { spec { exclhi(d0,d1) } methods { set { [e];[self->d1+[]~self->d0+] } send_rest { [~e];d0-,d1- } get { [d0->self-[]d1->self+] } recv_rest { e-;[~d0&~d1];e+ } recv_probe = (d0|d1); } }
When we use e1of2?
or e1of2!
, we need some mechanism to
specify the access permissions for the port parameters of the
user-defined type. The convention used is that there are five possible
ways to specify any constraints on access to port parameters. For our
example, we can use one of the following variations in the port parameter list:
bool d0; // No constraints; this port could be read or written bool! d0; // Both e1of2? and e1of2! have bool! permissions bool? d0; // Both e1of2? and e1of2! have bool? permissions bool?! d0; // e1of2? has bool? permissions, and e1of2! has bool! permissions bool!? d0; // e1of2? has bool! permissions, and e1of2! has bool? permissions
Hence, a better definition of an e1of2
channel would more
completely specify the access permissions for the port parameters in
the following way.
defchan e1of2 <: chan(bool) (bool?! d0,d1; bool!? e) { ... }
A careful examination of the type signature reveals that the sender and receiver have the appropriate permissions. There is a subtle interaction between connections and directional types in ACT, and this is detailed in the section on connections.