Основы программирования на языке visual prolog. Язык программирования Prolog (Пролог). Запуск программы при использовании раздела GOAL

Данный урок посвящен базовым понятиям языка 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.

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

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

Чем же он удивительный? Я знаю пару десятков языков и для меня не проблема изучить еще один новый, я просто уже не вижу необходимости.

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

Пролог - уникален по своей природе, он появился благодаря счастливому совпадению (таинственному устройству мира). Когда-то в 60-х годах очень бурно развивалась теория автоматического доказательства теорем и Робинсоном был предложен алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно). Как оказалось позже, это наилучшее решение общей задачи, невозможно доказать теорему за ограниченное число операций. Простыми словами, алгоритм представляет собой обход (в общем случае бесконечного) графа в ширину, естественно, что предсказуемость работы алгоритма практически равно 0, соответственно для Языка Программирования - это абсолютно не подходит. И в этот момент Кальмэроу нашел блестящее сужение задачи, благодаря которому доказательство некоторых теорем выглядело как процедурное исполнение программы. Стоит отметить, что класс доказуемых теорем достаточно широк и очень хорошо применим для класса программируемых задач. Вот так в 1972 появился Prolog.

В этой статье я попытаюсь рассказать о Prolog как инструменте решения общих логических задач. Этот топик будет интересен тем, кто уже владеет синтаксисом Prolog и хочет понять его изнутри, а также тем, кто абсолютно не владеет синтаксисом языка, но хочет понять его «изюминку» не тратя лишнее время на изучение синтаксических конструкций.


Главной чертой Prolog является то, что его можно легко читать, но очень тяжело писать, что принципиально отличается от всех mainstream языков, которые так и говорят писать стало еще легче еще один шаг и можно будет писать на планшете, перетягивая рабочие модули как друзей в Google+ , от этого все мы знаем очень сильно страдает само качество кода. Вроде бы каждая строчка понятна, но как система работает за гранью понимания даже для разработчиков, как говорится наиндусили. Мне кажется во всех книгах по обучению Prolog, делают одну и ту же ошибку, начиная рассказ о фактах, отношениях, запросах и у человека складывается отношение к языку как к Экспертной Системе или Базе Данных. Гораздо важнее научится правильно читать программы и почитать так с десяток:)

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

Читать программы очень просто, так как в языке очень мало специальных символов и ключевых слов и они легко переводятся на естественный язык. Главная ошибка программиста, что он хочет сразу представить как программа работает, а не прочитать, что программа описывает, поэтому мне кажется обучить незатуманенный мозг обычного человека, гораздо проще чем програмиста.
Понятия
В языке существует 2 понятия предикаты (условия) и объекты (они же переменные и термы). Предикаты выражают некоторое условие, например объект зеленый или число простое, естественно что условия имеют входные параметры. Например green_object(Object) , prime_number(Number) . Сколько в предикате параметров, такова и арность предиката. Объектами - являются термы, константы и переменные. Константы - это числа и строки, переменные - выражают неизвестный объект, возможно искомый, и обозначаются как строчки с большой буквы. Оставим пока термы и рассмотрим простейшую программу.
Программа
Программа - это набор правил, вида Если условие1 и условие2 и… то верно условие. Формально эти правила объединяются через И, но противоречие получить невозможно, так как в Прологе отсутствует логическое отрицание, а в связке То может присутствовать только один предикат (условие).

A:- B_1, B_2. % правило читается как: Если B_1 и B_2, то A
нечетное_простое(Число) :- простое(Число), нечетное(Число).
% Если "Число" - простое и нечетное, то "Число" - нечетное_простое

Как видно имя переменной имеет область видимости - это правило. Математически верно, правило звучит: для любой переменной - «Число», если оно простое и нечетное, то оно простое_нечетное. Аналогично, можно перефразировать так: Если существует «Число», что оно нечетное и простое, то оно нечетно_простое. Поэтому имя переменной очень важно! Если в левой части (до:-) заменить Число на Число2, то правило поменяет смысл: Для любого Число2 и Число, если Число - простое и нечетное, то Число2 - простое нечетное. Получается все числа простые_нечетные! Это самая распространенная ошибка в Прологе.

