Problem

Circom functions do not have a type specified and can be used at multiple call sites that require it to have a different effective type signature, as long as the operations within are valid for that signature. The Circom C witness generator ends up creating multiple concrete versions of a function as needed per each call site.

Example 1

function f(a) {
    return a[0][0];
}

template CallRetTest() {
    signal input inA[10][5][5];
    signal input inB[10][5];
    signal output outA[5];
    signal output outB;

    outA <== f(inA); // f: (felt[10][5][5]) -> felt[5]
    outB <== f(inB); // f: (felt[10][5]) -> felt
}

component main = CallRetTest();

Description

There are 2 concrete versions of this function, per the 2 call sites that use different input types.

Possible Solution 1

Do an initial scan of the circom program for function call sites to determine the necessary type signature for each call site and generate as many versions of the function as needed.

Example 2

function f(a) {
    return a[0][0];
}

template CallRetTest(N) {
    signal input inA[8][5][N];
    signal input inB[8][N];
    signal output outA[N];
    signal output outB;

    outA <== f(inA); // f: (felt[8][5][N]) -> felt[N]
    outB <== f(inB); // f: (felt[8][N]) -> felt
}

template Main() {
    signal input inA[8][5][3];
    signal input inB[8][3];
    signal input inC[8][5][2];
    signal input inD[8][2];
    
    signal output outA[3];
    signal output outB;
    signal output outC[2];
    signal output outD;

    component crt1 = CallRetTest(3);
    crt1.inA <== inA;
    crt1.inB <== inB;
    outA <== crt1.outA;
    outB <== crt1.outB;
    component crt2 = CallRetTest(2);
    crt2.inA <== inC;
    crt2.inB <== inD;
    outC <== crt2.outA;
    outD <== crt2.outB;
}

component main = Main();

Description

There are 4 concrete versions of this function (per the 2 call sites and 2 values of N). Creating all concrete instantiations of the function requires also instantiating CallRetTest which we would like to avoid in the circom-to-llzk frontend.

Possible Solution 2A

Add support for templated functions to LLZK. The naive approach would be to add parameter to the function.def op in the same way struct.def supports them. There are two downsides:

1. We would have to reimplement parse/print for function.def. Currently, they use MLIR helper functions since the format is identical to the core func.func op:

   https://github.com/Veridise/llzk-lib/blob/4df8040662d37209ea3482e5430f5fd3ab3dc0c7/lib/Dialect/Function/IR/Ops.cpp#L95-L111

2. The current approach in struct.def is already a bit awkward because it defines pseudo-symbols that are outside of the normal MLIR Symbol and SymbolTable structure. This makes a few things awkward and requires special handling in many locations:

   https://github.com/Veridise/llzk-lib/blob/4df8040662d37209ea3482e5430f5fd3ab3dc0c7/include/llzk/Dialect/Struct/IR/Ops.td#L76-L80

We can avoid both of these downsides by adding two new ops to the LLZK Polymorphic dialect to define a template region to contain the function.def and its named parameters:

def LLZK_TemplateOp
    : PolymorphicDialectOp<
          "template", [HasParent<"::mlir::ModuleOp">, Symbol, SymbolTable,
                  IsolatedFromAbove, NoRegionArguments]#GraphRegionNoTerminator.traits> {
  let arguments = (ins SymbolNameAttr:$sym_name);
  let regions = (region SizedRegion<1>:$bodyRegion);
  let assemblyFormat = [{ $sym_name $bodyRegion attr-dict }];
}

def LLZK_TemplateParamOp
    : PolymorphicDialectOp<
          "param", [HasParent<"::llzk::polymorphic::TemplateOp">, Symbol]> {
  let arguments = (ins SymbolNameAttr:$sym_name);
  let assemblyFormat = [{ $sym_name attr-dict }];
}

This would allow the following LLZK IR: