Miden assembly style guidelines

[hackaugusto]

The goal of this discussion is to document a preferred style for structuring and commenting code, so that we avoid confusion when reading it.

Documentation

https://0xpolygonmiden.github.io/miden-vm/user_docs/assembly/code_organization.html#comments

Documentation format

Do's

• Short single line with a description of the procedure
• Optinally followed by paragraphs adding additional details to the procedure behavior
• Followed by annotations:
  • First the required stack with Input:
  • Then the result stack with Output:
  • If necessary, additional details about the Inputs
• Followed by an estimation of the cycle count with Cycles:

#! Returns true if `n` is prime, false otherwise.
#!
#! This procedure use algorithm XYZ to decide if the integer at the first position of the stak
#! is a primer number.
#! 
#! Input:  [ n, ...]
#! Output: [ b, ...]
#!
#! <optional explanation of inputs outputs> 
#!
#! Cycles: <x>
proc.is_prime.0
  ...
end

example: account.masm

Dont's:

• A high level description should not be included

#! proc is_prime(n: Felt) -> Bool
#! Returns true if `n` is prime, false otherwise.
proc.is_prime.0 ... end

What calling convention should we adopt for procedures?

Called procedure should consume all of its arguments and only return new computed values at the end, the stack may be empty if the procedure just asserts or save to memory.

Inline documentation

examples

Do's

• When useful, describe the goal of the instructions
• Add comments describe the expected state of the stack after the instructions are executed

# Index in the stack is 0-indexed, convert it to 1-indexed
push.1 add
# => [index, ...]

Dont's

• Add the stack state before instructions, always after, with the expected state after the execution of said instructions

[hackaugusto]

Note: There is another relevant discussion about endianess, that goes over the stack order of elements: #656

[jjcnn]

The question of inline comments documenting the stack just came up in one of my PRs, so I'll just comment on that:

I find the "stack after instruction" really confusing:

# [1, ...]
push.1

There are in essence two types of inline comments:

• What does the code do? These are usually placed before the relevant code. For example:

  // Find the smallest element in the list
  let mut smallest = ...;
  foreach x : list_of_things {
   ...
  }

• What is the current state of the program? A typical example is stating an invariant. These are usuall placed at the point where that state is current, i.e., after the code that creates the state and before the code that changes the state. For example:

  x = y / z + offset;
  // x + y is now equal to n^2 + 42
  y = z + 1;

Stack inline comments fall in the latter category rather than the former, so I think they should be placed at the point at which the stack is what the comment says it is.

[bobbinth]

I tend to agree with this. Though, I usually add comments describing the current state of the stack before instructions. For example:

# [...]
push.1

# [1, ...]
push.2

[bobbinth]

when should we use # versus #!?

There is a brief explanation of this here. One thing that is missing from the explanation is that #! can also be used for module-level comments (when placed at the top of the file). We should probably update the docs to include this.

[hackaugusto]

What I was trying to say in the original comment, is that #! is confusing. Because in rust //! means "documentation of the parent object", and /// means documentation of the next sibling. Here #! means documentation of the next sibling, which changes the meaning of !.

With that said, I don't think we need to follow the rust code style. I was just bringing it up as likely confusing issue to new comers.

Updated the description with a link to the documentation.

[bobbinth]

Regarding the documentation format. I'd prefer a slight variation on the second alternative:

#! Returns true if `n` is prime, false otherwise.
#! 
#! Input:  [ n, ...]
#! Output: [ b, ...]
#!
#! <optional explanation of inputs outputs> 
#!
#! Cycles: <x>

The optional explanation is for cases when the initial short description is not sufficient.

[hackaugusto]

I just realized that if we add a rule on how to group assembly opcodes, for example, opcodes that are not split by a comment are aligned on the same line up to 90 characters. When can write an formatter for MASM (I really like formatter because they save me tons of time while coding :) )

[bobbinth]

Inline comments:

begin
  # comment to explain what the following code block does
  <some instructions here>
  # => [a, b, c, d, ...]
end 

[hackaugusto]

sometimes it is useful to document state for something besides the operator_stack, like the advice map or advice stack. we could expand this syntax to:

# operator_stack => []
# advice_stack => []
# advice_map => {key: value}

wdyt?

[bobbinth]

Yep, I think that works. Two comments:

• I usually call it operand_stack - not operator_stack.
• In cases when nothing is important, I think we can still use just => [...] for the operand stack.

[hackaugusto]

@frisitano I believe you also mentioned that this may be useful for procedures inputs? Or am I misremembering?

Here is one suggestion:

#! Short description
#! 
#! Long paragraph
#! with important details
#! 
#! Inputs:
#!   operand_stack => [A]
#!   advice_stack => [B] 
#! Outputs:  
#!   operand_stack => [C] 
#! 
#! Where:
#!   C = A + B
#! 
#! Cycles: 2
proc.example
   ...
end

[frisitano]

Yes, in some cases we will have inputs from multiple sources - advice_map, advice_stack, etc.

[hackaugusto]

When writing loops I like to add a tag and the expected stack state, for example:

proc.move_even_words_from_tape_to_memory.0
  dup.13 neq.0
  # LOOP: => [b, A, B, C, write_ptr, num_words, ...]

  # while(words>0)
  while.true
    adv_pipe
    # => [A', B', C', write_ptr', num_words, ...]

    # update `num_words` (note: `num_words` is required to be even)
    swapw.3 swap sub.2 swap swapw.3
    # [A', B', C', write_ptr', num_words-2, ...]

    # while(words>0)
    dup.13 neq.0
    # LOOP: => [b, A', B', C', write_ptr', num_words-2, ...]
  end

  movup.13 drop
  # => [A', B', C', write_ptr', ...]
end

I do this because for the next iteration of the loop, the stack state expects the stack position to be the same, that makes it easier to track the values down.

[bobbinth]

Yep - agreed. That would be helpful too.

[hackaugusto]

As documentation, it was decided a while ago to not use high-level like syntax to describe the procedure signature #668 (comment)

[hackaugusto]

on cycle counting

when counting cycles of a long procedure, it is useful to have intermediary values to add later, so one strategy that I use is to add a (x cycles) comment, e.g.:

miden-vm/stdlib/asm/crypto/hashes/native.masm

Lines 34 to 36 in 2690d5c

	# figure out if the range is for an odd number of words (9 cycles)
	dup.1 dup.1 sub is_odd
	# stack: [is_odd, start_addr, end_addr, ...]

[hackaugusto]

One notation that can be useful when using swapw.<x> is to wrap a sequence of elements in a bracket:

instead of:

# => [a, b, c, d, e, f, g, h, i, j, k, l, m, n, ...]
swapw.2
# => [i, j, k, l, a, b, c, d, e, f, g, h, m, n, ...]

becomes:

# => [[a, b, c, d], [e, f, g, h], [i, j, k, l], m, n, ...]
swapw.2
# => [[h, i, j, k], [a, b, c, d], [e, f, g, l], m, n, ...]

I actually made a mistake when doing the first example, that was obvious when writing the counter-example below, this can be super useful to check things at a glance.

The downside of this is that when we have words in the stack, for example:

# => [a, b, W, g, h ...]
swapw

I'm not sure how to have a good notation for the case above.

[hackaugusto]

When writing code that reads from the advice stack, we have to remember to validate the data. It can be useful to have notation to mark unverified values, e.g.:

adv.u64div
=> [#quot_high, #quot_low, #rem_high, #rem_low, ...]

[hackaugusto]

Some procedures also have failure conditions, e.g. division by zero. This should be documented. To follow the existing format it makes sense to have something like:

## Divides the top two stack elements and pushes the result to the stack.
##
## Input: [a, b, ...]
## Output: [c, ...]
## Where:
## - c = floor(b / a)
## Fails:
## - if $a=0$
## Cycles: XX

[bobbinth]

Makes sense! A couple of nits:

• the format we use for doc comments is #!.
• I think it would be good to add some blank lines for readability. I'd probably format it as follows

#! Divides the top two stack elements and pushes the result to the stack.
#!
#! Input:  [a, b, ...]
#! Output: [c, ...]
#!
#! Where:
#! - c = floor(b / a)
#!
#! Fails:
#! - if $a=0$
#!
#! Cycles: XX