Если распознающая машина на рисунок слона отзывается сигналом «мура», на изображения верблюда — тоже «мура» и на портрет видного ученого — опять-таки «мура», это не обязательно означает, что она неисправна. Она может быть просто философски настроена.
Владимир Савченко, «Открытие себя»
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» в примере — это обычные термы Пролога.
Примеры вызова нашего палиндрома:
?- 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),!.
Реализацию других операторов оставляем на самостоятельную изучение.
Вместо заключения
Приведенный код не претендует на уникальность или практическое применение. Однако, смеем надеяться, подтолкнет читателя поближе познакомиться с такими замечательными языками, как Пролог и Рефал.
