Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


“еоретические сведени€




¬ этой работе ¬ы познакомитесь с €зыком логического программировани€ ѕролог. “еоретической основой €зыка ѕролога €вл€етс€ раздел символьной логики, называемый исчислением предикатов. Ќазвание ѕролог (Prolog) произошло от словосочетани€ Ђпрограммирование при помощи логикиї (PROgramming in LOGic).

—оздание логического программировани€ можно приписать –оберту  овальскому и јлэну  олмероэ. –.  овальский разработал процедурную интерпретацию хорновских дизъюнктов. ¬ начале 70-х годов ј.  олмероэ и его группа создали в ћарсельском университете (‘ранци€) специальную, написанную на ‘ортране программу, предназначенную дл€ доказательства теорем. ѕрограмма доказательства теорем, названна€ ѕрологом, включала в себ€ интерпретатор –.  овальского. — тех пор было сделано несколько расширений и усовершенствований €зыка. «десь можно отметить работу группы из Ёдинбургского университета (Ўотланди€). Ўотландский вариант получил название C&M Prolog в честь авторов классической работы Ђѕрограммирование на €зыке ѕрологї ”иль€ма  локсина и  ристоффера ћеллиша. —егодн€шней своей попул€рности ѕролог во многом об€зан эффективной реализации этого €зыка, полученной в Ёдинбурге ƒэвидом ”орреном и его коллегами в конце 70-х годов. Ќаписанный ими компил€тор (компил€тор был почти полностью написан на ѕрологе) остаетс€ и поныне одной из лучших реализаций ѕролога.

¬ то врем€, как традиционные €зыки программировани€ €вл€ютс€ процедурно-ориентированными, ѕролог основан на описательной или декларативной точке зрени€ на программирование. Ёто означает, что машине в качестве программы можно предоставить не алгоритм, а формальное описание предметной области и задачи в виде аксиоматической системы, и тогда построение решени€ задачи в виде вывода в этой системе можно поручить самой машине. “аким образом, от программиста не требуетс€ построение алгоритма, решающего задачу, поскольку нужный алгоритм порождаетс€ интерпретатором, стро€щим вывод по определенной стратегии. “еперь основна€ задача программиста Ц удачно аксиоматизировать, т.е. описать в виде системы логических формул предметную область и такое множество отношений на ней, которые с достаточной степенью полноты описывают задачу.

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

ѕри выполнении лабораторных работ мы будем использовать визуальную среду программировани€ Ц VisualProlog. —уществует реализаци€ системы VisualProlog дл€ таких платформ как: DOS, Windows 3.x, Windows 95/98, Windows NT, OS/2, SCO Unix, Linux. VisualProlog прекрасное средство дл€ разработки клиент-серверных приложений. ¬ насто€щее врем€ Visual Prolog также включает оболочку дл€ разработки экспертных систем Ц ESTA.

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

ѕрограммирование на €зыке ѕролог состоит их 3-х этапов:

1. ќпределение фактов предметной области.

‘акты могут описывать свойства объектов и отношени€ между объектами. Ќапример, факт Ђнравитс€ ellen tennisї можно записать так:

likes(ellen, tennis).

Ётот факт включает в себ€ два объекта, обозначенных словами ellen и tennis, и отношение, обозначенное словом likes (нравитс€). ќбратите внимание, что каждый факт и каждое правило предметной области должны заканчиватьс€ точкой. »мена объектов, список которых в каждом факте заключен в круглые скобки, называютс€ аргументами. »м€ отношени€ Ц называетс€ предикатом. “аким образом, likes Ц предикат с двум€ аргументами.

2. ќпределение правил.

ѕравило Ц это факт, истинность значени€ которого зависит от истинности других фактов. ѕравила позвол€ют получать новые факты исход€ из уже имеющихс€.

ќбщий вид правила:

A:- B1,..., Bn. (n>0)

«десь A Ц заголовок правила, Bi Ц тело правила. —имвол Ђ:-ї читаетс€ Ђеслиї.

