Организация вычислительного процесса

Введение

Название “Пролог” есть сокращение для "ПРОграммирование в терминах ЛОГики". Пролог может быть использован в различных приложениях, относящихся к искусственному интеллекту:

– общение с ЭВМ на естественном языке;

– символьные вычисления;

– написание компиляторов;

– базы данных;

– экспертные системы и т.д.

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

Следует отметить некоторую трудность усвоения языка начинающими пользователями. Пролог относится к так называемым декларативным языкам, требующим от автора умения составить формальное описание ситуации. Как следствие, в языке отсутствуют управляющие конструкции типа if … then, while … do; нет даже оператора присваивания. Программа, составленная на этом языке, не содержит детального описания последовательности шагов, ведущих к результату. Однако методические трудности, связанные с обучением использованию Пролога начинающих программистов, можно успешно преодолеть на основе принципа – "делай как мы".

Организация вычислительного процесса

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

А:– В1, В2, ... , Вn,

которая интерпретируется : "А является истинным, если В1, В2, ...., Вn являются истинными". Если n=0, то такое предложение выражает факт, и это записывается "А." .

Если получен запрос (т.е. цель, которую нужно удовлетворить), Пролог пытается определить его истинность двумя способами. Во-первых, цель успешно удовлетворяется (т.е. считается истинной), если она сопоставляется с существующим фактом (так как факты всегда являются истинными). Во-вторых, цель считается истинной, если она сопоставляется с заголовком “А” правила " А, если В1, ... , Вn " и если подцели В1, ... , Вn могут быть завершены успешно. В случае успешного сопоставления Пролог выдает ответ "yes", т.е. цель согласована.

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

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

В Прологе нет оператора присваивания, а есть логическое сравнение, обозначаемое знаком равенства, поэтому понятно, что запись вида N = N+ 1 бессмысленна: величина никогда не равна самой себе, увеличенной на единицу, надо использовать другую переменную: N1 = N + 1.

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

В синтаксисе Пролога факт имеет следующий вид:

relation(object, object,.....object).

Правила имеют основную форму:

relation(object, object,.....object) :–

relation1(object, object,.....object) ,

...

relationN(object, object,.....object).

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

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

p :– q,s.

p :– r,t.

Эту программу можно прочитать следующим образом. При выполнении процедуры p выполняются процедуры q и s. Если они завершаются успешно, то и процедура p считается успешно завершенной. Если это не так, то выполняются процедуры r и t. В этом случае процедура успешно завершается, если r и t завершены успешно. В противном случае процедура p терпит неудачу. Этот процесс возврата к поиску других решений называется бэктрекингом (backtracking).

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

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