A Tydi language about tydi HOT 1 OPEN

// This is a brainstorm, not just a grammar definition or just examples,
// It's going to be a weird mix of both and more.
// I wrote this mainly from a user perspective, not from a compiler
// designer/implementer perspective.


// --------
// Literals
// --------

// signed integers, defaults to type i32
10      // decimal
1_0     // decimal
-10     // decimal
0xA     // hex
0o12    // octal
0xb1010 // binary

// unsigned integers, defaults to type u32
10u      // decimal
1_0u     // decimal
-10u     // ERROR
0xAu     // hex
0o12u    // octal
0xb1010u // binary

// character literals (ASCII or UTF8 ?)
'd'
'\n'

// string literals (ASCII or UTF8 ?)
"dolphins"

// half precision IEEE 754 floating point
1.0f16
// single precision IEEE 754 floating point
1.0f32
// double precision IEEE 754 floating point (the default)
1.
1.0
1.0f64
// quadruple precision IEEE 754 floating point
1.337f128
// octuple precision IEEE 754 floating point
42.0f256


// --------------------
// Builtin scalar types
// --------------------

// Null type - useful for e.g. user part of streams or generics (see e.g. Map
// below)
null

// Boolean types
bool // true or false

// Bit type
bit
// Should this hold VHDL-like std_logic values such as
// 0, 1, U, X, Z, W, L, H, - ?
// or probably better, like Verilog:
// 0, 1, X, Z


// -----------------------
// Builtin composite types
// -----------------------

// Integer types.

// Integer types consist of N bit parts that can be indexed or sliced (see
// below). Their numeric value is their two's complement value.

// Signed
int<N>
// Unsigned
uint<N>
// They have a size generic N, useful for type or generic propagation. N can be
// an expression, but it must resolve to a positive integer.
uint<0> // error

// These could maybe be aliased in a std lib as such?:
// Unsigned
u1, u2, u3, ... u(2^??)
// Signed
i1, i2, u3, ... i(2^??)

// Does a Rust-like u/isize make sense? Probably not, because there is no
// architecture. We *could* have isynth and usynth to refer to the compiler host
// architecture native integer size, but I currently lean towards not having
// something that could lead to portability issues.

// Floating-point numbers follow IEEE 754.

// While floats could be defined as structs (see below), we need them in generic
// arithmetic, so I think it's useful to define them as basic types.
// Operations on floats may not be synthesizable for now.
// Floating-point parts consist of their respective IEEE 754 fields, that can
// be indexed (but I don't think slicing makes sense here).

// IEEE 754 basic types:
f32, f64, f128  // binary floating point types
d64, d128       // decimal floating point types

// IEEE 754 non basic types:
f16, f256
d32

// Textual
char    // ascii or utf8? or have byte for ascii and char for utf8 like Rust?

// I suppose "char" could make people uncomfortable w.r.t. encoding, so we could
// also have:
byte   // obviously represented as 8 bits when used as net/port
ascii  // represented as 7 bits (or do we want extended ascii?)
utf8   // represented as 32 bits

string  // should we allow dynamic sizing? if so, it is not (easily)
        // synthesizable. This type is meant for non-synthesizable stuff such
        // as debug prints and generics.

// Maybe later:
// custom precision floating point ?
// fixed point ?
// posits ?


// Fixed-size array of size S elements of type T.
// S must be an expression of literals or constants
T[S]

// Tuples
// Should they carry the same semantics as struct (i.e. Tydi Group) ?
(T0, T1, ...)

// Product type

// Direction token for field (and port declarations, later).
>  // (forward or out)
<  // (reverse or in)
// Yes, these symbols are up for massive debates. And yes, I have already
// confused myself profoundly with it when typing port directions.

// Field declaration syntax:
// <attributes> <field identifier> <direction token> <type>

// Product type decl.
// Syntax:
// struct <identifier> {
//     <field decl> (, <field decl>)*
// }

// Product type example:
struct LegacyStream {
    valid > u1,
    ready < u1,
    data  > u8
}

