Pull to refresh

Пишем интерпретатор Brainfuck на Mercury

Reading time 5 min
Views 2.4K
Продолжая неделю Brainfuck на хабре и свои эксперименты с Mercury, написал свою версию интерпретатора. Заранее прошу извинить, что еще не представил «вступительную» статью о Mercury. На самом деле, она в процессе написания.
Пока же приведу код решения, который проиллюстрирует заодно несколько возможностей языка Mercury.

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


И сразу вывод этой программы:

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


Немного о моем решении. Оно состоит из 2 шагов
  1. преобразование текста brainfuck программы в AST (abstract syntax tree)
  2. исполнение дерева AST

На перовом этапе из куска BF-кода, для примера, '+++>>[+-]<' получиться структура AST в виде списка [plus, plus, plus, step, step, cycle([plus, minus]), back]. За это отвечает недетерминированный предикат ast. Для тех, кому не вполне ясно это понятие, упрощенно поясню, что это такой предикат, который может возвратить более одного решения, и эти решения будут перебираться с помощью перебора с откатами (backtracking), пока все выражение, состоящее из этого и окружающего его предикатов, не будет истинно. На этом принципе основано удобство написания парсера, разбирающего текст программы методом поиска в глубину (хотя у этого подхода есть и немало недостатков, эта тема неплохо освещена в этом харбратопике). Стоит отметить, что этот этап наряду с разбором автоматически проверяет синтаксическую корректность (а именно, правильность скобочной структуры). В случае её неправильности цель ast(Ast_, Chars, []:list(char)) закончится неудачей, и мы получим ошибку «Program invalid (parse error)!». Вторая ремарка: предикат ast написан в DCG нотации, которая поддерживается языком mercury так же как и многими традиционными прологами.

На втором этапе (за который отвечают предикаты execute_*) происходит «вычисление» полученного синтаксического дерева. Каждый предикат execute_* принимает на вход исходное состояние ленты ячеек, изменяет его в соответствие с AST brainfuck-программы, и выдает результирующее, каковое должно быть после применения оного предиката (как мы знаем, функциональные языки терпеть не могут изменяемых структур данных).

Тут следует отметить структуру задания состояния ленты. Как известно, (правильно) выбранная структура данных определяет (оптимальный) алгоритм реализации и его сложность. В данном случае, была выбрана структура ленты определяемая двумя списками и числом: bf_state(LeftCells, Cell, RightCells). При таком подходе увеличение и уменьшение ячейки это изменение Cell на +-1, а сдвиг влево (вправо), это перемещение головы списка из Left(Right)Cells на место Cell а самой Cell в голову Right(Left)Cells (ну и частный случай присвоения Cell=0 в случае пустого списка Left(Right)Cells).

Преимущество такого представления:
  • не нужно предзаполнять список фиксированной длины (экономия памяти)
  • неограниченная длина ленты (кроме ограничений, накладываемых ресурсами вычислительной машины)

Еще одно пояснение. Непонятная запись !S в mercury называется state variable и представляет собой пару переменных !.S, !:S с mode'ами in и out. Это удобно для цепного вызова предикатов с передачей параметров с выхода предыдущего на вход последующего, ну т.е. запись

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

или в виде DCG нотации:

some_pred --> pred1, pred2, pred3.

Но подробнее об этом и других особенностях mercury в другой статье =)
Tags:
Hubs:
+8
Comments 10
Comments Comments 10

Articles