7344

позволяют использовать не только механизм вывода от цели, но и легко моделиро-

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

дукции. В прологе отсутствуют средства объектно-ориентированного программиро-

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

Название языка «Пролог» происходит от слов ЛОГическое ПРОграммирова-

ние (PROgrammation en LOGique во французском варианте и PROgramming in LOGic

– в английском). Пролог основывается на таком разделе математической логики,

как исчисление предикатов.

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

ции. Фактически Пролог представляет собой не столько язык для программирова-

ния, сколько язык для описания данных и логики их обработки. Программа на Про-

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

ориентированного программирования.

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

тами. Поэтому Пролог называют реляционным языком. Причем «реляционность» Пролога значительно более мощная и развитая, чем «реляционность» языков, ис-

пользуемых для обработки баз данных. Часто Пролог используется для создания си-

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

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

ляет собой не столько язык для программирования, сколько язык для описания дан-

ных и логики их обработки. Программа на Прологе не является таковой в классиче-

11

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

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

По статистике, строка исходного текста программы на языке Пролог соответ-

ствует четырнадцати строкам исходного текста программы на императивном языке,

решающем ту же задачу. Пролог-программу, как правило, очень легко писать, по-

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

В Прологе легко описывать и обрабатывать сложные структуры данных.

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

дом программирования является рекурсия.

Основные области применения Пролога:

•быстрая разработка прототипов прикладных программ;

•автоматический перевод с одного языка на другой;

•создание естественно-языковых интерфейсов для существующих систем;

•символьные вычисления для решения уравнений, дифференцирования и ин-

тегрирования;

•проектирование динамических реляционных баз данных;

•экспертные системы и оболочки экспертных систем;

•автоматизированное управление производственными процессами;

•автоматическое доказательство теорем;

•полуавтоматическое составление расписаний;

•системы автоматизированного проектирования;

•базирующееся на знаниях программное обеспечение;

•организация сервера данных или, точнее, сервера знаний, к которому может

12

обращаться клиентское приложение, написанное на каком-либо языке программи-

рования.

Области, для которых Пролог не предназначен:

•большой объем арифметических вычислений (обработка аудио, видео и т.д.);

•написание драйверов.

Язык Пролог предназначен для представления и использования знаний в раз-

личных предметных областях. Математическую основу языка составляет исчисле-

ние предикатов первого порядка (ИППП), при этом объекты предметной области, их свойства и связи представляются конъюнкцией правильно построение формул спе-

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

лизован метод резолюции.

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

где 0, – атомарная формула (предикат), все переменные связаны не ука-

занными явно кванторами всеобщности, областью действия которых служит вся формула. Атомарная формула, входящая в дизъюнкт с отрицанием, называется от-

рицательным литералом, а формула без отрицания - положительном литералом.

Эквивалентной, но более удобной для человека, является импликативная фор-

ма записи дизъюнктов Хорна:

которую, с учётом правила Modus Ponens, можно трак-

товать как "Если ..., то ...".

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

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

тов Хорна), составляющих базу фактов и базу правил, к которым допустимо обра-

щение с запросами. Запросы называются также целевыми утверждениями или про-

сто целями. Термин "программа" мы применяем к Прологу по "традиции", т.к. Про-

лог – декларативный язык.

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

Раздел 3. Основные конструкции языка LISP. Управляющие структуры языка

LISP.

Лисп (LISP, от англ. LISt Processing language – «язык обработки списков»; со-

временное написание: Lisp) – семейство языков программирования, программы и данные в которых представляются системами линейных списков символов. Созда-

тель Лиспа Джон Маккарти занимался исследованиями в области искусственного интеллекта (в дальнейшем ИИ) и созданный им язык по сию пору является одним из основных средств моделирования различных аспектов ИИ.

Это один из старейших (наряду с Фортраном и Коболом) используемых по сей день высокоуровневых языков программирования, а также первый из сохранивших-

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

Традиционный Лисп имеет динамическую систему типов. Язык является функ-

циональным, но начиная уже с ранних версий обладает также чертами императивно-

сти, к тому же, имея полноценные средства символьной обработки, позволяет реали-

зовать объектно-ориентированность; примером такой реализации является платфор-

ма CLOS.

Является языком системного программирования для так называемых лисп-

14

машин, производившихся в 1980-е годы, например, фирмой Symbolics.

Наряду с языком Ада, Лисп прошёл процесс фундаментальной стандартизации для использования в военном деле и промышленности, в результате чего появился стандарт Common Lisp. Его реализации существуют для большинства платформ.

Характерная особенность программы на Лиспе состоит в том, что абсолютно всё: и данные, и код любой сложности – описывается в достаточно примитивном синтаксисе. Существуют следующие два подхода:

