From Lyra

Contents 1 Overview 2 Limitations 3 Data Types 3.1 Void 3.2 Integer 3.3 Bool 3.4 String 3.5 Tuple 3.6 Array 3.7 The sizeof operator 3.8 Type compatibility and casting 4 Constants 4.1 C Style integer constants 4.2 Verilog Style constants 4.3 Other constants 4.4 Named constants 5 Semantic Operators 6 Module 6.1 Declaration of ports 6.2 Declaration of rendezvous 6.3 Declaration of signals 6.4 Declaration of sub-modules 6.5 Declaration of internal state variables 6.6 Initialization of internal state variables 6.7 Declaration of FSMs 6.8 Declaration of DPs 6.9 Semantic statements 6.9.1 Goto statement 6.9.2 When statement 6.9.3 Switch statement 6.9.4 Assignment statement 7 Function 7.1 External function 7.2 Purity of function 8 Template 8.1 Template Parameters 8.2 Instantiation of template 8.3 Name mangling 9 Include and Preprocessing 10 Simulation

Overview

This document introduces the Lyra language, a light-weight language designed for modeling logic hardware at higher abstraction levels than the traditional RTL HDLs. Compared to mainstream transaction-level modeling approaches based on C++, Lyra is based on a formal theoretical foundation — the Lyra modeling theory. The use of a formal theory makes it practical to perform high level synthesis, and formal verification tasks on hardware models.

Before one attempts to use the Lyra language, it is necessary to understand the Lyra model. Readers should refer to related documents for details of the theory. This document focuses on the major features of the Lyra language. Detailed grammar of the language is specified in a separate EBNF (extended Backuas-Naur form) specification. A tutorial on coding and using the accompanying reference simulator also accompanies this document.

A Lyra-based system contains a network of finite state machines (FSMs) and datapaths (DPs) that communicate with each other via rendezvous, signals and optionally shared registers. To describe such a network, Lyra adopts the similar module-based hierarchical structure to the Verilog HDL. Its basic units of description are modules, each containing a list of ports, registers, DPs, FSMs, instances of sub-modules, as well as rendezvous, signals that connect the FSMs, DPs, the sub-modules and the ports. Lyra defines a high-level type system for the convenience of modeling. It includes low level types such as bit-accurate integers, as well as high-level types such as arrays and tuples. It performs rigorous type checking on module definitions. Lyra also defines a comprehensive set of operators for computation. In addition, it supports the definition of functions for common computation. Users can also supply external functions defined in other high level languages in the form of shared libraries.

Lyra supports static polymorphism via template modules and functions. Both value-based template parameters and type-based template parameters are supported. Value-based parameters are similar to the parameters of Verilog HDL. Type-based parameters further enable one to define generic modules and functions that operate on different data types.

Limitations

Being a light-weight hardware modeling language, Lyra has the following limitations:

1. It does not support explicit loops, recursion, or references/pointers. Loops can be implemented either by cycles in state diagrams, or via external functions. Recursion is not native to hardware, and thus should be either converted to cycles in the state diagram, or be confined in external functions.
2. Data in Lyra are always communicated by the actual value. Lyra does not support pointers or references.
3. The language requires a single assignment in functions and on state transition edges. In other words, a register or a value can be assigned only once during each evaluation of a function or a state transition edge.
4. Lyra currently adopts a synchronous evaluation model. Each state transition edge takes only one step to evaluate. It does not model evaluation delay.
5. Lyra does not support dynamic creation of processes.

Data Types

The supported data types in the language include the following:

1. Void
2. Integer
3. Bool
4. String
5. Tuple
6. Array

Void

A void-typed data cannot be read from or written to. The void type can only be used in two context, for ports without data, and for functions that do not return a value. For example, in a port declaration input x, x will be considered to have type void.

Integer

An integer type can be either signed or unsigned. It optionally carries an explicit bit width. When the width is omitted, the type is considered to be 32-bit wide. An integer type can have subfields, and can inherit the subfields of a parent type of the same bit-width. For example, the following declaration creates a myint type that is based on the int type but has its own subfields. A subsequent myint2 type inherits all subfields of the myint type and adds a new field field3. A field is by default given an unsigned integer type of proper width. The field1 below has uint<11> as its type. Optionally, one can provide a type to the field, such as for field3 below. The type is apparently redundant in this case. But if an integer type with subfields is used to specify a subfield, one can further reference the subfields of the subfield. Subfield referencing is done by the . operator described in semantic operators section.

   typedef int
   {
     	field1 : {10:0},
     	field2 : {31:11},
   } myint;

   typedef myint
   {
     	field3 : uint<8> = {20:13},
   } myint2;

