11.4.3. Языки планирования

До сих пор в книге программистским подробностям уделялось мало внимания, поскольку языки меняются быстро, а логические основания, видимо, более постоянны. Однако необходимость планирования при решении задач ставит ряд проблем перед создателем языка программирования. Любой язык, способный описать автомат с магазинной памятью (и, следовательно, любой контекстно-свободный язык), можно использовать для выражения плана решения задачи, но оно может оказаться неизящным, ибо в языке, созданном для планирования, могли бы с успехом участвовать лингвистические конструкции, которых, скорее всего, нет в языках, созданных для обычных вычислений. Поэтому неоднократно предпринимались попытки сконструировать специальный язык программирования для искусственного интеллекта. Хороший обзор истории этого вопроса дала Самметт (1971), поэтому мы упомянем лишь самое интересное. Язык обработки информации , самый ранний из этих языков, был, по существу, машинным упорядоченным кодом для ЭВМ, рассчитанной на выполнение символьных, а не числовых операций (Ньюэлл и др., 1964). Мак-Карти (1961) объединил конструкции с формализмом ламбда-исчисления Чёрча для получения языка Лисп — языка программирования, допускающего формальный анализ (Вегнер, 1968). Многие

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

Программа решения задач должна уметь работать с тремя первичными сущностями: объектами, свойствами объектов и отношениями между объектами. В бесскобочной записи означает, что объект имеет свойство „красный", а — что объект находится на объекте Такое представление согласуется с нашей интуицией. Однако свойства можно считать функциями объекта, а отношения — функциями нескольких аргументов. Поэтому нам нет нужды различать их. Более того, связан ли символ с отношением или с данным объектом, зависит во многом от контекста. КРАСНЫЙ — это иногда свойство цветного объекта, а иногда сам объект, красный цвет. Для того чтобы различать, какой смысл вкладывается в употребление терма X, мы будем писать когда речь идет об отношении, и когда он обозначает объект.

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

Второй пример: Робот берет

С помощью отношения ПЕРЕД можно создать новый объект, чтобы выразить событие, состоящее в том, что появляются в данной последовательности:

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

можно описать как событие с объектами и отношениями между ними:

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

Для того чтобы рассуждать, нам необходимы как представление об объектах в мире, так и правила вывода, дающие возможность получать новое представление из старого. Это значит, что мы различаем явные события, с которыми имели дело до определенного момента, и знание об отношениях, которые сохраняются в общем случае. Мы снова можем обратиться к психологии, в частности к рассуждениям Тулвинга (1972) о разнице между эпизодической и семантической памятями. Примеры типа (50) входят в эпизодическую память. Семантическое предложение

просто означает, что свойство быть человеком подразумевает свойство быть смертным. Такое предложение можно интерпретировать как план доказательства истинности чего-либо. Следовательно, по (51), чтобы доказать, что X смертен, надо доказать, что X — человек. Некоторые планы гораздо сложнее, чем этот, и требуют более гибкой записи. Рассмотрим одно из наставлений, которое Виноград (1972) предлагал аспирантам. Статью можно принять как диссертацию, либо если она большая, либо если в ней содержатся убедительные доводы. На языке PLANNER это выглядит так:

Предложение (52) полезно считать определением приемлемости, которое можно структурировать как процедуру последовательного решения подобно тем, что обсуждались в гл. 6. Соответствующая (52) диаграмма показана на рис. 11.9. Ее с тем же успехом можно считать графом сведения задачи к подзадачам. Каждый узел

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

Рис. 11.9. Графсведёния задачи к подзадаче для доказательства приемлемости X.

Это делается путем определения теорем следования, которые указывают, как доказать, что отдельный факт есть следствие известных фактов. Пример такой теоремы:

Она определяет процедуру, устанавливающую, можно ли удовлетворить графу сведения задачи к подзадачам (рис. 11.9). Схема

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

Рис. 11.10. (см. скан) Блок-схема процедуры поиска, определенной утверждением (53).

В этой строке отмечается присутствие второй переменной Обозначения утверждают, что X и — свободные переменные. Следующие строки — это условия; если они выполняются, то этого достаточно, чтобы утверждать, что X имеет свойство быть приемлемым. Каждое условие называется целью. Первое

утверждает, что если X уже имеет свойство быть диссертацией, то он имеет свойство быть приемлемым по самому смыслу. Следующая цель теперь — множество ИЛИ-подцелей, как указано с помощью ТЕОРИЛИ, которая указывает, что цель поставлена, если поставлена хотя бы одна из ее подцелей. Первая подцель это Сама по себе цель — доказать, что X имеет свойство „большая». Вторая конструкция указывает языку PLANNER использовать метод доказательства, называемый — (здесь не определяется) для обнаружения свойства X „большая". Вторая ИЛИ-подцель представляет конъюнкцию подцелей

причем все они должны быть удовлетворены перед тем, как будет удовлетворена сама подцель. Их интерпретация должна быть ясна. Таким образом, предложение устанавливает конкретный тип поиска на графе сведения задачи к подзадачам. Следовательно, активация предложения очень схожа с активацией программы решения задач — как в GPS или Различие здесь в том, что общие программы должны использовать одни и те же методы поиска на графе для каждой задачи, в то время как PLANNER позволяет программисту дать, как надеются, полезные подсказки о методах решения. При этом, однако, программист может сосредоточиться на выделении полезных целей и подцелей, и ему не нужно думать о том, как достичь целей, до тех пор, пока он сам этого не захочет.

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

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

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

Очень старый силлогизм демонстрирует мощность языка PLANNER. Допустим, что

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

Вопрос „Кто-нибудь может ошибаться?" оценивается с помощью

что заставляет PLANNER сначала исследовать базу данных, чтобы определить, есть ли там хоть одна константа, для которой способность ошибаться записана как ее свойство, и затем, если поиск не приводит к успеху, применить любой имеющийся метод доказательства, чтобы вывести способность ошибаться. Поскольку (55) устанавливает теорему, следствием которой являются способность ошибаться, PLANNER просмотрит базу данных в поисках подходящих условий для предыдущего члена отношения. Если (57) оценена на базе данных (56), то вернется ответ Если предложение было удалено из базы данных, а вопрос задан снова, то ответом будет поскольку содержится в базе данных и по — имплицированный факт. Усложнили вопрос: „Любой ли грек может ошибаться?" Программа в этом случае спросит так:

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

В игру вступает свойство „возвращаться назад» языка поскольку система автоматически возвращается назад, чтобы найти второй объект, который На этот раз обнаружилось, что по выводу но не возвращается снова, доказывает, что по выводу и затем находит, что . В дополнение к иллюстрации возвращения назад этот пример полезен тем, что показывает, насколько важно упорядочение целей. Очевидно, потребовалась бы гораздо меньшая обработка данных, если бы (58) было переписано в виде

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