Не будем терять темпа. Поскольку неделя еще не закончилась, еще есть время для очередного топика про Brainfuck. Идея меня захватила, но реализаций интерпретаторов было уже такое количество, что захотелось какой-то изюминки. Поэтому в качестве цели эксперимента я выбрал Brainfork — многопоточную версию Brainfuck-а. А в качестве средства — Erlang, который прекрасно подходит для реализации параллельных процессов. Тем, кому эта тема до сих пор не осточертела, предлагаю заглянуть под кат.
Принципы языка Brainfork абсолютно аналогичны принципам Brainfuck-а за одним исключением: добавляется дополнительная инструкция Y, которая форкает процесс, обнуляя текущую ячейку в родительском, и инкрементируя следующую ячейку в дочернем процессе. При этом указатель ячейки в дочернем так же сдвигается на единицу вправо.
Для начала можно взглянуть на код, а комментарии я дам ниже
Код исполняется по-символьно. Было бы здорово (и не так трудно) построить AST, как в реализации bf на Mercury. Но это вызвало бы существенное усложнение кода для форка. А поскольку за скоростью интерпретации гонки нет, то реализация дешева и сердита.
Для упрощения в первую очередь инициализации дочернего процесса код между всеми процессами делится. Занимается этим сервер кода, процесс которого регистрируется второй строкой в функции start под именем code. В данном случае, процессы интерпретатора являются для него клиентами. Сервер может принимать запросы на получение инструкции в определенной позиции, а так же вспомогательные функции для нахождения позиции левой и правой соответствующей скобки. Этот сервер автоматически завершает работу через 5 секунд простоя (очевидно, что все потоки интерпретатора или завершились так или иначе, или не завершаться никогда).
Сама интерпретация кода довольно тривиальна: спрашиваем у сервера инструкцию, исполняем ее и спрашиваем следующую. И так, пока сервер не ответит нам, что кода больше нет (end_of_program). Тогда мы просто завершаем процесс. Способ хранения ленты ячеек я позаимствовал у хабраюзера xonix (спасибо-спасибо!): это кортеж, содержащий список ячеек до текущей, текущую ячейку, и список ячеек после текущей. Он оказался достаточно удобен не только потенциальной бесконечностью ленты, но и простотой работы с ним имеющимися языковыми средствами.
Самое главное, то, ради чего все это и писалось, содержится в всего в четырех строках: последнем клозе в определении execute_token и в fork. Собственно, порождение дочернего процесса. И там все довольно просто: спавним новый процесс, слегка изменив его ленту ячеек.
В качестве эксперимента можно попробовать запустить такой код (это дополненный хэлоуворлд):
А лучше, запустить его несколько раз и удостоверится, что результат каждый раз разный: все из-за того, что между потоками не происходит никакой синхронизации.
Код, конечно, не является эталонным. И написан больше в тренировочных целях. Так что не думаю, что кому-то это пригодится. Но и блог выбран подходящий.
Принципы языка Brainfork абсолютно аналогичны принципам Brainfuck-а за одним исключением: добавляется дополнительная инструкция Y, которая форкает процесс, обнуляя текущую ячейку в родительском, и инкрементируя следующую ячейку в дочернем процессе. При этом указатель ячейки в дочернем так же сдвигается на единицу вправо.
Для начала можно взглянуть на код, а комментарии я дам ниже
-module(bf).
-export([start/1, code_server_loop/1, execute_loop/2]).
start(ProgramString) ->
Program = array:from_list(ProgramString),
register(code, spawn(?MODULE, code_server_loop, [Program])),
spawn(?MODULE, execute_loop, [{[], 0, []}, 0]).
code_server_loop(Program) ->
receive
{get_token, Pid, Pos} ->
reply(Pid, token, array:get(Pos, Program)),
code_server_loop(Program);
{get_left_brace, Pid, Pos} ->
reply(Pid, left_brace, find_left_brace(Pos, Program)),
code_server_loop(Program);
{get_right_brace, Pid, Pos} ->
reply(Pid, right_brace, find_right_brace(Pos, Program)),
code_server_loop(Program);
stop -> ok
after 5000 ->
self() ! stop,
code_server_loop(Program)
end.
reply(Pid, ReplyType, Value) ->
case Value of
undefined -> Pid ! end_of_program;
Value -> Pid ! {ReplyType, Value}
end.
find_left_brace(Pos, Program) -> find_left_brace(Pos - 1, Program, 0).
find_left_brace(Pos, Program, Count) ->
case array:get(Pos, Program) of
$[ ->
if
Count == 0 -> Pos;
true -> find_left_brace(Pos-1, Program, Count-1)
end;
$] -> find_left_brace(Pos-1, Program, Count+1);
undefined -> undefined;
_ -> find_left_brace(Pos-1, Program, Count)
end.
find_right_brace(Pos, Program) -> find_right_brace(Pos + 1, Program, 0).
find_right_brace(Pos, Program, Count) ->
case array:get(Pos, Program) of
$] ->
if
Count == 0 -> Pos;
true -> find_right_brace(Pos+1, Program, Count-1)
end;
$[ -> find_right_brace(Pos+1, Program, Count+1);
undefined -> undefined;
_ -> find_right_brace(Pos+1, Program, Count)
end.
get_code_server(MessageType, Position) ->
code ! {MessageType, self(), Position},
receive
end_of_program -> exit(normal);
{_ReplyType, Reply} -> Reply
end.
get_token(Position) -> get_code_server(get_token, Position).
get_left_brace(Position) -> get_code_server(get_left_brace, Position).
get_right_brace(Position) -> get_code_server(get_right_brace, Position).
execute_loop(Tape, CodePosition) ->
Token = get_token(CodePosition),
case execute_token(Token, Tape, CodePosition) of
{skip, SkipPosition, NewTape} -> execute_loop(NewTape, SkipPosition);
NewTape -> execute_loop(NewTape, CodePosition + 1)
end.
execute_token($., {_, C, _} = Tape, _) -> io:format("~c", [C]), Tape;
execute_token($,, {L, _, R}, _) -> [C] = io:get_chars("> ", 1), {L, C, R};
execute_token($+, {L, C, R}, _) -> {L, C+1, R};
execute_token($-, {L, C, R}, _) -> {L, C-1, R};
execute_token($>, {L, C, []}, _) -> {[C|L], 0, []};
execute_token($>, {L, C, [RH|RT]}, _) -> {[C|L], RH, RT};
execute_token($<, {[], C, R}, _) -> {[], 0, [C|R]};
execute_token($<, {[LH|LT], C, R}, _) -> {LT, LH, [C|R]};
execute_token($[, {_, C, _} = Tape, Position) ->
case C of
0 -> {skip, get_right_brace(Position) + 1, Tape};
_ -> Tape
end;
execute_token($], Tape, Position) -> {skip, get_left_brace(Position), Tape};
execute_token($Y, {L, _, R} = Tape, Position) -> fork(Tape, Position + 1), {L, 0, R}.
fork({L, C, []}, Position) -> fork({L, C, [0]}, Position);
fork({L, C, [RH|RT]}, Position) ->
spawn(?MODULE, execute_loop, [{[C|L], RH+1, RT}, Position]).
Код исполняется по-символьно. Было бы здорово (и не так трудно) построить AST, как в реализации bf на Mercury. Но это вызвало бы существенное усложнение кода для форка. А поскольку за скоростью интерпретации гонки нет, то реализация дешева и сердита.
Для упрощения в первую очередь инициализации дочернего процесса код между всеми процессами делится. Занимается этим сервер кода, процесс которого регистрируется второй строкой в функции start под именем code. В данном случае, процессы интерпретатора являются для него клиентами. Сервер может принимать запросы на получение инструкции в определенной позиции, а так же вспомогательные функции для нахождения позиции левой и правой соответствующей скобки. Этот сервер автоматически завершает работу через 5 секунд простоя (очевидно, что все потоки интерпретатора или завершились так или иначе, или не завершаться никогда).
Сама интерпретация кода довольно тривиальна: спрашиваем у сервера инструкцию, исполняем ее и спрашиваем следующую. И так, пока сервер не ответит нам, что кода больше нет (end_of_program). Тогда мы просто завершаем процесс. Способ хранения ленты ячеек я позаимствовал у хабраюзера xonix (спасибо-спасибо!): это кортеж, содержащий список ячеек до текущей, текущую ячейку, и список ячеек после текущей. Он оказался достаточно удобен не только потенциальной бесконечностью ленты, но и простотой работы с ним имеющимися языковыми средствами.
Самое главное, то, ради чего все это и писалось, содержится в всего в четырех строках: последнем клозе в определении execute_token и в fork. Собственно, порождение дочернего процесса. И там все довольно просто: спавним новый процесс, слегка изменив его ленту ячеек.
В качестве эксперимента можно попробовать запустить такой код (это дополненный хэлоуворлд):
Y[-<]++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.А лучше, запустить его несколько раз и удостоверится, что результат каждый раз разный: все из-за того, что между потоками не происходит никакой синхронизации.
Код, конечно, не является эталонным. И написан больше в тренировочных целях. Так что не думаю, что кому-то это пригодится. Но и блог выбран подходящий.