A:- B_1, B_2. % правило читается как: Если B_1 и B_2, то A нечетное_простое(Число) :- простое(Число), нечетное(Число). % Если "Число" - простое и нечетное, то "Число" - нечетное_простое

Пример - совершенные числа
совершенное_число(Ч) :- число(Ч), сумма_делителей_без_числа(Ч, СуммаДелителей), равно(СуммаДелителей, Ч). совершенное_число(1). равно(Объект, Объект). сумма_делителей_без_числа(1, 1). сумма_делителей_без_числа(Число, Сумма) :- число_предыдущее(Число, Предыдущее), сумма_делителей_числа_до_числа(Число, Сумма, Предыдущее). сумма_делителей_числа_до_числа(Число, 1, 1). сумма_делителей_числа_до_числа(Число, Сумма, Делитель) :- делится_на(Число, Делитель), число_предыдущее(Делитель, Предыдущее), сумма_делителей_числа_до_числа(Число, СуммаПред, Предыдущее), сложить(СуммаПред, Делитель, Сумма). сумма_делителей_числа_до_числа(Число, Сумма, Делитель) :- не_делится_на(Число, Делитель), число_предыдущее(Делитель, Предыдущее), сумма_делителей_числа_до_числа(Число, Сумма, Предыдущее).

Для начала формально прочитаем, что означают правила:

  1. Если «Ч» - число и для «Ч» и «СуммаДелителей» выполняется условие сумма_делителей_без_числа, проще говоря СуммаДелителей есть сумма делителей числа «Ч», и «Ч» равно «СуммаДелителей», то «Ч» совершенное число.
  2. 1 - совершенное число. Правила могут не иметь условий, в этом случае они называются фактами.
  3. Всякий объект «О» равен «О». В принципе существует, стандартный предикат "=", но можно вполне заменить на свой.
  4. Факт сумма_делителей_без_числа 1 равна 1.
  5. Если сумма делителей «Число» до предыдущего числа «Число» равна «Сумма», то это и есть сумма_делителей_без_числа. Таким образом выражается, сумма делителей X меньше либо равных Y, так как X делится на X, поэтому берем Y = X - 1.
  6. Далее 3 предиката определяют сумму делителей число меньше либо равных Y (Делитель), 1-й случай Y равное 1, 2-й случай Число делится на Y, тогда сумма_делителей(X, Y) = сумма_делителей(X, Y-1) + Y, и 3-й случай Число не делится на Y, тогда сумма_делителей(X, Y) = сумма_делителей(X, Y-1).
Программа - как набор определений
Существует второй способ прочтения данных правил, менее математический и более естественный, основанный на «определениях». Можно заметить, что в Прологе все правила слева (в части то) содержат только одно условие, что по сути является «определением» это условия.
Например, 1-ое правило определение совершенных чисел. «Ч» совершенное число, когда «Ч» число и сумма делителей «Ч» равна «Ч». Одинаковые предикаты группируются по имени объединяясь условием «или». То есть к определению можно добавить: «Ч» совершенное число, когда.., или когда «Ч» - это 1.

Данный способ чтения широко применяется, так как позволяет объединять предикаты в однородные группы и помогает понять, в каком же порядке интерпретатор раскручивает предикаты, для того, чтобы
проверить истинность некоторого утверждения. Например, очевидно, что если предикат не имеет ни одного определения, то доказать истинность утверждения с ним невозможно. В примере № 1 не имеет определения предикат «делится_на».

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

