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

Автор работы: Пользователь скрыл имя, 07 Мая 2014 в 08:20, контрольная работа

Краткое описание

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

Вложенные файлы: 1 файл

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ.docx

— 27.60 Кб (Скачать файл)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

 

ФГБОУ ВПО «Уральский государственный экономический университет»

 

Центр дистанционного образования

 

 

 

 

 

Контрольная работа

по дисциплине: Основы логического     программирования________________________

по теме: Структура программы на языке Пролог

 

 

 

 

Исполнитель: студент(ка)

Направление__________

Профиль

Группа  ПИЭ-11

Ф.И.О Е.А.Тесленко.

 

 

 

 

Екатеринбург

2013

 

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

 

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

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

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

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

Фразы Хорна (Horn clause) представляют собой подмножество фраз, содержащих только один позитивный литерал. В общем виде фраза Хорна представляется выражением

В языке PROLOG эта же фраза записывается в таком виде:

р :- q1,...,qn. Такая фраза интерпретируется следующим образом:

"Для всех значений переменных  в фразе p истинно, если истинны q1 и ... и qn",

т.е. пара символов ":-" читается как "если", а запятые читаются как "и".

PROLOG — это не совсем обычный  язык программирования, в котором  программа состоит в основном  из логических формул, а процесс  выполнения программы представляет  собой доказательство теоремы  определенного вида.

Фраза в форме

р :- q1, ...,qn.

может рассматриваться в качестве процедуры. Такая процедура предполагает следующий порядок выполнения операций.

(1) Литерал цели сопоставляется  с литералом р (унифицируется с р), который называется головой фразы.

(2)Хвост фразы ql, ...,qn конкретизируется подстановкой значений переменных (или унификаторов), сформированных в результате этого сопоставления.

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

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

Например, рассмотрим набор фраз языка PROLOG, представленных в листинге 1. Предположим, что a, b и с — какие-то блоки в мире блоков. Две первые фразы утверждают, что а находится на (on) b, a b находится на (on) с. Третья фраза утверждает, что X находится выше (above) Y, если X находится на (on) Y. Четвертая фраза утверждает, что X находится выше (above) Y, если существует какой-то другой блок Z, размещенный на (on) Y, и X находится выше (above) Y.

Листинг 1. Простая программа на языке PROLOG, определяющая отношение

on (на)

on(а, b).

on(b, с).

above(X, Y) :- on(X, Y).

above(X, Y) :- on(Z, Y),

above(X, Z).

Очевидно, что от программы требуется вывести цель above (а, с) из этого множества фраз. Процесс формулировки выражения цели включает обработку двух процедур above и использование двух фраз on. В языке PROLOG используется "интерпретация фраз Хорна для решения проблем" Фундаментальный метод доказательства теорем, на котором базируется PROLOG, называется опровержением резолюций (resolution refutation).

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

  • Для представления знаний используются фразы Хорна.
  • Программа описывает логическую модель Предметной Области в виде фактов относительно свойств Предметной Области и отношений между этими свойствами + правила вывода новых свойств и отношений из уже заданных.
  • В качестве единообразной структуры данных используется терм. 
  • Отсутствуют операторы присваивания, ветвлений, безусловных переходов, а также указатели, которые используются при определении динамических структур данных в традиционных процедурно-ориентированных языках. 
    Написание программы на языке Пролог включает следующие этапы:
  1. Объявление некоторых фактов об объектах и отношениях между ними.
  1. Определение некоторых правил, касающихся объектов и отношений между ними.
  2. Формулировка вопросов об объектах и отношениях между ними. 
    Для объяснения смысла программы применяются три семантические модели: декларативная, процедурная модели и модель в виде абстрактной машины. 
            Процедурная  трактовка  Пролог-программы. 
    При процедурной трактовке Пролог-программы подчеркивается последовательность шагов, которые выполняет интерпретатор при обработке запроса. Здесь имеет значение порядок следования подцелей в правиле. 
    Множество фраз, имеющих одно и то же имя и одинаковое количество аргументов, рассматривается как процедура. При этом запрос (или подцель правила)  является  вызовом  процедуры. 
              Декларативная  трактовка  Пролог-программы. 
    При декларативной трактовке Пролог-программы специфицируются истинностные значения конкретных случаев отношений. 
    Для декларативной модели фразы Пролога являются формулами логики предикатов 1-го порядка, записанными в форме фраз Хорна. 
            Модель  в  виде  абстрактной  машины. 
    С позиций декларативной модели Пролог-программа есть описание логической структуры. При выполнении запроса интерпретатор применяет по отношению к множеству фраз Пролога некоторую стратегию решения задачи. С точки зрения вычислений эта стратегия может быть описана при помощи  некоторой  абстрактной  машины. 
           В языке Пролог запрос и множество фраз программы имеет вычислительный смысл. Это проявляется в том, что они вызывают определенное поведение интерпретатора Пролога. Модель в виде абстрактной машины описывает смысл запроса и множества фраз через действия  этой  машины. 
    Действия такой абстрактной машины можно рассматривать как применение правила резолюции.