Bool

The bool type defines binary values which may be either true or false.

String

The string data type is similar to the STL string class. A string value is elastic in that its length can grow and shrink as needed.

Tuple

A tuple type is formed by a list of data types separated by comma. The list of types may include all types except void. The list needs to have at least two elements. The following are all valid examples of tuple types.

    (string, int, bool)
    (string, bool[10])
    (int<32>, (string, int, bool))
    (int<32>, (string, (int, bool)))

The followings are not valid tuple types since they violates the above-mentioned rules.

    (int<32>, (uint))
    (int<32>)
    ()
    (int, void)

Array

An array type consist of two parts: the base type which can be any type except void, and the length. Multidimensional array types can be defined by using array types as the base. The length of an array can be either fixed or variable. For a fixed length array, the length should be specified as an integer constant. If the array has a variable length, then the length is omitted. A variable-length array can grow on demand. It does not directly corresponds to any realizable hardware component, but is useful in modeling conceptual elements such as an unbounded FIFO. Below are a few example array types.

   int[10]  -- int array with 10 elements
   int[]    -- int array with variable length
   (bool, string)[10] -- tuple array
   string[2][4] -- 2 dimensional string array
   int<15>[][16][4] -- 3 dimensional int<15> array, the highest dimension has variable length

Constant array values can be formed using braces.

   {true, false, false} -- bool[3] typed array

The sizeof operator

The sizeof operator is used to test the array length of a value. For all types except array, it returns 1. For array-typed values, it returns the length of the highest-order dimension. For example, sizeof(v) where v has a string[2][4] type will return 2. Sizeof is mostly useful in testing the length of variable-length arrays.

Type compatibility and casting

Values of one data type may be implicitly up-casted to another type in a Lyra program when necessary and appropriate. For example, if a uint<15> value and an int<2> value are used as the operands of the binary "+" operator, the compiler will automatically promote the int<2> value to uint<15> before the addition. This type of automatic up-casting is the so-called arithmetic promotion in high level languages. In general, the compiler will silently promote a value of a smaller data type when it is used in the context where a bigger data type is expected. The compiler will issue an error message when a value of a bigger data type is used in a context where a smaller data type is expected, except when

1. The value is used as the condition of the ? : operator, or
2. The value is used as an operand of logical AND/OR/NOT operators.

In the above cases, the compiler will automatically down-cast the operand to bool type. If an error message regarding down-casting is shown, one must use explicit type casting. For example, the following code will result in an error message since the 32-bit integer ii is used in the context where a 5-bit integer is expected.

   function int<5> foo (int<5> aa)
   {
     return aa + 1;
   }

   module bar
   {
     reg int ii;
     init
     {
        ii = foo(ii); // should be ii = foo (<int<5> > ii);
     }
   }

The above code requires an explicit casting of ii to int<5> when calling function foo. Only compatible types can be casted between each other. The table below shows the compatibility relationships between data types.

Type Compatibility

	void	bool	integer	string	tuple	array
void	Yes
bool	Yes	Yes
integer	Yes	Yes	Yes
string	Yes	Yes	Yes	Yes
tuple	Yes	No	No	Yes	*
array	Yes	No	No	Yes	No	**

* Two tuple types are compatible if both have the same length and the relationship of their individual elements are consistent. In other words, all elements of one type should be greater than or equal to the corresponding elements of the other. If some elements are bigger while some others are smaller, then these two types are not compatible. The following table compares the types.

** Two array types are compatible if their base types are compatible.

Data types are partially ordered. Two compatible data types can be compared against each other. The table below illustrates the comparison relationship. The rows are compared against the columns. Void is smaller than all other types. And string is bigger than all other types.

Data Types Comparison Relationship

	void	bool	integer	string	tuple	array
void	=
bool	>	=
integer	>	>	*
string	>	>	>	=
tuple	>	N/A	N/A	<	**
array	>	N/A	N/A	<	N/A	***

* Comparison between two integer types is solely determined by their widths. A wider type is bigger than a narrower type.

** Comparison between two tuple types is determined by the element types. Only compatible tuple types can be compared, i.e. the element types can be consistently compared.

