Получение программ из данных [1980 Уинстон П.

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

Функции и типы объектов образуют таблицу

Еще один пример, который легко строится в контексте мира кубиков Робби, касается таких действий, как "убрать кубик". Предположим, что у Робби имеется по коробке для игрушек, предназначенных для каждого вида кубиков: коробка BLOCKS для прямоугольных блоков, коробка PIRAMIDS для пирамид и коробка BALLS для шаров. Функция PUT-AWAY (УБРАТЬ) принимает некоторый предмет в качестве своего аргумента и помещает его в соответствующую коробку. Так, (PUT-AWAY'A) должно бы привести к выполнению (PUT-ON 'A 'BLOCKS). Функция PUT-AWAY и ее возможные типы аргументов образуют часть таблицы, показанной на рис. 12.7.

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

Программное воплощение таблицы может быть осуществлено многими способами. Простейшим и, пожалуй, самым худшим способом было бы объединить имя операции и название типа объекта для всех возможных комбинаций, образовав новую функцию для каждой из таких пар. Тогда мы получили бы PUT-AWAY-BLOCK (УБРАТЬ-БЛОК), PUT-AWAY-PIRAMID (УБРАТЬ-ПИРАМИДУ) и PUT-AWAY-BALL (УБРАТЬ-ШАР).

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

Очевидным улучшением было бы иметь вместо функций специального назначения универсальную функцию PUT-AWAY (УБРАТЬ). Чтобы она работала, необходимо, чтобы каждый объект проявлял свой тип посредством свойства TYPE (ТИП), находящегося в его списке свойств. В этом случае выбираемая конкретная функция специального назначения зависит от результата исследования свойства TYPE аргумента:

Аргументы могут поставлять и свои собственные процедуры

В другом, более совершенном решении существенно изменяется способ, которым универсальная программа связана с программами специального назначения. Эти функции специального назначения появляются не в процессе проверки типов объектов в предложении, содержащем функцию COND. Вместо этого имена функций специального назначения выявляются через списки свойств имен типов. Тип BLOCK, например, имеет свойство, именуемое PUT-AWAY-FUNCTION (УБРАТЬ-ФУНКЦИЯ). Универсальная функция PUT-AWAY, следовательно, может решить, что некоторый объект, скажем А, должен быть убран с использованием функции PUT-AWAY-BLOCK (УБРАТЬ-БЛОК) с помощью следующих шагов:

Функция FUNCALL позволяет вычислять имена функций или их описания

Указанная процедура может быть реализована многими способами, одним из которых является использование FUNCALL. Функция FUNCALL использует свой первый аргумент для вычисления имени функции или LAMBDA-описания, а затем применяет результат к другим аргументам. Так, следующие выражения оказываются эквивалентными:

Но форма FUNCALL обобщается так, чтобы допускать следующую запись, которая приводит к тому же самому результату:

Таким образом, функция PUT-AWAY (УБРАТЬ) может быть определена следующим образом:

Существенно, что наша общая идея работает и тогда, когда в ячейку свойства PUT-AWAY-FUNCTION помещаются не имена функций, а LAMBDA-определения. Нет необходимости формировать имена функций для функций специального назначения, если только к ним не обращаются многократно и не возникает вопрос эффективного использования памяти. Так, следующие способы приводят к эквивалентному результату, когда функция PUT-AWAY применяется к некоторому предмету:

При первом методе описание функции находится непосредственно в свойстве PUT-AWAY-FUNCTION (УБРАТЬ-ФУНКЦИЯ). При втором методе на один шаг меньше, за счет использования некоторого промежуточного имени функции.

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

Управляемое данными программирование становится все более популярным

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

Распространению стиля программирования, направляемого данными, способствовал ряд успешных программ, написанных в таком стиле. Одна программа, предназначенная для анализа электронных схем, была создана Сассманом и Столлманом, а другая, для хранения и извлечения информации,- Сандеволом.