// Sum type decl
// Syntax:
// union <identifier> {
//     <field decl> (, <field decl>)*
// }

// Sum type example:
// To define a net/port of type struct A outside of a stream,
// all values must be defined. Therefore, when A is used as a stream data type,
// for each handshake on X, there must be a handshake on Y. This is inherit to
// the Tydi spec representation of this stream as a stream of group<x, y>
union OptionalValue {
    None > null,
    Value > f64
}

// Variant decl:
// Syntax: <variant identifier> (= <custom value expression>)

// Enum type.
//
// Syntax:
// enum <identifier> (: <T>) {
//     <variant decl> (, <variant decl>)*
//     ...
// }

// Where T is the synthesized type. Perhaps analogous to "storage" type, this
// could be called "spatial" type. T will be log2ceil(num variants) number of
// bits when synthesized, unless explicitly defined to be otherwise.

// Enum type example:
enum ProtocolVersion {
    IPv4,
    IPv6
}

// Enum type with explicit spatial type and value
enum ProtocolVersion : u8 {
    IPv4 = 0,
    IPv6 = 0x1
}

// Tydi stream.

// A Tydi stream has three generics:
// T = the stream data type
// D = dimensionality, an expression or another generic from which a positive
//  integer can be derived, default = 0
// U = user data type, default = null

// It may appear some of the original Tydi attributes for streams are missing.
// They are described elsewhere:
// - Direction is not defined here; it is declared through the struct or union
//   field decl. This makes more sense, as direction is relative (to another
//   field).
// - Synchronicity, same story, as the struct/union decl is the context in
//   which child/parent relations are visible.
// - Complexity and throughput should be an attribute of a net or port,
//   since they talk about properties of an interface but not of a data
//   structure. Types should only capture unique properties of the data
//   structure they represent.

stream<T, D, U>

// Stream examples:

stream<u8>     // an infinite stream of u8s
stream<u8, 1>  // an infinite stream of variable length sequences of u8s

// A stream of a struct type:
struct A {
    x > u8,
    y < u8,
}

// a stream with A.x in forward direction, A.y in reverse  direction.
// To define a net of type struct A outside of a stream, all values must be
// defined. Therefore, when A is used as a stream data type, for each handshake
// on X, there must be a handshake on Y. This is inherit to the Tydi spec
// representation of this stream as a stream of group<x, y>
stream<A>

// A struct type with the synchronicity attribute set explicitly to flatten.
// This attribute is meaningless for non-stream nets or ports using this
// type (i think?)
struct B {
    x > u8,
    #[flatten]
    y > u8  // if B were to be used in a stream with dimensionality > 0,
            // only one y has to be transferred for each outermost
            // sequence of x's.
}

stream<B, 1>  // a stream with B.x with a last signal, and a stream with B.y
              // without a last signal.

// A struct type with the synchronicity attribute set explicitly to desync.
struct C {
    x > u8,
    #[desync]
    y > u8,
}

stream<C, 1>    // Two streams with their own last signal. The same amount of
                // sequences must be transfered, but each corresponding sequence
                // can be of different length.

// I'm following the Rust attribute macro style here, but perhaps a nicer syntax
// is possible.


// ---------------------------------
// Builtin type operations/functions
// ---------------------------------

// It would be nice to have builtin special operators/functions so we can get
// properties of (stream) types, e.g. to be used in generic arithmetic.
DimOf(stream<T, 1>) // yields 1


// -------------
// Special types
// -------------
// We need to think about clocks.
// When using streams types, they always must have some associated clock.
// I would propose there is always an implicit global default clock domain with
// an associated clock and reset that will be propagated to any component using
// a stream type in their port list and does not explicitly define some other
// clock/reset to be used. I think this is also done in Spatial.
// It should be possible to define more clock domains to automate e.g. CDC.

clk // explicit clock type?
rst // explicit reset type?

// Random thought: associating stuff that uses clock/reset with it could look
// syntactically similar to Rust's lifetime specifier


// ------------
// Type aliases
// ------------
type CharStream = stream<char>;  // This is a stream of char type without a
                                 // last bit.

