GOTO instruction in Brainf***

Question

There is an extended version of bf which has a goto instruction, ?.

I know that, in theory, it should be possible to simulate a goto in the classic 8 instruction version of bf. How can I do that in practice? Is there an existing bf goto pattern or algorithm? Is there a way to transform a goto ? instruction into a version of bf without goto ? instruction?

Answer 1

There are no easy or trivial ways to do this that I know of. This is one of the main challenges in compiling a language into Brainfuck.

It is of course possible in theory, as you said, but it requires you to structure your code in a very disciplined manner by implementing a stack or heap or some similar data structure.

The project C2BF is a partial compiler from C to Brainfuck that does exactly this. It emulates a stack by interpreting the Brainfuck cells into a repeating pattern of five, namely,

1) Stack
2) Heap
3) Stack location marker / top marker
4) Walk
5) Carry

If you are interested in more specific implementation details of doing this sort of thing, you might be interested in looking at this description for BrainFix, which describes more fully how to do simple flow and memory control.

Answer 2

The only way I can think of, is by using a brainfuck interpreter written in brainfuck to run the program (like dbfi). With some modifications you can add new instructions such as LBL and GOTO.

The only problem is that it will be very slow. Another problem is that you will have to store the actual brainfuck program on the memory tape (easiest way of doing that is by inputting the program, just as dbfi does). For a more 'clean' way of doing it you will have to make a brainfuck program that will put the actual program on the memory tape, in such a way that the interpreter can read and run it.

It is of course not a very elegant method, but I think it actually might work pretty well, though it certainly will be very slow.

Answer 3

Actually it isn't that complex. The pseudo code you want to make is this:

goflg := 1
while goflg do begin

  // repeat this for each section
  if goflg <> 0 then begin
    goflg := goflg - 1
  end else begin
    // run your code in here and at the end
    // set goflg to get to the section you want next.
  end
  // to here

  // repeat this for each section
  if goflg <> 0 then begin
    goflg := goflg - 1
  end else begin
    // run your code in here and at the end
    // set goflg to get to the section you want next.
  end
  // to here


end

You'll have to add a flag to do the ELSE part and another if you want to do the IF part without a copy but it's quite doable.