View source

=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 &mdash; 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 [[Lyra EBNF Grammar|EBNF (extended Backuas-Naur form) specification]]. A [[Lyra Tutorial|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 [[#Module|modules]], each containing a list of [[#Declaration of ports|ports]], [[#Declaration of internal state variables|registers]], [[#Declaration of DPs|DPs]], [[#Declaration of FSMs|FSMs]], instances of [[#Declaration of sub-modules|sub-modules]], as well as [[#Declaration of rendezvous|rendezvous]], [[#Declaration of signals|signals]] that connect the FSMs, DPs, the sub-modules and the ports.
Lyra defines a [[#Data Types|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 [[#Semantic Operators|operators]] for computation. In addition, it supports the definition of [[#Function|functions]] for common computation. Users can also supply [[#External function|external functions]] defined in other high level languages in the form of shared libraries.

Lyra supports static polymorphism via [[#Template|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:
# 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. 
# Data in Lyra are always communicated by the actual value. Lyra does not support pointers or references. 
# 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.
# Lyra currently adopts a synchronous evaluation model. Each state transition edge takes only one step to evaluate. It does not model evaluation delay.
# Lyra does not support dynamic creation of processes.

=Data Types=

The supported data types in the language include the following:

#[[#Void|Void]]
#[[#Integer|Integer]]
#[[#Bool|Bool]]
#[[#String|String]]
#[[#Tuple|Tuple]]
#[[#Array|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 | 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
# The value is used as the condition of the ? : operator, or
# 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.
 
{| border="2" align="Center"
|+ align="top" |'''Type Compatibility'''
|- align="center"
!
! void
! bool
! integer
! string
! tuple
! array
|- align="center"
! void
| Yes
|- align="center"
! bool
| Yes
| Yes
|- align="center"
! integer
| Yes
| Yes
| Yes
|- align="center"
! string
| Yes
| Yes
| Yes
| Yes
|- align="center"
! tuple
| Yes
| No
| No
| Yes
| <nowiki>*</nowiki>
|- align="center"
! array
| Yes
| No
| No
| Yes
| No
| <nowiki>**</nowiki>
|}

<nowiki>*</nowiki> 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.

<nowiki>**</nowiki> 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.

{| border="2" align="Center"
|+ align="top" |'''Data Types Comparison Relationship'''
|- align="center"
!
! void
! bool
! integer
! string
! tuple
! array
|- align="center"
! void
| <nowiki>=</nowiki>
|- align="center"
! bool
| >
| <nowiki>=</nowiki>
|- align="center"
! integer
| >
| >
| <nowiki>*</nowiki>
|- align="center"
! string
| >
| >
| >
| <nowiki>=</nowiki>
|- align="center"
! tuple
| >
| N/A
| N/A
| <
| <nowiki>**</nowiki>
|- align="center"
! array
| >
| N/A
| N/A
| <
| N/A
| <nowiki>***</nowiki>
|}

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

<nowiki>**</nowiki> 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.

<nowiki>***</nowiki> 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.

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

# [[#Declaration of ports|Declaration of ports]]
# [[#Declaration of rendezvous|Declaration of rendezvous]]
# [[#Declaration of signals|Declaration of signals]]
# [[#Declaration of sub-modules|Declaration of sub-modules]]
# [[#Declaration of internal state variables|Declaration of internal state variables]]
# [[#Initialization of internal state variables|Initialization of internal state variables]]
# [[#Declaration of DPs|Declaration of DPs]]
# [[#Declaration of FSMs|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 [[#Declaration of rendezvous|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.
<!--Multi-cycle rendezvous can be used with all port types for modeling convenience, which introduces implicit states. Multi-cycle port only connected with opposite multi-cycle port.The star (*) behind port name denotes multi-cycle port, for example, a multi-cycle outin port can be specified as:

    oi <uint<12>, uint<8> > read*,

In this example, read* is a port that can take multiple cycles to finish. Read will be treated as a rendezvous pair: read.begin and read.end. Since it is of oi type, output occurs first, and input occurs later. Therefore, port output/write is associated with write.begin, and port input/read is associated with read.end.
-->

==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;<br/>
    /* positional association */
    producer pro1(r1); //Producer has an output port.
    buffer   buf1(r1,r2); /*The position are input port and output port respectively*/<br/>
    /* 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 [[#Declaration of FSMs|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;<br/>
    reg (int[4], bool)[] xarray;<br/>
    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|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;<br/>
        fifo f1(.enq(inp), deq(consume));<br/>
        reg int myreg;<br/>
        fsm p1(in <int> consume)
        {
            init U: // start state
                when (consume)
                {
                    myreg = consume.read();
                    goto V; 
                }<br/>
            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|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;<br/>
        reg int myreg;<br/>
        init {
           myreg = 0;
        }<br/>
        dp sum(sout <int> s) {
            val int tmp;
            tmp = myreg + inp;
            s = tmp;
        }<br/>
        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.


{| border="3" cellpadding="3" align="center"
|+ align="top" |'''Semantic Statements'''
|- align="center"
! Name
! Syntax
|- align="center"
| assignment
| exp = exp;
|- align="center"
| expression
| exp;
|- align="center"
| goto
| goto state_name;
|- align="center"
| when<br />
| align="left" | when (list of ports or exps)<br/>&nbsp;&nbsp;statement;
|- align="center"
| switch
| align="left" | switch(exp)<br/>{<br/>&nbsp;&nbsp;case val1: statement;<br/>&nbsp;&nbsp;case val2: statement;<br/>&nbsp;&nbsp;...<br/>&nbsp;&nbsp;default: statement;<br/>}
|- align="center"
| 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;<br/>
     when (rendv1)
     {
       goto bar1;
     }<br/>
     z = func1(x, y);<br/>
     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;<br/>
     when (rendv1)
     {
       goto bar1;
     }<br/>
     when (rendv2)
     {
       z = func2(x, y);
       goto bar2;
     }<br/>

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;<br/>
      when (rendv1)
      {                       
        when (rendv2)
        {
          _print_(x);
          goto bar1;
        }
      }<br/>
      z = func1(x, y);<br/>
      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;<br/>
      when (rendv1)
      {
        z = func1(x, y);<br/>
        when (rendv2)
        {
          _print_(x);
          goto bar2;
        }<br/>
        goto bar1;
      }<br/>
      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 [[#Purity of function|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 [[#Purity of function|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:                             
# The mangled name starts with the original function/module name, followed by a list of tokens enclosed by '<' and '>'.
# 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.