Обучение prolog. Язык программирования Prolog (Пролог). Версии и компиляторы

Windows 7
17.03.2024

Цель урока: Знакомство с историей языка программирования Prolog, основы работы с компиляторами


Prolog (Pro gramming in log ic) — это язык высокого уровня, не алгоритмический, предназначенный для написания программ с использованием концепций и методов .

История

Пролог был разработан в Марсельском университете во Франции Алэном Колмероэ и другими членами «группы искусственного интеллекта» в 1973 году. Данная команда энтузиастов разработала программу, предназначенную для доказательства теорем. Написана она была на Фортране, и использовалась при построении систем обработки текстов на естественном языке. Работала программа довольно медленно и назвалась Prolog (от Programmation en Logique на франц.). Программа послужила прообразом Пролога.

Язык логического программирования prolog — , что означает, что программа, написанная на нем, выглядит как набор логических описаний, определяющих цель, ради которой она и написана .

В основе Пролога лежит раздел математической логики, называемый исчисление предикатов . Его базис составляет процедура доказательства теорем методом резолюции для хорновских дизъюнктов .

Логика предикатов - это простейший способ объяснить, как «работает» мышление.

По сути, Prolog представляет собой не столько язык для программирования, сколько средство для описания данных и логики их обработки. Поскольку язык не алгоритмический, то и программа на Прологе не содержит явных алгоритмических конструкций типа условных или циклических операторов, т.е. не является программой в классическом понимании. Написанная на Прологе, она представляет собой модель фрагмента предметной области на решение проблемы которой и направлена задача. Само решение задачи записывается не в терминах компьютера, как это принято в , а в терминах предметной области решаемой задачи, по сути, в духе .

Пролог включает механизм вывода, который основан на сопоставлении образцов, с помощью подбора ответов на запросы он извлекает хранящуюся (известную) информацию.

Области применения языка Prolog и декларативных языков в целом

  • Реализация систем искусственного интеллекта.
  • Создание экспертных систем и оболочек экспертных систем.
  • Разработка систем помощи принятия решений.
  • Разработка систем обработки естественного языка.
  • Построение планов действий роботов.
  • и т.п.

Особенности языка

  • Описание проблемы и правил ее решения.
  • Нахождение всех возможных решений с помощью механизма поиска с возвратом (backtracking).
  • Легкий синтаксис.

Версии и компиляторы

На сегодня существует довольно много реализаций Пролога. Но самый первый компилятор языка был создан Уорреном и Перейрой в 1977 году в Эдинбурге, компилятор предназначался для ЭВМ DEC–10. Тот самый компилятор, известный как реализация под названием «эдинбургская версия», фактически стал первым и единственным стандартом языка и послужил прототипом для многих последующих реализаций Пролога. Интересным фактом является то, что компилятор был написан на самом Прологе.

Изучать Пролог без привязки к конкретной его версии не совсем целесообразно. Версий Пролога очень много, но мы выберем наиболее известную в России и довольно эффективную версию Пролога - Турбо Пролог . Начинала разработку версии (реализации) фирма Borland International совместно с датской компанией Prolog Development Center (PDC ). Первая версия вышла в 1986 году. Последняя совместная версия 1988 года вышла под номером 2.0.

Рис. 1. Сайт центра разработки Prolog (Prolog Developement Center)

Остальные версии начиная с 1990 года, когда PDC получила монопольное право на Турбо Пролог, продвигались под названием PDC Prolog.

Таким образом, в 1992 году вышла версия PDC Prolog 3.31, а в 1996 году, при участии группы питерских программистов, PDC выпустила систему Visual Prolog 4.0, у которой много достоинств, но мы не будем на них останавливаться.

Для работы мы выберем самый простой компилятор TPtolog (Турбо Пролог).

К достоинствам Турбо Пролога относится возможность присоединять к программе на этом языке процедуры, написанные на Паскале, Си , Фортране или ассемблере.

Для работы в Tprolog с 68 битной системой необходимо использовать программу для эмуляции DOS (например, dosbox).

Алгоритм работы с программой следующий:

  • запуск dosbox
  • mount c c:\dos\TProlog
  • c: => enter
  • prolog => enter
  • Набор кода программы в редакторе «notepad++» и сохранение с расширением.PRO в папке tprolog\labs

Работа в Tprolog

Горячие клавиши и основные команды:

  • F10 , Esc — переход в главное меню.
  • Esc — выход из текущего пункта / отмена.
  • Меню Edit — переход к редактированию кода.
  • Меню Files -> New File — создание нового файла.
  • Меню Compile -> Memory -> Меню Run — компиляция и запуск программы.

При работе в tprolog иногда возникают нестандартные ситуации, когда программа не реагирует на нажатия клавиш. Если не открывается какой-либо пункт меню – то надо несколько раз нажать клавишу i .

Запуск программы осуществляется :

  1. Через написание раздела GOAL и запуска программы в меню compile и run .
  2. Работа с окном DIALOG (в таком случае раздел GOAL в программе не нужен).

Запуск программы при использовании раздела GOAL

  • Compile — компилируем
  • Run — запускаем
  • Esc – выход в меню


Работа с окном dialog

  • Команда Run .
  • Окно dialog .
  • Запрос в виде: postroil (jack,house) .

Раздел Goal программы нельзя использовать, если работа осуществляется в окне dialog

