AirScript TODOs

As of March 2024:

A few immediate things that we need to finish in AirScript are described in the v0.4 milestone. To cover them in a bit more details:

• Support for variable-length public inputs is super important as without this we cannot describe all Miden VM constraints (these are used for boundary constraints against initial/final stack state and kernel ROM). This change would affect all parts of AirScript: front-end, IR, and back end.
• Support for functions (front-end changes only): while it is possible to live without this, it would make describing constraints way simpler. There is also a half-finished PR for this - though, it's been stale for some time.
• Combine constraints generated by selector expressions is needed as without it, verification of constraint evaluation in the recursive context will likely be prohibitively expensive. This is a front-end change only.

Beyond these, there are some smaller front-end improvements (e.g., #331, #333, #334) which are not super-critical, but also could be very nice to have. There is also a more fundamental improvement of the front-end and IR described here which would be really nice to implement.

Once the above is done, the front-end and the IR for AirScript would be in a very good shape. And the next step would be to put the back-ends in order. This includes:

• Finishing MASM backed as without this we cannot do recursive proof verification. The prototype of this backend has already been implemented, but we still need to finish it, optimize it, and better integrate it into the Miden VM stdlib. Some issues related to this are #335 and #339, but there are probably a few other things which are not yet captures in the issues.
• Update and better test Winterfell back-end.
• Implement Plonky3 backend (this is not yet captures in the issues).

It is also likely that the current GKR+LogUp implementation work will affect some parts of AirScirpt. Specifically, we may need to figure out how to handle the "univeral bus" enabled by GRK (some thoughts from #183) may be relevant here.