#!/usr/bin/env swipl
% Basic Brainf**k interpreter in Prolog with non-determinism
% (With thanks to Florian for the free idea!)

:- use_module(library(clpfd)).
:- use_module(library(apply)).
:- use_module(library(dif)).
:- use_module(library(readutil), [read_file_to_string/3]).
:- use_module(library(main), [main/0]).
:- initialization(main, main).

interpret([], S, S).
interpret(['+'|Rest], s(C, L, R, S), St)     :- N #= (C + 1) mod 256, interpret(Rest, s(N, L, R, S), St).
interpret(['-'|Rest], s(C, L, R, S), St)     :- N #= (C - 1) mod 256, interpret(Rest, s(N, L, R, S), St).
interpret(['.'|Rest], s(C, L, R, S), St)     :- put_code(C), interpret(Rest, s(C, L, R, S), St).
interpret([','|Rest], s(_, L, R, S), St)     :- get_code(I), interpret(Rest, s(I, L, R, S), St).
interpret(['<'|Rest], s(C, [],    R, S), St) :- interpret(Rest, s(0, [], [C|R], S), St).
interpret(['<'|Rest], s(C, [N|L], R, S), St) :- interpret(Rest, s(N, L, [C|R], S), St).
interpret(['>'|Rest], s(C, L, [],    S), St) :- interpret(Rest, s(0, [C|L], [], S), St).
interpret(['>'|Rest], s(C, L, [N|R], S), St) :- interpret(Rest, s(N, [C|L], R, S), St).
interpret(['['|Prog], s(0, L, R, S), St) :-
    after_loop(Prog, Rest, 0), interpret(Rest, s(0, L, R, S), St).
interpret(Prog, s(C, L, R, S), St) :-
    C \= 0, Prog = ['['|Rest], interpret(Rest, s(C, L, R, [Prog|S]), St).
interpret([']'|_], s(C, L, R, [H|S]), St) :- interpret(H, s(C, L, R, S), St).
interpret(['!'|Rest], s(_, L, R, S), St) :-
    interpret(Rest, s(0, L, R, S), St);
    interpret(Rest, s(1, L, R, S), St).
interpret([X|Rest], St0, St1) :-
    maplist(dif(X), ['+', '-', '.', ', c', '[', ']', '<', '>', '!']),
    interpret(Rest, St0, St1).

interpret(Text, Out) :-
    string_chars(Text, Prog),
    interpret(Prog, s(0, [], [], []), Out).
interpret(Text) :- interpret(Text, _).

% utility predicate to jump over an unexecuted loop
after_loop([']'|Rest], Rest, 0).
after_loop([']'|Prog], Rest, N) :- N > 0, N0 is N - 1, after_loop(Prog, Rest, N0).
after_loop(['['|Prog], Rest, N) :-        N0 is N + 1, after_loop(Prog, Rest, N0).
after_loop([C|Prog],   Rest, N) :- maplist(dif(C), ['[', ']']), after_loop(Prog, Rest, N).

main([File]) :-			%https://www.swi-prolog.org/pldoc/man?section=plscript
   read_file_to_string(File, Contents, [expand(true)]),
   string_chars(Contents, Text),
   interpret(Text).