Parallel Brainfuck

Let's not lose pace. Since the week is not over yet, there is still time for another topic about Brainfuck. The idea captured me, but there were already so many implementations of the interpreters that I wanted some zest. Therefore, I chose Brainfork , the multithreaded version of Brainfuck, as the goal of the experiment. And as a means - Erlang, which is perfect for implementing parallel processes. To whom this topic is still not fed up, I suggest 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 forks the process, zeroing the current cell in the parent, and incrementing the next cell in the child process. At the same time, the cell pointer in the child is also shifted by one to the right.

First you can look at the code, and I will give the 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 as a symbol. 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 divided among all processes. The server of the code deals with this, the process of which is registered in 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 receiving instructions at a certain position, as well as support 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 interpreter threads either ended up one way or another, or never terminated).

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

Most importantly, for the sake of what all this was written, is contained in a total of four lines: the last clause in the definition of execute_token and in the fork. Actually, the generation of the child process. And there everything is quite simple: spawn a new process, slightly changing its cell ribbon.

As an experiment, you can try to run such code (this is augmented helloWorld):
Y[-<]++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
And it is better to run it several times and make sure that the result is different each time: all due to the fact that 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 would be useful to anyone. But the blog is selected as appropriate.