bf.ex

defmodule BF do
  def new do
    %{
      tape: %{},
      ptr: 0,
      output: "",
      stack: [],
      code: []
    }
  end

  # 1. go with the code and eat it on the way
  # 2. encounter an "[" - push the code to the stack
  # 3. go with the code and eat it on the way
  # 4. encounter a "]" - test
  # a. if it is > 0 -> substitute code for the stack head and keep going
  # b. if it is == 0 -> pop the stack head and keep going

  def run(context, code) when is_binary(code) do
    context = %{ context | code: String.codepoints(code) }
    run(context)
  end

  def run(context) do
    case context.code do
      [] -> context
      [ operator | tail ] ->
        context = %{ context | code: tail }
        context = execute(context, operator)
        run(context)
    end
  end

  def execute(context, operator) do
    case operator do
      ">" -> %{ context | ptr: context.ptr + 1 }
      "<" -> %{ context | ptr: decrement(context.ptr) }
      "+" -> %{ context | tape: increment(context.tape, context.ptr) }
      "-" -> %{ context | tape: decrement(context.tape, context.ptr) }
      "." -> %{ context | output: print(context) }
      "[" -> %{ context | stack: push(context) }
      "]" -> loop?(context)
    end
  end

  def decrement(pointer) do
    case pointer do
      0 -> 0
      n -> n - 1
    end
  end

  def increment(tape, pointer) do
    {_, new_tape} = Map.get_and_update(tape, pointer, fn
      (nil) -> { nil, 1 }
      (255) -> { 255, 255 }
      (prev) -> { prev, prev + 1 }
    end)
    new_tape
  end

  def decrement(tape, pointer) do
    {_, new_tape} = Map.get_and_update(tape, pointer, fn
      (nil) -> { nil, 0 }
      (0) -> { 0, 0 }
      (prev) -> { prev, prev - 1 }
    end)
    new_tape
  end

  def print(context) do
    character = context.tape[context.ptr]
    new_output = context.output <> <<character>>
  end

  def push(context) do
    [ context.code | context.stack ]
  end

  def loop?(context) do
    case context.tape[context.ptr] do
      0 -> %{ context | stack: Enum.drop(context.stack, 1) }
      n -> %{ context | code: hd(context.stack) }
    end
  end
end

bf_tests.exs

defmodule BrainfuckTest do
  use ExUnit.Case
  import BF

  @doc "
  	BF is our Brainfuck turing machine
  	Output will be a map
  	%{
		tape: map #our tape, in the format %{0=> 0, 1=> 0, 2=> 0 ...}
		ptr: int, #pointer position
		output: string #brainfuck output
  	}
  "

  test "moves right" do
    assert (BF.new() |> BF.run(">")).ptr == 1
  end

  test "moves left" do
  	assert (BF.new() |> BF.run(">><")).ptr == 1
  end

  test "doesnt overflow moving left" do
  	assert (BF.new() |> BF.run("<")).ptr == 0
  end

  test "increments at pointer" do
  	assert (BF.new() |> BF.run("+")).tape[0] == 1
  end

  test "increments at pointer on the first position" do
    assert (BF.new() |> BF.run(">+")).tape[1] == 1
  end

  test "decrements at pointer" do
  	assert (BF.new() |> BF.run("++-")).tape[0] == 1
  end

  test "doesnt overflow decrements" do
  	assert (BF.new() |> BF.run("+--")).tape[0] == 0
  end

  test "decrements at pointer on the first position" do
    assert (BF.new() |> BF.run(">-")).tape[1] == 0
  end

  test "doesnt overflow increments" do
  	code = String.duplicate("+", 300)
  	assert (BF.new() |> BF.run(code)).tape[0] == 255
  end

  test "outputs oi" do
  	code = String.duplicate("+", 104)
  		<> ".>"
  		<> String.duplicate("+", 105)
  		<> "."
  	assert (BF.new() |> BF.run(code)).output == "hi"
  end

  test "loops" do
  	code = "++++[>+<-]"
  	assert (BF.new() |> BF.run(code)).tape[1] == 4
  end

  test "hello world" do
  	code = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."
  	assert (BF.new() |> BF.run(code)).output == "Hello World!\n"
  end
end