¬озможны два варианта прочтени€ данного правила:

- декларативное прочтение Ц ЂA истинно, если истинны Biї;

- процедурное прочтение Ц Ђчтобы решить задачу A, сначала надо решить подзадачу B1, затем подзадачу B2,..., затем подзадачу Bnї

“аким образом, дл€ выполнени€ цели в заголовке правила, необходимо вначале выполнить (согласовать) все подцели из тела правила.

Ќапример, правило Ђтому нравитс€ футбол, если футбол €вл€етс€ видом спортаї на ѕрологе можно записать следующим образом:

likes(tom, football):- sport(football).

÷ель likes(tom, football) будет истинной в том случае, если выполн€ютс€ все подцели из тела правила. ¬ данном случае подцель sport(football).

3. ‘ормулировка вопросов об объектах предметной области и отношени€х между ними.

»ме€ некоторую совокупность фактов, мы можем обращатьс€ к ѕрологу с вопросами о них.

Ќапример, пусть имеетс€ следующа€ совокупность фактов:

likes(ellen, tennis).

likes(tom, football).

likes(tom, swimming).

“еперь мы можем задать системе вопрос Ђнравитс€ ли тому футболї:

?-likes(tom, football)

yes

ѕоскольку нужный факт имеетс€ в базе фактов и правил, получен положительный ответ.

ѕеременные

ƒо сих пор мы рассматривали отношени€, аргументами которых выступали конкретные объекты Ц константы, такие как, ellen, tennis, и т.д. “акие объекты называютс€ атомами. јргументами отношений могут выступать также абстрактные объекты Ц переменные. ѕеременные используютс€ дл€ задани€ общих правил и формулировки общих вопросов. ѕеременные должны начинатьс€ с большой буквы. Ќапример, правило Ђбиллу нравитс€ то же, что и томуї на ѕрологе можно записать так:

likes(bill, X):- likes(tom, X).

¬ этом правиле объект X Ц переменна€, объекты bill и tom Ц константы (начинаютс€ с маленькой буквы). ≈сли ¬ы хотите, чтобы константа начиналась с большой буквы, необходимо заключить ее в двойные кавычки, например: ЂBillї.

ѕеременна€ может также встречатьс€ в запросе. ≈сли в запрос переменна€ не входит, то ответом будет либо да (yes), либо нет (no). ≈сли же в запрос входит переменна€, то ѕролог найдет все значени€ этой переменной и вернет ответ. Ќапример, вопрос Ђчто нравитс€ биллуї можно записать на ѕрологе следующим образом:

?- likes(bill, What). % What переменна€

ѕролог найдет все значени€ переменной What, которые удовлетвор€ют вопросу, и вернет ответ:

What = football

What = swimming

2 Solutions

»ногда возникает необходимость в использовании переменной, им€ которой не будет потом нигде употребл€тьс€. Ќапример, если необходимо определить Ђнравитс€ ли что-то томуї и при этом не важно, что именно, можно использовать анонимную переменную. јнонимна€ переменна€ обозначаетс€ одиночным знаком подчеркивани€: Ђ_ї. Ќапример, вопрос Ђнравитс€ ли что-то томуї на ѕрологе можно записать так:

?- likes(tom, _).

yes

¬опрос Ђнравитс€ ли эллен теннис и нравитс€ ли тому теннисї можно задать следующим образом:

?- likes(ellen, tennis), likes(tom, tennis).

«ап€та€ между подцел€ми likes читаетс€ как Ђиї. ѕролог пытаетс€ согласовать каждую подцель по очереди. —очета€ возможности конъюнкции и использовани€ переменных, можно строить достаточно содержательные вопросы. Ќапример, вопрос Ђсуществует ли что-нибудь такое, что нравитс€ обоим эллен и томуї на ѕрологе можно записать так:

?- likes(ellen, X), likes(tom, X).

ќбратите внимание на использование одной и той же переменной X в разных подцел€х одного и того же запроса. —ледует отметить, что область действи€ переменной в ѕрологе ограничиваетс€ правилом, т.е. одинаковые переменные в разных правилах никак между собой не св€заны.

