search

0xPolygonMiden / miden-vm

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

Consider refactoring the semantics of `DYN` operation #1091

Open bobbinth opened 1 year ago

bobbinth commented 1 year ago

Support for dynamic procedure invocation was added in #1055. Currently, this works as follows: to invoke a dynamic procedure we get the MAST root of the procedure from the top of the stack. However, as discussed in https://github.com/0xPolygonMiden/miden-vm/pull/1078#discussion_r1340907960, this results in an inconvenience: we can't drop the entire procedure root from the stack at the time DYN operation is executed, and thus, we keep the full procedure root on the stack. This means that the called procedure is responsible for dropping the root from the stack. And in turn, this means that semantics for dynamic and static invocations are different.

One potential solution is described in https://github.com/0xPolygonMiden/miden-vm/pull/1078#discussion_r1343335121. Basically, we change the semantics of the DYN operation to work as follows:

Inputs:  [proc_ptr, ...]
Outputs: [...]

Basically, when DYN operation is executed, we'd read the procedure hash from memory locations specified by proc_ptr (instead of getting it from the top of the stack), and then drop the pointer from the stack. Thus, by the time we start executing procedure code, the stack would be "clean" from the procedure's standpoint. This would make invocation semantics between static and dynamic calls the same.

Or, at least almost the same. There is one thing that will remain different: the number of stack slots which can be used for parameters for call instructions. Specifically, for regular call instruction, we would still be able to pass 16 field elements to the callee. However, for dyncall, we'd only be able to pass 15 as 1 element would be taken up by the procedure pointer.

Fumuran commented 1 week ago

The same problem occurred during the implementation of foreign procedure invocation (https://github.com/0xPolygonMiden/miden-base/issues/847): foreign procedures should be invoked using dyncall which require to handle the procedure hash on the top of the stack.