Термы
Термы имеют рекурсивное определение, как именованная совокупность объектов. Терм = "имя"(объект, объект, ...), пример person("Name", "Surname"), "+"(1, 2), person(address("Некоторый адрес"), surname("Фамилия"), phone("Телефон")) . Если рассматривать терм, как математическое понятие, то терм является функцией, а точнее функтором, то есть "+"(1, 2) - означает, что существует такой объект, который равен 1+2. Это абсолютно не означает, что 1+2 = 3, в Прологе - это выражение неистинно, точно так же как и в группе остатков по модулю 2, там 3 вообще не существует. Опять же с математической точки зрения Переменные связываются словом Для Всех, а если в утверждении необходимо слово существует то, для этой цели применяется терм (функтор). Для любого числа существует число-факториал:- factorial(X, fact(X)).

С точки зрения программирования терм можно объяснить гораздо проще: терм - это объект с набором атрибутов, атрибуты могут быть другими термами или константами или переменными (то есть не определены). Главное отличие, все объекты в Prolog immutable, то есть менять атрибуты в них нельзя, зато есть специальное состояние - переменная.

Пример - целочисленная арифметика
нат(0). нат(число(Число)) :- нат(Число). плюс(0, Число, Число). плюс(число(Ч1), Ч2, число(Рез)) :- плюс(Ч1, Ч2, Рез). умножить(0, Число, 0). умножить(число(Ч1), Ч2, Рез2) :- умножить(Ч1, Ч2, Рез), плюс(Рез, Ч2, Рез2).
  1. Определение свойства нат (натуральное число). 0 - натуральное число, если Число натуральное, то существует объект число(Число), которое тоже является натуральным. Математически терм «число» выражает функцию +1, с точки зрения программирования «число» рекурсивная структура данных, вот ее элементы: число(0), число(число(0)), число(число(число(0))).
  2. Отношение плюс - 0 + Число = Число. Если Ч1 + Ч2 = Рез, то (Ч1+1) + Ч2 = (Рез+1).
  3. Отношение умножить - 0 * Число = 0. Если Ч1 * Ч2 = Рез и Рез + Ч2 = Рез2, то (Ч1+1) * Ч2 = Рез2.
Очевидно эти утверждения верны для обычной арифметики, но почему тогда мы не включили такие же очевидные как Число + 0 = Число. Ответ простой: избыточность очень плохо для любого определения. Да, это может помогать вычислениям, своеобразная преждевременная оптимизация, но побочными эффектами могут быть противоречия в определениях, неоднозначный вывод утверждения, зацикливание интерпретатора.

Как 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)) :
1. Находим резолюцию с правилом плюс(0, Число, Число): Результат = 0, 0 = Число, число(0) = Число, но (!) Число = 0 = число(0) - не возможно так как 0 совпадает число(0). Следовательно ищем резолюцию со следующим правилом.
2. Находим резолюцию с правилом плюс(число(Ч1), Ч2, число(Рез)), получаем число(Ч1) = Результат, Ч2 = 0, число(Рез) = число(0), отсюда Рез = 0. У этого правила, есть условия которые мы должны проверить, учитывая результаты резолюции (значения переменных), плюс(Ч1, Ч2, Рез) -> плюс(Ч1, 0, 0). Запоминаем значение переменных в стеке и формируем новый запрос плюс(Ч1, 0, 0)
3*. Решая запрос плюс(Ч1, 0, 0) находим резолюцию с плюс(0, Число, Число) и получаем Ч1 = 0 и Число = 0.
4. Возвращаемся по стеку к предыдущим переменным Результат = число(Ч1) = число(0). Ответ найден число(0). Соответственно сейчас пролог машина решила уравнение X + 0 = 1.

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

Пример запроса плюс(Число, Число, Число) : ответ да, Число = 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.

Чем же он удивительный? Я знаю пару десятков языков и для меня не проблема изучить еще один новый, я просто уже не вижу необходимости.

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

