Disclaimer: The following is a diversion from BeerRiot. To all Rioters waiting on new features, I apologize. I can only claim temporary insanity due to cold.
I ran across two interesting Erlang posts recently. The first was to the Trapexit help form, where someone was attempting to implement a Brainfuck interpreter in Erlang, as a way of learning the language. I didn't understand the question being asked, so I decided to give it a go myself, to see if I ran into a similar question.
A little while later, this is the implementation I had:
-module(bf).
-export([run/1]).
run(Program) ->
run([], Program, [], 0, []).
run(Left, [$>|Right], LP, Data, RP) ->
case RP of
[D|Rest] -> run([$>|Left], Right, [Data|LP], D, Rest);
[] -> run([$>|Left], Right, [Data|LP], 0, [])
end;
run(Left, [$<|Right], LP, Data, RP) ->
case LP of
[D|Rest] -> run([$<|Left], Right, Rest, D, [Data|RP]);
[] -> run([$<|Left], Right, [], 0, [Data|RP])
end;
run(Left, [$+|Right], LP, Data, RP) ->
run([$+|Left], Right, LP, Data+1, RP);
run(Left, [$-|Right], LP, Data, RP) ->
run([$-|Left], Right, LP, Data-1, RP);
run(Left, [$.|Right], LP, Data, RP) ->
io:put_chars([Data]),
run([$.|Left], Right, LP, Data, RP);
run(Left, [$,|Right], LP, _, RP) ->
Data = io:get_chars([], 1),
run([$,|Left], Right, LP, Data, RP);
run(Left, [91|Right], LP, Data, RP) ->
if Data == 0 ->
{NewLeft, NewRight} = pass_match(91, 93, [91|Left], Right),
run(NewLeft, NewRight, LP, Data, RP);
true ->
run([91|Left], Right, LP, Data, RP)
end;
run(Left, [93|Right], LP, Data, RP) ->
if Data /= 0 ->
{[91|NewRight], NewLeft} = pass_match(93, 91, [93|Right], Left),
run([91|NewLeft], NewRight, LP, Data, RP);
true ->
run([93|Left], Right, LP, Data, RP)
end;
run(Left, [X|Right], LP, Data, RP) ->
run([X|Left], Right, LP, Data, RP);
run(_, [], _, Data, _) ->
Data.
pass_match(This, Match, Accum, Source) ->
pass_match(This, Match, Accum, Source, 0).
pass_match(_, Match, Accum, [Match|Source], 0) ->
{[Match|Accum], Source};
pass_match(This, Match, Accum, [Match|Source], Depth) ->
pass_match(This, Match, [Match|Accum], Source, Depth-1);
pass_match(This, Match, Accum, [This|Source], Depth) ->
pass_match(This, Match, [This|Accum], Source, Depth+1);
pass_match(This, Match, Accum, [X|Source], Depth) ->
pass_match(This, Match, [X|Accum], Source, Depth).Basically, a list for what is to the left of the current execution point, and another for what is to the right, as well as a list each for what is to the left and right of the current data point. Just tail-recurse through the right list (with a little extra jumping for the loop operators), pattern matching the opcode at the head of the right program list. Run the program by calling bf:run(Program) where Program is just a list of characters (including Brainfuck symbols if you want any result other than 0). For example, the following code will print out "Hello World" (found on the Wikipedia page).
bf:run("
++++++++++
[>+++++++>++++++++++>+++>+<<<<-] The initial loop to set up useful values in the array
>++. Print 'H'
>+. Print 'e'
+++++++. Print 'l'
. Print 'l'
+++. Print 'o'
>++. Print ' '
<<+++++++++++++++. Print 'W'
>. Print 'o'
+++. Print 'r'
------. Print 'l'
--------. Print 'd'
>+. Print '!'
>. Print newline").The second post I happened across was someone noticing the alternative way to make Erlang atoms (by enclosing characters in single quotes). Commenters were unhappy that they had never found a good use for functions named using these atoms.
Well, guess where that thought took me:
-module(bf2).
-export([run/1]).
-export(['>'/2, '<'/2, '+'/2, '-'/2, '.'/2, ','/2, '['/2, ']'/2, stop/2]).
-record(tape, {left=[], current=0, right=[]}).
function_list() ->
lists:foldl(fun({Atom, _}, Funs) ->
case atom_to_list(Atom) of
[Char] -> [{Char, Atom}|Funs];
_ -> Funs
end
end, [], proplists:get_value(exports, bf2:module_info())).
run(Program) ->
Funs = function_list(),
Atoms = lists:foldl(fun(C, T) ->
case proplists:get_value(C, Funs) of
undefined -> T;
A -> [A | T]
end
end, [], Program),
[Current|Rest] = lists:reverse([stop|Atoms]),
bf2:Current(#tape{current=Current, right=Rest}, #tape{}).
advance(Program, Data) ->
[Next|Rest] = Program#tape.right,
bf2:Next(#tape{left = [Program#tape.current | Program#tape.left],
current = Next,
right = Rest},
Data).
stop(_, #tape{current=Value}) ->
Value.
'>'(Program, Data) ->
case Data#tape.right of
[X|R] -> NewPoint = X, NewRight = R;
_ -> NewPoint = 0, NewRight = []
end,
advance(Program, #tape{left = [Data#tape.current | Data#tape.left],
current = NewPoint, right = NewRight}).
'<'(Program, Data) ->
case Data#tape.left of
[X|L] -> NewPoint = X, NewLeft = L;
_ -> NewPoint = 0, NewLeft = []
end,
advance(Program, #tape{right = [Data#tape.current | Data#tape.right],
current = NewPoint, left = NewLeft}).
'+'(Program, Data) ->
advance(Program, Data#tape{current = Data#tape.current + 1}).
'-'(Program, Data) ->
advance(Program, Data#tape{current = Data#tape.current - 1}).
'.'(Program, Data) ->
io:put_chars([Data#tape.current]),
advance(Program, Data).
','(Program, Data) ->
In = io:get_chars([], 1),
advance(Program, Data#tape{current = In}).
'['(Program, Data) ->
if Data#tape.current /= 0 ->
advance(Program, Data);
true ->
{Left, Right} = skip('[', ']',
Program#tape.left,
Program#tape.right),
advance(#tape{left=Left, current=']', right=Right}, Data)
end.
']'(Program, Data) ->
if Data#tape.current == 0 ->
advance(Program, Data);
true ->
{Right, Left} = skip(']', '[',
Program#tape.right,
Program#tape.left),
advance(#tape{left=Left, current='[', right=Right}, Data)
end.
skip(Up, Down, Acc, Src) -> skip(Up, Down, [Up|Acc], Src, 0).
skip( _, Down, Acc, [Down|Src], 0) -> {Acc, Src};
skip(Up, Down, Acc, [Down|Src], N) -> skip(Up, Down, [Down|Acc], Src, N-1);
skip(Up, Down, Acc, [Up|Src], N) -> skip(Up, Down, [Up|Acc], Src, N+1);
skip(Up, Down, Acc, [X|Src], N) -> skip(Up, Down, [X|Acc], Src, N).Basically, create a function named for each Brainfuck operator. Then, convert all of the valid Brainfuck operators in the program into atoms, and use them to call the functions sharing their names. Run it just like the earlier example, bf2:run(Program).
Now, I'm not going to call the first implementation ugly. In fact, I think it's a fair example of walking a list, doing different things depending on the value of the head of the list. But, I have to say that The second version does read a bit nicer, in some respects. (I also tried using the tape record in the first example, but I thought it made things worse.)
Yeah, okay, Brainfuck clearly still isn't a great use for quirky-atom function names, but perhaps it represents some problem space that can make good use of them?
Anyone have a better neat trick - for either Brainfuck interpretation or funky-atom function names?
P.S. My apologies for not posting an answer to Alboin (the Trapexit poster). I can't remember my login details for Trapexit. :P
Categories: Erlang
Post Copyright © 2008 Bryan Fink