Появление "Пролога" было обусловлено развитием логики, математики и программирования. Последнее сыграло самую существенную роль. Специалисты по логике и математике предприняли попытку поставить программирование на «правильный путь», но развитие информационных технологий показало совершенно другой результат.

Прагматичное императивное программирование оказалось перспективнее. "Пролог" как язык программирования состоялся, но основой для искусственного интеллекта не стал.

Классическое программирование против логики

Человек принимает сложные решения логично и обоснованно. Практически не задумываясь, человек поступает разумно. Если не брать в расчет решения, требующие сбора информации, ее анализа и сложных расчетов, то любой результат - это быстро, точно и обоснованно.

Этот факт всегда давал призрачное основание считать создание инструмента для принятия решений простым делом. С появлением "Пролога" казалось: вопрос искусственного интеллекта - дело техники, и человек разумный придумал три закона робототехники. Однако искусственный интеллект так и остался призраком, а три закона робототехники оказались из сказки - «сделай то, не знаю что».

Программирование в классическом значении этого слова (часто используют термины "процедурное", "императивное" или "функциональное") развивалось и успешно преодолело «смутные времена» 80-90-х годов, когда языков программирования было несчетное количество.

Показательная борьба между "Паскалем" и "Си" длилась долго, была жестокой, но закончилась нейтрально и тихо. Осталась идея хорошего языка программирования и несколько удачных ее реализаций.

Нельзя сказать, что "Пролог" как язык программирования не развивался. Но он не достиг обозначенных целей. Сегодня можно не только сказать, но и обосновать: "Пролог" - это академический язык для:

  • целей обучения;
  • логики предикатов;
  • математики;
  • узкого применения.

Сомнительно, что это утверждение можно опровергнуть. Искусственный интеллект - это не только широкое применение, но и слишком серьезное событие, кардинально меняющее общественное устройство и картину мира.

Программирование на языке "Пролог" для искусственного интеллекта не состоялось: за более чем сорокалетнюю историю языка не было ни одного кардинально нового, актуального для общественного сознания события, свидетельствующего об обратном.

Объективная реальность такова: выживает не столько сильнейшее, сколько востребованное и актуальное.

"Пролог" - язык декларативного программирования

Иметь инструмент описания фактов и правил - хорошо, но какой смысл? Факты и правила прекрасно ложатся в обычную базу данных. Квалифицированный классический программист предоставляет интерактивный диалог для пользователя, и последний решает свои задачи.

При необходимости программист дорабатывает диалог, а пользователь дополняет базу данных фактов и правил. Абсолютно рабочий и проверенный десятилетиями вариант реализации массы уже решенных и решаемых задач.

Декларативное изложение фактов и правил на любой реализации языка программирования "Пролог" - это условность, попытка формализовать реальность в ее интеллектуальном состоянии. Обычное программирование не трогает интеллект. Классическое программирование устраивает позиция: описание и обработка данных. Здесь есть масса проблем, но есть множество блестящих и работающих решений.

"Пролог" как язык программирования - это факты:

  • мама (Мария, Наташа); - Мария - мама Наташи;
  • папа (Евгений, Марина); - Евгений - папа Марины.

Здесь сразу за бортом оказывается факт: «Мария» и «Марина» - разные имена. Ничего не мешает дописать факт:

  • папа (Евгений, Мария); - Евгений - папа Марии.

Эти описания дают жизнь правилам:

  • родитель (x, y) <- папа (x, y);
  • родитель (x, y) <- мама (x, y);

Но не позволяют сделать вывод, что папа - отец Марины, а Марина - мама Марии. Эта проблема решаемая, можно дописать еще одно правило, добавить еще один факт. Но сколько таких действий следует предпринять в реальной ситуации?

Фактически "Пролог" как язык программирования - пример декларации фактов и правил, но не логика, к которой привыкло сознание классического программиста. "Пролог" позиционирует себя как язык логики предикатов, но учиться программированию на нем можно только по примерам и образцам описаний от разработчиков конкретной реализации языка.

Семейство "Прологов"

Франция считается родиной "Пролога", а 1973 год - годом рождения. Интерес к языку периодически возобновлялся, но с завидной стабильностью затихал. Девиз языка: «Логика предикатов - это элементарно! Это способ объяснить, как работает мышление» - так и остался девизом.

Любая реализация языка программирования "Пролог" строго следовала логике предикатов, но всегда включала в себя классические идеи процедурного программирования. Правильнее сказать "императивного", поскольку этот термин употребляется с большей формальностью, чем процедурное, функциональное, объектно-ориентированное или иное.

Любое программирование - это данные и их обработка. Конструкции языка должны максимально точно описывать решаемую задачу, именно поэтому все известные реализации "Пролога": Turbo Prolog, Win Prolog, SWI Prolog, GNU Prolog, Visual Prolog и другие - содержат, помимо декларативных конструкций, обычные императивные выражения.

Считается, что семейство "Прологов" развивается в академических и научно-исследовательских организациях и поэтому как об общем языке можно говорить только в концептуальном смысле. Тем не менее сам факт, что концепция "Пролога" жива и развивается, можно считать: у этого языка есть область применения, и она востребована в определенном спектре задач.

Основа искусственного интеллекта