Пролог - уникален по своей природе, он появился благодаря счастливому совпадению (таинственному устройству мира). Когда-то в 60-х годах очень бурно развивалась теория автоматического доказательства теорем и Робинсоном был предложен алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно). Как оказалось позже, это наилучшее решение общей задачи, невозможно доказать теорему за ограниченное число операций. Простыми словами, алгоритм представляет собой обход (в общем случае бесконечного) графа в ширину, естественно, что предсказуемость работы алгоритма практически равно 0, соответственно для Языка Программирования - это абсолютно не подходит. И в этот момент Кальмэроу нашел блестящее сужение задачи, благодаря которому доказательство некоторых теорем выглядело как процедурное исполнение программы. Стоит отметить, что класс доказуемых теорем достаточно широк и очень хорошо применим для класса программируемых задач. Вот так в 1972 появился Prolog.

В этой статье я попытаюсь рассказать о Prolog как инструменте решения общих логических задач. Этот топик будет интересен тем, кто уже владеет синтаксисом Prolog и хочет понять его изнутри, а также тем, кто абсолютно не владеет синтаксисом языка, но хочет понять его «изюминку» не тратя лишнее время на изучение синтаксических конструкций.


Главной чертой Prolog является то, что его можно легко читать, но очень тяжело писать, что принципиально отличается от всех mainstream языков, которые так и говорят писать стало еще легче еще один шаг и можно будет писать на планшете, перетягивая рабочие модули как друзей в Google+ , от этого все мы знаем очень сильно страдает само качество кода. Вроде бы каждая строчка понятна, но как система работает за гранью понимания даже для разработчиков, как говорится наиндусили. Мне кажется во всех книгах по обучению Prolog, делают одну и ту же ошибку, начиная рассказ о фактах, отношениях, запросах и у человека складывается отношение к языку как к Экспертной Системе или Базе Данных. Гораздо важнее научится правильно читать программы и почитать так с десяток:)

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

Читать программы очень просто, так как в языке очень мало специальных символов и ключевых слов и они легко переводятся на естественный язык. Главная ошибка программиста, что он хочет сразу представить как программа работает, а не прочитать, что программа описывает, поэтому мне кажется обучить незатуманенный мозг обычного человека, гораздо проще чем програмиста.
Понятия
В языке существует 2 понятия предикаты (условия) и объекты (они же переменные и термы). Предикаты выражают некоторое условие, например объект зеленый или число простое, естественно что условия имеют входные параметры. Например green_object(Object) , prime_number(Number) . Сколько в предикате параметров, такова и арность предиката. Объектами - являются термы, константы и переменные. Константы - это числа и строки, переменные - выражают неизвестный объект, возможно искомый, и обозначаются как строчки с большой буквы. Оставим пока термы и рассмотрим простейшую программу.
Программа
Программа - это набор правил, вида Если условие1 и условие2 и… то верно условие. Формально эти правила объединяются через И, но противоречие получить невозможно, так как в Прологе отсутствует логическое отрицание, а в связке То может присутствовать только один предикат (условие).

A:- B_1, B_2. % правило читается как: Если B_1 и B_2, то A
нечетное_простое(Число) :- простое(Число), нечетное(Число).
% Если "Число" - простое и нечетное, то "Число" - нечетное_простое

Как видно имя переменной имеет область видимости - это правило. Математически верно, правило звучит: для любой переменной - «Число», если оно простое и нечетное, то оно простое_нечетное. Аналогично, можно перефразировать так: Если существует «Число», что оно нечетное и простое, то оно нечетно_простое. Поэтому имя переменной очень важно! Если в левой части (до:-) заменить Число на Число2, то правило поменяет смысл: Для любого Число2 и Число, если Число - простое и нечетное, то Число2 - простое нечетное. Получается все числа простые_нечетные! Это самая распространенная ошибка в Прологе.

A:- B_1, B_2. % правило читается как: Если B_1 и B_2, то A нечетное_простое(Число) :- простое(Число), нечетное(Число). % Если "Число" - простое и нечетное, то "Число" - нечетное_простое

