0xPolygonMiden / miden-vm

STARK-based virtual machine
MIT License
621 stars 158 forks source link

Allow repeat opcode to be set programmatically #1324

Open partylikeits1983 opened 5 months ago

partylikeits1983 commented 5 months ago

Feature description

Currently the repeat opcode in miden assembly requires the developer to specify the number of loop iterations:

repeat.5
    # 5 loop iterations
end

However, it would be extremely useful to allow the number of loop iterations to be set programmatically. For example:

push.5
repeat
     # 5 loop iterations
end

Why is this feature needed?

I know that there is a while opcode where a similar functionality could be achieved, however, allowing the repeat opcode to be set programmatically would be useful.

bobbinth commented 5 months ago

Interesting! I think what will need to happen is that the assembler will need to transform this into a while loop under the hood. Not sure yet how easy it would be.

bitwalker commented 3 months ago

The assembler could track the operand stack state in abstract (like we do in the compiler), and transform a runtime-bounded repeat like this to a while.true predicated on the current iteration count. This is more or less how something like for i in items.len() { .. } gets translated by the compiler anyway. Doable in the assembler, but not sure if the benefits outweigh the costs in terms of implementation complexity.

Somewhat related, but at some point I'd like to sit down and analyze whether it is feasible to represent something like goto-with-labels in a MAST-like structure (i.e. MAST, but maybe with some new/modified primitives). With that we could allow a much richer set of control primitives to be represented. I'm convinced it has to be possible, but until then, we unfortunately have to find clever ways to represent the control flow we want using the current set of primitives.

bobbinth commented 3 months ago

Somewhat related, but at some point I'd like to sit down and analyze whether it is feasible to represent something like goto-with-labels in a MAST-like structure (i.e. MAST, but maybe with some new/modified primitives). With that we could allow a much richer set of control primitives to be represented. I'm convinced it has to be possible, but until then, we unfortunately have to find clever ways to represent the control flow we want using the current set of primitives.

519 is something similar to this. I am not sure this is possible in MAST - but I also didn't think Dyn blocks were possible originally :)