Внешне программа на лиспе выглядит как гигантское нагромождение скобок.

Имеющиеся в любой современной системе средства форматированного выво-

да, позволяющие отобразить список так, чтобы была видна его структура, не-

сколько исправляют ситуацию, но в целом для восприятия программ на лиспе

«на глаз» требуется определённый навык. Впрочем, редактирование программ значительно упрощается использованием текстового редактора, поддержива-

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

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

ких-либо трудностей обрабатываться в качестве программы, а программа – в

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

нимать каждый поступающий на неё список на самом абстрактном уровне,

например как мета-лисп-машину, модифицирующую воспринимающую ма-

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

трюков и генераторов всевозможных машин.

Любая программа на языке Лисп состоит из последовательности выражений

(форм). Результат работы программы состоит в вычислении этих выражений. Все выражения записываются в виде списков – одной из основных структур Лиспа, по-

этому они могут легко быть созданы посредством самого языка. Это позволяет со-

здавать программы, изменяющие другие программы или макросы, позволяющие

15

существенно расширить возможности языка.

Базовые символы, операторы и функции

Развитые реализации Лиспа содержат сотни системных функций, макросов и операторов. Здесь приводятся лишь те из них, которые составляют базис работы со списками и создания функциональных программ на Лиспе.

T и NIL

Встроенные символы-константы Лиспа, обозначающие логическую истину и ложь соответственно. Значения T и NIL возвращаются логическими операторами и операторами и функциями сравнения.

Помимо этого у символа NIL есть ещё одно значение – он может обозначать пу-

стой список.

LIST

Эта функция возвращает список своих аргументов:

(list 1 3/7 'foo) ==>> (1 3/7 'foo)

(здесь ==>> означает, что в результате вычисления левой части интерпретатор Лиспа выдаёт то, что находится справа)

Если аргументов нет, возвращается пустой список:

(list) ==>> NIL

Если некоторые элементы являются выражениями, то сначала вычисляется их значение:

(list 1 2 (list 1 2)) ==>> (1 2 (1 2)). QUOTE

Системный оператор QUOTE подавляет вычисление своего аргумента. Если он не используется, то интерпретатор Лиспа, получив на входе список или символ, пы-

тается его вычислить: для символа возвращается его значение, для списка – резуль-

тат вызова функции, имя которой находится в голове списка, с параметрами – хво-

стом списка. Если же нужно, чтобы интерпретатор не вычислял значения, а взял символ или список «как есть», к нему применяют QUOTE.

(LIST 1 2 (QUOTE(LIST 1 2))) ==>> (1 2 (LIST 1 2)) (QUOTE (list 1 2 (list 1 2))) ==>> (LIST 1 2 (LIST 1 2))

Поскольку подавление вычислений – очень частая операция, имеется сокраща-

16

ющий её запись синтаксический сахар – вместо полной формы вызова QUOTE мож-

но просто поставить перед выражением апостроф:

(LIST 1 2 '(LIST 1 2)) ==>> (1 2 (LIST 1 2)). EVAL

Эта функция, по сути, и есть интерпретатор Лиспа. Являясь противоположно-

стью QUOTE, она вычисляет значение своего аргумента.

(EVAL '(LIST 1 2 '(LIST 1 2))) ==>> (1 2 (LIST 1 2)) (EVAL '(LIST 1 2 (EVAL'(LIST 1 2)))) ==>> (1 2 (1 2))

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

чений порождать и непосредственно исполнять в системе любые программы на лис-

пе.

CAR

Возвращает голову списка:

(CAR '(A B C D)) ==>> A (CAR '((A B)(C D))) ==>> (A B)

Специальный случай:

(CAR NIL) ==>> NIL

Формально в чистом функциональном программировании значение головы пу-

стого списка является неопределённым, но в Лиспе (по крайней мере, в большинстве диалектов) принято соглашение, по которому и голова, и хвост пустого списка равны

NIL.

CDR

Возвращает хвост списка:

(CDR '(A B C D)) ==>> (B C D) (CDR '((A B)(C D))) ==>> ((C D))

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

редь, сам является списком из двух элементов.

(CDR NIL) ==>> NIL C*R

17

Здесь на месте звёздочки «*» в имени функции может стоять от 2 до 4 букв «A»

и «D» в любых комбинациях. То есть возможны функции CDDDDR, CADAR, CADDR и так далее. Вызов такой функции эквивалентен вложенному вызову соот-

