Схема программ
Схема программ (Program schemata) - математическая модель программ, в которой такие понятия, как оператор, операнд, переменная, выполнение и т.д., являются обобщением соответствующих понятий существующих языков программирования. Понятие схемы программы принадлежит советскому математику А.А.Ляпунову, которое он ввел в 1953г., исходя из общей концепции необходимости и возможности формализации процесса программирования. В настоящее время теория схем программ - это широко разветвленная область исследования, которая имеет многочисленные выходы в практику программирования и содержит фундаментальные результаты не только по операторным методам программирования, определившим современное состояние автоматизации программирования, но и по признаваемым перспективными методам рекурсивного и параллельного программирования.
Одновременно с появлением первых систем автоматизации программирования возникли и стали бурно развиваться два направления в теории преобразований операторных схем программ как теоретической основы эквивалентных и оптимизирующих преобразований транслируемых программ и их обоснования.
Первое направление, основу которого заложили работы Ю.И.Янова, Н.А.Криницкого, А.П.Ершова, А.А.Летичевского, изучает отношения эквивалентности в разных семантических моделях программ с целью построения полных систем эквивалентных преобразований. Семантическая модель программы - это множество схем с введенным в нем отношением эквивалентности. При переходе к схеме конкретные объекты программы (такие как, например, переменные, константы и операции) заменяются на формальные символы, а моделируемая программа получается из схемы некоторой интерпретацией формальных символов, входящих в схему. Множество выполнений схемы определяется таким образом, что оно покрывает множество выполнений каждой программы с данной схемой, а две схемы объявляются функционально эквивалентными, если функции, вычисляемые схемами, совпадают. Исходной для исследования является функциональная эквивалентность схем, хотя изучаются также и более сильные формы эквивалентности, главным образом для того, чтобы выявить те свойства моделей, без выполнения которых построение полной системы либо невозможно, либо затруднено. В рамках этого направления были получены важные результаты по нахождению и исследованию разрешимых случаев эквивалентности и полных систем эквивалентных преобразований. Однако требование разрешимости приводило к тому, что большинство преобразований, полезных для оптимизации, находились вне исследованных моделей программ.
Практически же применяемые оптимизирующие преобразования (и другие виды семантической обработки программ) изучались в рамках второго подхода, так называемых "направленных преобразований", возникновение которого связано с трудами А.А.Ляпунова, С.С.Лаврова, А.П.Ершова, В.В.Мартынюка. Идея, лежащая в основе этого подхода, состоит в формулировании практически полезного способа оптимизации программ (или другого вида работы с программой) в виде некоторого класса формальных схем, представляющего собой специальную символическую запись реальных программ или их фрагментов с заданной (явно или с помощью инварианта) системой формально корректных преобразований. Класс формальных схем может отражать только те из свойств реальных программ, которые наиболее существенны для выбранного способа их обработки, и не обязан охватывать их полностью, во всем классе программ. Таким образом, это направление, новый этап в развитии которого связан с работами Дж.Кока, Ф.Аллен и, в особенности, К.Килделла по глобальным оптимизациям методом разметки, впервые примененным А.П.Ершовым при исследовании схем Янова и Лаврова, позволяет изучать достаточно глубокие способы обработки программ, оставаясь в рамках простых (разрешимых) моделей. Однако практическое применение полученных при этом результатов для создания оптимизирующих трансляторов (и других инструментальных систем) требует решения ряда нетривиальных задач по установлению связи между изученными классами формальных схем и классом преобразуемых программ. Наиболее важной из этих задач является задача схематизации программ, при которой формальные схемы корректно и достаточно полно отражают выбранный способ обработки, а переход от программы к ее формальной схеме и обратно имеет приемлемую сложность. В том случае, когда нужно реализовать не один, а несколько способов обработки (что, как правило, и бывает), возникает проблема такого объединения систем формальных преобразований, чтобы совместный эффект их применения был наибольшим. Поэтому исследование систем преобразований в рамках формальных схем должно подкрепляться выделением и изучением семантических моделей программ, для которых эти преобразования являются корректными.
См. также
Крупноблочная схема программ, Неинтерпретированные схемы, Стандартные схемы, Схема с косвенной адресацией, Схема с распределенной памятью, Схемы Мартынюка.
Литература
[Ершов/77],
[Касьянов/88]