Интерес к искусственному интеллекту никогда не ослабевал, просто о нем начинают говорить, когда появляется очередной повод, но никогда "Пролог" не ассоциировался с искусственным интеллектом больше, чем обычный классический язык программирования.

В конце 80-х годов был реальный, актуальный и востребованный интеллектуальный проект «Изобретающая машина». Была реальная попытка применить "Пролог" для формализации огромной практичной базы знаний (данных) по изобретениям, физическим, химическим и иным закономерностям.

Результат не был достигнут, слишком много фактов и правил нужно было написать на "Прологе" как языке программирования, которые носят банальный императивный характер. Между тем параллельно была реализована масса успешных программных продуктов на обычных языках.

В начале 90-х годов был успешно реализован проект реальной интеллектуальной системы, моделирующей поведение ребенка в возрасте до 3-лет на ЕС ЭВМ! Вариант использования "Пролога" даже не рассматривался.

Данная интеллектуальная система не только «соображала», что такое мама, папа, и чем отличается Мария от Марины, но и без особого напряжения самостоятельно перескочила с приобретенных знаний по этим вопросам к мячикам и их отличиям от кубиков, к цветам предметов и... (!) к элементарной математике: простые арифметические операции оказались ей по силам на основании знаний, приобретенных при решении совсем других задач.

Можно не утверждать, что классическое программирование опережает "Пролог" в части освоения территории искусственного интеллекта, но оно дает реальные результаты.

Что касается интеллекта как задачи - видимо, вопрос здесь лежит не в языке, а в идее реализации. Если ассемблер 1991 года смог «стать основой» для интеллектуальной системы ситуативного интеллекта, то вопрос явно лежит не в языке реализации, а в идее.

Данный урок посвящен базовым понятиям языка Prolog. Так, на уроке будут изучаться основы написания программ на Прологе


Для начала вспомним нормальную форму Бэкуса-Наура (БНФ) , которая была создана для формального описания синтаксиса языков программирования в 1960 году . Ее авторы — Джон Бэкус и Питер Наур.

Итак, в БНФ приняты следующие обозначения:

Символ::= читаемый как «по определению» («это», «есть»). Слева от символа располагается объясняемое понятие, справа — разъясняющая конструкция. Например,

<Имя> ::= <Идентификатор>

Части выражения, используемые для обозначения синтаксической конструкции языка, берутся в угловые скобки; в нашем примере это <Имя> и <Идентификатор> .

Символ | означает логическое «или» и применяется для разделения различных равнозначных альтернативных объяснений определяемого понятия.

Используя данный символ можно, например, определить десятичную цифру:

<цифра> ::= 0|1|2|3|4|5|6|7|8|9

Если часть конструкции заключена в квадратные скобки , то это означает, что она является необязательной, т.е. может отсутствовать.

Так запись

<Целое число> ::= [-]<Положительное целое число>

говорит о том, что целое число можно объяснить как положительное целое число, перед которым может стоять знак минус (а может и не стоять).

Символ * указывает на то, что стоящая перед ним синтаксическая конструкция может повторяться произвольное количество раз (начиная с ноля и выше). Вместо символа * иногда используются фигурные скобки ({, }), по сути равнозначные ему.

Снова определим положительное целое число, используя нотацию БНФ:

<Положительное целое число> ::= <цифра>[<цифра>]*.

Что означает, что положительное целое число состоит из одной или нескольких цифр.

Структура программы на языке Prolog

Стандартная программа на языке состоит из следующих разделов :

  1. Constants

    2. Необязательный раздел определения констант.

  2. Domains

    3. Раздел описания доменов (аналогичен описанию типов данных).

    В Turbo Prolog можно выделить простые типы данных :
    char — символьный тип
    integer — целое число
    real — вещественное число
    string — последовательность символов типа char, которая заключена в кавычки
    symbol — последовательность букв латинского алфавита, цифр и знаков подчеркивания, которая начинается со строчной буквы (тогда без кавычек) или заключена в кавычки (тогда можно с прописной буквы)

  3. Predicates

    4. Раздел описания предикатов (аналогичен разделу описания процедур и функций); по сути представляет собой шаблон написания фактов в разделе Clauses.

  4. Clauses

    5. Утверждения (аналог: тело основной программы).

  5. Goal

    6. Целевое утверждение – «цель».

Задание prolog 2_1: Запустите компилятор . Создайте новый файл и наберите код программы, выводящий ответ на вопрос «Любит ли Мэри яблоки?» (ответ true или false). Код представлен ниже:

domains a= symbol predicates likes (a, a) clauses likes (mary, apples) .

domains a=symbol predicates likes (a,a) clauses likes (mary,apples).

Перейдите в окно Dialog (меню Run) и введите запрос:

likes(mary, apples)

likes(mary,apples)

В результате в окне должен появиться ответ true

Факты и правила

Часто программу, написанную на Прологе, называют базой знаний .

База знаний на Прологе состоит из предложений , т.е. утверждений, каждое из которых завершается точкой .

Существует два вида предложений: факты и правила .

Предложения-правила имеют вид:

A:- B1,… , Bn.

Где A — это заголовок или голова предложения, а B1,..., Bn – это тело .

Факт обычно утверждает , что между объектами выполнено некоторое отношение и состоит из :

  • отношения
  • объекта или объектов, заключенных в круглые скобки (аргументы)
  • завершается точкой (.)