*** Comparison between to array types is first determined by the base types, and then the lengths of the arrays. If the base types are equal, a longer array type is considered bigger than a shorter array type, and a variable sized array is considered bigger than a fixed-length array type.

Constants

Constants of any data type can be used in semantic expressions or statements. Two type of integer constants are supported in the Lyra Language. Verilog Style constants and C Style constants.

C Style integer constants

• Natural numbers, e.g. 5.

• Octal Numbers (0-7), e.g. 05, 067, 05412.

• Hexadecimal Numbers (0-F), e.g. 0x4A, 0x15F, 0XBECD.

• Binary Numbers (0 or 1), e.g. 0b010101, 0B101010.

Verilog Style constants

The difference between Verilog-style constants and C-style constants is their explicit bit widths. One needs to give the bit width, a ' , a base character, and then the actual value.

• Decimal Numbers use d or D as base character, e.g.32'd1500.

• Hexadecimal Numbers use x or X as base character, e.g. 8'XAF.

• Octal Numbers use o or O as base character, e.g. 20'o777.

• Binary Numbers use b or B as base character, e.g. 8'b10101011.

Other constants

String constants are interpreted in the same way as C strings, including the treatment of escape characters. Tuple constants are formed by using parenthesis and commas. Array constants are formed by using braces and commas.

Named constants

Named constants can be declared in a Lyra program using the const keyword. They can be referenced by name throughout a Lyra program. Below are a few example named constants.

   const int ten = 10;
   const int eleven = ten + 1;
   const int nums[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ten, eleven};

Semantic Operators

Operators are useful in specifying semantic expressions. The following table lists all the semantic operators of the Lyra language in descending order of precedence. Note that the first element in an array has the index 0, while the first element in a tuple has the index 1.

Semantic Operators

Name	Operator	Associativity
Array element reference	[ ]	None
Function call Port Access	func(args) port.read() , port.write()	None
Field reference Tuple element reference	. .$index	Left
Type cast	<type>	Right
Logical NOT 1's complement 2's complement	! ~ -	Right
Bit Concatenation	::	Left
Multiplication Division Modulo	* /  %	Left
Add Subtract	+ -	Left
Right shift Left shift	>> <<	Left
Greater than Greater than or equal Less than Less than or equal	> >= < <=	Left
Equal Not equal	==  !=	Left
Bitwise AND	&	Left
Bitwise XOR	^	Left
Bitwise OR	|	Left
Logical AND	&&	Left
Logical OR	||	Left
Conditional	? :	Left

Module

Modules are the basic units of description in Lyra. Modules are hierarchical. A module can contain ports, instances of sub-modules, registers, DPs, FSMs, as well as rendezvous and signals as communication channels among ports, sub-modules, DPs and FSMs. A special highest level module, named toplevel, is the root of hierarchy in every Lyra model. A module definition describes a module class. The class can be later instantiated as sub-modules in other modules. The only exception is the special toplevel module. It should not be instantiated by users. The Lyra compiler will automatically instantiate a toplevel instance. A module definition contains the following parts:

1. Declaration of ports
2. Declaration of rendezvous
3. Declaration of signals
4. Declaration of sub-modules
5. Declaration of internal state variables
6. Initialization of internal state variables
7. Declaration of DPs
8. Declaration of FSMs

These orders of the links above are not arranged by the mandatory order of appearance in a module.

Declaration of ports

A Lyra module or an FSM inside a module can define ports. Ports of sub-module instances and FSMs are connected together by rendezvous declared in a module. Unlike the ports in common HDLs, an Lyra port not only provides data communication capability, but also synchronization capability.

Depending on the existence of dataflow and its direction, the following types of port are supported:

• in/rin/bin/sin port receiving data
• out/rout/bout/sout port transmitting data
• io/rio/bio port receiving data and then transmitting data, the latter depends on the former
• oi/roi/boi port transmitting data and then receiving data, the latter depends on the former

The declarations of in and out ports generally require data types. For example, an in port can be specified as

   in <int> my_port,

The port can be connected to one or more output ports of the same data type via a rendezvous. Similarly, an out port also requires a data type for its output data. If the data type is omitted for an in or an out port, the port is considered to have a void type. The port can only be used for synchronization purposes, but not be accessed by the read and write operators. in and out ports can connect to either barrier or rendv rendezvous. A rendv occurrence involves two components connected to the rendezvous, one input, and one output. See the rendezvous section for more details.