type String = stream<char, 1>;   // A stream of char type with a last bit.


// -----------
// Expressions
// -----------
// We need expressions.
// At this stage, they will mainly be used to do arithmetic with generics and
// constants.
// Any decision here will have great impact on the language design, and needs
// some more thought. I personally like languages that are "expression
// languages" like Rust or Scala. (see:
// https://doc.rust-lang.org/reference/statements-and-expressions.html)
// At this point I don't feel qualified enough to come up with something good
// enough to discuss here so I will leave this completely open for suggestions.


// ---------
// Operators
// ---------
// Expressions require operators such as:
//
// +            arith addition
// -            arith subtraction
// *            arith multiplication
// /            arith division
// .            member access?
// etc... needs more thought at this point, as described above.


// ---------
// Constants
// ---------
// syntax: const <identifier> : <type> = <expression>

// boolean types
const a = true;
const a : bool = true;

// numeric types
const a : u3 = 7;               // u3
const a = 10;                   // i32
const a : u4 = -10;             // error
const a = 10u10;                // u10

// composite types
const a = [1, 3, 3, 7];                             // array<4, i32>
const a = (42.0, 1.337);                            // tuple<2, f64>
const a = LegacyStream { valid = 0, data = 0 };     // LegacyStream
const a = OptionalValue::Value { 0.1 };             // OptionalValue
const a = ProtocolVersion::IPv4;                    // ProtocolVersion

// expressions can be used to define values, as long as the expressions use
// other constants.
const a = 0;
const b = 1;
const c = a + b;

reg a = 0;
const b = 1;
const c = a + b; // error


// -----
// Ports
// -----
// Syntax: <identifier>
//           <direction token> <type>
//           ('=' <default value expression>)


// ----------
// Components
// ----------
// Components are entities that help to build hierarchy and reusable parts of
// the design.
// While it is an awesome term, I don't think streamlet should be a keyword,
// since a streamlist is just a special case of a component for which all ports
// have a stream type, but they carry no special semantics that cannot be
// expressed with the component keyword.
//
// Syntax:
// comp <identifier>
//      ('<' <generic list> '>')
//      (':' <interface list>)
//      ('(' <port decls> ')')
//      ('{' <implementation '}')
//
// When a component has no defined implementation and is not marked "extern",
// (see below), the compiler should issue a black-box error by default, and not
// a warning that is buried under thousands of other useless warnings like we
// are used to from traditional HDLs / toolchains.
//
// A component should probably be a type itself?

// An adder
comp Add (
    a < u8,
    b < u8,
    y > u8
) {
    // implementation goes here.
    // Referring to ports could be done through a keyword such as e.g. self:
    self.y = self.a + self.b;
    y // invalid reference

    // Or could we omit self and not allow local declarations of stuff with
    // the port name? This would result in smaller code, but it will have less
    // local reasoning. I would personally still go for the latter.
    y = a + b;
}

// An N-bit adder
comp Add<N: u64> (
    a < u<N>,
    b < u<N>,
    y > u<N>
) {
    // implementation goes here.
}


// -------------------
// Component instances
// -------------------
comp PlusOne<N: u64> (
    a < u<N>,
    y > u<N>

) {
    // An instantiation of Add<8> with the identifier adder:
    inst adder : Add<N>;

    // VHDL-like associativity lists suck.
    // We can refer to instance ports anywhere in implementation code as
    // follows:
    adder.a = a;
    adder.b : u<N> = 1;
    y = adder.y;
}


// --------------------
// Component attributes
// --------------------
// It may be useful for later on if we could give components specific
// attributes, such as:
#[streamlet]
comp foo (
    // only ports with the stream type are allowed.
);

// Perhaps to even define latency useful for building larger designs with
// automated buffering, if it cannot be derived automatically of course.
#[streamlet, latency={{a,b,5},{a,c,6}}]
comp foo (
    a < stream<...>,
    b > stream<...>,
    c > stream<...>,
);