Язык Пролог основывается на языке исчисления предикатов первого порядка и методике автоматического доказательства теорем (метод резолюции с ограничениями для уменьшения пространства поиска). Пролог был разработан в 1972 г. А. Кольмероэ из Марсельского университета. В течение следующего десятилетия язык получил дальнейшее развитие благодаря работам Р. Ковальского и других исследователей. Теперь Пролог применяется в следующих областях:

– общение  с  ЭВМ  на  естественном  языке; 
– интерфейсы  реляционных  баз  данных; 
– создание  систем  автоматического  программирования; 
– представление и обработка знаний в задачах искусственного интеллекта; 
– экспертные  системы; 
– символические  вычисления; 
– решение  задач  в  области  математической  логики; 
– написание компиляторов.

К достоинствам языка Пролог относятся:

– сочетание  декларативного  и процедурного  подхода; 
–простые  и  легко  понимаемые  тексты  программ; 
– высокая степень модульности, облегчающая модификацию и отладку программ; 
– эффективность реализации и доступность транслятора на всех типах ЭВМ.

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

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

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

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

нравится(джон,пиво).

нравится(мэри,кино).

нравится(джон,кино).

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

?-нравится(джон,деньги).

no

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

no

?-нравится(мэри,кино).

yes

?-президент(буш,сша).

no

На второй запрос был получен отрицательный ответ, так как из того, что Джону нравится Мэри, не следует, что Мэри нравится Джон. Остальные отрицательные ответы связаны с ограниченностью БД, в которой не отражаются связи, возможно существующие в действительности. Чтобы узнать все объекты, которые нравятся Джону, нужно указать в запросе вместо имени конкретного объекта переменную. Имя переменной должно начинаться с прописной буквы или символа подчеркивания.

 

?-нравится(джон,X).

X=мери;

X=пиво;

X=кино;

no

Интерпретатор сопоставляет цель в запросе с фактами в БД, при этом переменная получает значение аргумента отношения, стоящего в соответствующей позиции. Если согласование цели с БД возможно, то значение переменной выводится на экран, и можно ввести символ ";", чтобы получить другой вариант решения. Если вариантов больше нет, то выводится отрицательный ответ. Если альтернативные решения не нужны, то вместо ";" нужно нажать клавишу Enter.

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

?-нравится(джон,X),нравится(мери,X).

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

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

нравится(мэри,X):-нравится(X,кино).

 

 

 

 

 

 

 

 

 

 

Список литературы

 

  1. Клоксин.Мелиш, Программирование на языке Пролог
  2. И.Братко. Программирование на языке ПРОЛОГ для искусственного интеллекта. М.Мир,1990
  3. Стерлинг, Э.Шапиро. Искусство программирования на языке ПРОЛОГ. М. Мир, 1990.

Информация о работе Структура программы на языке Пролог