The declarations of io and oi ports always require two types. For an io port, the first type is for its input data, and the second for its output data. For example, an io port can be specified as:

   io <int, bool> my_port2,

It receives int-typed data, and sends out bool-typed data. The semantics of io is that the output data depends on the input data. This is similar to a function interface. The function parameters (inputs) are used to compute the return value (output). However, io implements rendezvous-style communication and is more powerful than a function interface.

An oi port is the opposite of an io port. The output data does not rely on the input. Its semantics is similar to the calling of a function. The output data are the outgoing arguments, the input is the expected result from the other module.

In the higher level module where sub-modules are instantiated and/or FSMs are defined, ports of matching data types and opposite directions can be connected together via rendezvous. So an out port with an integer data type can be connected to one or more in ports with the same type. The above io port can be connected to an oi port with the <int, bool> data type.

Declaration of rendezvous

Rendezvous are used to connect the ports of sub-modules and the ports of FSMs in a module for different modes of communication. However, they should not be used to connect to the ports of the module itself. Depending on the type of ports, the following rendezvous types can be used.

• rendv one to one rendezvous
• barrier group synchronization rendezvous

The rendv type implements bi-party handshaking. Two sets of ports can be connected to a rendv, representing the two different sides of the communication. All ports in one set must share the same data type, and the same port direction. The ports of the other set must have the same data type but the opposite direction. For example, a rendv can be used to connect the following three sub-module instances, one producer instance on one side and two consumer instances on th other side.

   rendv r1;
   producer pro1(r1); //producer has an out port.
   consumer con1(r1); //consumer has an in port.
   consumer con2(r1);

The rule of occurrence of a rendv is that exactly one party from each set should participate. In the example, there can be 2 choices for this rendv to occur: pro1 vs. con1 or pro1 vs. con2.

The other type barrier implements barrier synchronization. Barrier should be connected to one out port and several in ports of the same data type. The occurrence of a barrier requires all connected parties to participate.

Every rendv and barrier can carry an integer weight, which will be used by the scheduler to make choices. When multiple scheduling alternatives exist, the scheduler will calculate the total weight of all rendezvous in each alternatives, and select the one with the heaviest weight. By default, the weight value is 1. So the following two declarations are equivalent.

   rendv r;
   rendv r(1);

Declaration of signals

Signals are used to connect the ports of sub-modules and the ports of DPs and FSMs in a module for data communications. A signal is equivalent to a combinational wire.

   signal s1;
   producer pro1(s1); //producer has an sout port.
   consumer con1(s1); //consumer has an sin port.
   consumer con2(s1);

Declaration of sub-modules

A sub-module declaration instantiates a module inside the parent module, and connects the ports of the sub-module to the rendezvous and signals declared in the parent module, or the ports of the parent module. There are two ways to connect the ports of a sub-module, positional association and named association. This following example shows both connection methods.

   rendv r1,r2,r3;

   /* positional association */
   producer pro1(r1); //Producer has an output port.
   buffer   buf1(r1,r2); /*The position are input port and output port respectively*/

   /* named association */
   buffer   buf2(.inp(r2),.outp(r3));
   consumer con1(.inp(r3)); //Consumer has an input port.

The following example shows connecting the sub-module to port of the parent module.

   module producer (out outp)
   {
	rendv r1;
	fifo f1(.enq(r1),. deq(outp));
	fifo f2(.enq(r1),. deq(outp));
	inner_ process ip(r1); 
   }

In the above example, there are two fifos in the parent producer module. Both's deq ports are connected to the outp of the parent module. When the parent module is instantiated and its port connected to a rendezvous in the grand-parent module, the deq's will then be connected to that rendezvous. In essence, modules and their ports are used in Lyra to support modular and hierarchical description. When the hierarchy is flattened in the Lyra compiler, modules will disappear and port connections will be short-circuited. Every rendezvous is eventually connected to a set of FSMs.

Declaration of internal state variables

These variables are registers. A register declaration starts with the keyword reg, followed by a data type, then a list of register names. Below are a few example register declarations.

   reg uint x, y[2];
   reg (int[2], bool) z;

   reg (int[4], bool)[] xarray;

   reg int[4]  farray;
   reg int     garray[4];
   reg int[][] varray;

The above x is an unsigned integer. y is an unsigned integer array of length 2. z is a tuple of int[2] and bool. xarray is a variable-length array of tuples. farray and garray are integer arrays of length 4. They use different syntax but have identical array types. varray a two dimensional variable-length array.