// -------------------
// External components
// -------------------
// (Imperfect analogies ahead:)
// Using the "extern" keyword and an "RTL" specifier, it is possible to declare
// a component is implemented outside this hardware description. We need to
// think about how far we could take this. There is no real "ABI" for hardware
// so we must think about how the build tool "links" such an external component
// into the target output. Hence I called it "RTL" here but perhaps there is a
// better name for this. It would be possible to "link" such components into the
// design when they use e.g. the Tydi canonical representation of it in VHDL,
// SystemVerilog, Verilog, or lower level stuff like FIRRTL. For the traditional
// HDLs mentioned here, the build tool must know how to deal with such external
// sources.

// Example:
extern "VHDL" comp foo (
    i < u8,
    o > u8
); // implementation is omitted.


// ----------------------------------------------
// Special attributes for ports with stream types
// ----------------------------------------------
comp X (
    #[throughput=10, complexity=5]
    a < stream(u8)
);


// ----
// Nets
// ----
// Nets are simply wires between things within a component implementation, like
// the Verilog "wire" keyword. They do not have the semantics of VHDL "signal"s
// as in that they could be used to create registers.
//
// Syntax:
// net <identifier> (: <type>) (= <expression>)

net q : u8 = 1;     // a net named q of type u8 tied to 0b00000001
net r = q;          // a net named r of type u8 driven by q.
net s = stream<u8>; // a net named s of type stream<u8>. If nothing drives this
                    // net, the default value of the streams "valid" is
                    // de-asserted with the other values don't care.
net t : stream<u4> = s;   // Error.


// ----------------
// Registers (TODO)
// ----------------
reg x = 0;


// -----------
// Connections
// -----------
// Connections declarations of source and sink connections.
// Syntax:
// <destination identifer> = <expression>;
// Source can be any expression. Perhaps the assignment symbol = should be an
// operator, and the assignment should be an expression itself that yields a
// reference to the net being driven, so you can chain like: a = b = c;.

// Example:
comp X (
    a < u8,
    b > u8
) {
    b = 0;  // drives b to zero (all bits are typically ground).
    a = 0;  // error, a is an input.
    b = a;  // drives b with a.
    a = b;  // error, a is an input.
}


// --------------------------------------
// Selecting and slicing into basic types
// --------------------------------------
// Single part/element selection and slicing is done through the [] operator.

// Range expression:
// Syntax: <inclusive start index> .. <exclusive end index>
// Syntax: <inclusive start index> ..= <include end index>
// etc.., see Rust.

// Slicing into arrays:
net a : array<u8, 3> = [1, 2, 3];
net b : array<u8, 2> = a[0..1];
net c : array<u8, 2> = a[1..];
net d : array<u8, 2> = a[..1];
net e : array<u8, 2> = a[0..3]; // error

// Slicing into numeric types is allowed for numbers that have "parts"
// (somewhat following Verilog terminology here), i.e. int<N>, uint<N> and f32,
// f64, f128, d64, d128.

// Slicing into integer parts
net a : u8 = 1;
net b : bit = a[0];
net c : a[0..3]; // becomes a u4
net d : a[4..8];

// Selecting float parts:
net e = 0.1;    // f64
net f = e.sign; // bit
net g = e.exp;  // i don't even want to go into this.

// Selecting stream parts:
net h = stream<u8>;
net i : bit = h.valid;

// --------------------------------------------
// Generative structural expressions/statements
// --------------------------------------------
// Conditional generate
// Syntax: gen if <bool expression> { <statements> } else { <statement> }

// Example:
gen if a = 0 {
    b = c;
} else {
    b = d;
}

// Pattern matching generate
// Syntax: gen match <expr> {
//    <expr> : { <statements>},
//    ...,
// }

// Example:
gen match a {
    0 : { b = c; }
    1 : { b = d; }
    _ : { b = 0; }
}

// Generative for
// Syntax: gen for <iterator> in <iterable> { <statements> }
gen for I in [1, 2, 3] {
    inst a;
}

// How could we refer to some instance of a?
// What if we could have arrays of instances?


