Metaprogramming

Metaprogramming lets you write units whose implementation depends on the type parameters provided. Currently, Spade has only a single metaprogramming construct:

gen ifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.

It looks very similar to normal if expressions, but the condition in gen if must be a type parameter rather than a runtime parameter. Unlike if expressions where both the true and false branches are instantiated, a gen if only instantiates one of the branches depending on the condition. In fact, the untaken branch gen if can have type errors, which as we shall see is very useful.

The most common use case for gen if is to write code that operates on all elements of an array, and does so in a way that is generic over the number of elements. For example, we can write a function which sums the elements of an array like this:

fnFunctions together with entityEntities together with fn and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike fn, entity can contain registers and therefore have state and unlike pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline., they do not have a statically known latency or pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. structure. and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure). sum_elems<#uint N>(array: [uint<32>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits; N]) -> uint<32>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits {
    gen ifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it. N == 0 {
        0
    } else {
        array[0] +.Add two values, producing a value of the same size while wrapping ifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it. the result overflows. This is unlike + where the addition results in one more bit than the input type, guaranteeing no overflows. sum_elems(array[1..])
    }
}

As you can see, we gen if to do compile time recursion based on the length of the array. In the base case, when the array is empty, the sum of the elements is trivial to compute: it is 0. In the recursive case, we can compute the sum of the elements by separating the first element from the rest, computing the sum of the rest of the elements, and adding that to the value of the first element.

Normally, recursion in hardware is not possible; each instance of a unit becomes instantiated as a physical circuit, and with unbounded recursion, that requires infinite resources. However, with gen if, the recursion happens at compile time which means that as this function is called, the N passed to recursive calls shrinks by 1 until it eventually reaches the base case at which point the recursion is finished. This of course means that we end up with N adders, which is necessary in order to add an array of N elements in a combinational circuit.

Exercises

Working with recursion can feel unfamiliar at first, but once you get used to it, it is a very powerful technique for doing code-generation based on type parameters. To help you get familiar with the technique, try a few of these exercises:

Write a function that returns true if the array contains the value 5
Write a add_one function that takes an array and produces a new array where each element is the element in the old array plus one. You can use array1.concat(array2) to concatenate two arrays, and [N..M] to access parts of arrays.
If you did the first exercise with a linear search, implement it using binary search.

Lambda Units

The functions in the previous exercises are not re-usable. If your project needs to be able to also add 2 elements of an array, or find an element whose value is equal to 10 instead of 5, you have to add new functions. This very quickly runs into scaling issues. Modern languages, especially languages with a functional heritage allow you to customize the behavior of functions by passing other functions as values. Spade, having a functional heritage via Rust is of no exception.

Because it is much more common to use functions which take functions as inputs, than it is to define them, we will first discuss how they are used.

To generalize the add_one function, you can think of it as a function which transforms a value from one to another, and performs the same transformation on all values in the array. A function that does this may have a signature like this:

impl<#uint N> [uint<32>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits; N] {
    fnFunctions together with entityEntities together with fn and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike fn, entity can contain registers and therefore have state and unlike pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline., they do not have a statically known latency or pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. structure. and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure). transform(self, f: impl Fn(uint<32>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits) -> uint<32>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits) -> [uint<32>Type used to represent unsigned integers. The generic parameter (<N>) specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.ies the number of bits; N] {
        // Implementation details
    }
}

It takes the original array as an input, as well as a value called f which has the type impl Fn(uint<32>) -> uint<32>. This means that f has to be a function that transforms from one value of type uint<32> to another. Using this function, the implementation of transform produces a new value.

So, how do we get a value of that type? The answer is a lambda function which can be defined as:

fnFunctions together with entityEntities together with fn and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike fn, entity can contain registers and therefore have state and unlike pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline., they do not have a statically known latency or pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. structure. and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure). |fnFunctions together with entityEntities together with fn and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike fn, entity can contain registers and therefore have state and unlike pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline., they do not have a statically known latency or pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. structure. and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure). |...| is a lambda function, a function written in-line to be passed to other functions to control their behaviour.
The arguments to the function are the part between the ||value| {
    value + 5
};

It is a function that has no name, it can be used directly in an expression. The parameters are specified between || and unlike non-lambda units, the type of parameters can be inferred. The body of the lambda function works exactly as the body of non-lambda functions.

To use this lambda function in the transform function we defined above, you can pass it directly as a value:

some_array
    .transform(fnFunctions together with entityEntities together with fn and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike fn, entity can contain registers and therefore have state and unlike pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline., they do not have a statically known latency or pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. structure. and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure). |fnFunctions together with entityEntities together with fn and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike fn, entity can contain registers and therefore have state and unlike pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline., they do not have a statically known latency or pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. structure. and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure). |...| is a lambda function, a function written in-line to be passed to other functions to control their behaviour.
The arguments to the function are the part between the ||value| {
        value +.Add two values, producing a value of the same size while wrapping ifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it. the result overflows. This is unlike + where the addition results in one more bit than the input type, guaranteeing no overflows. 5
    })

Lambda functions are values, which means that you can bind them to variables if desired. For example, you could use transform like this:

letlet is used to define a variable. Spade infers the type of most variables from context, but you can also specifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it.y the type with : <type> before the =. f = fnFunctions together with entityEntities together with fn and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike fn, entity can contain registers and therefore have state and unlike pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline., they do not have a statically known latency or pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. structure. and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure). |fnFunctions together with entityEntities together with fn and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike fn, entity can contain registers and therefore have state and unlike pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline., they do not have a statically known latency or pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. structure. and pipelineDefines a pipeline. The number in in the parentheses is input-to-output latency of the pipeline. are the basic building blocks of Spade circuits. Unlike entities and pipelines, functions have no internal state, they are combinational (pure). |...| is a lambda function, a function written in-line to be passed to other functions to control their behaviour.
The arguments to the function are the part between the ||value| {
    value +.Add two values, producing a value of the same size while wrapping ifReturns the value of the first branch if the condition is true, otherwise the second branch.
Note that unlike software languages, Spade does not have conditional execution. You do not conditionally assign values inside if expressiosn, you compute a value and return it. the result overflows. This is unlike + where the addition results in one more bit than the input type, guaranteeing no overflows. 5
};
some_array
    .transform(f)