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.