Если на рисунок слона машина распознавания реагирует сигналом «мура», на изображения верблюда — тоже «мура», а на портрет выдающегося учёного — опять же «мура», это не обязательно означает, что она неисправен.Теги: #Prolog #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([], [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»).Приведем примеры использования «рф» на примере того же палиндрома (сама реализация будет чуть позже):
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([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 префиксом для второго аргумента (помним, что префикс также может быть пустым списком).
Далее проверяем остальные аргументы
- Остальные два правила описывают тривиальные случаи совпадения.
3. Примеры
3.1. Первый пример
В замечательной статье «Пролог, введение» предлагает решение проблемы, предложенной в Рефал сообщество , в Прологе.Постановка проблемы:
Входной файл содержит две строки ASCII, одна состоит только из заглавных латинских букв, другая может содержать заглавные латинские буквы и еще два специальных символа — * (звездочка) и? (вопросительный знак).Решение Рефал:Строки могут иметь длину от 1 до 255 символов, и находиться в файле в любом порядке (но их всего две, формат входных данных правильный).
Назовем строку, состоящую только из букв, словом.
Строка со специальными символами представляет собой шаблон, в котором "?" и "*" играют роль подстановочных знаков по правилам, идентичным подстановочным знакам в именах файлов в DOS или Unix-оболочке, т.е.
"?" заменяет ровно один произвольный символ, а «*» заменяет любое количество произвольных символов — 0 и более (то есть может заменять и пустую строку).
Программа должна ответить ДА, если слово соответствует шаблону, или НЕТ в противном случае.
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*/; };
Перепишем предикат Refal на Прологе, используя описанный выше подход:ischar(H, [H]).match([],[]) :- !.
match("*",_) :- !.
match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), rf([s(T1), e(E2)],Word),
-
Всемирный Экономический Форум, Вэф
19 Oct, 24 -
Супер - Услуги По Уходу На Дому
19 Oct, 24 -
Peopleconnect: Одолжите Режиссера
19 Oct, 24 -
Как Создается Звук Для Другой Реальности
19 Oct, 24
