Brainfuck V2 implementations are broken

rdebath commented 7 years ago

Many by https://github.com/kostya/benchmarks/commit/387b17d0c84cacb8e20d9f29a4fcb8b1d778f247

The condition should be testing for zero or non-zero not greater than.

This "Hello World!" contains a relevent test case.

>++++++++[-<+++++++++>]<.>[][<-]>+>-[+]++>++>+++[>[->+++<<+++>]<<]>-----.
>->+++..+++.>-.<<+[>[+>+]>>]<--------------.>>.+++.------.--------.>+.>+.

NB: Some languages use an unsigned byte value which would make the two condition types equivalent.

kostya commented 7 years ago

it was like that, but i change it in https://github.com/kostya/benchmarks/issues/112

rdebath commented 7 years ago

Ah, you were confused by the BOTTLES.BF implementation on the esolang archive. If you look at the report below you see there are nineteen significant "underflows", this usually means that the program is assuming that the interpreter uses 8-bit wrapping cells.

As another example, on an 8-bit interpreter this will work:

+[[->]-[-<]>-]>.>>>>.<<<<-.>>-.>.<<.>>>>-.[<]>++.>>++.

OTOH, it won't work on a 32bit or unbounded interpreter but this one will.

++++[>+++++<-]>[>[++++++>]++[<]>-]>>>>.<<<--.>>>-.<+.<.>---.<<+++.>>---.<---.

Report from profilebf for BOTTLES.BF

Program size 2633
Final tape contents:
 :   0  48  48   0   0   1   0   0   0
     ^
Tape pointer maximum 8
Range error: value check, underflows: 19
Sequence '[-]' on negative cell: 19
Skipped loops (zero on '['): 49571
Counts:     +: 416627       -: 421394       >: 293932       <: 293932
Counts:     [: 87690        ]: 235928       .: 11849        ,: 0
Total:         1761352

NB: The fact that the 19 [-] sequences account for all the underflows actually means that this will work correctly on any wrapping interpreter given enough time or optimisation.

kostya / benchmarks

Brainfuck V2 implementations are broken #144