ветствующего набора функций CAR и CDR, например, (CADAR '((A B C) D E F))

соответствует (CAR (CDR (CAR '((A B C) D E F)))) и вернёт значение «B». Необхо-

димость в подобных странных функциях связана с часто повторяющейся задачей:

извлечь из списка определённый элемент, положение которого известно.

CONS

Принимает в качестве аргумента голову и хвост и создаёт из них список или то-

чечную пару, если аргументы являются атомами:

(CONS 'A '(B C D)) ==>> (A B C D) – присоединение атома к списку;

(CONS '(A B) '((C D))) ==>> ((A B) (C D)) – добавление списка к голове другого списка;

(CONS 'A 'B) ==>> (A . B) – создание точечной пары из двух атомов.

COND

Обобщённая условная конструкция. Имеет вид:

(COND ((Условие1)(Выражение1)) ((Условие2)(Выражение2)) …)

Последовательно вычисляются Условие1, Условие2 и так далее до тех пор, пока очередное УсловиеN не окажется истинным (станет иметь значение T). Тогда будет выполнено соответствующее ВыражениеN и его значение будет возвращено в каче-

стве значения вызова COND. Если истинного условия не будет найдено, COND вер-

нёт значение NIL. Обычной практикой является ставить в качестве последнего усло-

вия в COND значение T, гарантируя тем самым, что при невыполнении всех осталь-

ных условий будет вычислено последнее из выражений; так создаётся аналог ветви

ELSE условных операторов императивных языков программирования.

DEFUN

Конструкция, позволяющая определить функцию. Общий (упрощённый) фор-

мат определения следующий:

(DEFUN Имя (Параметр1 Параметр2 …) Выражение1 Выражение2 …)

Здесь Имя – имя функции. Соответствующий символ, если его ещё нет, будет создан в системе и в его функциональный слот запишется определение функции. В

18

дальнейшем интерпретатор Лиспа, встретив Имя в голове вычисляемого списка, ин-

терпретирует его как вызов данной функции с перечисленными в хвосте параметра-

ми. Параметр1 и так далее – имена формальных параметров функции.

Последовательность Выражение1, Выражение2 и так далее – это последова-

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

ленное последним по порядку выражением.

Специальные операторы позволяют управлять последовательностью вычисле-

ний. С их помощью реализуются ветвления и циклы. Оператор if позволяет вычис-

лить одно из двух выражений в зависимости от выполнения условия, которое тоже является выражением. Если его результат не ЛОЖЬ (не nil), то вычисляется первый аргумент, иначе – второй. Например, (if nil (list 1 2 "foo") (list 3 4 "bar")) всегда воз-

вращает (3 4 "bar").

Лисп изначально проектировался как функциональный язык программирования с отдельными императивными чертами, введёнными из соображений удобства прак-

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

2.4 Контрольные вопросы

Контрольные вопросы к разделу 1 «Общие сведения о языках логического и

функционального программирования».

1.Почему среди декларативных языков наибольшее применение получили языки ФП и ЛП?

2.Перечислите математические понятия, которые лежат в основе функциональ-

ного и логического программирования.

3. Какой способ программирования потенциально обеспечивает более высокую

19

эффективность вычислений и почему?

4.Определите назначение «решателя» (интерпретатора) при декларативном подходе.

5.Как представляется «база данных» в ФП и ЛП?

6.Чем может отличаться запрос в ФП от запроса в ЛП?

7.Может ли декларативный язык иметь несколько процедурных семантик?

8.Какая некорректность процедурной семантики допускается для функцио-

нальных языков?

9.Можно ли при использовании декларативных языков полностью отказаться от учета процедурной семантики?

10.Какими свойствами обладают программы на ФП- и ЛП-языках?

11.Что можно сказать о вычислительной эффективности программ ФП и ЛП?

12.Приведите примеры применения ФП и ЛП.

13.За счет чего возможно применение математических методов для анализа,

трансформации и синтеза программ ФП и ЛП?

Контрольные вопросы к разделу 2 «Основные элементы и приемы про-

граммирования языка ПРОЛОГ. Методы построения программ в языке ПРО-

ЛОГ».

1.Основные элементы и приемы программирования языка ПРОЛОГ.

Предложения: факты и правила. Цели внутренние и внешние.

2.Основные элементы и приемы программирования языка ПРОЛОГ.

Отношения (предикаты). Переменные свободные и связанные. Ано-

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

3.Основные элементы и приемы программирования языка ПРОЛОГ. От-

сечение. "Зеленые" и "красные" отсечения.

4.Семантические модели Пролога: декларативная и процедурная.

5.Ввод и вывод. Встроенные предикаты. Отладка программ.

6.Методы построения программ в языке ПРОЛОГ. Рекурсивные пред-

ставления данных и программ. Рекурсия. Достоинства и недостатки рекурсии. Хвостовая рекурсия. Организация циклов на основе рекур-

20