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

    Продолжая неделю 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 в другой статье =)
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 10

      0
      Again…
        –1
        Откуда взялся такой императивный print в якобы чисто декларативном языке? Вы либо крестик снимите…
          +2
          как раз все там декларативно и чисто, прочтите внимательнее начало поста habrahabr.ru/blogs/programming/112030/

          причина в том, что запись

          main --> print("Hello"), nl, print("World")
          на самом деле является более короткой формой записи

          main(IO0,IO) :- print("Hello",IO0,IO1), nl(IO1,IO2), print("World",IO2,IO)


          где значения IO* символизируют значение «внешнего мира» до и после вызова соответствующих функций.
            0
            Есть ли что-то похожее на call-by-reference?

            То есть

            main(IO) :- print(«hi»,IO), print(«there»,IO).

            как короткая форма для

            main(IO0,IO1) :- print(«hi»,IO0,IO0'), print(«there»,IO0',IO1).

            ? Или это не имеет смысла в ЛП? (Просто в одном ФЯП call-by-reference помогает упростить «протаскивание» переменной линейного типа — полезно)
              0
              только в виде синтаксического сахара

              main(!IO) :- print("hi",!IO), print("there",!IO).

          0
          Очень прикольно. И даже читается вроде.

          Вот это:

          :- type bf_state ---> bf_state(
          left :: list(int),
          cell :: int,
          right :: list(int)
          ).

          напоминает zipper для односвязного списка. :) Судя по описанию в тексте, так и используется.

          Вопрос: есть ли какие-нибудь книжки по Mercury? Интересно, как там реализовать, например, структуру данных смежного списка с линейными типами.
            0
            Много материалов есть на официальном сайте, но они, понятно, на английском:
            www.mercury.csse.unimelb.edu.au/

            Есть одна книжка на русском (а точнее перевод) — учебник для лёгкого въезда в mercury, лежит тут:
            Учебник Ральфа Бекета по Mercury
              0
              Спасибо большое. :)

              Почитаем-с.
                0
                Пожалуйста =)
            +1
            Новая традиция — вместо Hello World писать интерпритатор brainfuck? :)
            Хорошая традиция, а то Hello World только на проверку работоспособности компилятора годится. Может кто-нибудь сваяет такое на php? :)

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое