4762

Основные понятия языка Prolog

Реферат

Информатика, кибернетика и программирование

Основные понятия языка Prolog. Теоретические принципы Пролога Синтаксис языка Prolog Теоретические принципы Пролога Пролог существенно отличается от языков, традиционно используемых в программировании. В языках Бейсик, Алгол и Паскаль о...

Русский

2012-11-25

112 KB

71 чел.

Основные понятия языка Prolog.

  1.  Теоретические принципы Пролога
  2.  Синтаксис языка Prolog

Теоретические принципы Пролога

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

Свое название Пролог получил от слов «Программирование на языке ЛОГики». На самом деле Пролог не считается чистым языком логического программирования, но его создание - важный этап в этом направлении. Большой интерес к Прологу проявляют специалисты в области инженерии знаний и искусственного интеллекта. Растет его популярность в академическом мире.

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

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

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

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

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

ПРОЛОГ является языком исчисления предикатов. Предикат – это логическая формула от одного или нескольких аргументов. Можно сказать, что предикат – это функция, отображающая множество произвольной природы в множество {ложно, истинно}. Обозначаются предикаты F(x), F(x, y), F(x, y, z) и   т. д. Одноместный предикат F(x), определенный на предметной области M, является истинным, если у объекта x есть свойство F, и ложным – если этого свойства нет.

Двухместный предикат F(x, y) является истинным, если объекты x и y находятся в отношении F. Многоместный предикат F(x1 , x2 , x3 ,..., xN ) задает отношение между элементами x1, x2, ..., xN и интерпретируется как обозначение высказывания: “Элементы x1 , x2, xN находятся между собой в отношении F”. При разработке логических программ предикаты получают обычно названия, соответствующие семантике описываемой предметной области.

Мы не будем употреблять термины «истинно» и «ложно», поскольку они определяют смысл результата. Доказанное утверждение обычно является истинным, но не обязательно, так как доказательство зависит от известных фактов и сделанных на их основе выводов. Итак, мы ввели два новых термина. Факт есть некоторое утверждение, все факты определяются как доказанные. В частности, факт «рекс - это собака» считается доказанным по определению. Но такой запрос к факту, как «Является ли феликс собакой ?», не будет доказан с помощью известных фактов. Отрицательный ответ системы Пролог означает вовсе не то, что утверждение «феликс - собака» ложно, а лишь то, что у нас нет фактов о «феликсе» и о том, является ли он собакой. Другим термином, который мы использовали, был вывод. Имея множество фактов, мы можем определять новые свойства описанных в них объектов. Иными словами, допускается вывод свойств из фактов. Вернемся к факту «реке - это собака». Предположим, мы хотим на основе известных фактов выявить все объекты, обладающие свойством «быть собакой». Задав вопрос «Какие существа являются собаками?», получим ответ: «Рекс - это собака». Мы привели тривиальный пример вывода. Введем некоторую дополнительную информацию (слайд3).

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

Объект является собакой в том случае, если он имеет свойство «быть собакой» или же имеет свойство «быть родителем» и существует объект, связанный с родителем и обладающий свойством «быть собакой».

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

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

Используемый нами синтаксис Пролога подробно будет определен позже. Пока примем, что каждый элемент, записанный строчными буквами, есть литерал. Он представляет объект и не может быть изменен. Каждое слово, начинающееся с прописной буквы (например, X, Y, Кто), является переменной. Во время выполнения программы переменным присваиваются значения. Символ ?- означает попытку согласовать, т.е. доказать следующую за ним цель (собака (Кто) является целью).

Мы определили, что рекс - это собака. Некоторый X является собакой (X называется именованной переменной) при условии, что X является родителем Y (другой свободной именованной переменной) и Y является собакой. Мы задали также условия, что голди - это родитель рекса и джок - это родитель рекса.

Синтаксис языка Турбо Пролог

Объекты данных Турбо Пролог

