- PVSM.RU - https://www.pvsm.ru -
Если распознающая машина на рисунок слона отзывается сигналом «мура», на изображения верблюда — тоже «мура» и на портрет видного ученого — опять-таки «мура», это не обязательно означает, что она неисправна. Она может быть просто философски настроена.
Владимир Савченко, «Открытие себя»
Всем известно, что есть такой язык программирования — Рефал. Рефал разработан в 1966 году нашим соотечественником Валентином Турчиным. Судьба у Рефала сложная, но язык до сих пор жив и развивается. Для интересующихся приведем несколько ссылок:
Сильно утрируя, можно сказать, что Рефал — это смесь Лиспа и Пролога. В синтаксисе языка есть одна интересная особенность — сопоставление с образцом т.н. «прямым выводом».
Т.е., например, предикат для определения палиндрома [3] на Рефале можно записать так:
Palindrom {
= True;
s.1 = True ;
s.1 e.2 s.1 = <Palindrom e.2> ;
e.1 = False ;
}
Каждая строка в фигурных скобках — это правило сопоставления с образцом. Тело каждого правила разделяется символом "=". Элементы образца разделяются пробелом. Вызов функции записывается в угловых скобках. Символы, начинающиеся с «s» и «e» — переменные определенного вида. Имя переменных записывается после точки.
Т.о. данное определение палиндрома можно прочитать так:
Надо отменить, что в современных реализациях Рефала сопоставление с образцом реализовано достаточно эффективно.
В Рефале есть много от языка Пролог. Попытаемся реализовать механизм рефаловского сопоставления с образцом на Прологе.
Прежде чем мы начнем, определим вспомогательный предикат «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([], []).
Прокомментируем наше определение построчно:
В замечательной статье «Prolog, введение» [4] приводится решение задачи, предложенной в Рефал-сообществе [5], на Прологе. Формулировка задачи:
Во входном файле две 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, введение» [4].
Приведем еще один пример использования нашего предиката. Определим тривиальный предикат, вычисляющий арифметические выражения в строке.
Пример использования:
?- 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
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/nenormal-noe-programmirovanie/46597
Ссылки в тексте:
[1] Самостоятельное изучение Рефала-5. Взгляд студента: http://ulm.uni.udm.ru/~soft/wiki/doku.php?id=refal-5:korsa
[2] Журнал «Практика функционального программирования», выпуск №7: http://fprog.ru/2011/issue7/
[3] палиндрома: http://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D0%BB%D0%B8%D0%BD%D0%B4%D1%80%D0%BE%D0%BC
[4] «Prolog, введение»: http://habrahabr.ru/post/49399/
[5] Рефал-сообществе: http://wiki.botik.ru/Refaldevel/ForJavaProgrammer
[6] Источник: http://habrahabr.ru/post/198972/
Нажмите здесь для печати.