Пример факта:

likes (bill, dogs) .

likes (bill, dogs).

где likes — факт
bill , dogs — аргументы факта, между которыми выполнено отношение (likes)

Т.к. отношение в математической логике принято называть предикатами , то и мы иногда будем использовать понятие «предикат» вместо «факта» или «правила» .

Таким образом, предикат (факт) может состоять либо только из имени, либо из имени и следующей за ним последовательности параметров (аргументов) , которые заключаются в скобки.

Если факт состоит только из заголовка, то можно сказать, что факт – это предложение, у которого тело пустое .

Аргументом факта или предиката может быть константа , переменная или составной объект; от их числа зависит так называемая местность (n-местность) факта.

Отличие константы от переменной: константа получает свое значение в разделе описания констант , тогда как переменная инициализируется в процессе работы программы .

В TProlog имя предиката или факта может содержать: латинские буквы, цифры, знаки подчеркивания и начинаться с буквы или знака подчеркивания.

В следующем примере наводите курсор на части конструкций, и появится подсказка:

likes (bill, dogs). - Билл любит собак.
bird (vorobej). Птица – воробей.

Таким образом, в примере likes — это имя двухаргументного предиката (факта), у которого строковая константа « bill » является первым аргументом, а « dogs » — вторым аргументом.

Аргументы с известными или постоянными значениями должны начинаться со строчных букв


Задание prolog 2_2: Дано начало программы (раздел domains и predicates) для базы данных «Возраст ребенка» . Составить факты для программы, основываясь на данных указанных разделов и следующих сведений: Ивану 2 года, Алексу 3 года, Марии — 5 лет.

domains a= symbol b= integer predicates age(a, b) clauses age(...,... ) . ... (...,... ) . ... (...,... ) .

domains a=symbol b=integer predicates age(a,b) clauses age(...,...). ...(...,...). ...(...,...).

Наберите код программы в компиляторе.

Цели

Цель — это формулировка задачи, которую программа должна решить. Цель также служит «триггером» для запуска программы.

Турбо-Пролог использует как , которые содержатся в программе, так и , которые вводятся с клавиатуры после запуска программы. Здесь существует два варианта:

  1. Если цель является фактом , то Турбо-Пролог отвечает True (истина) или False (ложь):

goal likes(mary,X).

Дословно: Что любит Мэри?


Важно: Переменные начинаются с прописных букв


* Понятие переменной в Прологе будет рассмотрено в .

Таким образом, цель состоит из взаимосвязанных предикатов. Ее структура точно такая же, как у факта. Т.е. цель зачастую совпадает с правилом или фактом .

Так, наш пример может быть как фактом, так и целью:

likes(mary,apples). — Мэри любит яблоки и Любит ли Мэри яблоки?

Алгоритм составления программы

Программа для компилятора TProlog состоит из разделов, рассмотренных в примере:

clauses likes (mary,apples). likes(mary,oranges). color(apples,red).

Факты
goal likes(mary, X) , write ("mary lyubit ", X) .

goal likes(mary,X),write("mary lyubit ", X).

Запрос

Результатом примера будет: «mary lyubit apples» .

В данном примере цель записана в виде раздела GOAL прямо в программе, но нужно иметь в виду, что чаще всего цели, требующие логический ответ (правда или ложь), записываются в окне Dialog (goal в программе тогда не пишется)

Бесконечный цикл

В примере, описанном выше, в результате выдается значение только первого из трех фактов:

clauses likes (mary, apples) . likes(mary, oranges) . color(apples, red) . goal likes(mary, X) , write ("mary lyubit ", X) .

clauses likes (mary,apples). likes(mary,oranges). color(apples,red). goal likes(mary,X),write("mary lyubit ", X).

Результат выдает только apples . Хотя еще есть oranges.

Чтобы выдать все значения, необходимо организовать бесконечный цикл , который в коде выглядит как оператор fail , установленный в конце раздела GOAL


Раздел gaol того же примера, но с бесконечным циклом будет выглядеть так:
goal likes(mary, X) , write ("mary lyubit ", X) , nl , fail .

goal likes(mary,X),write("mary lyubit ", X),nl,fail.

nl — означает переход на следующую строку (каждое значение выводится с новой строки).
Результат:
«mary lyubit apples» .
«mary lyubit oranges» .

Код программы целиком:

domains a= symbol predicates likes (a, a) clauses likes (mary, apples) . likes(mary, oranges) . color(apples, red) . goal likes(mary, X) , write ("mary lyubit ", X) , nl , fail .

domains a=symbol predicates likes (a,a) clauses likes (mary,apples). likes(mary,oranges). color(apples,red). goal likes(mary,X),write("mary lyubit ", X),nl,fail.

Рассмотрим еще один пример.

Пример: Составить базу фактов по стихотворению «Дом, который построил Джек» .
Составить разные запросы к базе данных (выполнить часть запросов в окне Dialog , а другую часть в разделе Goal программы).

Код программы без запросов:

domains a= symbol predicates построил (a, a) хранится (a, a) ворует (a, a) ловит (a, a) треплет (a, a) доит (a, a) бранится (a, a) будят (a, a) clauses построил (джек, дом) . хранится (пшеница, чулан_дома) . ворует (птица_синица, пшеница) . ловит (кот, птица_синица) . треплет (кот, птица_синица) . треплет (пес, кот) . доит (старушка, корова) . бранится (пастух, старушка) . будят (два_петуха, пастух) .

