Brainfuck Roll

roll.bf

// this file is not valid Brainfuck as Brainfuck has no notion of comments
// and all symbols within comments would be interpreted as commands
// but let's pretend those are comments for the sake of this being readable

// given a stack of values [....,s06,s05,s04,s03,s02,s01,s00,d,n]
// this function rolls the stack `n` times at a depth `d`
// for instance:
//   input:  [5,4,3, 2,1,0, 3,2]
//   output: [5,4,3, 1,0,2]

// while the iteration counter `n` isn't 0, we decrease it by 1 and loop
[-
  // we triplicate `d`, to have two "expandable" copies
  // before this: [...,d,<n>]
  // after this:  [...,d,d,d,n,<0>]
  [->>>+<<<]<[->>>+<<<]>>>[-<+<+<+>>>]>[-<+>]
  
  // we go to the leftmost d, and decrease it by 1:
  // we only need to move the top value of the stack `d-1` times
  // then we loop over it
  <<<<-
  [-
    // we copy the value that's two to our left, so below the original top stack value,
    // past our moving state
    // before this: [..., sn,s0,<d0>,d1,d2,n, 0]
    // after this:  [...,<0>,s0, d0 ,d1,d2,n,sn]
    <<[->>>>>>+<<<<<<]
    
    // then we move all our state one step down
    // before this: [...,<0>,  s0,d0,d1,d2,n,sn]
    // after this:  [..., s0,<d0>,d1,d2, n,0,sn]
    >[-<+>]>[-<+>]>[-<+>]>[-<+>]>[-<+>]<<<<
    
    // we're back on our d0 value, but we've moved all our state one step down the stack
    // bringing the original top value of the stack with us
  ]
  
  // we're done with the first loop! we've successfully buried the top value of the stack at depth `d`
  // now we just need to go back up, and bring all our state with us
  // our memory is now: [...,s0,<0>,d1,d2,n,0,...]
  
  // we go to `d1`, our second copy of the original `d` value, decrease it by 1 (same reason)
  // and we loop
  >-
  [-
    // we do the same thing as the first loop, but the other way around:
    // while that second copy of `d` isn't 0, move things back to the right
    // and move the stack values back to the left
    >>>>[-<<<<<+>>>>>]
    <<[->+<]<[->+<]<[->+<]>
  ]
  
  // we're done! we now just have two zeroes to the left of `d` and `n`
  // we just move them back
  >[-<<+>>]>[-<<+>>]<<
  
  // and now we have buried the top value of the stack and restored the stack shape:
  // we can continue looping on `n`
]
// n is now 0, we're done, clean d on the way back down
<[-]<