Пример - совершенные числа
совершенное_число(Ч) :- число(Ч), сумма_делителей_без_числа(Ч, СуммаДелителей), равно(СуммаДелителей, Ч). совершенное_число(1). равно(Объект, Объект). сумма_делителей_без_числа(1, 1). сумма_делителей_без_числа(Число, Сумма) :- число_предыдущее(Число, Предыдущее), сумма_делителей_числа_до_числа(Число, Сумма, Предыдущее). сумма_делителей_числа_до_числа(Число, 1, 1). сумма_делителей_числа_до_числа(Число, Сумма, Делитель) :- делится_на(Число, Делитель), число_предыдущее(Делитель, Предыдущее), сумма_делителей_числа_до_числа(Число, СуммаПред, Предыдущее), сложить(СуммаПред, Делитель, Сумма). сумма_делителей_числа_до_числа(Число, Сумма, Делитель) :- не_делится_на(Число, Делитель), число_предыдущее(Делитель, Предыдущее), сумма_делителей_числа_до_числа(Число, Сумма, Предыдущее).

Для начала формально прочитаем, что означают правила:

  1. Если «Ч» - число и для «Ч» и «СуммаДелителей» выполняется условие сумма_делителей_без_числа, проще говоря СуммаДелителей есть сумма делителей числа «Ч», и «Ч» равно «СуммаДелителей», то «Ч» совершенное число.
  2. 1 - совершенное число. Правила могут не иметь условий, в этом случае они называются фактами.
  3. Всякий объект «О» равен «О». В принципе существует, стандартный предикат "=", но можно вполне заменить на свой.
  4. Факт сумма_делителей_без_числа 1 равна 1.
  5. Если сумма делителей «Число» до предыдущего числа «Число» равна «Сумма», то это и есть сумма_делителей_без_числа. Таким образом выражается, сумма делителей X меньше либо равных Y, так как X делится на X, поэтому берем Y = X - 1.
  6. Далее 3 предиката определяют сумму делителей число меньше либо равных Y (Делитель), 1-й случай Y равное 1, 2-й случай Число делится на Y, тогда сумма_делителей(X, Y) = сумма_делителей(X, Y-1) + Y, и 3-й случай Число не делится на Y, тогда сумма_делителей(X, Y) = сумма_делителей(X, Y-1).
Программа - как набор определений
Существует второй способ прочтения данных правил, менее математический и более естественный, основанный на «определениях». Можно заметить, что в Прологе все правила слева (в части то) содержат только одно условие, что по сути является «определением» это условия.
Например, 1-ое правило определение совершенных чисел. «Ч» совершенное число, когда «Ч» число и сумма делителей «Ч» равна «Ч». Одинаковые предикаты группируются по имени объединяясь условием «или». То есть к определению можно добавить: «Ч» совершенное число, когда.., или когда «Ч» - это 1.

Данный способ чтения широко применяется, так как позволяет объединять предикаты в однородные группы и помогает понять, в каком же порядке интерпретатор раскручивает предикаты, для того, чтобы
проверить истинность некоторого утверждения. Например, очевидно, что если предикат не имеет ни одного определения, то доказать истинность утверждения с ним невозможно. В примере № 1 не имеет определения предикат «делится_на».

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

Термы
Термы имеют рекурсивное определение, как именованная совокупность объектов. Терм = "имя"(объект, объект, ...), пример person("Name", "Surname"), "+"(1, 2), person(address("Некоторый адрес"), surname("Фамилия"), phone("Телефон")) . Если рассматривать терм, как математическое понятие, то терм является функцией, а точнее функтором, то есть "+"(1, 2) - означает, что существует такой объект, который равен 1+2. Это абсолютно не означает, что 1+2 = 3, в Прологе - это выражение неистинно, точно так же как и в группе остатков по модулю 2, там 3 вообще не существует. Опять же с математической точки зрения Переменные связываются словом Для Всех, а если в утверждении необходимо слово существует то, для этой цели применяется терм (функтор). Для любого числа существует число-факториал:- factorial(X, fact(X)).