domains a=symbol predicates построил (a,a) хранится (a,a) ворует (a,a) ловит (a,a) треплет (a,a) доит (a,a) бранится (a,a) будят (a,a) clauses построил (джек,дом). хранится (пшеница, чулан_дома). ворует (птица_синица, пшеница). ловит (кот, птица_синица). треплет (кот, птица_синица). треплет (пес, кот). доит (старушка, корова). бранится (пастух, старушка). будят (два_петуха, пастух).

Выполнение запросов в окне dialog:

Построил (Х, дом). /*Кто построил дом?*/

Ответ: Х=Джек

? – ловит (кот, Y) /*Кого ловит кот?*/

Ответ: Y= птица_синица

? – хранится (X, чулан_дома), ворует (X,Y). /*Что хранится в чулане дома и кто ворует это */

Ответ: X = пшеница, Y= птица_синица

Выполнение запросов в разделе Goal:

goal postroil(X, house) , write (X) , nl , fail .

goal postroil(X,house),write(X),nl,fail.

Задание prolog 2_3:

  1. Составить базу данных «Именины и хобби друзей» .
  • чьи именины в сентябре?
  • когда именины у Ивана?
  • кто любит танцы?
  • кто любит книги и спорт?
  • что любит Петр?
domains a= symbol b= integer predicates birthday(a, b, a) likes(a, a) clauses birthday(nataly, 8 , september) . birthday(yana, 25 , august) . birthday(nina, 28 , september) . birthday(peter, 2 , august) . birthday(ivan, 12 , august) . likes(nataly, books) . likes(nataly, sport) . likes(yana, books) . likes(yana, dances) . likes(peter, music) . likes(peter, dances) . likes(ivan, sport) . likes(ivan, books) . Goal /* birthday(X,Y,september),write(X," rodilas ", Y, " sentyabrya"),nl,fail.*/

domains a=symbol b=integer predicates birthday(a,b,a) likes(a,a) clauses birthday(nataly, 8, september). birthday(yana, 25, august). birthday(nina, 28, september). birthday(peter, 2, august). birthday(ivan, 12, august). likes(nataly, books). likes(nataly, sport). likes(yana, books). likes(yana, dances). likes(peter, music). likes(peter, dances). likes(ivan, sport). likes(ivan, books). Goal /* birthday(X,Y,september),write(X," rodilas ", Y, " sentyabrya"),nl,fail.*/ … , write(…), nl, fail.

Задание prolog 2_4:

  1. Составить базу данных «Предметы и преподаватели» , содержащую информацию о названии предмета, должности и фамилии преподавателя, номер семестра, отчетность.
  2. Составить запросы к базе данных, исходя из приведенных ниже:
  • по каким предметам экзамен?
  • какой предмет и когда читает доцент морозов?
  • какая отчетность по тои?
  • кто и когда читает ПРЗ?
domains a= symbol b= integer predicates teach(a, a, a, b) vedomost(a, a) clauses teach(prz, assistent, ivanova, 2 ) . teach(toi, docent, morozov, 4 ) . teach(mpi, docent, petrova, 5 ) . vedomost(toi, exam) . vedomost(prz, zach) . vedomost(mpi, exam) . Goal /* vedomost(X,exam) ,write("exam po predmetu ", X),nl,fail. */ … , write (…) , nl , fail .

domains a=symbol b=integer predicates teach(a,a,a,b) vedomost(a,a) clauses teach(prz, assistent,ivanova,2). teach(toi, docent, morozov,4). teach(mpi,docent, petrova, 5). vedomost(toi, exam). vedomost(prz, zach). vedomost(mpi, exam). Goal /* vedomost(X,exam) ,write("exam po predmetu ", X),nl,fail. */ … , write(…), nl, fail.

* Для удобства после выполнения очередного запроса, комментируйте его (/* ... */) и приступайте к написанию кода следующего запроса.

* При использовании материалов обязательна ссылка на

Логическое программирование базируется на убеждении, что не человека следует обучать мышлению в терминах операций компьютера, а компьютер должен выполнять инструкции, свойственные человеку. В чистом виде логическое программирование предполагает, что инструкции даже не задаются, а сведения о задаче формулируются в виде логических аксиом. Такое множество аксиом является альтернативой обычной программе. Подобная программа может выполняться при постановке задачи, формализованной в виде логического утверждения, подлежащего доказательству (целевого утверждения ).

Идея использования логики исчисления предикатов I порядка в качестве основы языка программирования возникла в 60-е годы, когда создавались многочисленные системы автоматического доказательства теорем и вопросно-ответные системы. В 1965 г. Робинсон предложил принцип резолюции, который в настоящее время лежит в основе большинства систем поиска логического вывода. Метод резолюций был использован в системе GPS (general problem solver). В нашей стране была разработана система ПРИЗ, которая может доказать любую теорему из школьного учебника геометрии.

Язык программирования PROLOG (programming in logic) был разработан и впервые реализован в 1972 г. группой сотрудников Марсельского университета во главе с Колмероэ. Группа занималась проблемой автоматического перевода с одного языка на другой. Основа этого языка - исчисления предикатов I порядка и метод резолюций.