Система распознает тип объектов по его синтаксической форме в тексте программы. Это возможно благодаря тому, что синтаксис записи для различных типов имеет свои формы. Переменные начинаются с прописной буквы, атомы со строчной. Для изображения переменных и атомов используются буквы латинского алфавита: прописные (A, В, …, Z), строчные (a, b…z), цифры (0…9), специальные символы ( , / ( + – * / < > = : _ ).

Атомы можно создать тремя способами:

1. из цепочки букв, цифр и символа подчеркивания, начиная со

строчной буквы: x, sister, y10, x_y ;

2. из цепочки символов, заключенный в одинарные кавычки, это

используется, если надо иметь атом начинающийся с прописной

буквы: ' X ', ' Anna';

3. из специальных символов: < - - - >, = = = = . , . . . , :: =.

Объекты данных в Турбо-Прологе называются термами.

Константы представляют собой самоопределённые термы, т.е. их «значением» является их графическое представление (последовательность символов или число). Константы в Прологе используются для обозначения (именования) конкретных объектов предметной области и конкретных отношений между ними.

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

ОБЛАСТЬ ДЕЙСТВИЯ ПЕРЕМЕННЫХ

Областью действия переменной является утверждение. В пределах утверждения одно и то же имя принадлежит одной и той же переменной. Два утверждения могут использовать одно имя переменной совершенно различным образом. Единственным исключением из правила определения области действия переменных является анонимная переменная, например, "_" в цели любит(Х,_). Каждая анонимная переменная есть отдельная сущность.

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

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

Имя структуры = функтор(компонента-1, ...., компонента-N),

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

Если объекты структуры относятся к одному и тому же типу доменов, то такая структура называется однодоменной. Если объекты структуры относятся к разным типам доменов – многодоменная.

Объекты могут быть константами, переменными или структурами. Для того, чтобы объединить объекты в структуры, надо выбрать функтор. Каждый функтор определяется двумя параметрами:

  •  именем, синтаксис которого совпадает с именем предиката;
  •  арностью – т. е. числом аргументов.

Рассмотрим в структуру date:

 

date (1, september, 2002),

где date –  функтор, все аргументы данной многодоменной структуры являются константами.

date (Day, september,2002)

В этом примере date представляет функтор многодоменной структуры, аргументы которой являются переменные и константы.

likes ('Katja', fruits(banana, apples, oranges)),

А в этом примере likes – главный функтор, аргументы данной многодоменной структуры – константа и структура.

Рассмотренную структуру в программе можно описать следующим образом:

domains

personal_liking = fruits(type1,type2, type3)

type1, type2, type3 = symbol

predicates

likes(symbol, personal_liking)

Чтобы легче понять структуры, их обычно представляют в виде дерева, в котором каждому функтору соответствует вершина, а компонентам соответствуют ветви дерева, в соответствии с рисунками 3 и 4. Каждая ветвь может указывать на другую структуру, так что можем иметь структуры внутри структур.

Рисунок 3 – Представление структуры date в виде дерева

Рисунок 4 – Представление структуры likes в виде дерева

Нормальная форма Бэкуса-Наура (БНФ),

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

При описании синтаксиса конструкций используются следующие обозначения:

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

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

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

Символ | означает в нотации БНФ "или", он применяется для разделения различных альтернативных растолкований определяемого понятия.

Пример. Десятичную цифру можно определить следующим образом:

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

Часть синтаксической конструкции, заключенная в квадратные скобки, является необязательной (может присутствовать или отсутствовать);

Пример. Запись

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

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

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

Пример. Определить положительное целое число в нотации БНФ можно следующим образом:

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

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

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

  1.  Утверждения

   

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

  •  Объявления некоторых фактов об объектах и отношениях между ними.
  •  Определения некоторых правил об объектах и отношениях между ними.
  •  Формулировки вопросов об объектах и отношений между ними.

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

Предложения бывают двух видов: факты, правила.

Предложение имеет вид

A:-

  B1,... , Bn.

A называется заголовком или головой предложения, а B1,..., Bn - телом.

  1.  Факты 

Факт констатирует, что между объектами выполнено некоторое отношение. Он состоит только из заголовка. Можно считать, что факт - это предложение, у которого тело пустое. Например, известный нам факт, что Наташа является мамой Даши, может быть записан в виде:

мама(Наташа, Даша).

Или предположим, что мы хотим сообщить Прологу факт: «Джону нравиться Мэри». Этот факт включает в себя два объекта Джон и Мэри и отношение между ними нравится. Этот факт на Прологе можно записать следующим образом:

нравится (джон, мэри)

Важно соблюдать следующие правила:

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

Факт представляет собой безусловно истинное утверждение.

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

Если воспользоваться нормальной формой Бэкуса-Науэра, то предикат можно определить следующим образом:

<Предикат>::=<Имя> | <Имя>(<аргумент>[,<аргумент>]*),

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

Соответственно, приведенный выше пример факта можно записать в Турбо Прологе, например, так:

mother("Наташа", "Даша").

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

Приведем некоторые факты и постараемся их интерпретировать:

ценный (золото)

женщина (джейн)

владеет (джон, золото)

отец (джон, мэри)

дает (джон, книга, мэрии)

Имена объектов и отношений являются полностью произвольным. Например, вместо терма нравится (джон, мэри) мы могли с таким же успехом написать a (b,c). Но для читабельности программы, лучше всего использовать имена, которые доносят до нас какой-то смысл.

Совокупность фактов в Прологе называется базой данных.

Некоторые предикаты уже известны системе, они называются стандартными или встроенными.

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

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

В нотации БНФ правило будет иметь вид:

<Правило>::=<предикат>:-<предикат>[,<предикат>]*.

Пример. Известно, что бабушка человека - это мама его мамы или мама его папы.

Соответствующие правила будут иметь вид:

бабушка(X,Y):-

  мама(X,Z),мама(Z,Y).

бабушка(X,Y):-

  мама(X,Z),папа(Z,Y).

Символ ":-" означает "если", и вместо него можно писать if.

Символ "," - это логическая связка "и" или конъюнкция, вместо него можно писать and.

Первое правило сообщает, что X является бабушкой Y, если существует такой Z, что X является мамой Z, а Z - мамой Y. Второе правило сообщает, что X является бабушкой Y, если существует такой Z, что X является мамой Z, а Z - папой Y.

В данном примере X, Y и Z - это переменные.

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

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

     Третьим специфическим видом предложений Пролога можно считать вопросы.

  1.  Имея некоторую совокупность фактов, мы можем обращаться к Прологу с вопросами о них. Вопрос состоит только из тела и может быть выражен с помощью БНФ в виде:

<Вопрос>::=<Предикат>[,<Предикат>]*

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

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

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

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

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

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

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

мама("Наташа","Даша").

мама("Даша","Маша").

Можно спросить у системы, является ли Наташа мамой Даши. Этот вопрос можно ввести в виде:

мама("Наташа","Даша")

Найдя соответствующий факт в программе, система ответит "Yes" (то есть "Да"). Если мы спросим:

мама("Наташа","Маша")

то получим ответ "No" (то есть "Нет"). Можно также попросить вывести имя мамы Даши:

мама(X,Даша).

Система сопоставит вопрос с первым фактом, конкретизирует переменную X значением "Наташа" и выдаст ответ:

X=Наташа

1 Solution

Вопрос об имени дочери Наташи записывается в виде:

мама(Наташа,X).

Соответствующим ответом будет:

X=Даша

1 Solution

Можно попросить систему найти имена всех известных ей мам и дочек, задав вопрос:

мама(X,Y).

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

В итоге получим ответ:

X=Наташа Y=Даша

X=Даша Y=Маша

2 solutions

Если надо получить только имена всех мам, можно воспользоваться анонимной переменной и записать вопрос:

мама(X,_).

Получим ответ:

X=Наташа

X=Даша

2 solutions

И, наконец, если надо получить ответ на вопрос: есть ли информация о людях, находящихся в отношении "мама - дочка", то его можно сформулировать в виде:

мама(_,_),

В данном случае нам не важны конкретные имена, а интересует, есть ли в нашей базе знаний хотя бы один соответствующий факт. Ответом в данном случае будет просто "Yes". Система сообщит о том, что у нее есть информация об объектах, связанных отношением "мама".

Введем в нашу программу правило, определяющее отношение "бабушка - внучка", в терминах "быть мамой":

бабушка(X,Y):-

  мама(X,Z),

  мама(Z,Y).

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

бабушка("Наташа",X).

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

Это можно сделать, конкретизировав переменную Z именем "Даша". Затем система ищет предложение, в заголовке которого стоит предикат мама с первым аргументом "Даша" и каким-то именем в качестве второго аргумента. Подходящим предложением оказывается факт мама("Даша","Маша"). Система установила, что обе подцели мама("Наташа",Z) и мама(Z,Y) достижимы при Z="Даша", Y="Маша". Она выдает ответ:

X=Маша

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

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

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

При описании правил часто возникает необходимость использовать логические связки И и ИЛИ. В качестве связки И используется запятая, а в качестве связки ИЛИ – точка с запятой.

Например:

gigant(X) :- rost(X,Y),Y>200.

star_or_mlad(X) :- X>70; X<10.

ПРОЛОГ имеет большое количество встроенных предикатов, т.е. предикаты, определяемые автоматически. Например, встроенный предикат nl вызывает перевод строки, а встроенный предикат write применяется для вывода информации на экран. Встроенные предикаты используются так же, как и определяемые пользователем предикаты, но встроенный предикат не может являться головой правила или появляться в факте. Часто используемыми встроенными предикатами являются = (унификация) и логическое отрицание not.

Например:

student(X) :- X=”Петров”; X=”Иванов”.

xor_student(X) :- not(X=”Петров”), not(X=”Иванов”).

planeta(X) :- not(X=”солнце”).

Утверждение not(X = Y) эквивалентно X<>Y.

Иногда бывает полезно использовать предикаты, про которые заранее известно, истинны они или ложны. Для этих целей используют предикаты true и fail. Предикат true всегда истинен, в то время как fail всегда ложен. Последний предикат используется для управления процессом решения задачи на ПРОЛОГе.

ПРОЛОГ-программа может использовать комментарии, которые не влияют на выполнение программы, но могут оказать помощь человеку, читающему программу. ПРОЛОГ игнорирует произвольное число строк, заключенное между символами /* и */. Все, что находится между % и концом строки, также рассматривается как комментарий.

Сравнение с традиционными языками программирования.

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

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

Точнее, правило А <- В t,B 2,.. .,В„ можно рассматривать как определение процедуры:

procedure A

 call В1,

call В2

       call В

end.

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

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

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

В логическом программировании обработка данных полностью заключена в алгоритме унификации. В унификации реализованы:

однократное присваивание,

передача параметров,

размещение записей,

доступ к полям записей для одновременных чтения/записи.

Унификация

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

Например, в программе для согласования запроса ?- собака(Х) целевое утверждение собака (X) было отождествлено с фактом собака (рекс), в результате чего переменная Х стала конкретизированной: Х= рекc. Переменные, входящие в утверждения, отождествляются особым образом - сопоставляются. Факт доказывается для всех значений переменной (переменных). Правило доказывается для всех значений переменных в головном целевом утверждении при условии, что

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


 

А также другие работы, которые могут Вас заинтересовать

47193. Реалізація мультисервісної мережі 6.21 MB
  Актуальність розробки мережі У місті діє лише один провайдер який надає ряд телекомунікаційних послуг основними з яких є: місцевий внутрішньозоновий міжміський та міжнародний телефонний звязок телеграфний звязок поштовий звязок послуги передачі даних та інші. Звідси випливає і актуальність проектування нової мультисервісної мережі з наданням послуг Інтернет VoIP та IPTV.2 Сегменти й вузли проектованої мережі Визначимо категорії абонентів які будуть користуватися певними послугами мобільного інтернету–...
47194. Разработка занятий имеющих цель повторения материала по теме «Четырехугольники» 4.48 MB
  В процессе повторения у учащихся развивается память. Эмоциональная память опирается на наглядно–образные процессы, постепенно уступает памяти с логическими процессами мышления, которая основана на умении устанавливать связи между известными и неизвестными компонентами, сопоставлять абстрактный материал, классифицировать его, обосновывать свои высказывания.
47195. Возникновение моббинговых ситуаций внутри коллектива и путей выхода из них на примере магазина «Рибок» ООО «Адидас» 661.5 KB
  Проблема моббинга становится особенно актуальной в последние годы – когда страх потерять работу стал очень популярен а желание сделать карьеру любой ценой уже никого не удивляет. Для достижения поставленной цели необходимо решение следующих задач: определить понятие моббинг в организации; рассмотреть виды типы моббинга проявления и причины появления; провести анализ на наличие моббинга внутри коллектива магазина Рибок и разработать мероприятия по его устранению. Предметом исследования является наличие моббинга ситуаций на...
47196. Разработка стратегии формирования клиентоориентированного состава услуг для целевого сегмента ООО Поликлиника «УРАЛСИБ» в поддержку ее стратегии достижения рентабельного уровня 2.74 MB
  Поликлиника «УРАЛСИБ» существует более 11 лет, и первоначально строилась на средства Урало-Сибирского Банка. Услугами Поликлиники пользовались только сотрудники Банка. При этом Поликлиника полностью финансировалась Банком.
47198. Разработка системы бизнес-процессов, как инструмент повышения результативности действий персонала в поддержку стратегии компании (на примере компании «ИК Ист Коммерц») 1.08 MB
  Цель данного исследования заключалась в оптимизации портфеля БП и разработке критериев оценки эффективности организационной структуры департамента и протекающих процессов с целью повышения уровня обслуживания клиентов. Автор считал, что определение приоритетов усилий сотрудников по различным процессам и адекватное их содержание способно повысить эффективность работы Департамента брокерского обслуживания
47199. Разработка клиентоориентированной стратегии по выводу продукции в целевые розничные сети в интересах продвижения бренда компании на рынке В2В (на примере частного случая компании “Пластал”) 923.5 KB
  Исходя из отмеченного, главной целью предполагаемого исследования выступает разработка клиентоориентированной стратегии производственной компании по выводу продукции строительного назначения в целевые розничные сети (с сильными брендами) в интересах продвижения бренда компании на рынки В2В.