A state variable is accessible by all FSMs in the module. Users should beware of race conditions or data hazards when two FSMs access the same state variable.

Initialization of internal state variables

The registers in a module can be initialized by the init declaraion. So the following example shows an example init declaration inside a module.

   reg int areg[100], breg[2];
   init {
       areg[0] = 5;
       areg[1] = 6;
       breg = {2, 3};
   }

Declaration of FSMs

A module may contain several FSMs, each corresponding to a process. A Lyra program essentially specifies a network of FSM processes and datapaths connected by rendezvous and signals. An FSM declaration contains the following parts:

• Declaration of ports

  An FSM can connect to the ports of the owner module, or rendezvous declared in the owner module. In the latter case, the FSM needs to specify the direction and the data type of communication in the form of port declarations. The ports should have the same name as the rendezvous.

• Declaration of temporary variables

  A temporary variable does not have memory. It is similar to a memoryless wire in Verilog. The temporary variables are accessible by all statements in the FSM.

• Declaration of state

  An FSM can have multiple states. Among them, exactly one must be an initial state highlighted by the init keyword. Regular states start with the state keyword. A state declaration contains a list of semantic statements.

The following is an example module containing one sub-module and one FSM. Both are connected to the consume rendezvous. The FSM receives data from the rendezvous, and the sub-module provides data. The FSM has two states, an initial state U and a normal state V.

   module consumer(in <int> inp)
   {
       rendv consume;

       fifo f1(.enq(inp), deq(consume));

       reg int myreg;

       fsm p1(in <int> consume)
       {
           init U: // start state
               when (consume)
               {
                   myreg = consume.read();
                   goto V; 
               }

           state V: 
               goto U;
        }
   }

Declaration of DPs

A module may contain several datapaths. A datapath is defined by the keyword dp. A DP declaration contains the following parts:

• Declaration of ports

  A DP can connect to the ports of the owner module, or signals declared in the owner module. In the latter case, the DP needs to specify the direction and the data type of communication in the form of port declarations. The ports should have the same name as the signals. sout type port can only declared by a DP.

• Declaration of temporary variables

  A temporary variable does not have memory. It is similar to a memoryless wire in Verilog. The temporary variables are accessible by all statements in the DP.

• Declaration of body

  A DP body declaration contains a list of semantic statements.

The following is an example module containing one DP and one FSM. Both are connected to the signal s. The FSM receives data from the signal to update the register myreg, and the DP does the computation and provides data. The DP also receives input data via port inp of its owner module.

   module accumulator(sin <int> inp)
   {
       signal s;

       reg int myreg;

       init {
          myreg = 0;
       }

       dp sum(sout <int> s) {
           val int tmp;
           tmp = myreg + inp;
           s = tmp;
       }

       fsm f1(sin <int> s)
       {
           init S0: 
               myreg = s;
               goto S0;
       }
   }

All expressions in a DP are evaluated every cycle and are executed concurrently, but follow the data dependency order. A DP can only read from a register but can not modify a register.

Semantic statements

Every state contains a list of semantic statements. The following table lists all valid semantic statements.

Semantic Statements

Name	Syntax
assignment	exp = exp;
expression	exp;
goto	goto state_name;
when	when (list of ports or exps)   statement;
switch	switch(exp) {   case val1: statement;   case val2: statement;   ...   default: statement; }
block	{ list of statements }

The when, switch and goto statements are control statements. They help to form the state transition edges in FSMs. The others are regular statements.

Statements are grouped into a hierarchical tree of lists. Every node in the tree is a statement list. Some statements, such as a block, a when, or a switch, contain subtrees. A state declaration contains the root of the tree. A block statement introduces a lower level statement list as a subtree. In the middle of a list, one can declare temporary variables. The scope of a temporary variable is from the declaration point to the end of the list. It is accessible by all statements at the same level and at lower levels in the scope.

Goto statement

Every goto statement creates a state transition edge in the FSM from the current state to the target of goto. All statements preceding the goto at the same level or higher will be associated to the state transition edge. For example, the code below will result in an unconditional state transition edge from foo to bar. The two computation statements are associated with the edge.

   state foo:
     x = x + 1;
     y = y - 1;
     goto bar;
  

If a state declaration contains no goto statement, then no outgoing edge will be created from the state.

When statement

The when statement specifies the condition of a state transition and the actions when the transition occurs. The condition is the conjunction of the following two lists.