При программировании на Прологе усилия программиста должны быть направлены на описание логической модели фрагмента предметной области решаемой задачи в терминах объектов предметной области, их свойств и отношений между собой, а не деталей программной реализации. Фактически Пролог представляет собой не столько язык для программирования, сколько язык для описания данных и логики их обработки. Программа на Прологе не является таковой в классическом понимании, поскольку не содержит явных управляющих конструкций типа условных операторов, операторов цикла и т. д. Она представляет собой модель фрагмента предметной области, о котором идет речь в задаче. И решение задачи записывается не в терминах компьютера, а в терминах предметной области решаемой задачи, в духе модного сейчас объектно-ориентированного программирования.

Суть Пролога – программирование в терминах целей. Программист описывает условие задачи, пользуясь понятиями объектов различных типов и отношений между ними, и формулирует вопрос. PROLOG-система обеспечивает ответ на вопрос, находя автоматически последовательность вычисления решения, используя встроенную процедуру поиска. До 1981 г. число исследователей, занимавшихся логическим программированием, составляло около сотни во всем мире. В 1981 году PROLOG был выбран в качестве базового языка компьютеров пятого поколения, и количество исследователей логического программирования резко возросло. Одной из наиболее интересных тем исследований является связь логического программирования с параллелизмом.

Где же используется Пролог в настоящее время? Это область автоматического доказательства теорем, построение экспертных систем, машинные игры с эвристиками (например, шахматы), автоматический перевод с одного языка на другой.

В настоящее время создано достаточно много реализаций языка Пролог: Wisdom Prolog, SWI Prolog, Turbo Prolog, Visual Prolog, Arity Prolog и т.д.

В нашем курсе будем использовать SWI Prolog. SWI-Prolog развивается с 1987 года. Его создателем и основным разработчиком является Ян Вьелемакер (Jan Wielemaker). Название SWI происходит от Sociaal-Wetenschappelijke Informatica (гол. социально-научная информатика), первоначального названия группы в Амстердамском университете, где работает Вьелемакер.

SWI-Prolog позволяет разрабатывать приложения любой направленности, включая Web-приложения и параллельные вычисления, но основным направлением использования является разработка экспертных систем, программ обработки естественного языка, обучающих программ, интеллектуальных игр и т.п. Это интерпретатор. Файлы, содержащие программы, написанные на языке SWI Prolog, имеют расширение pl.

SWI-Prolog-Editor является средой программирования для языка SWI-Prolog, включающую редактор программ с подсветкой синтаксиса, интерпретатор и отладчик программ. Основным назначением среды является обучение логическому программированию на языке Prolog.

Сначала устанавливаем SWI Prolog, затем - SWI Prolog Editor. Для запуска редактора SWI Prolog Editor необходимо запустить файл SwiplEdit.exe. Для настройки работы интерпретатора в специальном окне редактора, следует установить путь к интерпретатору, выполнив в редакторе команду Окно-Конфигурация на закладке Программы установить в строке Папка Пролога путь к интерпретатору. Там же, на закладке Настройки необходимо установить поле Codepage равным cp1251. Настройка кодовой страницы необходима для правильного сопоставления строковых констант, набранных русским алфавитом, между текстом программы в среде SWI-Prolog-Editor и языком SWI-Prolog. Для запуска программы из панели редактирования программ ее следует сохранить и нажать функциональную клавишу F9 или соответствующий значок на панели инструментов. В случае успешной загрузки на панели запросов появится:

Consult(<имя файла>).

Загрузить файл можно так же с помощью команды: [<имя файла>].

После любой модификации программу требуется заново загрузить в память. Перезапуск интерпретатора Пролога осуществляется нажатием Ctrl+F9 или соответствующего значка на панели инструментов.

Для выхода из интерпретатора Пролога используется команда: halt.

Факты и правила

Как уже отмечалось Пролог использует исчисление предикатов первого порядка. Предикаты определяют отношения между объектами. Рассмотрим дерево родственных отношений:

Рисунок 10 - Дерево родственных отношений

Пример 1: Это дерево можно описать следующей Пролог-программой.

родитель(пам, боб).

родитель(том, боб).

родитель(том, лиз).

родитель(боб, энн).

родитель(боб, пат).

родитель(пат, джим).

У нас имеется отношение родитель между двумя объектами. Описаны 6 фактов наличия отношений между конкретными объектами. Имена объектов начинаются с маленьких букв (они являются константами). В Прологе принято соглашение, что константы начинаются с маленькой буквы, а переменные – с большой. После набора такой Пролог-программы в редакторе можно загрузить программу в Пролог и задавать вопросы, касающиеся отношения родитель.

Запрос к программе набирается после приглашения?- и должен заканчиваться точкой. Для выполнения набранного запроса необходимо нажать Enter. Ответ будет выдан под запросом. Запрос может быть набран в несколько строк - для перехода на новую строку используется клавиша Enter. В том случае, если строка будет заканчиваться точкой и будет нажата клавиша Enter SWI-Prolog начнет выполнение запроса. Если возможны несколько вариантов ответа на запрос, то для получения каждого следующего используется клавиша Enter. Варианты ответов SWI-Prolog отделяет друг от друга точкой с запятой. Прекратить выполнение программы (выдачу альтернативных ответов) можно нажав клавишу «a».