¬ыполнение запроса

ѕри выполнении запроса интерпретатор пытаетс€ унифицировать (сопоставить) аргументы запроса с аргументами базы данных. ѕролог имеет внутренние подпрограммы дл€ выполнени€ сопоставлени€. ќни €вл€ютс€ неотъемлемой частью €зыка и называютс€ внутренними подпрограммами унификации. Ёти подпрограммы выполн€ют сопоставление целей и подцелей с фактами и головами правил дл€ того, чтобы доказать (или вычислить) эти цели или подцели. —уществует несколько правил унификации:

 

1. »дентичные структуры сопоставл€ютс€ друг с другом.

2. —вободна€ переменна€ сопоставл€етс€ с константой или с ранее св€занной переменной (и становитс€ св€занной с соответствующим значением).

3. ƒве свободные переменные могут сопоставл€ть и св€зыватьс€ друг с другом. — момента св€зывани€ они трактуютс€ как одна переменна€: если одна из них принимает какое-то значение, то это же значение принимает немедленно и друга€.

ћеханизм поиска с возвратом

ѕри выполнении логического вывода ѕролог использует метод, который называетс€ поиск с возвратом. —уть его в следующем: если ѕролог должен выбрать между двум€ альтернативными пут€ми, он ставит маркер у места ветвлени€ (который называетс€ точкой отката) и в случае неудачи по одному из путей ѕролог возвращаетс€ к точке отката и пытаетс€ найти решение по альтернативному пути. ¬ процессе логического вывода может быть несколько точек отката дл€ различных подцелей. ѕоиск с возвратом имеет четыре принципа:

1. ѕодцели должны быть согласованы по пор€дку сверху вниз.

2. ѕредикатные предложени€ провер€ютс€ в том пор€дке, в каком они по€вл€ютс€ в программе.

3.  огда подцель соответствует заголовку правила, тело этого правила образует новое множество подцелей дл€ согласовани€.

4. ÷елевое утверждение считаетс€ согласованным, когда соответствующий факт найден дл€ каждой оконечности (листа) целевого дерева.

ќсновные программные секции программ на VisualProlog

ќбычно программа на VisualProlog состоит из 4-х программных секций.  аждой секции предшествует свое ключевое слово.

—екци€ доменов (domains) служит дл€ объ€влени€ всех используемых нестандартных доменов. VisualProlog позвол€ет создавать свои собственные типы объектов из базисных типов доменов. —уществует несколько встроенных стандартных доменов:

 

ƒомен ќписание
short диапазон значений Ц32768.. 32767
ushort диапазон значений 0.. 65535
long диапазон значений -2147483648.. 2147483647
ulong диапазон значений 0.. 4294967295
integer дл€ 32-битных платформ диапазон значений -2147483648.. 2147483647
unsigned дл€ 32-битных платформ диапазон значений 0.. 4294967295
byte диапазон значений 0.. 255
word диапазон значений 0.. 65535
dword диапазон значений 0.. 4294967295
char отдельный символ, заключенный в апострофы, например: 'a'
real число с плавающей точкой, эквивалент типу double в €зыке C
string 1. ѕоследовательность букв, цифр и знаков подчеркивани€, котора€ начинаетс€ со строчной буквы, например: telephone_number. 2. Ћюба€ последовательность символов, заключенна€ в двойные кавычки, например: УVisual PrologФ.
symbol —интаксис такой же, как и дл€ строк. ƒанные типа symbol в отличие от данных типа string запоминаютс€ в таблице символов. Ёто обеспечивает более быстрый поиск.

 

ѕример описани€ нестандартных типов данных:





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-10-01; ћы поможем в написании ваших работ!; просмотров: 502 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

ƒва самых важных дн€ в твоей жизни: день, когда ты по€вилс€ на свет, и день, когда пон€л, зачем. © ћарк “вен
==> читать все изречени€...

1270 - | 1170 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.019 с.