РАЗДЕЛ 5. Введение в теорию схем программ

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

Исследования по теоретическому программированию несут в себе отпечаток общематематических средств, используемых при изучении моделей программы:

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

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

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

Теоретическое программирование сформировалось на основе двух моделей вычислений:

- последовательных программ с памятью или операторных программ;

- рекурсивных программ.

Обе модели строятся над абстрактной алгебраической системой <D,F,Р>, образованной предметной областью D, конечным набором (сигнатурой) функциональных F = {f1, f2, …, fm} и предикатных P={p1,…,pn} символов с заданным для каждого символа числом его аргументов (арностью).

Определение класса программ слагается из трех частей:

- схемы программ (синтаксиса)

- интерпретации;

- семантики.

Определение 5.1. Схема программ – это конструкционный объект, показывающий, как строятся программы с использованием сигнатуры и других формальных символов.

Определение 5.2. Интерпретация – это задание конкретной предметной области и сопоставление символам сигнатуры конкретных функций и предикатов (базовых операций), согласованных с предметной областью и арностью символов.

Определение 5.3. Семантика – это способ сопоставления каждой программе результата ее выполнения.

Как правило, с программами связывают вычисляемые ими функции.

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

Понятие схемы программы принадлежит советскому математику А.А.Ляпунову, которое он ввел в 1953г., исходя из общей концепции необходимости и возможности формализации процесса программирования.

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

Схема программ как математическая модель удовлетворяет следующим требованиям:

-модель позволяет изучать свойства достаточно широких классов программ, а не отдельных конкретных программ;

-сохраняет все интересующие исследователя свойства и особенности рассматриваемого класса программ;

-позволяет игнорировать несущественные для данной проблемы свойства, например, синтаксические детали;

-модель модифицируема и допускает нововведения, отслеживающие развитие языков программирования;

-удобно, когда структура модели изобразительно подобна структуре программ, что дает возможность привлекать на некоторых этапах исследований программистскую интуицию.

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

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

В схемах же индивидуальные операции и функции заменены абстрактными символами переменных-операций и переменных-предикатов (или функциональными и предикатными символами). Если вместо каждого такого символа подставить конкретную функцию или, соответственно, предикат (как говорят, задать интерпретацию схемы), то схема превращается в программу.

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

Пример 5.1.

Программа вычисления факториала   начало целые х, у; ввод (х); у:= 1; m: если х = 0 то на m1; у:= х * у; х:= х – 1; на m; m1: вывод (у); конец

Схема программы   начало ввод (х); у:= а; m: если p(x) то на m1; у:= g (х, у); х:= h (х); на m; m1: вывод (у); конец