11.3. Фортранная дедуктивная система — автоматическое порождение таблиц связей
11.3.0. Исторические сведения и общий подход
Эффективность программы GPS для конкретной задачи зависит во многом от выбранного определения различий в таблице операторов и различий. Некоторые исследователи занимались задачей автоматического порождения этой таблицы. В частности, Куинлан (Куинлан и Хант, 1968,1969; Куинлан, 1969) создал фортранную дедуктивную систему 
— программу, сходную с GPS во всем, за исключением того, что таблица операторов и различий здесь выводится из описания операторов.
Хотя можно показать, что представление объектов в FDS соответствует деревьям в GPS, все же при работе с этой программой легче пользоваться лингвистической терминологией. Состояния объектов представляются как цепочки из алфавита терминальных и нетерминальных символов. Нетерминальными являются переменные символы, обозначаемые здесь буквами из конца алфавита, например 
. К терминальным символам относятся конечное множество констант, знаков унарных и бинарных операций; они определяются заново для каждой задачи. То что в терминах GPS было бы объектом, в терминах FDS есть правильно построенное выражение (п. п. в.). Оно определяется правилами:
(1) Константа или переменная есть п. п. в.
(2) Бинарная операция с двумя п. п. в. после нее есть п. п. в.
(3) Унарная операция с одним п. п. в. после нее есть п. п. в.
Эти правила определяют префиксную, или „обратную бесскобочную" запись. Они также устанавливают соотношение между деревьями в GPS и цепочками в 
Рассмотрим задачу интегрирования, представленную выше. Можно определить множество Т первичных символов следующим образом:
Выражение
теперь принимает форму
Заметим, что мы соблюдали соглашение о том, что за бинарной операцией следует сначала ее правый операнд, а затем левый. Если читатель снова обратится к рис. 11.5, он обнаружит, что существует соответствие между этой цепочкой и выражением (8), представленным в виде дерева.
Рис. 11.7. Дерево для 
Правило подстановки содержится в FDS, как и в программе GPS. Оно позволяет работать с цепочками типа
как с частным случаем цепочки
Эти операторы FDS именуются правилами переписывания цепочек, так как они указывают, что одну цепочку можно заменить другой. Например,
можно применить к 
чтобы получить или 
или 
Как видно из примера (11), правила переписывания имеют форму 
где 
- п. п. в. Правило переписывания цепочки
требует двух преобразований в 
Это
поскольку отношение равенства не обязательно рефлексивно.
С помощью (13) можно также проиллюстрировать, как определяются различия при построении таблицы операторов и различий. Рассмотрим (13а). И правая, и левая части представляют собой п. п. в., а, следовательно, деревья, как показано на рис. 11.7.
Список различий между левой и правой частями этих деревьев таков:
Различия (1) и (2) являются абсолютными различиями, поскольку эти изменения останутся в силе, где бы ни применялось данное правило. Характер же изменения, обусловленного различием (3), нельзя точно определить, пока мы не знаем, к каким структурам нужно применить правило переписывания. Например, если бы это правило нужно было применить к цепочке
то константы В и С поменялись бы местами, а если это же правило используется для получения
то константа В будет заменена бинарной операцией + и соответствующими ей операндами. Это примеры контекстно-зависимых изменений. Когда операторы определены, программа FDS исследует каждый из них, чтобы определить, какие абсолютные и контекстнозависимые изменения он может вызвать. Подробности того, как это делается, сейчас несущественны. (Детальное обсуждение содержится в статье Куинлана и Ханта, 1968.) Дело в том, Что такое задание операторов определяет матрицу операторов и различий, которую программа способна вывести.
Та же схема используется для выявления различий между состояниями и целями при решении задач. Вначале исходное и целевое состояния выражаются цепочками. Эти цепочки сравниваются покомпонентно, и отмечаются различия между ними. Затем программа, опираясь на свою таблицу операторов и различий, работает практически так же, как GPS.
