Делаем Refal на Prolog. Магия в семь строк

    Если распознающая машина на рисунок слона отзывается сигналом «мура», на изображения верблюда — тоже «мура» и на портрет видного ученого — опять-таки «мура», это не обязательно означает, что она неисправна. Она может быть просто философски настроена.
    Владимир Савченко, «Открытие себя»


    1. Полюбите Рефал. Немедленно!



    Всем известно, что есть такой язык программирования — Рефал. Рефал разработан в 1966 году нашим соотечественником Валентином Турчиным. Судьба у Рефала сложная, но язык до сих пор жив и развивается. Для интересующихся приведем несколько ссылок:


    Сильно утрируя, можно сказать, что Рефал — это смесь Лиспа и Пролога. В синтаксисе языка есть одна интересная особенность — сопоставление с образцом т.н. «прямым выводом».

    Т.е., например, предикат для определения палиндрома на Рефале можно записать так:

     Palindrom {
         = True;
         s.1 = True ;
         s.1 e.2 s.1 = <Palindrom e.2> ;
         e.1 = False ;
     }
    


    Каждая строка в фигурных скобках — это правило сопоставления с образцом. Тело каждого правила разделяется символом "=". Элементы образца разделяются пробелом. Вызов функции записывается в угловых скобках. Символы, начинающиеся с «s» и «e» — переменные определенного вида. Имя переменных записывается после точки.
    • Переменная типа «s» означает, что сопоставление верно только для одного элемента последовательности
    • Переменная типа «e» означает, что сопоставление верно для 0 или больше элементов


    Т.о. данное определение палиндрома можно прочитать так:
    • Выражение верно для пустого списка. Т.е. пустую последовательность можно назвать палиндромом.
    • Выражение верно для списка из одного элемента. Т.е. последовательность из одного элемента можно назвать палиндромом. Тип переменной «s» говорит нам о том, что образец верен только для одного элемента.
    • Выражение верно для списка, состоящего минимум из 2 элементов, причем первый и последний элемент списка должны быть равны. Равенство первого и последнего элемента указывается одинаковыми именами переменных («1»). Подсписок между первым и последним элеменом (переменная «e.2», т.е. длина такого подсписка может быть 0 или больше элементов) необходимо рекурсивно проверить на палиндром.
    • Если не сработало ни одно выше определенное правило — то переданный аргумент не является палиндромом.


    Надо отменить, что в современных реализациях Рефала сопоставление с образцом реализовано достаточно эффективно.

    2. Пролог. Магия начинается!



    В Рефале есть много от языка Пролог. Попытаемся реализовать механизм рефаловского сопоставления с образцом на Прологе.

    Прежде чем мы начнем, определим вспомогательный предикат «prefix». Предикат должен проверять, является ли первый аргумент началом второго аргумента. Оставшаяся часть второго аргумента указывается в третьем аргументе.

    prefix([], [X|Xs], [X|Xs]).
    prefix([X|Prefix], [X|List], Rest) :- prefix(Prefix, List, Rest).
    


    Примеры вызова:

    ?- prefix([1,2], [1,2,3,4], [3,4]).
    true.
    
    ?- prefix([], [1,2,3,4], X).
    X = [1, 2, 3, 4].
    


    Теперь у нас все готово для определения предиката рефаловсого сопоставления с образцом (назовем предикат «rf»). Приведем примеры использования «rf» на примере все того же палиндрома (сама реализация будет чуть позже):

    palindrom([]).
    palindrom([_]).
    palindrom(List) :- rf([s(X1), e(Y), s(X1)], List), palindrom(Y).
    


    Как видно, такое определение похоже на то, что мы писали ранее на Рефале. Четвертое правило в рефаловском примере нам не понадобилось, т.к. Пролог сам отсечет ложные ветви сопоставления. Обратим внимание, что «s» и «e» в примере — это обычные термы Пролога.

    Примеры вызова нашего палиндрома:

    ?- palindrom("abc").
    false.
    
    ?- palindrom("abcba").
    true .
    
    ?- palindrom("aa").
    true .
    


    Теперь перейдем, собственно, к определению предиката «rf»:

    rf([X | Pattern], [X|Xs]) :- rf(Pattern, Xs).
    rf([s(X) | Pattern], [X|Xs]) :- rf(Pattern, Xs).
    rf([e(X) | Pattern], Xs) :- prefix(X, Xs, Rest), rf(Pattern, Rest).
    rf([e(X)], X).
    rf([], []).
    


    Прокомментируем наше определение построчно:
    • Сопоставление верно, если, как минимум, и образец и список начинаются с одного и того же элемента (переменная X). Далее сверяем оставшуюся часть аргументов
    • Правило верно и для «s» элемента в образце
    • Если очередным элементом образца является «e» переменная, то проверяем, является ли переменная X префиксом для второго аргумента (напомним, что префиксом может быть и пустой список). Далее сверяем оставшуюся часть аргументов
    • Оставшиеся 2 правила описывают тривиальные случаи сопоставления


    3. Примеры



    3.1. Первый пример



    В замечательной статье «Prolog, введение» приводится решение задачи, предложенной в Рефал-сообществе, на Прологе. Формулировка задачи:

    Во входном файле две ASCII-строки, одна состоит только из больших латинских букв, в другой могут встречаться большие латинские буквы и еще два спецсимвола — * (звездочка) и? (знак вопроса). Строки могут иметь длину от 1 до 255 символов, быть в файле в произвольном порядке (но их всего две, формат входных данных корректен). Строку только с буквами назовем словом. Строка со спецсимволами — шаблон, в котором "?" и "*" играют роль символов подстановки по правилам, идентичным wildcards в именах файлов в DOS или Unix-shell, т.е. "?" заменяет собой ровно один произвольный символ, а "*" заменяет собой любое количество произвольных символов — 0 или более (т.е. может заменять и пустую строку). Программа должна выдать ответ YES, если слово подпадает под шаблон (match'ит его), либо NO в противном случае.


    Решение на рефал:

    Match {
        s.1 e.2     (s.1 e.3)  = <Match e.2 (e.3)>;
        s.1 e.2     ('?' e.3) = <Match e.2 (e.3)>;
        e.1 ('*' e.3) = { e.1 : e.11 e.12, <Match e.12 (e.3)>; };
        /*empty*/ ()       = /*yes*/;
     };
    


    Перепишем рефаловский предикат на Прологе с использованием описанного выше подхода:

    ischar(H, [H]).
    
    match([],[]) :- !.
    match("*",_) :- !.
    
    match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), rf([s(T1), e(E2)],Word),
    	match(E1, E2),!.
    
    match(Pattern, Word) :-	rf([s(T1), e(E1)], Pattern),  ischar(T1, "?"),
    	rf([s(_T2), e(E2)], Word),
    	match(E1,E2),!.
    
    match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), ischar(T1, "*"),
    	rf([e(_E21), e(E22)], Word),
    	match(E1,E22),!.
    
    
    check:- match("ASDFAASDASDAAASDASDASD", "ASDFAASDASDAAASDASDASD"),
                  match("*", "ASDFAASDASDAAASDASDASD"),
                  match("A?DF?A*ASD*ASDA?DASD", "ASDFAASDASDAAASDASDASD"),
                  \+ match("ASDFAASDADAAASDASDASD", "ASDFAASASDAAASDASDASD").
    


    Отметим, что, разумеется, наше определение значительно менее эффективно, чем решение из статьи «Prolog, введение».

    3.2. Второй пример



    Приведем еще один пример использования нашего предиката. Определим тривиальный предикат, вычисляющий арифметические выражения в строке.

    Пример использования:

    ?- infix("2+2*2", R).
    R = 6.
    
    ?- infix("1+1+1+1", R).
    R = 4.
    


    Пусть предикат infix «понимает» только операции сложения и умножения. Тогда решение может выглядеть так:

    ischar(H, [H]).
    
    infix(A,R) :- rf([e(X), OpPlus, e(Y)], A),
    	ischar(OpPlus, "+"),
    	infix(X,R1), infix(Y,R2),
    	R is R1 + R2,!.
    
    infix(A,R) :- rf([e(X), OpMul, e(Y)], A),
    	ischar(OpMul, "*"),
    	infix(X,R1), infix(Y,R2),
    	R is R1 * R2, !.
    
    infix(A,R) :- rf([e(X)], A), number_codes(R, X),!.
    


    Реализацию других операторов оставляем на самостоятельную изучение.

    Вместо заключения



    Приведенный код не претендует на уникальность или практическое применение. Однако, смеем надеяться, подтолкнет читателя поближе познакомиться с такими замечательными языками, как Пролог и Рефал.
    Метки:
    • +10
    • 8,1k
    • 8
    Поделиться публикацией
    Похожие публикации
    Комментарии 8
    • +2
      Всем известно, что есть такой язык программирования — Рефал

      Ну как–же, как–же… конечно же, всем, неужто найдётся хоть кто–нибудь кто что ещё на нём не писал, не говотя о том уже о том, что не слышал

      Простите, не удержался

      По теме:
      – а какие ещё языки программирования были созданы в СССР?
      – чем это компилируется?
      • 0
        1. Я знаю только про Рапиру. Можно добавить еще ДРАКОН, но это визуальный язык
        2. Реализации можно посмотреть тут: refal.ru/dialects.html
        • +1
          Спасибо!
          Очень про Рапиру понравилось:
          Ключевые (зарезервированные) слова:
          возврат   иначе     проц
          всё       кнц       фун
          до        от        шаг
          если      повтор

          Проц Старт()
              Вывод 'Здравствуй, мир!'
          Кон Проц
          

          Кстати, там ещё про языкы Сетл, ПОПЛАН и Робик упомянуто, правда, они для других платформ
          • +1
            С википедии про ДРАКОН:
            ДРАКОН превратился в семейство языков моделирования и программирования. Программа ИС Дракон поддерживает работу с гибридными языками программирования Дракон-С, Дракон-Delphi, Дракон-1С, Дракон-ASM, Дракон-Oberon. ДРАКОН-редактор обеспечивает работу с гибридными языками Дракон-Java, Дракон-C#, Дракон-C, Дракон-Python, Дракон-Tcl, Дракон-Javascript, Дракон-Lua, Дракон-Erlang.

            Однако…
            А вообще, очень интересно почитать, спасибо за ссылки!
          • +1
            Вы про автора РЕФАЛа прочтите и его «Феномен науки». Курцвел в конце 90х со своей сингулярностью плагиатом занимался с Турчина 70х годов прошлого века.
            • 0
              Поддерживаю. Книга крайне спорная, но интересная.

              Если же говорить про рефал, то отдельная тема — это суперкомпиляция рефала. На эту тему есть статья в ПФП. Есть кое-что и для Хаскеля: ghc.haskell.org/trac/ghc/wiki/Supercompilation
              • 0
                А чего там спорного? Перекос в сторону космонавтики? Космонавтика тогда в тренде была и, похоже, тренд возвращается. К 2020 году будет в таком же тренде, как и в 60хх и 70хх.
            • +1
              У меня лежит дома ГОСТ на АГЛАМС. На самом деле это Алгол, но советский. Не уверен, что это считается самостоятельным языком, но создано в СССР, да.

              Книжечка, кстати, страниц тридцать со всеми формальностями.

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