// ----------
// Interfaces
// ----------
// Interfaces are pre-defined sets of port declarations with associated
// generics, that may be implemented by components. They are useful when
// when components have generics that take other components as an argument, to
// scope the allowed components according to some interface specification.

// Syntax:
// interface <identifier>
//   ('<'<generic list>'>')
//   '(' <port decls> ')'

// Example for a Map interface:
interface Map<type I, type O, type U=null> (
    input  < I,  // input port
    output > O,  // output port
    user   < U   // custom data port
);

// Example of a component implementing the Map<u8, u8, u8> interface.
// This component will increment elements of i by u.
comp Incrementer : Map<u8, u8, u8> {
    // impl goes here
}

// Could be equivalent to:
comp Incrementer : Map (
    // I and O could be inferred using this syntax:
    Map::input  < u8,
    Map::output > u8,
    Map::user   < u8
) {
    // impl goes here.
}

// Example continued:
// A component with a component generic requiring the above Map interface.
// This component would implement a one-to-one mapping of every element of the
// sequence of i to o. U is used for a custom net to the MapComp that can be
// used for e.g. run-time parameters, but is null by default.
comp MapSeq<type I, type O, comp C : Map<I, O, U>, type U=null> (
    input  < stream<I, 1>,  // Input sequence.
                            // I'm assuming here if I = stream<T, 1>,
                            // stream<I, 1> becomes stream<T, 2>.
    output > stream<O, 1>,  // Output sequence.
    user   < U              // Custom signals to the internal instance of C.
) {
    inst map : C;
    map.user = user;
    // More implementation would follow here, but requires non-structural stuff.
}

// Example continued:
comp Top (
    i < stream<u8, 1>,
    o > stream<u8, 1>
) {
    inst inc_seq : MapSeq<u8, u8, Incrementer, u8>;

    // Increment every element by 42.
    inc_seq.u : u8 = 42;
    inc_seq.i = i;
    o = inc_seq.o;
}

// Example of a reduce component.

// Reduces two values to one, given some initial value.
interface Reduce<type T, type U=null> (
    input_0 < T,
    input_1 < T,
    output  > T,
    user    < U
)

// Example continued:
comp Add<T> : Reduce<T> {
    // This would implement: output = input_0 + input_1;
}

// Example continued:
// Reduces a sequence
comp ReduceSeq<type T, comp C : Reduce<T, U>, type U=null> (
    initial < stream<T>,   // initial value
    input   < stream<T,1>, // input sequence
    output  > stream<T>,   // reduced result
    user    < U            // custom signals to the internal instance of C.
) {
    inst reduce_seq : C;
    reducer.user = user;
    // More implementation would follow here, but requires non-structural stuff.
}

// Example continued:
comp Top (
    numbers < stream<u8, 1>,
    sum > stream<u8>
) {
    inst reducer : ReduceSeq<u8, Add<u8>>;
    reducer.i = numbers;
    reducer.d = 0;
    sum = reducer.o;
}

// Components can implement multiple interfaces:
interface X ( a > u8 );
interface Y ( a < u8 );

comp Z : X, Y {
    // impl goes here
    X::a    // refers to port a of interface X
    Y::a    // refers to port a of interface Y
    a       // error, undefined.
}


// --------
// Packages
// --------
// Packages are namespaced collections of types, constants and components.
// The package name "work" is reserved for the root namespace.

// Example:
package X {
    type String = stream<char, 1>;

    const pi = 3.14;

    comp foo {
        a < u8,
        b > u8
    }
}

// Packages and their constituents can be used without their nasmespace
// through a use declaration.

// Example:
use X::*;               // use everything
use X::{String, pi};    // use only specific stuff

comp bar {
    inst moo : X::foo;
}

// The root namespace for a project is "work".
inst a : work::bar;
inst b : work::X::foo;


// ------------
// Doc comments
// ------------
// Doc comments start with three slashes: /// and are placed in front of the
// declaration to be documented.

// Example:

/// A dolphin
struct Dolphin {
    /// The name of the dolphin.
    name : String,
    /// The size of the dolphin in cm.
    size : u32
}