С точки зрения программирования терм можно объяснить гораздо проще: терм - это объект с набором атрибутов, атрибуты могут быть другими термами или константами или переменными (то есть не определены). Главное отличие, все объекты в Prolog immutable, то есть менять атрибуты в них нельзя, зато есть специальное состояние - переменная.

Пример - целочисленная арифметика
нат(0). нат(число(Число)) :- нат(Число). плюс(0, Число, Число). плюс(число(Ч1), Ч2, число(Рез)) :- плюс(Ч1, Ч2, Рез). умножить(0, Число, 0). умножить(число(Ч1), Ч2, Рез2) :- умножить(Ч1, Ч2, Рез), плюс(Рез, Ч2, Рез2).
  1. Определение свойства нат (натуральное число). 0 - натуральное число, если Число натуральное, то существует объект число(Число), которое тоже является натуральным. Математически терм «число» выражает функцию +1, с точки зрения программирования «число» рекурсивная структура данных, вот ее элементы: число(0), число(число(0)), число(число(число(0))).
  2. Отношение плюс - 0 + Число = Число. Если Ч1 + Ч2 = Рез, то (Ч1+1) + Ч2 = (Рез+1).
  3. Отношение умножить - 0 * Число = 0. Если Ч1 * Ч2 = Рез и Рез + Ч2 = Рез2, то (Ч1+1) * Ч2 = Рез2.
Очевидно эти утверждения верны для обычной арифметики, но почему тогда мы не включили такие же очевидные как Число + 0 = Число. Ответ простой: избыточность очень плохо для любого определения. Да, это может помогать вычислениям, своеобразная преждевременная оптимизация, но побочными эффектами могут быть противоречия в определениях, неоднозначный вывод утверждения, зацикливание интерпретатора.

Как 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)) :
1. Находим резолюцию с правилом плюс(0, Число, Число): Результат = 0, 0 = Число, число(0) = Число, но (!) Число = 0 = число(0) - не возможно так как 0 совпадает число(0). Следовательно ищем резолюцию со следующим правилом.
2. Находим резолюцию с правилом плюс(число(Ч1), Ч2, число(Рез)), получаем число(Ч1) = Результат, Ч2 = 0, число(Рез) = число(0), отсюда Рез = 0. У этого правила, есть условия которые мы должны проверить, учитывая результаты резолюции (значения переменных), плюс(Ч1, Ч2, Рез) -> плюс(Ч1, 0, 0). Запоминаем значение переменных в стеке и формируем новый запрос плюс(Ч1, 0, 0)
3*. Решая запрос плюс(Ч1, 0, 0) находим резолюцию с плюс(0, Число, Число) и получаем Ч1 = 0 и Число = 0.
4. Возвращаемся по стеку к предыдущим переменным Результат = число(Ч1) = число(0). Ответ найден число(0). Соответственно сейчас пролог машина решила уравнение X + 0 = 1.

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

Пример запроса плюс(Число, Число, Число) : ответ да, Число = 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.

Цель урока: Знакомство с историей языка программирования 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

Лекция посвящена решению задач при помощи графа пространства состояний. Пространство состояний описывается в виде множества состояний – вершин графа, множества переходов от состояния к состоянию – дуг графа, множества начальных состояний и множества конечных состояний. Решение задачи представляется в виде пути на графе пространства состояний, соединяющего начальное состояние с конечным. Если пространство состояний задачи невелико, то будут находиться все оптимальные решения с помощью поиска в глубину. В задачах с большим пространством состояний будет вычисляться только одно оптимальное решение посредством поиска в ширину. К задачам применяются универсальные решатели. Состояния в разных задачах могут принадлежать различным доменам. Для запоминания наилучших среди найденных решений используется "изменяемая переменная" varM. Компилятор сам находит нужные типы. Версия Visual Prolog 7.5, еще не опубликована. Ее публикация планируется в 2014 году, но точная дата пока не известна. Сейчас всем доступна версия Visual Prolog 7.4.