Вопросы могут быть простые и сложные (в качестве связки «и» при составлении сложного вопроса используется запятая). Ответы Пролог-системы выводятся сразу после вопроса. Могут быть следующие варианты ответов:

  • No (соответствует нет или не найдены значения переменных в вопросе);

    Перечисляются возможные значения переменных в вопросе. При этом при нажатии клавиши «a» поиск решений прекращается, а при нажатии клавиши Enter, продолжается поиск новых решений до тех пор, пока не будут найдены все. Альтернативные решения разделяются точкой с запятой. Вывод завершается словом Yes, если не все решения были найдены и No, если других решений не осталось.

Вопрос относительно отношения родитель

Вопрос в Пролог-системе

Ответ Пролог-системы

Боб является родителем Пат?

родитель(боб,пат).

Пат – ребенок Лиз?

родитель(лиз,пат).

Кто родители Лиз?

родитель(X,лиз).

Кто дети Энн?

родитель(энн, X).

Кто дети Боба?

родитель(боб,X).

Есть ли дети у Лиз?

родитель(лиз,_).

Кто чей родитель?

родитель(X,Y).

Кто внуки Тома?

родитель(том,X),

родитель(X,Y).

Кто родители родителей Джима?

родитель(X,джим),

родитель(Y,X).

Итак, в простейшем случае Пролог-программа описывает факты и правила.

Факт – это безусловное утверждение (всегда истинное), характеризующее объект с некоторой стороны или устанавливающее отношение между несколькими объектами. Факт не требует доказательств. Факт имеет следующий вид:

<имя предиката>(O 1 ,O 2 ,…,O n).

Обратим внимание на то, что в конце факта ставится точка. <имя предиката> должно начинаться со строчной буквы и может содержать буквы, цифры, знаки подчеркивания. О i (i = 1,..,n) - аргументы предиката могут быть конкретными объектами (константами) или абстрактными объектами (переменными). Если конкретные объекты начинаются с буквы, то эта буква должна быть строчной.

Переменные начинаются с прописной буквы или символа подчеркивания. Переменная в Прологе, в отличие от алгоритмических языков программирования, обозначает объект, а не некоторую область памяти. Пролог не поддерживает механизм деструктивного присваивания, позволяющий изменять значение инициализированной переменной, как императивные языки. Переменные могут быть свободными или связанными. Свободная переменная – переменная, которая еще не получила значения. Она не равняется ни нулю, ни пробелу; у нее вообще нет никакого значения. Такие переменные еще называют неконкретизированными. Переменная, которая получила какое-то значение и оказалась связанной с определенным объектом, называется связанной. Если переменная была конкретизирована каким-то значением и ей сопоставлен некоторый объект, то эта переменная уже не может быть изменена.

Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно и то же имя переменной для обозначения разных объектов. Исключением из правила определения области действия является анонимная переменная, которая обозначается символом подчеркивания. Анонимная переменная предписывает интерпретатору проигнорировать значение переменной. Если в правиле несколько анонимных переменных, то все они отличаются друг от друга, несмотря на то, что записаны с использованием одного и того же символа.

Правило – утверждение, которое истинно при выполнении некоторых условий. Правило состоит из условной части (тела) и части вывода (головы). Головой правила является предикат, истинность которого следует установить. Тело правила состоит из одного или нескольких предикатов, связанных логическими связками: конъюнкция (обозначается запятой), дизъюнкция (обозначается точкой с запятой) и отрицание (означается not или \+). Правило имеет следующий вид:

<голова правила > :–­­­­ <тело правила>.

В конце правила так же ставится точка. Можно считать, что факт – это правило, имеющее пустое тело.

С помощью правил можно описывать новые отношения.

Пример: Пусть имеется двуместное отношениеродительи одноместное отношение мужчина. Эти отношения описываются в виде фактов. Опишем новое двуместное отношениедед, используя правила.Xявляется дедомY, если существует цепочка:X– родительZ,Z– родительY, при этомXдолжен быть мужчиной.

дед(X,Y):–­­­­родитель(X,Z),родитель(Z,Y),мужчина(X).

Пример: Пусть имеется двуместное отношение родитель, описанное в виде фактов. Опишем новое двуместное отношение предок, используя правила. X является предком Y, если X – родитель Y или существует цепочка людей между Х и Y, связанных отношением родитель.

предок(X,Y):–­­­­родитель(X,Y).

предок(X,Y):–­­­­родитель(X,Z),предок(Z,Y).

Эти правила можно записать по-другому:

предок(X,Y):–­­­­родитель(X,Y);­­­

родитель(X,Z),предок(Z,Y).

В данном примере получили рекурсивное определение отношения предок.

Пример. Определим двуместное отношение дальний_родственник с помощью правила, используя имеющееся отношение предок. X является дальним родственником Y, если они связаны отношением предок, но при этом не связаны отношением родитель.

дальний_родственник (X,Y):–­­­предок(X,Y),not(родитель(X,Y));­­­

предок(Y,X),not(родитель(Y,X)).

В правой части правила для сравнения можно использовать знаки @<, @=<, @>=, @> для проверки на упорядоченность, == для проверки на равенство и \== для проверки на неравенство.

Язык программирования Prolog является одним из ведущих логических языков программирования. Он был создан Аленом Колмерье (Alain Colmerauer) в 1970-х годах. Это была попытка сделать язык программирования для начинающих, который дает возможность выразить логику, а не тщательно задавать инструкциями на экране компьютера то, что хочется получить.