/// An interface for components producing Dolphins.
interface DolphinProducer (
    /// Dolphin output.
    o > Dolphin,
)


// ----------------------
// An example from TPCH-6
// ----------------------
// SELECT
//     sum(l_extendedprice * l_discount) as revenue
// FROM
//     lineitem
// WHERE
//     l_shipdate >= date '1994-01-01'
//     AND l_shipdate < date '1995-01-01'
//     AND l_discount between 0.06 - 0.01 AND 0.06 + 0.01
//     AND l_quantity < 24;

/// Package with components performing TPC-H queries.
package tpch {

/// A date.
struct Date {
    year > u12,
    month > u4,
    day > u5,
}

/// A range (dynamic).
struct Range<T> {
    /// Start value (inclusive)
    start > T,
    /// End value (exclusive)
    end > T,
}

/// A row from the LineItem table.
struct LineItem {
    extended_price > f64,
    discount > f64,
    ship_date > Date,
    quantity > f64,
}

/// Parameters for TPC-H query 6
struct Q6Params {
    /// The shipdate range for which the revenue must be calculated.
    shipdate_range < Range<Date>,
    /// The discount range for which the revenue must be calculated.
    discount_range < Range<f64>,
}

/// Interface for filter predicates
interface Predicate<T> {
    i < T,
    o > bool,
}

/// Component implementing the Predicate interface, outputting true for T's
/// that fall within the range, false otherwise.
comp WithinRange<T> : Predicate<T> (
    range < Range<T>,
) {
    // impl goes here.
}

/// TPC-H Query 6 with dynamic shipdate and discount ranges.
comp Q6 (
    /// Parameters for the query on each table.
    params < stream<Q6Params>,
    /// The stream of tables to operate on.
    tables < stream<LineItem, 1>,
    revenue > stream<f64>,
) {
    /// The ship date filter. See definition of MapSeq above.
    inst date_flt : MapSeq<Date, bool, WithinRange<Date>, Range<Date>>;

    /// The discount filter.
    inst discount_flt : MapSeq<f64, bool, WithinRange<f64>, Range<f64>>;

    // The params stream has members that go different ways. It's probably
    // good to make the sync explicit. Perhaps it could look like this:
    date_flt.range, discount_flt.range = params.split({shipdate_range},
                                                      {discount_range});
    // With .split(...) which should be a builtin member of a stream type,
    // you can split the streams out (at your own risk) to any combination.
    // Each argument of split is a list of members that should stay
    // together. This results in new (anonymous) types.

    // Implicit stream split could be a thing:
    date_flt.range = params.shipdate_range;
    discount_flt.range = params.discount_range;

    // Warning! Control flow ahead - non-goal for now so can be safely ignored.
    // Just a brainstorm.
    // For each table (this continues indefinitely unless reset is asserted).
    for table in tables {
        // For each row in the table.
        // This continues up to when the tables last bit is asserted.
        date_flt.input = row.shipdate;
        discount_flt.input = row.discount;
        // TODO
    }
    // end of control flow
}

// ---------------
// Random thoughts
// ---------------
// It would be nice if generics are Turing-complete.
// It would be nice if generics could interface with the file system.

// --------------------------------------------
// Random examples that got lost in the process
// --------------------------------------------

struct Dolphin {
    name : String,  // This is a stream
    size : u32,     // This is not a stream
}

/// This component feeds baby dolphins until they are the size of a grownup
/// model and then outputs them.
comp Feeder {
    // Since Dolphin.size is not a stream for model, there is no
    // synthesized synchronization between model.size and model.name.
    // Users are on their own in terms of how to synchronize between the fields
    // of the struct.
    model < Dolphin,

    // However, in the following case, a stream is wrapper around it.
    // We will interpret this as a Stream<Group< .... >> in the spec,
    // so for each name of the inner stream for name, also one size must be
    // handshaked on the outer stream for size.
    baby < stream<Dolphin>,
    grownup > stream<Dolphin>,
}