В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 62

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 62)

получено решение задачи (обратите внимание - правила (п3) и (п5) не были

использованы).

Замечание. Управление посредством целей описано нами в значительной

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

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

игнорировать проблемы читателя, которому о новом для него принципе

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

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

(простого реляционного языка представления знаний), причем именно

определенные операционные ее элементы существенны для той оптимизации

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

семантическую функцию (т.е. связь знака с денотатом), выплеснем с водой и

ребенка (оптимизацию ресурсов для решения конкретной задачи). Это наблюдение

подтверждает ту истину, что природа знания разнообразна и различные его

разновидности требуют адекватных средств. Так что и реляционный стиль,

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

громоздким и неадекватным в других.

Вопрос. Какие еще источники неэффективности имеются в предложенном

методе поиска согласующей подстановки?

Подсказка. Например, общий метод перебора с возвратом не защищен от

многократного анализа уже проанализированных подцелей.

Вопрос. Может ли развертка оказаться эффективней перебора с возвратом?

16.4. Предопределенные отношения

Внимательный читатель, повидимому, заметил неестественность, вводимых

правилами (п1)-(п3) из п.16.3.2. Ведь по таким правилам несложно оказаться

собственным братом или собственной сестрой. Конечно, следовало бы в каждое

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

(не_равно, X, Y).

Однако адекватно определить такое отношение в рамках простого

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

нужные факты, касающиеся конкретного набора атомов (хотя и это занятие не из

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

атомов!). Могут помочь правила, учитывающие симметричность и транзитивность

отношения "не_равно". Но это не избавит от необходимости при добавлении

каждого нового атома добавлять и "базовые" факты о его неравенстве всем

остальным атомам.

Дело в том, что простейший реляционный язык не содержит никаких

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

отрицательный ответ на запрос представлен пустым множеством положительных

ответов на него.

Пример с отношением неравенства в простейшем реляционном языке

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

в ЯП предопределенных (встроенных) средств. Так как неравенство нельзя

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

определения такого отношения, считая его предопределенным (т.е. фактически -

определенным иными средствами, выходящими за рамки ЯП). Конечно, в реальных

ЯП не для всех предопределенных средств нельзя написать явные определения.

Вопрос. Какие еще соображения могут повлмять на перечень

предопределенных средств.

Подсказка. Хорошо ли выражать умножение через сложение?

Мы рассмотрели лишь простейшие примеры "программирования" в реляционном

стиле. Из реальных ЯП, в которых это стиль взят за основу, отметим

отечественный Реляп [25] и широко известный Пролог [26]. В последнем,

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

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

Интересные результаты, способствующие применению Пролога в реляционном

стиле, получены А.Я.Диковским.

16.5. Связь с моделями МТ и Б.

Интересно проследить связь реляционного программирования с ранее

рассмотренными моделями ЯП (слово "модель" недавно использовалось в ином

смысле). Стремясь к ясности, не будем бояться частично повториться в этом

пункте. Зато станет прозрачней математическая суть реляционного подхода

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

позиции).

Итак, вернемся к исходной нашей цели - обеспечить абстракцию от

программы. С позиций нашего курса можно прийти к ней разными путями. Укажем

на два из них : от модели МТ и от модели Б.

16.5.1. Путь от модели Б

Основное математическое понятие в этой модели - функция из кортежей в

кортежи. Программа - композиция функций.

1. Первая необходимая модификация на пути к модели Р - переход к более

общему математическому понятию - отношению. Так как необходимо обеспечить

разрешимость, рассматриваются только конечные отношения.

Определение. (Конечное) отношение - именованное конечное множество

кортежей фиксированной длины. Длина кортежей называется местностью или

арностью отношения.

Для удобства положим, что имя отношения служит первой компонентой

каждого его кортежа. Тогда арность - на единицу меньше длины кортежей.

Например, отношение с именем "родитель" представлено совокупностью кортежей

(родитель, Иван, Степан)

(родитель, Иван, Дарья)

(родитель, Марья, Степан)

(родитель, Петр, Иван)

Содержательно это может означать, что Иван - родитель Степана, Петр -

родитель Ивана и т.п.

2. Вторая необходимая модификация. Вводится понятие базы данных (БД).

Определение. (Реляционная) база данных - это конечная совокупность

конечных отношений. (От английского relation - отношение).

3. Третья необходимая модификация. Вместо конкретных кортежей - образцы

с переменными и понятие согласующей подстановки (в точности как в модели

МТ). Появляется возможность записать, например

(родитель, Х, Степан)

(родитель, Марья, У)

Уже эта модификация позволяет легко задавать вопросы (ставить задачи)

относительно БД. Именно, каждый образец можно считать вопросом о содержимом

БД (а именно о совокупности согласующихся с ним кортежей). Например, наш

первый образец означает вопрос "Кто родитель Степана?", а второй - "Чей

родитель Марья?". В нашей БД из четырех кортежей ответы будут соответственно

(родитель, Иван, Степан)

(родитель, Марья, Степан) и

(родитель, Марья, Степан)

