They used a fixed size transformer, where the vocab determines the functions and input/output range. So unless the model needs more 'memory' for your class of expression there wouldn't necessarily be a big change in performance. They have experiments in the paper with bigger/smaller vocabs.

There's not any execution of the functions occurring here. It's modeled as a sequence-to-sequence problem where the training sequences have been pre-computed programmatically.

I think in this case the attention operation bounds the runtime by the longest possible sequence that can go in at once. Since you have a positional embedding, you can add arbitrarily many more functions without incurring a runtime penalty, although it may begin to interfere with the model's ability to effectively generalize as well, particularly when used with very long sequence lengths (so chains of operations, lists of ints).

Since each operation is mapped to an integer, the maximum number of tokens is bound by the precision of the system.