• List of rendezvous ports. If list of rendezvous must simultaneously occur and must all involve the FSM for the condition to be true. If any rendezvous cannot occur because the other FSMs connected to the rendezvous are not ready, the condition is false.
• List of Boolean-typed expressions. All the expressions are ANDed together to guard the state transition. Only when all are true, the transition is enabled.

A when statement may have both the above lists, only one of them, or none (implying an unconditional when). A when statement introduces a new branch from the current state in the state transition diagram. All regular statements prior to the when are included into the branch as its actions. A branch forms a state transition edge for a single-level when statement. For a nested when statement, a branch will fork further into smaller branches corresponding to the inner whens. Each path from the root to a leave-level branch form a transition edge. Below are examples illustrating how state transition edges are formed by using when and goto.

The example below results in two edges. The first edge goes from foo to bar1, with the assignments to x and y on it. The edge is guarded by the occurrence of the rendezvous connected to rendv1. The second edge goes from foo to bar2, with all three assignments on it. It is unconditional.

  state foo:
    x = x + 1;
    y = y - 1;

    when (rendv1)
    {
      goto bar1;
    }

    z = func1(x, y);

    goto bar2;

The example below results in two edges. The first edge goes from foo to bar1, with the assignments to x and y on it. The edge is guarded by the occurrence of the rendezvous connected to rendv1. The second edge goes from foo to bar2, with all three assignments on it. It is guarded by the occurrence of the rendezvous connected to rendv2.

  state foo:
    x = x + 1;
    y = y - 1;

    when (rendv1)
    {
      goto bar1;
    }

    when (rendv2)
    {
      z = func2(x, y);
      goto bar2;
    }

The following example results in two edges. The first edge goes from foo to bar1, with the assignments to x and y, and the _print_ function call on it. The edge is guarded by the simultaneous occurrence of the rendezvous connected to rendv1 and the rendezvous connected to rendv2. The second edge goes from foo to bar2, with all three assignments on it. It is unconditinal.

   state foo:
     x = x + 1;
     y = y - 1;

     when (rendv1)
     {                       
       when (rendv2)
       {
         _print_(x);
         goto bar1;
       }
     }

     z = func1(x, y);

     goto bar2;

The following example results in three edges. The first edge goes from foo to bar1, with the assignments to x, y and z. The edge is guarded by the occurrence of the rendezvous connected to rendv1. The second edge goes from foo to bar2, with all three assignments on it and the _print_ function call on it. The edge is guarded by the simultaneous occurrence of the rendezvous connected to rendv1 and the rendezvous connected to rendv2. The third edge goes from foo to bar3 with the assignments to x and y on it. It is unconditional.

   state foo:
     x = x + 1;
     y = y - 1;

     when (rendv1)
     {
       z = func1(x, y);

       when (rendv2)
       {
         _print_(x);
         goto bar2;
       }

       goto bar1;
     }

     goto bar3;

In principle, every goto statement forms a state transition edge. The conditions and actions on the edge are defined by all the statements preceding the goto at the same level or higher (closer to the root) in the statement tree.

Switch statement

A switch statements tests the value of an expression. Depending on the value, it performs different actions. It corresponds to several state transition edges leaving from the same state, but guarded by different conditions. In Lyra, it is simply considered as equivalent to a list of when statements. Each case becomes a when statement with a comparison conditional expression. The default case, if present, also becomes a when statement.

Assignment statement

The assignment statements assign values to state variables and temporary values. It is important to note that assignments to state variables have delayed update, in a similar fashion as the non-blocking assignment in Verilog, while assignments to temporary variables perform instantaneous update, in a similar fashion as the propagation of combinational signals.

Function

Similar to all high level programming languages, Lyra uses functions to help strucure code. The declaration of a function requires a function name, a return type, a list of arguments, and the function body. The function body may contain declaration of temporary variables, and a list of regular semantic statements. The control statements cannot be used in functions. A return statement must exist at the end of every function with a non-void return type. The following code shows an example of a simple function that increments the argument.

   function int add1(int<6> number)
   {
       val int<6> ret;
       ret = number + 1;
       return ret;
   }

A function can be invoked in a semantic expression in another function or an FSM. The arguments and the return value are all passed by value between the caller and the callee. So using a large array as a parameter may result in slow simulation performance.

Compared to C functions, the limitations of Lyra functions are:

• The function body should follow the single assignment rule, i.e. every variable can be assigned only once.
• Recursion (any cycle in call graph) is not allowed.
• No state variable (e.g. static variables in C) is allowed in a function.

External function

Lyra functions have limited capability. They cannot perform sophisticated computation such as trigonometric functions. They do not support loops or recursion. When these capabilities are desirable to a program, users can define external functions to work around the limitations. External functions are also helpful for a Lyra system under simulation to communicate with the external environment. In Lyra , prototypes of external functions are declared. The actual implementation is implemented in C++. Below is the prototype of an example external function. The function is considered a pure function since it does not have side effects.

   function int factor(int val) pure;

Some external functions accept a variable number of arguments, similar to the printf function in C. These functions can use ... to replace their argument list. For example, a print function can be declared as

  function void print(...);

Since print accesses file I/O, it is not pure. Therefore it does not have the pure flag.

The implementation of external functions should be in C++. Below is the implementation of the above factor example.

   void factor(const vector<const Value *> *parms, SIntValue *result)
   {
       int f;
       int n = parms->front()->operator int32_t();
       for (f = 1; n > 0; n--) f *= n;
       result->setValue(f);
   }

As a convention, the actual implementation of an external function always takes two arguments. The first is the pointer to a vector of arguments that comes from the caller, and the second is the pointer to the object where the return value is to be stored. Both arguments must use the Value class and its children classes since these are used internally by the Lyra simulator to store data values. The C++ file must include the value.hpp header file.

The Lyra compiler assumes that user provide the correct prototype for external functions. It will check the types of the arguments and the return value at compile time, and perform necessary type casting for those at simulation time. However, if the prototype mismatches the actual implementation, unpredictable results including segmentation fault may occur. Therefore, one should always define the prototype carefully.

All external functions should be compiled into shared libraries. Prior to simulation, the Lyra simulator will load shared libraries that are invoked in a program. To compile an external function, it is necessary to inform the compiler the path to the Lyra header files so that it can find the Value class. For example, to compile the default library librfsm.so, one can type

   g++ -Wl,-soname,librfsm.so -o librfsm.so -O -fpic -shared librfsm.cpp -I <path to rfsm headers>

Purity of function

Some functions have side-effects such as modifying the content of a global/static variable, allocating storage on heap, printing characters on console, etc. A function is considered pure if it does not have any side effect. For example, the aforementioned add1 and factor examples are pure functions. Understanding purity is important to the when statements of FSMs. Evaluation of the numerical condition of a when statement must be free of side effects, and thus should not involve the calling of any impure functions. The compiler will determine the purity of all functions.

Since the Lyra compiler does not know the implementation of an external function, it fully relies on its prototype to determine its purity. If the prototype contains the pure property, then the external function is considered pure. Otherwise, it is considered impure.

The Lyra compiler can analyze the function call graph to determine the purity of internal functions. If an internal function calls directly or indirectly an impure function, it is considered impure.

If several impure functions are called on a state transition edge or in an internal function, one should not assume that the calls are ordered the same as the source code. The Lyra simulation engine does not necessarily evaluate expressions in source code order. Actually, it evaluates according to the partial order of data dependency. It builds a data dependency graph for all expressions on a state transition edge, and evaluate the graph from leaves to roots. Unless there are clear data dependency between two function calls, their calls may occur in arbitrary order. Such nondeterminism may cause problems for side effects, e.g. the printing order of two values.

Template

Lyra borrows some generic programming ideas from C++. Functions and modules can be declared as templates so that they can be later specialized in different contexts.

Template Parameters

Template parameters are classified into two domains, type parameters and value parameters. Type parameters specify data types and value parameters specify values. A type parameter always starts with the word "type". In the definition of a template function or template module, the template parameters are shown at the very beginning of the definition. Below shows an example template function.

   template  < type vtype = int, vtype imm >
   function vtype addimm(vtype a) pure
   {
	return a + imm;
   }

As seen in the template declaration, the fist parameter is within the type domain, with the name vtype and it takes a default data type int. While the value parameter imm represents the value domain parameter, and it gets a value from the user when the template function is instantiated.

The template parameters are ordered. The type or value defined by a parameter can be used in the definition of subsequent parameters. In the above example, the template parameter imm uses vtype, which is the name of the first parameter. The following is another example illustrating the dependency of parameters.

   template < type vtype = int, vtype imm, vtype imm2 = (imm + imm)>
   function vtype addimm2(vtype a) pure
   {
       return a + imm2;
   }

