We write the Brainfuck interpreter on Mercury
Continuing the week Brainfuck on Habré and his experiments with Mercury , wrote his version of the interpreter. I apologize in advance for not having yet submitted the introductory article on Mercury. In fact, it is in the process of writing.
In the meantime, I will provide a solution code that will illustrate at the same time several possibilities of the Mercury language.
And immediately the output of this program:
')
A little about my decision. It consists of 2 steps.
At the first stage, from the piece of BF code, for example, '+++ >> [+ -] <', the structure of AST is obtained as a list [plus, plus, plus, step, step, cycle ([plus, minus]), back]. The nondeterministic predicate ast is responsible for this. For those who are not quite clear about this concept, I’ll simplify that this is such a predicate that can return more than one solution, and these solutions will be moved using backtracking, while the whole expression consisting of this and the predicates surrounding it will not be true. This principle is based on the convenience of writing a parser that parses the text of a program using the depth-first search method (although there are many shortcomings in this approach, this topic is well covered in this charteratopic ). It should be noted that this stage, along with parsing, automatically checks syntactic correctness (namely, the correctness of the bracket structure). If it is incorrect, the target ast (Ast_, Chars, []: list (char)) will fail, and we will get the error “Program invalid (parse error)!”. The second remark: the ast predicate is written in DCG notation, which is supported by the mercury language as well as by many traditional prologues.
At the second stage (for which the predicates execute_ * are responsible), the “computation” of the obtained syntax tree occurs. Each execute_ * predicate takes the initial state of the cell tape as an input, changes it according to the AST brainfuck program, and returns the resultant, which should be after applying this predicate (as we know, functional languages cannot tolerate variable data structures).
Here it should be noted the structure of the task state of the tape. As you know, the (correctly) selected data structure determines the (optimal) implementation algorithm and its complexity. In this case, the structure of the tape was determined by two lists and a number: bf_state (LeftCells, Cell, RightCells). With this approach, increasing and decreasing the cell is changing the Cell by + -1, and shifting left (right) is moving the head of the list from Left (Right) Cells to the Cell and Cell itself to the head Right (Left) Cells (well, and a special case Cell assignment = 0 in the case of an empty list of Left (Right) Cells).
The advantage of this view:
Another explanation. An incomprehensible! S entry in mercury is called a state variable and is a pair of variables! .S,!: S with in and out modes. This is convenient for chaining predicates with passing parameters from the previous output to the next input, i.e. a record
equivalent to:
which in turn is equivalent to:
or in the form of DCG notation:
But more about this and other features of mercury in another article =)
In the meantime, I will provide a solution code that will illustrate at the same time several possibilities of the Mercury language.
:- module bf. :- interface. :- import_module io. :- pred main(io::di, io::uo) is det. :- implementation. :- import_module list, string, char, solutions, require, int. :- type bf_cmd ---> plus; minus; step; back; print; cycle(list(bf_cmd)). :- type bf_state ---> bf_state( left :: list(int), cell :: int, right :: list(int) ). hello_world = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++\ .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.\ ------.--------.>+.>.". squares_1_to_1000 = "++++[>+++++<-]>[<+++++>-]+<+[\ >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+\ >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]\ <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-\ ]". fib_1_to_100 = "+++++++++++\ >+>>>>++++++++++++++++++++++++++++++++++++++++++++\ >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>\ +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-\ <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<\ -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]\ >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++\ +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++\ ++++++++++++++++++++++++++++++++++++++++++++.[-]<<\ <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<\ [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]". prog_to_ast(Prog) = Ast :- to_char_list(Prog, Chars), solutions(pred(Ast_::out) is nondet :- ast(Ast_, Chars, []:list(char)), Asts), ( Asts = [], error("Program invalid (parse error)!") ; Asts = [Ast|_] ). :- mode ast(out, in, out) is multi. ast([plus|Cmds]) --> ['+'], ast(Cmds). ast([minus|Cmds]) --> ['-'], ast(Cmds). ast([step|Cmds]) --> ['>'], ast(Cmds). ast([back|Cmds]) --> ['<'], ast(Cmds). ast([print|Cmds]) --> ['.'], ast(Cmds). ast([cycle(Cycle)|Cmds]) --> ['['], ast(Cycle), [']'], ast(Cmds). ast([]) --> []. execute_ast([], !State) --> []. execute_ast([Cmd|Cmds], !State) --> execute_cmd(Cmd, !State), execute_ast(Cmds, !State). execute_cmd(plus, bf_state(L,C,R), bf_state(L, C+1, R)) --> []. execute_cmd(minus, bf_state(L,C,R), bf_state(L, C-1, R)) --> []. execute_cmd(step, bf_state(L,C,R), bf_state([C|L], H, T)) --> {R = [], H=0, T=[]; R = [H|T]}. execute_cmd(back, bf_state(L,C,R), bf_state(T, H, [C|R])) --> {L = [], H=0, T=[]; L = [H|T]}. execute_cmd(print, S @ bf_state(_,C,_), S) --> print(char.det_from_int( C ):char). execute_cmd(Cmd @ cycle(Cmds), !.S @ bf_state(_,C,_), !:S) --> ( {C \= 0} -> execute_ast(Cmds, !S), execute_cmd(Cmd, !S) ; [] ). execute_str(Prog) --> {Ast = prog_to_ast(Prog)}, execute_ast(Ast, bf_state([], 0, []), _). main --> execute_str(hello_world), nl, execute_str(squares_1_to_1000), nl, execute_str(fib_1_to_100). And immediately the output of this program:
D:\stuff\test\mercury>bf.exe Hello World! 0 1 4 9 16 25 36 49 64 81 100 121 ... < > 9025 9216 9409 9604 9801 10000 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ')
A little about my decision. It consists of 2 steps.
- text conversion brainfuck program in AST (abstract syntax tree)
- execution tree AST
At the first stage, from the piece of BF code, for example, '+++ >> [+ -] <', the structure of AST is obtained as a list [plus, plus, plus, step, step, cycle ([plus, minus]), back]. The nondeterministic predicate ast is responsible for this. For those who are not quite clear about this concept, I’ll simplify that this is such a predicate that can return more than one solution, and these solutions will be moved using backtracking, while the whole expression consisting of this and the predicates surrounding it will not be true. This principle is based on the convenience of writing a parser that parses the text of a program using the depth-first search method (although there are many shortcomings in this approach, this topic is well covered in this charteratopic ). It should be noted that this stage, along with parsing, automatically checks syntactic correctness (namely, the correctness of the bracket structure). If it is incorrect, the target ast (Ast_, Chars, []: list (char)) will fail, and we will get the error “Program invalid (parse error)!”. The second remark: the ast predicate is written in DCG notation, which is supported by the mercury language as well as by many traditional prologues.
At the second stage (for which the predicates execute_ * are responsible), the “computation” of the obtained syntax tree occurs. Each execute_ * predicate takes the initial state of the cell tape as an input, changes it according to the AST brainfuck program, and returns the resultant, which should be after applying this predicate (as we know, functional languages cannot tolerate variable data structures).
Here it should be noted the structure of the task state of the tape. As you know, the (correctly) selected data structure determines the (optimal) implementation algorithm and its complexity. In this case, the structure of the tape was determined by two lists and a number: bf_state (LeftCells, Cell, RightCells). With this approach, increasing and decreasing the cell is changing the Cell by + -1, and shifting left (right) is moving the head of the list from Left (Right) Cells to the Cell and Cell itself to the head Right (Left) Cells (well, and a special case Cell assignment = 0 in the case of an empty list of Left (Right) Cells).
The advantage of this view:
- no need to prefill a fixed-length list (memory saving)
- unlimited tape length (except for limitations imposed by computer resources)
Another explanation. An incomprehensible! S entry in mercury is called a state variable and is a pair of variables! .S,!: S with in and out modes. This is convenient for chaining predicates with passing parameters from the previous output to the next input, i.e. a record
some_pred(In, Out) :- pred1(In, In1), pred2(In1, In2), pred3(In2, Out).
equivalent to:
some_pred(!.S, !:S) :- pred1(!.S, !:S), pred2(!.S, !:S), pred3(!.S, !:S). %
which in turn is equivalent to:
some_pred(!S) :- pred1(!S), pred2(!S), pred3(!S).
or in the form of DCG notation:
some_pred --> pred1, pred2, pred3.
But more about this and other features of mercury in another article =)
Source: https://habr.com/ru/post/113099/
All Articles