Higher order Filament

[gabizon103]

I think there would be a lot of utility in a version of Filament that allows for components to be passed into other components. This comes up when defining components like map; there is no way to write a general map component in Filament right now, so you'd need to write a separate module for each kind of map you want to compute.

A similar use case pops up when writing kernels like BLAS, for example, where you might want to perform the same computation over different number formats (integers, different floating point precisions, etc). Again, the way to accomplish this currently is to duplicate your components for each specific use case.

I haven't thought too deeply about this other than that it would be nice to have, but at first glance it seems like one way to accomplish this is to have something analogous to Rust's traits, where we can specify an interface for a component to implement, and then it can be passed into another component that requires it to satisfy that interface. For example, a component Dot can take in a component that it uses for its additions, and require that it satisfies some interface called Add that says the component adds two numbers of some arbitrary data format. AddInt, AddFP32, etc would all implement an Add interface.

We would need to think more about what sorts of things the compiler should check for to make all of this safe, but for now I am wondering about how others feel about the utility of something like this, and if it is worth exploring further.

[rachitnigam]

Thanks for creating the discussion! Yes, this has come up a couple of times and I've thought about this as well. Broadly, I'd say there three categories of questions:

• Technical questions: "how do we enforce filament's pipelining guarantees in a higher-order variant" (this depends on whether we allow passing instances or components. The former would require more complicated reasoning because it allows sharing the same instance across multiple invocations.)
• Usability questions: It is already quite hard to read Filament programs IMO with the signatures being so complex (events, parameters, ports). Adding higher-order stuff would make it even more complex. Furthermore, in presence of output parameters, the programs might look more complex potentially?
• Efficiency questions: How easy is it to write efficient higher-order components? In the case we just pass component definitions, maybe we can argue that it's easy to generate the most efficient circuit but if we allow instances to be shared, the control logic quickly gets out of hand.

My instinct is that we should come up with some compelling use cases/examples before we dive into this. We should also carefully study the state-of-the-art (Chisel and Bluespec) and see if we can learn from their design.

[gabizon103]

We talked about this synchronously a bit, so I'll document it here. One valuable thing about Filament is that the "cost" of the code you write is always clear; one concern about higher order Filament is that it could perhaps obfuscate that, i.e. make it unclear what will actually happen when your design gets compiled. One idea we had is that if higher order components only describe the way data is routed, then maybe it is possible to show that writing higher order components adds no overhead.

This last idea is in line with what I was thinking about the 3 points given above; my vision was to have higher order components accept a component (not an instance), that would just be instantiated/invoked as needed inside the higher order component. I think this would cut down on (eliminate?) the complicated control logic that might be necessary for passing instances to components, and keeps it pretty easy to see what is going on in the designs you write.

Regarding usability/readability, I admit I'm also concerned about this. I think it shouldn't be too bad, but at the same time these small costs add up. I was thinking of making it look similar to a parameter, so we might have a component signature that begins like Map[W, N, F: impl Mappable] or something, where Mappable is some trait or interface that lets us know a component can be used in a map operations; realistically, this would just mean it takes at least one input and produces one output. I think it may be a little weird to "overload" what an input parameter means, because up til now parameters can only represent integers. To be honest, I can't think of a way to encode this without compromising at least a little bit on readability.

[rachitnigam]

Finally catching up with this! I think accepting components is probably the right approach; it is not clear to me yet that there is a nice and ergonomic way to support fine-grained sharing and whether it's even needed. Higher-order component do not necessitate any control logic AFAICT because they get monomorphized.

I was thinking of making it look similar to a parameter, so we might have a component signature that begins like Map[W, N, F: impl Mappable] or something, where Mappable

I like this idea! I think the tricky thing here is that we've now implicitly proposed abstract signatures (or traits) and will have to come up with a crisp definition of what being compatible with a signature really means.

[UnsignedByte]

I think another possibility is sort of already implemented in our language.

We have the concept of externs, which are just component signatures with no implementation. Could we not do the same thing with all components - I.E. divorce the body of a component (its impl) from the signature. In this way, just as one instance can have multiple invocations, one signature can have multiple definitions? This does have a couple readability worries though, for example an implementation would either have to duplicate the signature of what it is implementing or risk confusion on the developer's side about the intervals for inputs and outputs, as well as constraints on parameters...

We could however then define normal components the same way we do in software languages with inheritance

interface FPAdd[E, M]<'G:1>(
  X: ['G, 'G+1] W,
  Y: ['G, 'G+1] W,
) -> (
  R: ['G+L, 'G+L+1] W,
) with {
  some W where W == E + M + 1;
  some L where L >= 0;
} where 
  E > 0,
  M > 0;

// Skipped rewriting signature here but that would probably be better to do for readability
comp FPAddImpl : FPAdd {
 // Implementation here
}

comp FPAddImpl2 : FPAdd { ... }

comp main <'G: 1> (...) -> (...) {
   fpadd := FPAddImpl[E, M]<'G>(X, Y);
   fpadd2 := FPAddImpl2[E, M]<'G>(X, Y);
}

[rachitnigam]

Yeah, I think this machinery makes perfect sense! However, I think the original motivation that @gabizon103 was describing was in order to allow components to take other components as arguments. This would somewhat complicate the story because you would either need to explicitly mention all the interfaces that a particular module implements or implement traits.

Consider for example us defining three interface:

interface CombAdd(...);
interface SeqAdd(...);
interface PipeAdd(...);

comp FourCyclePipeAdder<'G:2>: SeqAdd + PipeAdd

comp mac[Add: SeqAdd](...);
comp pipeMac[Add: PipeAdd](...) where delay(Add::'G) <= 2;

In this case, we want to specify that:

1. FourCyclePipeAdder implements both interfaces
2. We want to constraint the delay of the input module
3. We also want to say that anything is pipelined is necessarily also a sequential module

Making sure that the proposal can eventually support all of these combinations is going to be important.