что такое пролог в игре
Пролог
Смотреть что такое «Пролог» в других словарях:
пролог — а, м. prologue m. <гр. prologos < pro впереди + logos речь, слово. 1. Вступительная, вводная часть литературного или музыкального произведения или спектакля. БАС 1. Пролог <к комедии Евнух > оставлен мною не переведен, первое для того… … Исторический словарь галлицизмов русского языка
Пролог — (греч. πρόλογος предисловие): Пролог вводная часть какого либо текста, введение, предисловие; Пролог целая часть трагедии перед выступлением хора (Аристотель, Поэтика); Пролог стартовый, как правило короткий, этап… … Википедия
Пролог — – древнерусский житийный сборник, ведущий свое происхождение от византийских месяцесловов, или синаксарей. П. имеет календарный характер: жития святых расположены в нем в соответствии с днями их церковной памяти; на каждый день года обыкновенно… … Словарь книжников и книжности Древней Руси
ПРОЛОГ — греч. церковная книга, содержащая краткие слова на годичные праздники, жития святых и отрывки нз писаний ·св. отцев, для чтения при богослужении. | Пролог или пролог введение, вступление, предисловие к сочинению, особенно драматическому. См.… … Толковый словарь Даля
ПРОЛОГ — (греч., от pro прежде, вперед, и logos слово). 1) введение, предисловие, вступление к сочинению, особенно драматическому. 2) в древнегреческих театрах обращение хора к публики перед началом комедии. 3) церковная книга, содержащая краткие слова на … Словарь иностранных слов русского языка
пролог — См … Словарь синонимов
Пролог — ПРОЛОГ вступительная часть, присоединенная к художественному произведению, в которой излагаются обстоятельства, предшествовавшие тому, что изображено в произведении (драме, повести). Вместо этого пролог может содержать указание на основной… … Словарь литературных терминов
пролог — и пролог. В знач. «церковная книга, содержащая жития святых, поучения и т. п.» пролог, род. пролога; мн. прологи, род. прологов и пролога, прологов. В знач. «вступительная часть литературного или музыкального произведения» пролог, род. пролога;… … Словарь трудностей произношения и ударения в современном русском языке
ПРОЛОГ — 1. ПРОЛОГ, пролога, мн. пролога, муж. (греч. prologos предисловие) (лит.). В древней Руси сборник кратких житий, поучений, назидательных повестей, размещенных в порядке церковного календаря. Рукописный пролог. 2. ПРОЛОГ1, пролога, мн. и, муж.… … Толковый словарь Ушакова
ПРОЛОГ — 1. ПРОЛОГ, пролога, мн. пролога, муж. (греч. prologos предисловие) (лит.). В древней Руси сборник кратких житий, поучений, назидательных повестей, размещенных в порядке церковного календаря. Рукописный пролог. 2. ПРОЛОГ1, пролога, мн. и, муж.… … Толковый словарь Ушакова
ПРОЛОГ — 1. ПРОЛОГ, пролога, мн. пролога, муж. (греч. prologos предисловие) (лит.). В древней Руси сборник кратких житий, поучений, назидательных повестей, размещенных в порядке церковного календаря. Рукописный пролог. 2. ПРОЛОГ1, пролога, мн. и, муж.… … Толковый словарь Ушакова
Значение слова «пролог»
1. Вступительная часть к литературному или музыкальному произведению, предваряющая общее содержание произведения или раскрывающая общий замысел автора. Пролог к «Руслану и Людмиле» Пушкина.□ Из всего этого материала может выйти разве пролог к роману! И. Гончаров, Обрыв. Пролог симфонии незаметно переходит в развитие первой части. С. А. Морозов, Музыка остается с тобой.
Источник (печатная версия): Словарь русского языка: В 4-х т. / РАН, Ин-т лингвистич. исследований; Под ред. А. П. Евгеньевой. — 4-е изд., стер. — М.: Рус. яз.; Полиграфресурсы, 1999; (электронная версия): Фундаментальная электронная библиотека
ПРО’ЛОГ, а, мн. пролога́, м. [греч. prologos — предисловие] (лит.). В древней Руси — сборник кратких житий, поучений, назидательных повестей, размещенных в порядке церковного календаря. Рукописный п.
Источник: «Толковый словарь русского языка» под редакцией Д. Н. Ушакова (1935-1940); (электронная версия): Фундаментальная электронная библиотека
проло́г
1. филол. факультативный элемент сюжета эпического произведения, знакомящий читателя с кем-либо из участников, местом или общими обстоятельствами будущего сюжетного действия
2. филол. начальный элемент в структуре древнегреческой комедии, а затем европейских драматических произведений разных жанров, предназначенный для краткого разъяснения содержания и смысла пьесы
Делаем Карту слов лучше вместе
Привет! Меня зовут Лампобот, я компьютерная программа, которая помогает делать Карту слов. Я отлично умею считать, но пока плохо понимаю, как устроен ваш мир. Помоги мне разобраться!
Спасибо! Я стал чуточку лучше понимать мир эмоций.
Вопрос: пересидеть — это что-то нейтральное, положительное или отрицательное?
Prolog, введение
Довольно оживленное обсуждение предыдущей стати (http://habrahabr.ru/blogs/programming/47416/) показало, что тема пролога оказалась интересна сообществу.
Чтобы заинтересовать еще более читателя и вместе с тем облегчить ему начало работы с этим языком, я решил написать немного начальных данных о прологе.
Кратко основные особенности.
Сразу нужно сделать важную оговорку. Все переменные (неизвестные) обозначаются с большой буквы.
S = [1055, 1088, 1080, 1074, 1077, 1090, 32, 1084, 1080|. ].
Видно, что строки являются списками кодов символов, т.е. к ним применимы все те же операции что и к спискам, но об этом позже.
Видим, что списки
1) могут быть разнородными (содержать любые комбинации выше- (и ниже-) перечисленных типов)
2) могут быть вложенными
Структура в прологе представляется функтором (имя структуры, то что до скобок) и параметрами (то что в скобках). Число параметров называется арностью функтора.
Как видим, структуры тоже могут быть вложенными.
Последний запрос может быть не совсем понятен, но должен стать понятен в процессе прочтения статьи.
Заметим, что между этими типами существует глубокая связь, например, списки есть ни что иное, как более красивое (синтаксический сахар) применение функтора «.»
Забегая на перед скажем, что так можно разбивать список на голову и хвост
Хотя так никто не делает, в виду того, что для конструирования списков из головы и хвоста (а также обратное преобразование, т.е. разделение списка на голову и хвост) есть более удобный синтаксис вида [H | T].
Tail = [о, с, т, а, л, ь, н, о, е],
List = [голова, о, с, т, а, л, ь, н, о|. ].
В равнозначности синтаксисов можно убедиться запросом
Как видим, тут проявляется на первый взгляд не совсем привычное поведение знака «=», а именно то, что он работает «в обе стороны». И это очень важный момент. Дело в том, что в прологе знак «=» обозначает не обычное (императивное) равенство (присвоение), а унификацию (что в других языках называется сопоставление с образцом), а именно сопоставление левой и правой части и в случае удачного сопоставления конкретизация неизвестных значений.
Фраза может выглядеть немного заумно, легче пояснить на примере.
B = bbb. % удачно + выполнена конкретизация
Разобравшись немного с понятием унификации, становится понятно, почему
Выполнив первую унификацию, пролог система сопоставляет неизвестную A c числом 2. Таким образом вторая унификация будет ни что иное как 2 = 5, т.е. сопоставление чисел 2 и 5 которое конечно же окончится неудачей в виду того что числа не равны. Таким образом, в прологе переменные могут быть конкретизированы только один раз (по этому, например, попытки императивного программирования вида N = N + 1 в прологе не имеют смысла, подобное обычно делается через рекурсию).
Чтобы точно уяснить смысл последнего запроса, нужно еще пояснить смысл функтора «,». Да, не удивляйтесь, «,» это действительно функтор (а именно, инфиксный оператор с арностью 2). В этом можно убедиться, выполнив запросы
здесь противоречий нет, и система просто конкретизирует значения неизвестных.
Однако, мы отвлеклись. Оператор «,» обозначает ни что иное, как логическое «И». Понятно что если мы говорим системе что некоторое число равно 2 и (при этом) оно же равно 5 то мы, очевидно, врем, о чем система нам и сообщает. Для логического «ИЛИ» предусмотрен оператор «;».
Собственно, ответ системы не представляет ничего удивительного. Она ответила ровно то, что мы ей сообщили, а именно, что неизвестное число это либо 2 либо 5.
Впрочем если мы конкретизируем наш запрос (неизвестное число это либо 2 либо 5 и при этом оно четное), то и ответ системы обретет однозначность
тут нас ожидает конфуз. Оказывается, система воспринимает арифметические операции как обычную комбинацию функторов (впрочем наблюдательные могли заметить это выше). Действительно, запрос
показывает что так и есть. Что же тогда делать? Однако, оказывается, есть специальный предикат is/2 (через «/» обычно обозначается арность предиката), который выполняет арифметическое действие.
Пока что мы работали в интерактивном режиме, чтобы «пощупать» пролог на вкус. Обычно же, пролог-программы, как и программы на любом другом языке представляют собой файл с текстом программы. Обычной практикой является загрузка этого файла в интерактивную среду с помощью команды consult(‘file’). (или ее синтаксическим сахаром — [file].) и последующими запросами к программе, т.е. к фактам и предикатам в ней определенным.
Пролог машина, используя описанные выше 2 основных механизма (унификация с конкретизацией + backtracking) вычисляет необходимый результат.
Программа на прологе представляет собой обычно совокупность фактов и предикатов. Подробнее об этих понятиях.
Факт есть некоторое отношение, а точнее сказать экземпляр такого отношения, например
Полезно заметить, что факт — это фактически тоже разновидность предиката, более того вышеприведенные 3 факта woman(. ) могут быть записаны одним предикатом
но все же из соображений выразительности следует применять факты там где это логично.
Запросы к системе, ознакомленной с приведенной программой:
Или так (получить сразу список):
Хотелось бы особо отметить чем предикаты пролога отличаются от функций (методов) императивного языка.
Во-первых, они, в общем случае, могут быть «многовходовыми», что есть прямым следствием свойств рассмотренного понятия унификации, а во-вторых они могут «возвращать одновременно целый набор значений», что есть следствием бэктрекинга (правда, правильнее говорить, что предикат может оставлять несколько точек возврата).
Действительно, рассмотрим тривиальный предикат
этот предикат допускает фактически 3 способа применения:
заметим еще, что этот предикат может быть записан в виде факта:
Более показательный в этом плане пример с предикатом append (сложение списков).
И все это используя только один предикат!
Чтобы подытожить, можно отметить, что программа на прологе представляет собой одновременно базу данных (не реляционную, конечно, но допускающую практически любую функциональную зависимость) (факты) и инфраструктуру запросов к этой базе данных (предикаты), позволяющую построить по данным из базы данных новые отношения, зависимости, или получить некий результат, связанный с данными (впрочем, факты могут и отсутствовать).
При этом сами запросы (предикаты) способны иметь довольно замысловатую логику или даже выполнять вычислительные задачи. Чтобы окончательно повергнуть читателя, добавим, что предикаты способны динамически порождать факты и даже другие предикаты. Отличие от, вероятно, знакомой читателю императивной парадигмы программирования — в декларативной сущности получаемых программ.
Обратная сторона подобной гибкости концепции, разумеется, скорость (о чем справедливо указывали коментаторы предыдущего поста по прологу, впрочем коммерческие реализации пролога обладают довольно недурной производительностью).
Однако соблазнительная сторона такого подхода — возможность чрезвычайно выразительного (пусть, возможно, и не быстрого) решения на прологе задач символьных вычислений, парсинга текста и сложных структур данных (в т.ч. по грамматикам), задачах поиска, экспертных системах, задачах искуственного интеллекта.
Как-то гуляя по просторам сайта рефал-сообщества (еще один интересный язык программирования, местами идейно перекликающийся с прологом), наткнулся на сравнение Refal’а с Java’ой на примере решения конкретной задачи http://wiki.botik.ru/Refaldevel/ForJavaProgrammer (собственно первоисточник — тут http://nuclight.livejournal.com/111696.html ). Для интереса написал решение на прологе (написание заняло
% если равны первый знак патерна и строки, или первый знак паттерна «?»
% то для соответствия должны соответствовать «хвосты» строки и паттерна
matches([ H | T ], [ H1 | T1 ]) :-
и проверка (остальные тест-кейсы опустил из-за того, что очень длинные строки распирают страницу сайта)
PROLOG для программистов
Язык логического программирования PROLOG (далее – ПРОЛОГ) большинству программистов представляется чем-то запутанным и малопригодным для практического применения. В то же время, Интернет основан на символьной информации, поэтому практически все современные программисты сталкиваются с необходимостью обрабатывать символьные структуры данных, а ведь для этого и предназначен язык логического программирования ПРОЛОГ. Этот язык – идеальный для работы с символьными структурами, текстовыми файлами и для построения интеллектуальных программ.
После многолетней работы с ПРОЛОГом, столкнулся с новомодным Haskell, о котором все авторы гордо говорят – «высокий порог вхождения». По-моему, «высота» этого порога образовалась в результате запутанного синтаксиса и нагромождения встроенных процедур. Еще один источник этой «высоты» — высокомерие авторов многочисленных руководств, которые написаны так, будто читатель никогда программ не писал.
Сразу захотелось назад, к «родному» ПРОЛОГу – простому и понятному. Думаю, если объяснить без нагромождений, типа декларативной семантики, время вхождения в логическое программирование для «обычного» программиста не превысит 30 минут.
Попробую описать его с точки зрения процедурного программирования.
ПРОЛОГ имеет два основных отличия от процедурных языков — способ организации вычислений и способ представления данных. Оба этих аспекта языка коренным образом отличаются от традиционных языков программирования. Но не будем забывать, что логическое программирование реализуется на тех же машинах с фон — Неймановской архитектурой.
Представим себе язык программирования, в котором все операции сводятся к вызову процедур. При этом каждая процедура существует в нескольких вариантах и программа сама выбирает себе правильный, точнее говоря, пригодный для каждого конкретного варианта исходных данных вариант реализации (тело) процедуры. Как определяется пригодность – каждый вызов процедуры, во время исполнения программы, по результатам исполнения процедуры, получает логическое значение – TRUE или FALSE. Совокупность процедур с одинаковым именем и арностью называется предикатом.
Каждый предикат в языке ПРОЛОГ идентифицируется двумя параметрами –именем и арностью – количеством параметров. Например, предикат инвертирования списков идентифицируется, как nrev/2, а предикат соединения списков как append/3. Никакого объявления параметров или переменных не требуется, но можно ограничить параметры паттерном в заголовке процедуры. Например, в одном варианте предиката первый параметр может быть указан как [] – пустой список, в другом – как [A,B,C] – список из трех элементов, а в третьем как [H|T] – произвольный непустой список.
Если какое-то условие в теле процедуры не выполняется, выполнение прекращается и вызов процедуры, точнее говоря, выполнение очередного варианта тела процедуры, прекращается и получает значение FALSE. В этом случае, интерпретатор языка запускает следующий по порядку вариант тела этой процедуры. Если же все варианты оказались непригодными, происходит возврат к предыдущей процедуре и для нее также происходит перебор вариантов, таким образом, вычисление в ПРОЛОГе сводится к обходу дерева вложенности процедур.
Возврат к предыдущему вызову называется бэктрекингом (backtracking). По существу это откат, поскольку все значения, полученные переменными в отмененной процедуре, отменяются. Бэктрекинг – уникальное средство данного языка, не имеющее аналогов ни в одном из других массовых языков программирования. Бэктрекинг обеспечивает полный обход дерева логического вывода, что обеспечивает основу для решения интеллектуальных задач.
Алгоритм интерпретации программы (выполнения цели) в системе ПРОЛОГ.
1. Найти в памяти процедуру по имени p с арностью n.
2. Унифицировать входные параметры цели с заголовком найденной процедуры.
3. Если унификация параметров прошла, выполнить первую цель из тела найденной процедуры.
4. Если унификация не прошла, найти следующий вариант процедуры P/n.
5. Если следующий вариант процедуры P/n не найден, закончить работу с результатом FAIL.
6. Если первая цель выполнилась, перейти к выполнению следующей цели.
7. Если следующая цель не выполнилась, вернуться к предыдущей цели и выполнить следующий вариант ее реализации.
8. Если текущий вариант реализации процедуры P/n не выполнился, перейти к следующему варианту.
9. Если все цели из тела процедуры выполнены, закончить работу с результатом TRUE.
В связи с такой структурой вычислений каждый вызов процедуры называется целью, которая может быть достигнута или нет. Всякое вычисление в ПРОЛОГе имеет логическое значение. Вычисление еще называют поиском вывода (доказательства), а язык ПРОЛОГ – языком логического программирования.
Наверное, синтаксически ПРОЛОГ – самый простой среди языков программирования. Основной синтаксической процедурой является предикат – выражение, аналогичное вызову процедуры — имя и список аргументов –
P(x1, …xn). Имена пишем с малой буквы, а переменные – с большой.
Если опустить детали, синтаксис ПРОЛОГа можно описать следующим образом:
Проверка связи списков:
Здесь символ “;” означает запрос другого варианта решения путем запуска бэктрекинга.
В ПРОЛОГе принято различать вычисления с бэктрекингом (недетерминированные) и без него (детерминированные).
Пример недетерминированного предиката: Решение числовой головоломки.
/*
D O N A L D
+
G E R A L D
— R O B E R T */
sum1(L1,L2,L3,L11,L12,L13,Ii,Lv):-
dl(L11,L111,E1),
dl(L12,L121,E2),
dl(L13,L131,E3),
val(E1,Lv,Lv1),val(E2,Lv1,Lv2),val(E3,Lv2,Lv3),
sd(E1,E2,E3,Ii,Io),
sum1(L1,L2,L3,L111,L121,L131,Io,Lv3).
sd(A,B,C,Ii,Io):-
C1 is A+B+Ii,
C is C1 mod 10,
Io is C1 // 10.
s:-
A1=[D, O, N, A, L, D],
A2=[G, E, R, A, L, D],
A3=[R, O, B, E, R, T],
sum(A1,A2,A3),
write(A1),nl,
write(A2),nl,
write(A3),nl.
Предикат sum/3 выполняет основную операцию подбора значений цифр для заданной буквенной формулы. Вычисление проводится для формулы сложения двух чисел любой длины. При наличии известных цифр можно их вставлять вместо переменных. Если длина слагаемых различна, можно вставить нули в начале соответствующего списка.
Предикат sum1/8 использует первые три аргумента для записи результата, аргументы под номером 4,5,6 – в качестве рабочих переменных, седьмой аргумент – начальное значение разряда переноса, восьмой аргумент – список допустимых значений цифр.
Предикат dl/3 выполняет выбор и удаление последнего элемента из списка переменных.
Предикат val/3 выбирает допустимое значение из списка оставшихся вариантов, при этом выбранный вариант цифры, удаляется из списка допустимых вариантов.
Если вариант значения для очередной буквы устанавливался ранее, то он остается без изменений.
Предикат sd/5 проверяет вариант заданной тройки цифр одного столбца:
Если sd/5 не выполняется, возникает бэктрекинг — последний из вызовов предиката val/3 присваивает новое значение переменной E3. Если ни одно из значений E3 не подошло, бэктрекинг продолжается на шаг назад — для E2 выбирается новое значение, затем – если не подойдет ни один вариант E3 E2, для E1.
Предикат sum1/8 выполняется рекурсивно до исчерпания входного списка переменных.
Предикат s/0 – пример вызова предиката sum/3 для решения одного варианта головоломки.
Как видно из примера, программа на ПРОЛОГе может быть очень компактной, при этом алгоритм прост и прозрачен, поскольку никакие неявные вызовы функций не используются.
Можно развивать программу решения таких головоломок, например, сделать ее универсальной – для всех типов числовых ребусов, улучшить ввод исходных данных.
Для этого надо делать такие операции как лексический и синтаксический анализ. Эти операции рассмотрим во второй части.
Prolog — удивительный язык программирования
— Чем же он удивительный? Я знаю пару десятков языков и для меня не проблема изучить еще один новый, я просто уже не вижу необходимости.
Пролог — уникален. Это единственный язык представляющий парадигму декларативного программирования; это язык, который имеет сотни различных имплементаций, но они все равно называются Prolog, добавляя лишь префиксы и суффиксы к названию; это живой язык в котором не происходит никаких существенных изменений более 20 лет; это, наверное, единственный настолько популярный язык программирования, который не имеет применения в реальном программировании. Почему же Prolog?
Пролог — уникален по своей природе, он появился благодаря счастливому совпадению (таинственному устройству мира). Когда-то в 60-х годах очень бурно развивалась теория автоматического доказательства теорем и Робинсоном был предложен алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно). Как оказалось позже, это наилучшее решение общей задачи, невозможно доказать теорему за ограниченное число операций. Простыми словами, алгоритм представляет собой обход (в общем случае бесконечного) графа в ширину, естественно, что предсказуемость работы алгоритма практически равно 0, соответственно для Языка Программирования — это абсолютно не подходит. И в этот момент Кальмэроу нашел блестящее сужение задачи, благодаря которому доказательство некоторых теорем выглядело как процедурное исполнение программы. Стоит отметить, что класс доказуемых теорем достаточно широк и очень хорошо применим для класса программируемых задач. Вот так в 1972 появился Prolog.
В этой статье я попытаюсь рассказать о Prolog как инструменте решения общих логических задач. Этот топик будет интересен тем, кто уже владеет синтаксисом Prolog и хочет понять его изнутри, а также тем, кто абсолютно не владеет синтаксисом языка, но хочет понять его «изюминку» не тратя лишнее время на изучение синтаксических конструкций.
Главной чертой Prolog является то, что его можно легко читать, но очень тяжело писать, что принципиально отличается от всех mainstream языков, которые так и говорят писать стало еще легче еще один шаг и можно будет писать на планшете, перетягивая рабочие модули как друзей в Google+, от этого все мы знаем очень сильно страдает само качество кода. Вроде бы каждая строчка понятна, но как система работает за гранью понимания даже для разработчиков, как говорится наиндусили. Мне кажется во всех книгах по обучению Prolog, делают одну и ту же ошибку, начиная рассказ о фактах, отношениях, запросах и у человека складывается отношение к языку как к Экспертной Системе или Базе Данных. Гораздо важнее научится правильно читать программы и почитать так с десяток 🙂
Как правильно читать программы на прологе
Читать программы очень просто, так как в языке очень мало специальных символов и ключевых слов и они легко переводятся на естественный язык. Главная ошибка программиста, что он хочет сразу представить как программа работает, а не прочитать, что программа описывает, поэтому мне кажется обучить незатуманенный мозг обычного человека, гораздо проще чем програмиста.
Понятия
Программа
Программа — это набор правил, вида Если условие1 и условие2 и… то верно условие. Формально эти правила объединяются через И, но противоречие получить невозможно, так как в Прологе отсутствует логическое отрицание, а в связке То может присутствовать только один предикат (условие).
Как видно имя переменной имеет область видимости — это правило. Математически верно, правило звучит: для любой переменной — «Число», если оно простое и нечетное, то оно простое_нечетное. Аналогично, можно перефразировать так: Если существует «Число», что оно нечетное и простое, то оно нечетно_простое. Поэтому имя переменной очень важно! Если в левой части (до :- ) заменить Число на Число2, то правило поменяет смысл: Для любого Число2 и Число, если Число — простое и нечетное, то Число2 — простое нечетное. Получается все числа простые_нечетные! Это самая распространенная ошибка в Прологе.
Пример — совершенные числа
Программа — как набор определений
Данный способ чтения широко применяется, так как позволяет объединять предикаты в однородные группы и помогает понять, в каком же порядке интерпретатор раскручивает предикаты, для того, чтобы
проверить истинность некоторого утверждения. Например, очевидно, что если предикат не имеет ни одного определения, то доказать истинность утверждения с ним невозможно. В примере № 1 не имеет определения предикат «делится_на».
Интересный факт, что в Прологе нет ни циклов, ни присвоения переменных, ни объявления типов, а если вспомнить еще про термы и отсечение, то язык становится алгоритмически полным.
Термы
С точки зрения программирования терм можно объяснить гораздо проще: терм — это объект с набором атрибутов, атрибуты могут быть другими термами или константами или переменными (то есть не определены). Главное отличие, все объекты в Prolog immutable, то есть менять атрибуты в них нельзя, зато есть специальное состояние — переменная.
Пример — целочисленная арифметика
Как Prolog понимает предикаты и как доказывает утверждения
Конечно чтение программ, помогает ощутить стиль Пролог, но не делает понятным для чего и как данные определения могут использоваться. Полноценной программой, примеры приведенные выше, назвать нельзя так как не хватает входной точки. Входной точкой в Пролог является запрос, аналог запроса к базе данных SQL или аналог вызова главной функции в функциональном программировании. Примеры запросов: нат(Число) — найти натуральное число, плюс(0, 0, Результат) — найти результат сложения 0 и 0 в переменной Результат, нат(0) — проверить является ли 0 натуральным числом и др.
Конечно, результаты запросов не трудно предсказать из логических соображений, но крайне важно понять, как программа их получила. Все-таки Пролог не черный ящик, а язык программирования, и в отличие от базы данных, где строится SQL-план и запрос может выполняться по-разному на разных Базах данных, Пролог имеет вполне определенный порядок выполнения. Дело в том, что в Базе данных мы вполне знаем какой ответ мы хотим получить исходя из данных в таблице, к сожалению глядя на Пролог программы достаточно сложно сказать, какие утверждения логически выводимы, поэтому понять как работает Пролог интерпретатор гораздо проще.
Рассмотрим на примере запроса плюс(0, 0, Результат) :
1. Находим совпадение (своеобразный pattern-matching, резолюция) данного запроса с левой частью одно из правил. Для данного запроса плюс(0, Число, Число). Соотнесем поочередно все аргументы запроса с правилом и получим: 0 = 0, 0 = Число, Результат = Число. В этих уравнениях участвуют 2 переменные (Число и Результат), решив их мы получаем, что Число = Результат = 0. Так как у данного правила нет условий, мы получили ответ на заданный вопрос. Ответ: да и Результат = 0.
Запрос нат(Число) :
1. Находим 1-е совпадение с правилом, правило нат(0), решая уравнения по соответствию, проще говоря находя резолюцию, мы получаем Число = 0. Ответ: да и Число = 0.
Грамотное составление правил на языке Пролог, очень сложная штука, но если их составить компактно, то можно получать не только прямые ответы и решения, но и обратные.
Пример запроса плюс(Число, Число, Число): ответ да, Число = 0.
Пример запроса плюс(0, 0, 0): ответ нет, при первой же попытке все резолюции не выполняются.
Пример запроса плюс(Число, Число, число(Число)): ответ да, Число = 1. Решение уравнения X + X = X + 1.
Попробуйте провести вывод для умножить(Число, число(0), число(0)), для этого потребуется 2 раза заносить в стек переменные и вычислять новый запрос. Суть Пролог машины такова, что вы можете отказаться от 1-го результата, тогда Пролог вернется к предыдущему состоянию и продолжит вычисление. Например запрос нат(Число), сначала применит 1-е правило и выдаст 0, а затем применит 2-е правило + 1-е правило и выдаст число(0), можно повторить и получить бесконечную последовательность всех натуральных чисел. Другой пример, запрос плюс(Число, число(0), Число2), будет выдавать последовательность всех пар решения уравнения X + 1 = Y.
Заключение
К сожалению, разумный размер топика, не дал мне подобраться к главной теме, а именно к решению сложных логических задач на языке Пролог, не обладая стратегией их решения. Большие куски кода на Прологе могут отпугнуть не только начинающих, но даже опытных программистов. Цель данной статьи показать, что программы на Прологе могут простым образом читаться на естественном языке, а также исполняться простейшим интерпретатором.
Главная особенность Пролога — это не черный ящик и не библиотека, который решает сложные логические задачи, в Mathematica можно ввести алгебраическое уравнение и она выдаст решение, но последовательность выполняемых шагов — неизвестна. Пролог не может решать общие логические задачи (у него отсутствует логическое «или» и «отрицание»), иначе бы его вывод был недетерминированный как линейной резолюции. Пролог — это золотая середина, между простым интерпретатором и машиной для доказательства теорем, сдвиг в любую сторон приводит к потери одного из свойств.
В следующей статье я бы хотел рассказать, как решаются задачи сортировки, о последовательности переливаний, Miss Manners и другие известные логические задачи. Для тех, кто почувствовал себя неудовлеторенным хочу предложить следующую задачу (решившему первым приз):
Написать предикат, который бы генерировал, бесконечную последовательность натуральных чисел, начиная с 3. Это должны быть стандартные числа в Прологе, операции над которыми выполняются при помощи предиката is: X is 3 + 1 => X=4.