В сущности, если у нас есть общий алгоритм поиска согласования (а он

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

считать задачей вопрос, а моделью - БД. Мы скоро увидим, что это совершенно

естественно.

Обратите внимание, сколь много значит удобная и мощная система

обозначений (сколь разнообразные вопросы можно задавать с помощью переменных

в образцах). Скачок к простоте обозначений сравним с переходом от

"арифметических" формулировок задач к алгебраическим.

4. Четвертая модификация. Образцы становятся условными.

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

образцов. Первый из них называется следствием, а остальные - условиями.

Например, если бы в нашей БД были отношения

(мужчина, Иван)

(мужчина, Степан)

(мужчина, Петр) и

(женщина, Марья)

(женщина, Дарья)

то можно было бы задать условные вопросы

(родитель, Х, Степан) (женщина, Х) и

(родитель, Х, У) (мужчина, Х) (женщина, У)

Ответы были бы

(родитель, Марья, Степан) и

(родитель, Иван, Дарья)

Другими словами, второй и последующие образцы служат фильтрами образца-

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

согласованный со следствием, для которого все фильтры истинны (т.е. фильтры

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

следствием). Например, кортеж

(родитель, Иван, Степан)

не согласуется с последним условным образцом, так как при подстановке {Х ->

Иван, У -> Степан} невозможно согласовать второй фильтр (женщина, У).

Для поиска согласований с условными образцами используется перебор с

возвратом (backtracking), при котором последовательно проверяют возможность

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

предыдущему фильтру с новым претендентом на согласование. Существенно

используется конечность БД.

5. Пятая модификация. От условных образцов к правилам-предложениям.

Остался всего один принципиально важный шаг до реляционного языка

представления знаний (почти в точности Реляпа). Именно, условный образец

можно рассматривать как правило формирования базы данных.

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

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

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

этой подстановкой.

Конечно, в системе программирования должны быть средства, позволяющие

отличать трактовки условного образца как вопроса и как правила. Скажем,

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

вопросительным. Например, правило

! (дед, Х, У) (родитель, Х, Z) (родитель, Z, У) (мужчина, Х)

порождает в нашей базе новое отношение

(дед, Петр, Степан)

(дед, Петр, Дарья)

Теперь мы полностью готовы к объяснению абстракции от программы в

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

Теория представляет собой соединение исходной БД (фактов) и БЗ -

конечной совокупности правил (их называют правилами вывода, правилами

порождения, хорновскими формулами, логическими соотношениями и т.п.).

Описание модели представляет собой дополнительные факты и правила. В режиме

порождения модели все правила порождения применяются для построения

пополненной базы, которая и считается построенной моделью. Теперь можно

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

программирования в обычном смысле не требуется - во всех случаях работают

единые алгоритмы согласования образцов с кортежами.

Эта простая схема в практических реляционных языках (например, в

Прологе) модернизируется для более рационального расходования ресурсов и

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

16.5.2. Путь от модели МТ

Опишем его короче, учитывая сказанное выше. Первая модификация - полем

зрения служит вся БД, при этом отношения и кортежи представлены МТ-

выражениями специального вида. Вторая модификация - МТ-предложения

превращаются в правила порождения (левая часть - в последовательность

фильтров, т.е. правила анализа; правая часть - в следствия, т.е. правила

синтеза). Третья модификация - отменяется последовательный перебор правил -

они работают все сразу и не над ведущим термом, а над всем модифицированным

"полем зрения" - базой данных. Вот и все.

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

новом уровне разделения труда между человеком и компьютером. Человек

описывает мир (представляет знания о некоторой предметной области в базе

знаний). Человек ставит задачу (формулирует запрос к базе знаний). Компьютер

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

(правила вывода).

Можно сказать и так, что человек создает и представляет в БЗ теорию

предметной области (как мы создали "теорию родственных отношений"). Затем

(обычно другой человек) формулирует теорему (существования решения некоторой

содержательной задачи - например, теорему существования дяди Кузьмы).

Наконец, компьютер доказывает эту теорему, предъявляя решение задачи (т.е.

Степана в случае нашей задачи).

В связи с такой терминологией реляционное программирование называют

часто "логическим". Логическая терминология оправдана также тем, что в этой

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

метод резолюций. Его характерная особенность - при подборе сопоставимого

следствия выбирается наиболее общая согласующая подстановка.

С другой стороны, реляционное программирование обеспечивает абстракцию

от программы, требуя от пользователя БЗ лишь постановки задачи (запроса).

Такая абстракция полезна, например, для асинхронной (параллельной)

реализации реляционного языка. Скажем, в очередном цикле развертка каждого

правила может выполняться совершенно независимо над БЗ, используемой только

для чтения.

Нетрудно предвидеть развитие правил до активных процессов из

определенных классов, работающих над единым предсталением знаний о мире.

Такие процессы естественно трактовать как объекты, обменивающимися

сообщениями друг с другом (например, чтобы поручить решение подзадачи) и, в

частности, с БЗ (например, чтобы узнать некоторый факт). Остается добавить

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

Характеристики

Список файлов книги