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

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

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

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

• Самостоятельное изучение Рефала-5. Взгляд студента
• Журнал «Практика функционального программирования», выпуск №7(светлая ему память!). Статьи «Язык РЕФАЛ — взгляд со стороны» и «Суперкомпиляция: идеи и методы»

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

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

 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» в примере — это обычные термы Пролога.

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

?- pal("abc"). false.  ?- pal("abcba"). true .  ?- pal("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),!. 

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

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

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