The imm2 parameter in this example refers to both the first parameter vtype for its data type, and the second parameter imm for its default value. Note that it is necessary to enclose a template expression (e.g. the imm + imm above) with parenthesis unless the expression is a simple constant or an identifier.

The template parameters can be used throughout the body of the function or module that they belong to.

Instantiation of template

When a template function or module is instantiated, a list of parameter values should be provided. The list should be enclosed by #< and > after the name of the template. The parameter values can be specified in two formats: positional list or named list.

• Positional List

  In a positional list, the actual parameter values are enumerated in the same order as the declared order. The actual template parameters should be of the same length as the parameters declared. However, an empty element is allowed. In that case, the default value for that parameter is used.

• Named List

  In this type of list, the parameters are specified with their full names explicitly referenced. Unlike the positional list, the named list doesn't need to have the same length as the definition. Parameters with default values can be skipped.

Below shows different ways of specializing the above template function.

   addimm #<imm = "world", type vtype = string > ("hello");
   addimm #<,16> (32);
   addimm #<type string, "world")("hello ");

Name mangling

This section is for developers. Normal users can safely skip.

Same as in C++, the name of specialized functions or modules are mangled so that instances with different parameter values will have different names. Name mangling is non-deterministic. The same template function with the same set of actual parameters may have different names in two different Lyra programs. Therefore, external template functions are not allowed since one does not know the mangled name of the specialized function in the shared library.

Internally, the name of a template instance is mangled according to the following rules:

1. The mangled name starts with the original function/module name, followed by a list of tokens enclosed by '<' and '>'.
2. Each token represents one template parameter. The token list follows the same order as the list of declared formal parameters.
   • A type parameter is in the form of #id, where id is an unique integer the compiler assigns to the actual type value.
   • A value parameter is in the form of #id=val, where id is an unique integer for the type of the value, and val is the actual value.

For example, the above function addimm may have a mangled name of addimm<#8#8=4> when instantiated. "#8" is the unique integer assigned to the actual type value for "vtype", and 4 is the actual value for "imm". The unique integers assigned to the types are non-deterministic. (The type system supports an infinite number of types, and thus it is impractical to statically assign each type an unique integer ID. The assignment occurs at run time depending on which types are used by the program.) Therefore, the mangled names can change from program to program.

Include and Preprocessing

Lyra uses the C preprocessor cpp for preprocessing. Thus one can include other Lyra files in a file. One can also define and use macros permitted by cpp.

Simulation

The Lyra simulator has a Tcl-based interactive interface. The simulator has the following command line syntax.

 Usage: sim.tcl [-v] [-d num] [-L library path] [-l library name]
                [-I include path] [file name] 
        -v   Verbose mode
        -d   Set debug message level to num, default is 10
        -L   Set the path to shared library files
        -l   Specify the names of shared library files
        -I   Specify the path to included source files

The file name must be the Lyra file containing the special toplevel module. The file may include other Lyra files by using the #include directive of the C preprocessor. One may provide several include paths for the simulator to search for the included source files. One may also provide several library paths and library names so that the simulator can locate external functions. The library names will be prefixed by lib and suffixed by .so automatically. So if a command line option of -l test will instruct the simulator to search for the libtest.so library. The library named librfsm.so is always loaded by default.

After invocation, the simulator supports the following simulation control commands.

• load_design - load a new Lyra program
• reload - reload the current Lyra program, useful when the source code is modified
• step - simulate n steps, n equals one when omitted
• reset - reset all FSMs and initialize all registers
• verbose - turn on or off verbose mode
• debug - change the debugging level, for developers only

The simulator also supports the following query commands. Each command receives a qualified name, and prints the required content. The qualified name can contain wild card characters such as * and ?.

• print_reg - print the value of the named register(s)
• print_mach - print the current state of the named FSM(s)
• show_reg - show the type information of the named register(s)
• show_mach - show the state diagram of the named FSM(s)
• show_rendv - show the connectivity of the named rendezvous
• list_reg - list the names of registers
• list_mach - list the names of FSMs
• list_rendv - list the names of rendezvous

The following commands provide some run-time details of simulation.

• list_ready_rendv - print all rendezvous that may be ready to fire in the current step
• list_fired_rendv - print all rendezvous fired in the last step

A Tk based graphical user interface is also provided as a skin to the simulator. It can be invoked by the sim_tk.tcl command.