Writing a Brainfuck interpreter in Mercury

Continuing the week Brainfuck on the hub and his experiments with Mercury , wrote his version of the interpreter. I apologize in advance for not having submitted an “introductory” article about Mercury. In fact, she is in the process of writing.
In the meantime, I will give a solution code that will illustrate at the same time several features 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

1. text conversion brainfuck programs in AST (abstract syntax tree)
2. wood version AST

At the first stage, from a piece of BF code, for example, '+++ >> [+ -] <' we get the AST structure in the form of a list [plus, plus, plus, step, step, cycle ([plus, minus]), back]. The nondeterministic predicate ast is responsible for this . For those who don’t quite understand this concept, I’ll simplify that this is a predicate that can return more than one solution, and these solutions will be sorted through backtracking, until the whole expression consisting of this and its predicates will not be true. This principle is based on the convenience of writing a parser that parses the program text using the in-depth search method (although this approach has many drawbacks, this topic is well covered in this harbratopika) It is worth noting that this stage, along with the parsing, automatically checks the 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)!”. Second remark: the ast predicate is written in DCG notation, which is supported by the mercury language as well as many traditional prologs.

At the second stage (which execute_ * predicates are responsible for), the resulting syntax tree is “calculated”. Each execute_ * predicate takes the initial state of the cell tape as input, changes it in accordance with the AST of the brainfuck program, and produces the result that should be after applying this predicate (as we know, functional languages ​​cannot tolerate mutable data structures).

Here it should be noted the structure of setting the status 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 a cell is changing Cell by + -1, and shifting it to the left (right), this is moving the list head from Left (Right) Cells to the place of the Cell and the Cell itself to the head of Right (Left) Cells (well, a special case assignment Cell = 0 in case of empty list Left (Right) Cells).

The advantage of this view:

• no need to pre-populate a fixed-length list (memory saving)
• unlimited tape length (except for the restrictions imposed by computer resources)

One more explanation. An incomprehensible entry! S 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 to the next, i.e. the record is equivalent: which in turn is equivalent: or in the form of DCG notation: But more on this and other features of mercury in another article =)

some_pred(In, Out) :- pred1(In, In1), pred2(In1, In2), pred3(In2, Out).



some_pred(!.S, !:S) :- pred1(!.S, !:S), pred2(!.S, !:S), pred3(!.S, !:S). % компилятор сам расставит циферки



some_pred(!S) :- pred1(!S), pred2(!S), pred3(!S).



some_pred --> pred1, pred2, pred3.