Пролог используется во многих программах искусственного интеллекта, но его синтаксис и семантика очень простые и ясные (первоначальная цель заключалась в обеспечении инструментом для компьютерных неграмотных лингвистов). Название Пролог акроним для ПРОграммирования в ЛОГике и широко известен при обучении основам программирования.

Пролог основан на исчислении предикатов (точнее первого порядка исчисления предикатов), однако он ограничен формулами Хорна. Программы Пролога эффективны для доказательства теорем в первом приближении. Основные понятия объединения, хвостовая рекурсии и отслеживание.

Типы данных

Пролог не использует типы данных в том виде, который нам привычен в распространенных языках программирования. Мы можем говорить о Пролог лексических элементах вместо типов данных, что непривычно в программировании для чайников.

Текст константы вводится с помощью атомов. Атом последовательность, состоящая из букв, цифр и подчеркивания, который начинается с буквы в нижнем регистре. Обычно, если это не буквенно-цифровые атомы, то необходимо, обрамлять их апострофами (например, "+" является атомом, + является оператором).

Большинство реализаций Prolog не делают различий между действительными и дробными числами.

Переменные

Переменные обозначаются строкой, состоящей из букв, цифр и символов подчеркивания, а начинается с буквы верхнего регистра. В среде Пролог, переменная не является контейнером, который может быть назначен (в отличие от процедурных языков программирования). Его поведение ближе к модели, которая похожа на объединения.

Так называемые анонимные переменные записываются в виде одного подчеркивание (_).

Термины являются единственным способом, которым Пролог может представлять сложные данные. Термин состоит из головы, которая также называется функтор (который должен быть атомом) и параметров (не ограниченные типами). Число параметров, так называемых арностей термина, является важным. Термин определяется по его голове и арности, обычно записывается как функтор / арности.
Списки

Список не является автономным типом данных, потому что он определяется рекурсивным построением (используя термин / 2 "."):

Atom - пустой список

Для удобства программиста, списки могут быть построены и разрушены в разному.

Если L является списком и X является элементом, то "." (X, L) является членом списка. Первый элемент X, за которым следует содержимое контекста L, синтаксически представляют как.

Для удобства программиста, списки могут быть построены и уничтожены в разному.

Элемент перечисление:
Предварение одного элемента:
Предварение несколько элементов:
Расширение термина: "."(abc, "."(1, "."(f(x), "."(Y, "."(g(A,rst), )))))

Строки обычно записывается как последовательность символов в кавычках. Они часто представлены в виде списков кодов символов таблицы ASCII.

Программирование на языке ПРОЛОГ сильно отличается от работы с процедурными языками. В Прологе Вы работаете с базами данных из фактов и правил, вы можете выполнять запросы к базе данных. Основной единицей Пролог является предикат, который определен, чтобы быть правдой (true). Предикат состоит из головы и числа аргументов. Например:

Здесь "cat" это голова, и "tom" является аргументом. Вот некоторые примеры запросов вы можете выполнить с помощью транслятора Пролог на основе этого факта:

Cat(tom).
yes.

Cat(X).
X = tom;
no.

Предикаты обычно определяются для выражения факта, с помощью которого программа знает о мире. В большинстве случаев, использование предикатов требует определенных соглашений. Таким образом, какая из представленных версий будет означать, что Пэт является отцом Салли?

Father(sally,pat).
father(pat,sally).

"father" в обоих случаях это голова, а "sally" и "pat"- аргументы. Однако в первом случае, Салли на первом месте в списке аргументов, а на втором Пэт на и наоборот. Первый случай является примером определения в порядке Глагол Предмет и Объект, ну а во втором примере порядок следующий Глагол Объект Предмет. Поскольку Пролог не понимает по-английски, обе версии прекрасно подходят, однако, считается хорошим стилем программирования придерживаться одного стиля, называемого соглашением, в ходе написания одной программы, чтобы потом не писать что-то вроде:

Father(pat,sally). father(jessica,james).

Некоторые предикаты встроены в язык, и позволяют Прологу уменьшить рутину повседневной деятельности (например, ввод / вывод с использованием графики и иного общения с операционной системой). Например, предикаты записи могут быть использованы для вывода на экран таким образом:

Write ("привет")

Будет отображать слово "Hello" на экране.

Правила

Второй тип заявлений в Пролог - это правила. Пример правила:

Light(on) :- switch(on).

": -" означает "если", это правило означает, light (on) верно (включен), если switch (on) это правда (иначе, если переключатель switch включен, тогда есть свет light). Правила могут также использовать переменные, переменные начинаются с большой буквы в то время как константы начинаются со строчных буквам. Например,

Father(X,Y) :- parent(X,Y),male(Y).

Это означает, "если кто-то является родителем, и он мужчина, то он является отцом". Причины и следствия могут находиться и в обратном порядке, так что это не противоречит обычной логике. Можно разместить несколько предикатов в разделе следствий, объединив их вместе, например:

Что эквивалентно нескольким объявлениям:

A:- d. b:- d. c:- d.

Но не разрешаются инструкции вида:

Что является эквивалентом "если с, то a или b". Это связано с ограничением, на накладываемым формулой Хорна.