Brain F**k

brainf__k.ex

defmodule Brain do
  def fetch({_, [h | _]}), do: h

  def store({t0, [_ | t]}, h), do: {t0, [h | t]}

  def forward({t0, [h | t]}), do: {[h | t0], t}

  def reverse({[h | t0], t}), do: {t0, [h | t]}

  def forward_inf({t, [h0]}, h), do: {[h0 | t], [h]}
  def forward_inf(t, _), do: forward(t)

  def forward(t0, h) do
    t = forward(t0)

    case fetch(t) do
      ^h -> t
      _ -> forward(t, h)
    end
  end

  def reverse(t0, h) do
    t = reverse(t0)

    case fetch(t) do
      ^h -> t
      _ -> reverse(t, h)
    end
  end

  @max_ops 1_000_000_000

  def f__k(code), do: f__k({[], code}, {[], [0]}, 0)

  def f__k({code, []}, data, ops), do: {:ok, {code, []}, data, ops}

  def f__k(code, data, ops) when ops == @max_ops, do: {:error, code, data, ops}

  def f__k(code, data, ops) do
    {code, data} = f__k_(fetch(code), code, data)
    f__k(code, data, ops + 1)
  end

  defp f__k_(?<, code, data), do: {forward(code), reverse(data)}
  defp f__k_(?>, code, data), do: {forward(code), forward_inf(data, 0)}

  defp f__k_(?[, code, data) do
    {case fetch(data) do
       0 -> forward(code, ?])
            |> forward()
       _ -> forward(code)
     end, data}
  end

  defp f__k_(?], code, data) do
    {case fetch(data) do
       0 -> forward(code)
       _ -> reverse(code, ?[)
     end, data}
  end

  defp f__k_(?+, code, data) do
    {forward(code),
     store(
       data,
       case fetch(data) do
         255 -> 0
         xx -> xx + 1
       end
     )}
  end

  defp f__k_(?-, code, data) do
    {forward(code),
     store(
       data,
       case fetch(data) do
         0 -> 255
         xx -> xx - 1
       end
     )}
  end

  defp f__k_(?., code, data) do
    :ok =
      [fetch(data)]
      |> to_string()
      |> IO.write()

    {forward(code), data}
  end

  defp f__k_(?,, code, data) do
    [xx] =
      IO.read(1)
      |> to_charlist()

    {forward(code), store(data, xx)}
  end

  defp f__k_(_, code, data), do: {forward(code), data}
end

[n, m] =
  IO.read(:line)
  |> String.trim()
  |> String.split(" ")
  |> Enum.map(&String.to_integer/1)

input = IO.read(n)
"$\n" = IO.read(:line)

code =
  Enum.take(IO.stream(:stdio, :line), m)
  |> Enum.join("")
  |> to_charlist()

ExUnit.CaptureIO.capture_io(input, fn ->
  case Brain.f__k(code) do
    {:error, _, _, _} -> IO.puts("\nPROCESS TIME OUT. KILLED!!!")
    _ ->
  end
end)
|> IO.puts()

brainf__k.pl

brainf__k(I) :-
    brainf__k(I, _, _).

brainf__k(I, F, X) :-
    brainf__k(([]-I)-([]-[0]), F, 0, X).

brainf__k((I-[])-D, (I-[])-D, X, X) :-
    !.
brainf__k(I0-D0, I-D, X0, X) :-
    fetch(I0, H),
    brainf__k_(H, I0-D0, I1-D1),
    succ(X0, X1),
    (   X1 =:= 1 000 000
    ->  throw(error)
    ;   true
    ),
    brainf__k(I1-D1, I-D, X1, X).

brainf__k_(0'>, I0-D0, I-D) :-
    !,
    inc_inf_ptr(D0, D),
    inc_ptr(I0, I).
brainf__k_(0'<, I0-D0, I-D) :-
    !,
    dec_ptr(D0, D),
    inc_ptr(I0, I).
brainf__k_(0'], I0-D, I-D) :-
    !,
    (   fetch(D, 0)
    ->  inc_ptr(I0, I)
    ;   rewind(I0, 0'[, I)
    ).
brainf__k_(0'[, I0-D, I-D) :-
    !,
    (   fetch(D, 0)
    ->  fast_forward(I0, 0'], I)
    ;   inc_ptr(I0, I)
    ).
brainf__k_(0'+, I0-(D0-[X0|D]), I-(D0-[X|D])) :-
    !,
    (   X0 =:= 255
    ->  X = 0
    ;   succ(X0, X)
    ),
    inc_ptr(I0, I).
brainf__k_(0'-, I0-(D0-[X0|D]), I-(D0-[X|D])) :-
    !,
    (   X0 =:= 0
    ->  X = 255
    ;   succ(X, X0)
    ),
    inc_ptr(I0, I).
brainf__k_(0'., I0-(D0-[X|D]), I-(D0-[X|D])) :-
    !,
    put_code(X),
    inc_ptr(I0, I).
brainf__k_(_, I0-D, I-D) :-
    inc_ptr(I0, I).

rewind(I0, H, I) :-
    dec_ptr(I0, I1),
    rewind_(I1, H, I).

rewind_(I, H, I) :- fetch(I, H), !.
rewind_(I0, H, I) :- rewind(I0, H, I).

fast_forward(I0, H, I) :-
    inc_ptr(I0, I1),
    fast_forward_(I1, H, I).

fast_forward_(I, H, I) :- fetch(I, H), !.
fast_forward_(I0, H, I) :- fast_forward(I0, H, I).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

This is the starting point: build some primitives for manipulating and
querying a list-represented storage mechanism that behaves like a tape.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

fetch(_-[H|_], H).

store(T0-[_|T], H, T0-[H|T]).

inc_ptr(T0-[H|T], [H|T0]-T).

dec_ptr([H|T0]-T, T0-[H|T]).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

This is how the infinite data memory store manifests itself.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

inc_inf_ptr(T0-[H], [H|T0]-[0]) :- !.
inc_inf_ptr(A, B) :- inc_ptr(A, B).

:- begin_tests(brainf__k).

test(store, A == []-[1]) :- store([]-[0], 1, A).

test(inc_ptr, A == [0]-[]) :- inc_ptr([]-[0], A).

test(dec_ptr, A == []-[0]) :- dec_ptr([0]-[], A).
test(dec_ptr, fail) :- dec_ptr([]-[], _).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Note that the tape pair A-B has A in reverse. Hence rewinding from `[c,
b, a]-[1, 2, 3]` for `a` as the target gives `[]-[a, b, c, 1, 2, 3]`.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

test(rewind, A == [2, 1]-[3, 4, 5, 6]) :-
    rewind([3, 2, 1]-[4, 5, 6], 3, A).

:- end_tests(brainf__k).

hello_world(`\c
+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'`).

hello_world :- hello_world(A), brainf__k(A).