«язык логического программирования пролог»

МИНИСТЕРСТВО РАЗВИТИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ТЕЛЕКОММУНИКАЦИИ РЕСПУБЛИКИ УЗБЕКИСТАН

САМАРКАНДСКИЙ ФИЛИАЛ ТАШКЕНТСКОГО УНИВЕРСИТЕТА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
Факультет:
“Компьютер инжиниринг”


САМОСТОЯТЕЛЬНАЯ РАБОТА

По предмету: Искусственный интеллект

Тема: «ЯЗЫК ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ ПРОЛОГ»

Студент группы 309 Научный руководитель

Амриев А. С. доц. Бекмуродов К. А.
Самарканд-2020
Содержание

А1. Классификация языков программирования

А2. Основные вехи развития языка Пролог
А3. Основные понятия Пролога
А4. Краткие сведения об операциях и встроенных предикатах SWI-Prolog
А5. Процедура вывода в Прологе
А6. Рекурсия
А7. Управление процессом вывода
А8. Способы организации циклов

А1. Классификация языков программирования
Языки программирования в зависимости от базовых конструкций языка, заложенных в структуру программы можно разбить на четыре категории.
- функциональные;
- процедурные;
- объектно-ориентированные;
- декларативные (реляционные).
Программа, написанная на функциональном языке, выражает алгоритм решения задачи в терминах значений, которые возвращают функции. Таким образом, программа представляет набор функций, каждая из которых возвращает только одно значение определенного типа. Работа программы (алгоритм решения задачи) представляет собой последовательный вызов функций. К функциональным языкам относится С.
Программа, написанная на процедурном языке, выражает алгоритм решения задачи в терминах действий (процедур), которые необходимо выполнить. Отличие процедуры от функции заключается в том, что процедура может возвращать любое количество значений, в том числе и ни одного. Таким образом, работа программы представляет собой последовательный вызов процедур. К процедурным языкам относятся Pascal, Basic и т.д. Следует отметить, что в любом процедурном языке имеется возможность определения и использования функций, а в функциональном - процедур (функций, невозвращающих значений - обычно определяются с модификатором void).
Программа, написанная на объектно-ориентированном языке, представляет собой набор объектов, взаимодействующих между собой посредством посылки сообщений. Каждый объект характеризуется информационной составляющей (набором атрибутов) и поведенческой (набор событий и методов). Работа программы представляет собой последовательный обмен сообщениями (вызов методов) между объектами. К объектно-ориентированным языкам относятся Object Pascal, Visual Basic, С++, Java и т.д. Следует отметить, что в любом объектно-ориентрованном языке имеется возможность процедурного программирования.
Общим для всех перечисленных категорий языков является то, что в программе описывается, что и как необходимо сделать для решения задачи, т.е. описывается последовательность решения задачи.
Программа, написанная на декларативном языке, представляет собой описание предметной области через набор отношений (англ. relation) между объектами (сущностями) и формулировку цели (задачи), которую требуется решить. В отличие от перечисленных выше языков, в такой программе нет явного описания последовательности действий, необходимых для решения задачи. Как правило, процедура поиска решения выполняется автоматически с использованием соответствующего математического или логического аппарата, лежащего в основе языка и реализованная в его конкретном интерпретаторе¹ (компиляторе²). К декларативным языкам относятся Prolog, SQL и т.д. Таким образом, несомненным достоинством декларативных языков является концентрация внимания разработчика на том, что надо сделать, а не как.
Другая классификация языков программирования основана на стиле программирования [30]:
- императивные – программа представляет собой последовательность операторов (команд, выполняемых компьютером), с помощью которых программист должен объяснить компьютеру, как нужно решать задачу (функциональные, процедурные и объектно-ориентированные языки программирования);
- декларативные – программа представляет собой совокупность утверждений, описывающих предметную область или сложившуюся ситуацию, с помощью которых программист должен описать, что нужно решать (найти) – поиском решения будет заниматься императивная система программирования.
Известна классификация языков программирования по их близости либо к машинному, либо к естественному человеческому языку. Те, что ближе к компьютеру, относят к языкам низкого уровня (Ассемблер), а те, что ближе к человеку, называют языками высокого уровня (Basic, Pascal, Java и т.д.). В этом смысле декларативные языки можно назвать языками сверхвысокого или наивысшего уровня, поскольку они очень близки к человеческому языку и человеческому мышлению.
¹Интерпретатор - программа (система программирования), выполняющая пооператорный (покомандный, построчный) анализ, обработку и выполнение исходной программы или запроса.
²Компилятор - программа (система программирования), выполняющая перевод всей исходной программы, написанной на языке высокого уровня, в эквивалентную программу на низкоуровневом языке, близком машинному коду.
А2. Основные вехи развития языка Пролог
Наиболее известным языком декларативного (логического) программирования, реализующим модифицированную логику предикатов первого порядка, является PROLOG (англ. PROgramming LOGig - логическое программирование) [9, 28, 30].
В 1965 году в работе «A machine oriented logic based on the resolution principle»³, опубликованной в 12 номере журнала «Journal of the ACM», Дж Робинсон представил метод автоматического поиска доказательства теорем в исчислении предикатов первого порядка, получивший название «принцип резолюции». На самом деле, идея данного метода была предложена Эрбраном в 1931 году, когда еще не было компьютеров (Herbrand, «Une methode de demonstration», These, Paris, 1931). Робинсон модифицировал этот метод так, что он стал пригоден для автоматического ( компьютерного) использования и разработал эффективный алгоритм унификации, составляющий базис его метода.
Идеи использования логики в качестве языка программирования зародилась в начале 1970-х годов. Первыми исследователями, которые занялись разработкой этой идеи, были Роберт Ковальски (Robert Kowalski) из Эдинбурга (теоретические основы, статьи 1971 и 1974 г.), Маартен ван Эмден (Maarten van Emden) из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ (Alain Colmerauer) из Марселя (реализация, 1973 г.). В 1973 году «группа искусственного интеллекта» во главе с Аленом Колмероэ создала в Марсельском университете программу, предназначенную для доказательства теорем. Эта программа использовалась при построении систем обработки текстов на естественном языке. Программа доказательства теорем получила название Prolog (фр. PROgrammation en LOGique) и послужила прообразом Пролога. Ходят легенды, что автором этого названия была жена Алена Колмероэ. Программа была написана на Фортране и работала довольно медленно.
Популяризации Пролога во многом способствовали:
- эффективная реализация (интерпретатор/компилятор) этого языка для ЭВМ DEC-10 Дэвидом Д. Г. Уорреном (David D.H. Warren) из Эдинбурга в 1977 г. Послужила прототипом для многих последующих реализаций Пролога. Что интересно, компилятор был написан на самом Прологе. Эта реализация Пролога, известная как «эдинбургская версия», фактически стала первым и единственным стандартом языка;
- разработка Кларком и Маккейбом (Великобритания) в 1980 году версии для персональных ЭВМ;
- японский проект создания компьютеров V поколения. В конце 1978 г. Министерство внешней торговли и промышленности (МВТП) Японии поручило разработать проект интеллектуальных ЭВМ, специально созданному для этих целей Токийскому институту вычислительной техники (ICOT)⁴. Сердцем этих компьютеров должен был стать не арифметический процессор, а специально оптимизированный для работы с прологоподобными программами.
В 1995 году был опубликован официальный стандарт ISO⁵/IEC⁶ языка Пролог (ISO/IEC 13211-1 «Information technology - Programming languages - Prolog - Part 1: General core» - «Информационные технологии. Языки программирования. Пролог. Часть 1. Общее ядро»).
На сегодня существует довольно много реализаций Пролога. Наиболее известные из них следующие: BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, МПролог, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic iis Workbench, Strawberry Prolog, SWI-Prolog, Turbo Prolog (PDC Prolog, Visual Prolog), UNSW Prolog и т. д. В нашей стране были разработаны такие версии Пролога как Пролог-Д (С. Григорьев), Акторный Пролог (А. Морозов), а также Флэнг (А. Манцивода, В. Петухин).
³Эту работу можно прочитать в переводе: Робинсон Дж. Машинно-ориентированная логика, основанная на принципе резолюции // Кибернетический сборник. - Вып. 7 (1970).
⁴Согласно [30] в октябре 1981 года Японское министерство международной торговли и промышленности объявило о создании исследовательской организации - Института по разработке методов создания компьютеров нового поколения (Institute for New Generation Computer Technology Research Center).
⁵ISO – International Organization of Standardization (Международная организация по стандартизации).
⁶IEC – International Electrotechnical Commission (Международная комиссия по электротехнике).
А3. Основные понятия Пролога
При формальном описании синтаксиса конструкций алгоритмических языков часто используется так называемая «нормальная форма Бэкуса-Наура» (БНФ), разработанная в 1960 Джоном Бэкусом и Питером Науром. Впервые БНФ была применена Питером Науром при записи синтаксиса языка Алгол-60 [30]. Основными конструкциями БНФ являются следующие.
Символ «::=» читается как «по определению» («это», «есть»). Слева от разделителя располагается объясняемое понятие, справа - конструкция, разъясняющая его. Например,
<Имя> ::= <Идентификатор>
В угловые скобки «< >» заключается часть выражения, которая используется для обозначения синтаксической конструкции языка, в частности объясняемое понятие. В приведенном выше примере это <Имя> и <Идентификатор>.
Символ «|» означает в нотации БНФ «или». Он применяется для разделения альтернативных толкований определяемого понятия. Например, десятичную цифру можно определить следующим образом:
<цифра> ::= 0|1|2|3|4|5|6|7|8|9
Часть синтаксической конструкции, заключенная в квадратные скобки, является необязательной (может присутствовать или отсутствовать), например
<Целое число> ::= [-]<Положительное целое число>
означает, что целое число можно определить через положительное целое число, перед которым может стоять знак минус.
Символ «*» обозначает, что часть синтаксической конструкции может повторяться произвольное число раз (ноль и более). Заметим, что иногда вместо символа «*» используют фигурные скобки «{ }». Например, положительное целое число в нотации БНФ можно следующим образом:
<Положительное целое число> ::= <цифра>[<цифра>]*
или
<Положительное целое число> ::= <цифра>{<цифра>}.
Т.е. положительное целое число состоит из одной или нескольких цифр.
Программа на Прологе состоит из предложений (утверждений). Каждое предложение заканчивается точкой.