Parallel Brainfuck

Let's not lose the pace. Since the week has not ended yet, there is still time for the next topic about Brainfuck. The idea captured me, but there were already so many implementations of interpreters that I wanted some zest. Therefore, as the goal of the experiment, I chose Brainfork - a multi-threaded version of Brainfuck. And as a tool - Erlang, which is perfect for implementing parallel processes. For those who are still not tired of this topic, I propose to look under the cat.

The principles of the Brainfork language are absolutely similar to the principles of Brainfuck, with one exception: an additional instruction Y is added, which fork the process, zeroing the current cell in the parent, and incrementing the next cell in the child process. In this case, the cell pointer in the child is also shifted by one to the right.

First you can take a look at the code, and I will give comments below

-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]).	

The code is executed symbolically. It would be great (and not so difficult) to build an AST, as in the bf implementation on Mercury . But this would cause a significant complication of the code for the fork. And since there is no race behind the speed of interpretation, the implementation is cheap and angry.

To simplify the initialization of the child process, the code is shared among all processes. The server of code is engaged in this, the process of which is registered by the second line in the start function under the name code. In this case, the interpreter processes are clients for it. The server can accept requests for instructions at a specific position, as well as auxiliary functions for finding the position of the left and right corresponding brackets. This server automatically shuts down after 5 seconds of inactivity (it is obvious that all threads of the interpreter either terminated one way or another, or never terminate).

The interpretation of the code itself is quite trivial: we ask the server for instructions, execute it and ask for the following. And so, until the server tells us that there is no more code (end_of_program). Then we just complete the process. I borrowed a method of storing a tape of cells from the xonix habraiser (thanks, thanks!): This is a tuple containing a list of cells before the current one, the current cell, and a list of cells after the current one. It turned out to be quite convenient not only with the potential infinity of the tape, but also with the ease of working with it with the available language tools.

The most important thing, for the sake of which all this was written, is contained in only four lines: the last clause in the definition of execute_token and in fork. Actually, a child process. And everything is quite simple there: we’ll spawn the new process by slightly changing its ribbon of cells.

As an experiment, you can try to run such code (this is an extended haloworld):
Y[-<]++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
Better, run it several times and make sure that the result is different each time: all because there is no synchronization between the threads.

The code, of course, is not a reference. And written more for training purposes . So I don’t think it will be useful to anyone. But the blog has been chosen as suitable.