Pull to refresh

Параллелим Brainfuck

Abnormal programming
Не будем терять темпа. Поскольку неделя еще не закончилась, еще есть время для очередного топика про Brainfuck. Идея меня захватила, но реализаций интерпретаторов было уже такое количество, что захотелось какой-то изюминки. Поэтому в качестве цели эксперимента я выбрал Brainfork — многопоточную версию Brainfuck-а. А в качестве средства — Erlang, который прекрасно подходит для реализации параллельных процессов. Тем, кому эта тема до сих пор не осточертела, предлагаю заглянуть под кат.

Принципы языка 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[-<]++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
А лучше, запустить его несколько раз и удостоверится, что результат каждый раз разный: все из-за того, что между потоками не происходит никакой синхронизации.

Код, конечно, не является эталонным. И написан больше в тренировочных целях. Так что не думаю, что кому-то это пригодится. Но и блог выбран подходящий.
Tags:brainfuckbrainforkErlang
Hubs: Abnormal programming
Total votes 51: ↑42 and ↓9+33
Views2K

Popular right now