14.2.2. DEDUCOM: объединение вопросно-ответной системы с базой данных

Слейгл (1965) в своей программе DEDUCOM предложил интересную альтернативу применению заранее запрограммированных правил вывода. Она обобщает транслятор с языка Лисп (Мак-Карти и др., 1963), и для объяснения ее сначала вкратце опишем некоторые конструкции Лиспа.

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

интериретирующий цикл читает и затем производит вычисления со списочной структурой. Основной тип данных в Лиспе — атомные символы (атомы) и списки, т. е. упорядоченные множества, элементами которых могут быть атомы или другие списки. Для списков определены три функции, и они содержатся в интерпретаторе. Пусть — произвольный список. Значением функции служит первый элемент списка а значением остальные его элементы. (Заметим, что список может быть пустым.) Значением функции , где и М — либо списки, либо атомные символы, служит список ). Кроме того, интерпретатор Лиспа содержит ряд обычных арифметических функций и логических предикатов. Так, — это функция арифметических выражений, значение которой равно произведению значений Конечно, этим не исчерпывается описание Лиспа, но такого краткого введения должно быть достаточно, чтобы читатель разобрался в работе

Слейгл сначала добавил три новые функции к основному интерпретатору Лиспа: и предикат Аргументы первых двух функций — переменная V и вопрос Вопрос — это функция от аргументов, и поэтому его также можно представить в виде Рассмотрим вопрос

Формально это функция сколько с аргументами палец и человек. Точно так же

— это произведение Различие между (35) и (36) состоит в том, что интерпретатор Лиспа способен воспринять сразу, а для функции сколько пользователь должен указать способ ее вычисления через и основные функции Лиспа. Чтобы определить valueans и ans, допустим, что при значение равно А. Тогда — это упорядоченная пара Из определения функций следует, что для упорядоченной пары

так что

Рассмотрим пример. Пусть человек — это переменная, принимающая значения Джон, Джеймс, Роберт, Том, и пусть дети — вопрос. Предположим далее, что известен факт

Если мы спросим ans [Роберт, дети], то порядок вычислений будет таков:

Предикат — это утверждение на Лиспе о том, что ответ на вопрос содержится в множестве ответов на вопрос Следовательно, если можно ответить на то можно ответить и на хотя, быть может, ответ на можно получить и не отвечая на Далее, пусть Том, — правильные ответы на вопрос дети (Роберт). Лишь будет ответом на вопрос дочь. Поэтому утверждение [ребенок, дочь] истинно.

Для полноты база данных в DEDUCOM должна содержать следующий факт: если переменная V не встречается в вопросе и есть какой-то факт вида то

Кроме того, по определению значение любого вопроса, являющегося константой, равно этой константе. Таким образом, если то ответом на будет 5.

Предположим, что программа DEDUCOM должна вычислить

где — функция и вопросы. Это в сущности ответ на вопрос через вычисление ответов на другие вопросы. Этапы вычислений таковы:

(1) Может ли интерпретатор Лиспа вычислить сразу? Если да, сделать это. Такой случай возможен, если — константа или атомный символ.

(2) Известна ли функция интерпретатору Лиспа? Если да, вычислить (возможно, с помощью и затем, зная аргументы функции вычислить ее.

(3) Если не выполняются ни (1), ни (2), заменить на и спросить, известен ли какой-нибудь факт в форме где совпадает с с точностью до замены переменных. Если такой факт известен, перейти к (5), в противном случае к (4).

(4) Если имеет форму — ответ на для некоторого значения V), заменить на и перейти к (3) (пытаясь ответить на . В противном случае сообщить о неудаче.

(5) Рекурсивным образом применить процедуру DEDUCOM для вычисления Если получен ответ на он же будет ответом и на . В противном случае перейти к (3) и попытаться

найти новый вопрос (Заметим, что этот шаг делает DEDUCOM процедурой поиска в глубину (полного перебора) со всеми его недостатками).

Чтобы проиллюстрировать эту процедуру, допустим, что в DEDUCOM, помимо сформулированных фактов, включены еще следующие:

Для того чтобы в DEDUCOM интерпретировались эти факты, их надо сначала преобразовать в утверждение на Лиспе. Это не совсем просто. Факт (а) типовой. Он записывается так:

Пользователи системы DEDUCOM должны выполнить этот перевод. Недостаток очевиден. Вопрос в примере выше

также является выражением на Лиспе. Для нахождения ответа на него DEDUCOM осуществляет следующие шаги:

(1) Функцию сколько нельзя вычислить сразу, но (44) допускает для (45) замену

(2) Функцию ans также нельзя вычислить сразу, но в соответствии с (39)

заменяет (46).

(3) — это примитивное выражение Лиспа, которое можно вычислить, если известны аргументы. Для этого нужно вычислить функцию

(4) Процедура ответа повторяется, при этом используется факт (он здесь не приведен) о valueans. Наконец, приходим к вопросу

Для ответа на него используется факт

который представляет собой запись на Лиспе факта (б). Это сразу приводит к вопросу являющемуся своим собственным ответом.

(5) Переменная V получает значение рука. Следующий вопрос

Ответ на него в соответствии с фактом, подобным (50), есть 2.

(6) Подставляя значения, найденные для (49) и (51), видим, что ответ на (48) есть (рука, 10). Ответом на (47), а также на (46) и (45) (исходный вопрос) будет 10.

DEDUCOM может отвечать на довольно тонкие вопросы, в том числе и на вопрос, ключевой к сюжету Микадо Гилберта и Салливана (Слейгл, 1965). Программа имеет незначительный дефект: она осуществляет перебор в глубину (полный перебор) на И/ИЛИ-графе; однако это можно легко поправить. Гораздо более серьезная трудность связана с тем, что подход DEDUCOM требует, чтобы пользователи и устанавливали факты в форме выражений Лиспа, и предвидели, как должен происходить поиск ответа. Другими словами, DEDUCOM — скорее язык программирования для ответов на вопросы, чем программа искусственного интеллекта со свойственными ей способностями к рассуждению. Тем не менее подход DEDUCOM заслуживает серьезного внимания в тех приложениях, где пользователь хочет выделить тот или иной тип вывода.