brainfack interpreter implemented in prolog

brainfuck.prolog

%! ptr(-Ptr).
% return initial pointer Ptr. Next represents a byte stream of all zeros.
% Ptr is a form: (Prev, Cur, Next).
ptr(([], 0, X)) :- X = [0|X].

%! next_ptr(?Ptr, ?NextPtr)
% It means NextPtr is next point of Ptr.
% In the other hand, it means Ptr is previous point of NextPtr.
next_ptr((Prev, Cur, [X|Next]), ([Cur|Prev], X, Next)).

%! ptr_value(+Ptr, ?X, ?NewPtr)
% NewPtr is same as Ptr, but that has new value X.
ptr_value((Prev, _, Next), X, (Prev, X, Next)).

incr_ptr(Ptr, N, Ptr1) :-
    ptr_value(_, X, Ptr),
    X1 is X + N,
    ptr_value(Ptr, X1, Ptr1).

%! block(+Code, -Block, -Rest).
block([], [], []).
block([']'|Code], [], Code) :- !.
block(['['|Code], Block, Rest) :- !,
    block(Code, Block1, Rest1),
    block(Rest1, RestBlock, Rest),
    append(['['|Block1], [']'|RestBlock], Block).
block([X|Code], [X|Block], Rest) :- block(Code, Block, Rest).


%! bf(+CP -> -CP1)
bf((['>'|Code], Ptr) -> (Code, Ptr1)) :- !, next_ptr(Ptr, Ptr1).
bf((['<'|Code], Ptr) -> (Code, Ptr1)) :- !, next_ptr(Ptr1, Ptr).
bf((['+'|Code], Ptr) -> (Code, Ptr1)) :- !, incr_ptr(Ptr, 1, Ptr1).
bf((['-'|Code], Ptr) -> (Code, Ptr1)) :- !, incr_ptr(Ptr, -1, Ptr1).
bf((['.'|Code], Ptr) -> (Code, Ptr))  :- !, ptr_value(_, X, Ptr), put_code(X).
bf(([','|Code], Ptr) -> (Code, Ptr1)) :- !, get_code(X), ptr_value(Ptr, X, Ptr1).

bf((['['|Code], Ptr) -> (Rest, Ptr)) :-
    ptr_value(_, 0, Ptr), !,
    block(Code, _, Rest).
bf((['['|Code], Ptr) -> (Code1, Ptr)) :-
    !, 
    block(Code, Block, _),
    append(Block, ['['|Code], Code1).

bf(([_|Code], Ptr) -> (Code, Ptr)).

%! bf_all(+CP)
% Apply all transformation starts with CP.
bf_all(([], _)).
bf_all(CP) :- bf(CP -> CP1), bf_all(CP1).

%! bf(+CPi, -CP -> -CP1) is nondet
% Query CP -> CP1 transformation that starts with initial value CPi.
bf(([], P), ([], P) -> nil).
bf(CPi, CPi -> CPi1) :- bf(CPi -> CPi1).
bf(CPi, CP -> CP1) :- bf(CPi -> CPi1), bf(CPi1, CP -> CP1).


tokenize(Str, Code) :- atom_chars(Str, Code).

brainfack(Code) :-
    is_list(Code), !,
    ptr(Ptr), bf_all((Code, Ptr)).
brainfack(X) :-
    atom(X), !,
    tokenize(X, Code), brainfack(Code).

hello(Code) :-
    Str = '+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.',
    tokenize(Str, Code).

% :- hello(C), brainfack(C), fail.
% :- hello(C), ptr(P), bf((C, P), CP -> CP1).