Michael Blume (dudley_doright) wrote,
Michael Blume

Transformations of brainfuck programs

A brainfuck program is any string of characters in which the square brackets match. That is, you could walk the string, pushing addresses of left brackets to a stack, popping when you encounter right brackets, never encounter a stack underflow, and end with an empty stack.

A brainfuck program represents a transformation between strings (slightly complicated by the fact that some don't terminate. This can, of course, not always be programmatically determined in advance.)

Two brainfuck programs will be considered equivalent if they represent the same transformation between strings.

Any character not in the set "<>+-[].," can be removed from a brainfuck program.

If a brainfuck program ends with any character not in "].", that character can be removed.

If a brainfuck program ends with a ']', and there are no '.'s between it and the matching '[', the entire postfix (including both brackets) may be removed.

Any of "<>" "><" "+-" "-+" can be removed.

Once these rules are applied, nothing commutes nontrivially. That is, angle brackets commute with eachother, but adjacent opposite angle brackets should already be removed, and the commutation of '<' with '<' is pretty trivial =P. Same applies to '+' and '-'

That's all I've got. Any other easy simplifications of brainfuck programs that preserve behavior?
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded