Turing Repeat Machine

(This post assumes some introdutory knowledge about Prolog)

TL;DR: When programming in Prolog, take care with the predicate declaration order!

Context

I’m having a discipline called Theory of Computation (Teoria da Computação), where we study the limits of computability and complexity using Turing Machines.

The teacher provided us a Turing Machine emulator, but it is written in Java, and has a Java GUI. Currently, I am using Termux to work, and it cannot run that kind of programs. So, I thought that I could write my own Turing Machine emulator. And I decided to do just that, and picked Prolog to do it, because it seemed to fit the problem nicely.

So, in a weekend I got a prototype running, and some days after that I already have a mode of running a Turing Machine in a “stepping execution” mode, showing all the state transitions.

The code is currently available on both GitLab and GitHub.

The bug

However, sometimes the state appeared twice, but I never confirmed it, until one day I was experimenting with an edge case, and could reliably cause the double state showing up.

The relevant part of the code:

step(StateN, TapesLN, TapesRN, N, TapesLF, TapesRF) :-
    tapes_heads(TapesRN, Ins, TapesRest),
    ( rule(StateN, Ins, StateM, Outs, Movs)
      ; format("ABORTED: No rule found for state '~w', inputs '~w'~n",
        [StateN, Ins]), !, fail
    ),
    tapes_heads(TapesRMod, Outs, TapesRest),
    show_machine_state(N, StateN, StateM, Ins, Outs, Movs, TapesLN, TapesRMod),
    tapes_movimentations(Movs, TapesLN, TapesRMod, TapesLM, TapesRM),
    M is N+1, get_char(_),
    step(StateM, TapesLM, TapesRM, M, TapesLF, TapesRF).

This predicate (step/6) represents one step of the Turing Machine execution:

• Get the heads input (tapes_heads/3, second line)
• Search for a rule matching the current state and inputs (or abort execution if none find) (rule/5, line 3 to 5)
• Write the output to the heads (tapes_heads/3, sixth line)
• Move tapes (tapes_movimentations/5, eight line)
• Execute the next step with the new state and tapes (last line)

Between writing the output to the tapes and moving them, I showed the current state of the machine using show_machine_state/8.

Using that edge case, I started to trace the execution of the predicates. Basically, what was happenning was that tapes_movimentations/5 was failing, and the Prolog interpreter was backtracking until somewhere in the second tapes_heads/3, and then it found a new unification that was successful, and continued execution – but that caused show_machine_state/6 to be run again.

The kicker is that tapes_heads/3 is a fairly simple predicate: it is applying the predicate tape_head/3 to multiple lists. tape_head is defined as two facts:

tape_head([],    null, []).
tape_head([H|T], H,     T).

So, there are only two possibilities:

• The tape is empty, and trying to read the first symbol results in the null symbol
• The tape is not empty, and the first symbol is the first atom of the list.

Due to the reversible nature of Prolog predicates, I also used this predicate to write back to the tapes, by instanciating the second and third arguments, and getting back the first list.

The bug was in this second use of the predicate. When the symbol to write was null, and the rest of the tape is empty ([]), both predicates may apply, and they give different results: the first fact returns the empty list, the second a list with the null symbol (i.e. [null]).

The “correct” answer is the second one, because the predicate tapes_movimentations/5 assumes that the list has at least 1 symbol, even if it is null.

So, what was really happening was:

• tapes_heads/3 tries to write the null symbol, in the end of the tape
• tape_head/3 gives back an empty list
• show_machine_state/8 executes
• tapes_movimentations/6 fails, because it was not expecting an empty list
• Prolog begins backtracking
• This time, tape_head/3 gives a list with 1 element: [null]
• show_machine_state/8 executes again
• tapes_movimentations/6 is happy, and everything else goes just fine

The fix

As everything in Prolog, the solution is simple: if I just change the order of the predicates, then tape_head/3 will “return” a not-empty list, and then falling back to an empty list in case that fails for whatever reason.

tape_head([H|T], H,     T).
tape_head([],    null, []).

However, that was not the only mistake at play here: if the order of the predicates of step/5 was a little different:

step(StateN, TapesLN, TapesRN, N, TapesLF, TapesRF) :-
    tapes_heads(TapesRN, Ins, TapesRest),
    ( rule(StateN, Ins, StateM, Outs, Movs)
      ; format("ABORTED: No rule found for state '~w', inputs '~w'~n",
        [StateN, Ins]), !, fail
    ),
    tapes_heads(TapesRMod, Outs, TapesRest),
    tapes_movimentations(Movs, TapesLN, TapesRMod, TapesLM, TapesRM),
    show_machine_state(N, StateN, StateM, Ins, Outs, Movs, TapesLN, TapesRMod),
    M is N+1, get_char(_),
    step(StateM, TapesLM, TapesRM, M, TapesLF, TapesRF).

then this type of bug would not happen. The difference is that the predicate show_machine_state/8 was put more towards the end. The rationale is that, this predicate having side effects¹, it should only be “executed” after we are confident that backtracking will not be needed.