Talk:Total BF
Please remove this page, Total BF would get too complex. --Tailcalled 10:34, 21 January 2012 (UTC)
- How do you mean it would get too complex? Moreover, we should consider whether there's any value in keeping it in case somebody wants to develop the idea. See also this discussion a while back. — Smjg (talk) 13:30, 21 January 2012 (UTC)
- Well, effect systems are complex. But sure, keep it if you want, but I doubt anyone will develop it further. --Tailcalled 13:44, 21 January 2012 (UTC)
I'm really not familiar with effect systems (and I don't really understand the notation used in the article), but a possibility to assert that every program will terminate is to replace brainfuck's "while" loops with some kind of "for" loops, for instance:
| Instruction | Description |
|---|---|
> < + - . , |
Regular brainfuck instructions. |
[ |
If the current cell holds 0, jump to the instruction after the matching ]. Otherwise, add the current address and content of the current cell to the "call stack".
|
] |
Set the pointer to the address stored in the call stack, decrement the value stored in the call stack, then set the (new) current cell to that value. If the current cell is zero, pop the call stack. Otherwise, jump to the instruction after the matching [.
|
Basically, this corrects for unbalanced > and < inside a loop (that is, the current cell at the beginning of all iterations of a given loop is always the same), and makes sure the loop stops after exactly n iterations, where n is the content of the current cell the first time the loop was entered. The call stack contains couples (address of the current cell, value of the current cell), and at the end of every iteration, the value is decremented by one, and the current cell is set to the address and value from the call stack.
For instance the loop [>>+] in that language (let's call it "countdown brainfuck" or something) would be equivalent to the loop [>>+<<-] in regular brainfuck, the countdown brainfuck loop [+.] would be equivalent to the brainfuck loop [+.--]. Loops storing input in the current cell cannot directly be translated to regular brainfuck (because it is not known before runtime how much correction is needed to the counter cell), but for instance the following programs are equivalent:
| countdown brainfuck | regular brainfuck | C |
|---|---|---|
++++++++++[,.] |
++++++++++[>,.<-] |
for (i = 10; i > 0; i--) {putchar(getchar());}
|
Note however that the last char from input will still be in the memory tape in the brainfuck program, whereas it will have been replaced by a 0 in the countdown brainfuck program (because the same cell was used for input and for the loop counter). --Koen (talk) 22:07, 8 October 2012 (UTC)
- If you want to ensure that the program halts, it's enough to just make sure the loop is iterated the number of times given by the original cell value. That should restrict the computations to at most primitive recursive functions, while still allowing algorithms that move to runtime-decided positions on the tape. Although if cell values are bounded, it might still restrict too much for computing many things. If they are unbounded, your scheme in general needs to exclude negative values... --Ørjan (talk) 00:31, 9 October 2012 (UTC)