Пользователь
0,0
рейтинг
25 октября 2013 в 10:31

Разработка → Делаем 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),!.


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

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



Приведенный код не претендует на уникальность или практическое применение. Однако, смеем надеяться, подтолкнет читателя поближе познакомиться с такими замечательными языками, как Пролог и Рефал.
@basp
карма
21,0
рейтинг 0,0

Похожие публикации

Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (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
      У меня лежит дома ГОСТ на АГЛАМС. На самом деле это Алгол, но советский. Не уверен, что это считается самостоятельным языком, но создано в СССР, да.

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

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