Учебник Prolog для начинающих

Программа курса

1. 1 Логическая парадигма

   1. Что такое логическое программирование

      Логическое программирование как третья парадигма: вы описываете, ЧТО истинно, а не КАК вычислять. Связь с логикой предикатов и декларативностью.

   2. Декларативность: ЧТО против КАК

      Декларативный против императивного: программист задаёт отношения и факты, а движок вывода сам ищет решение. Сравнение кода и роль механизма вывода.

   3. Что такое Prolog и где он применяется

      История Prolog (Колмероэ, 1972, PROgrammation en LOGique), области применения: ИИ, экспертные системы, NLP, базы знаний, IBM Watson. Сильные и слабые стороны.

   4. Установка SWI-Prolog и первые шаги

      Установка SWI-Prolog на Windows, macOS и Linux, запуск интерпретатора swipl, загрузка файла через consult, первые запросы в ?- и выход через halt.

2. 2 Факты, правила и запросы

   1. Факты и база знаний

      Что такое факт в Prolog, синтаксис parent(tom, bob), предикаты и аргументы, имена-атомы со строчной буквы и из чего собирается база знаний.

   2. Запросы: как Prolog отвечает

      Запросы в Prolog: знак ?-, поиск факта в базе, ответ true/false, переменные в запросе и подстановки, перебор решений через точку с запятой.

   3. Правила и логический вывод

      Правила Prolog: запись head :- body, оператор :- как «если», конъюнкция-запятая (И) и дизъюнкция ; (ИЛИ), вывод новых фактов на примере grandparent и sibling.

3. 3 Переменные, унификация и термы

   1. Переменные и унификация

      Переменные Prolog пишутся с большой буквы. Унификация — это сопоставление термов, а не присваивание. Операторы = и \=.

   2. Анонимная переменная и сопоставление

      Анонимная переменная _ в Prolog означает «значение неважно». Каждое _ независимо. Паттерн-матчинг по структуре терма.

   3. Термы, функторы и арность

      В Prolog всё — терм: атомы, числа, переменные, составные термы. Функтор и арность name/N, оператор =.. (univ), сравнение @<, ==, \==.

4. 4 Бэктрекинг и рекурсия

   1. Бэктрекинг: поиск с возвратом

      Как Prolog перебирает решения сверху вниз: точки выбора, откат при неудаче, точка с запятой для запроса всех ответов и дерево поиска.

   2. Рекурсия в Prolog: предки

      Рекурсивное правило ancestor: предок — это родитель или родитель предка. Базовый и рекурсивный случай, ход вывода и опасность левой рекурсии.

   3. Пути в графе

      Граф как факты edge/2, рекурсивный предикат path, проблема циклов и бесконечного поиска, накопление посещённых узлов в списке Visited.

5. 5 Списки

   1. Нотация списков [H|T]

      Нотация списков в Prolog: пустой список, [1,2,3], голова и хвост [H|T], вложенная структура и сопоставление списков по образцу через унификацию.

   2. Рекурсивная обработка: member и length

      Рекурсия над списками в Prolog: реализуем member/2 и length/2 сами через [H|T], считаем сумму sum_list, разбираем базу и шаг рекурсии и трассировку.

   3. append и обработка списков

      Реализуем append/3 в Prolog сами, разбираем его обратимость и генерацию всех разбиений списка бэктрекингом, строим reverse и last через append.

6. 6 Арифметика и управление поиском

   1. Арифметика: оператор is

      Почему оператор = в Prolog не вычисляет арифметику, как работает is и чем отличаются сравнения =:=, =\=, меньше, больше, =< и >=.

   2. Отсечение cut (!)

      Отсечение ! в Prolog: как cut отбрасывает точки выбора, чем зелёное отсечение отличается от красного и в чём его опасности.

   3. Отрицание как неудача (\+)

      Отрицание как неудача \+ в Prolog: замкнутость мира, отличие от логического отрицания, ловушка с переменными и связь с cut-fail.

   4. Динамика базы знаний: assert и retract

      Динамические предикаты в Prolog: dynamic, assert/asserta/assertz и retract — накопление состояния, мемоизация и почему это «грязно».

7. 7 Недетерминизм, головоломки и ограничения

   1. Сбор всех решений: findall, bagof, setof

      Как собрать все решения цели Prolog в список: findall, bagof, setof и aggregate_all. Различия, ловушки пустого списка и сортировки с дедупликацией.

   2. Генерация и проверка (generate-and-test) и головоломки

      Парадигма generate-and-test в Prolog: генерируй кандидата — проверяй ограничение. Зебра-загадка Эйнштейна и раскраска карты на permutation и member.

   3. Программирование в ограничениях CLP(FD)

      Обзор CLP(FD) в Prolog: переменные над конечными доменами, ограничения #=, #\=, домен ins, all_different, labeling. Судоку и SEND+MORE=MONEY.

8. 8 DCG, парадигмы и применения

   1. Грамматики DCG

      Определённо-клаузальные грамматики DCG в Prolog: нотация стрелки, разбор токенов через phrase/2, разностные списки под капотом и генерация фраз.

   2. Prolog против императивного и функционального

      Чем логическая парадигма Prolog отличается от императивной и функциональной: состояние против отношений, унификация, бэктрекинг и связь с Haskell.

   3. Применения Prolog в реальном мире

      Где Prolog работает на практике: экспертные системы, базы знаний, IBM Watson, конфигураторы, верификация, NLP, планирование — и куда двигаться дальше.