1

I have written by own BF Interpreter in Assembly, and now I'm writing a BF Compiler in Java that compiles to Assembly code.

I wanted to implement a little nice feature that detected if the array of memory cells was out of bounds. A traditional limitation for the array is to let the index be in [0, 30000), otherwise [0, inf) is also commonly used. Another option is that memory is wrapped around, so in the first case it could mean that accessing index 30000 means accessing index 0.

In my compiler this detection would be done at the Semantic Analysis phase of a traditional compiler, so we have already obtained our AST (Abstract Syntax Tree) from the Syntax Analysis phase.

After trying to come up with a construct for this for a while I have found Detecting infinite loop in brainfuck program, together with BF's Wikipedia page I have found out that a BF program with as memory array [0, inf) resembles a Turing Machine.

So my question is, for both the [0, max) and [0, inf) cases, is it possible to detect if the memory pointer goes below zero, and in the former case below max? Obviously without ending up in an infinite loop while checking it, and I'd rather avoid setting a maximum execution time as well.

Bonus question: Is it possible to detect the amount of times a loop construct [...] loops?

Zoe
  • 27,060
  • 21
  • 118
  • 148
skiwi
  • 66,971
  • 31
  • 131
  • 216
  • 2
    I don't know brainfuck, but if you want to detect this at compile time, I think it's impossible in some cases (equivalent to the halting problem). – alain Nov 17 '16 at 17:12
  • @IraBaxter I didn't want to talk down the importance of static analysis (In fact I think it's a challenging and very interesting field), I just was not sure if skiwi was aware of the limitation. Now that I've read the question he linked, it looks like he was. – alain Nov 18 '16 at 12:34
  • @alain: Er, in retrospect, I wasn't aiming the comment at you, I should have left the @ blank :-} I was just driving in the nail you started :-} – Ira Baxter Nov 18 '16 at 14:44

1 Answers1

3

BF is Turing capable. If you use it to compute an index, then you cannot determine in general if the index has a specific value (e.g., 30001) because of the halting problem. So in general, you cannot detect an out of bound access. However, you may be able to detect this for many individual programs; this is why static analyzers are built and used in spite of being theoretically useless.

Regarding loop trip count: The loop construct operates based on whether a variable happens to be zero or not. BF being Turing capable means that in general you can't know if a variable is zero or not at any particular point. The implications are that you can't know the number of times that a loop construct works. Again, you may be able to figure this out for many individual programs.

For some programs with simple cases, you might be able to implement your checks easily. In general, doing these kind of static analyses take rather a lot of machinery.

Ira Baxter
  • 93,541
  • 22
  • 172
  • 341