1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 16
Текст из файла (страница 16)
Ссылочные структуры. 6. Блочность. 7. Типы данных. Б. Средства описания операций. 1. Арифметические выражения. 2. Логические выражения. 3. Процедуры и функции, в том числе рекурсивные. 4. Выражения специального вида н назначения — счетчики, операции над данными нечисловых типов и т. д. В. Средства описания структуры программ. 1. Операторы присваивания. 2. Условные операторы. 3. Операторы перехода и именующие выражения. 4. Операторы цикла. 5.
Механизмы вызова процедур. 6. Средства задания параллелизма, недетермвпированности и синхронизации выполнения операторов. Теория, изучающая программы, должна учитывать, в отличие от общей теории алгоритмов, структурный характер программ, особенности различных примитивов, их взаимосвязь, возможность замены одних другцми с тем, чтобы можно было ставить задачи практической ориентации. 1.2. От программ к схемам преграим.
Теория схем программ берет на вооружение обычный методологический прием теоретических разделов прикладных наук — замену сложных реальных объектов и явлений более простыми абстрактнымп моделями. Математические модели программ (заметны, что сани программм— тоже математические объекты) должны удовлетворять обычным для моделей требованиям, которые в атом случае звучат следующим образом: — модель позволяет научать свойства достаточно пшроких классов программ, а не отдельных конкретных программ; — сохраняет все интересующие исследователя свойства н особенности.
рассматриваемого класса программ; — позволяет игнорировать несущественные для данной проблемы свойства, например, синтаксические детали; — модель модифицируема и допускает нововведения, отслеживающие развитие языков программирования; — дает возможность отделить разрешимые и неразрешимью свойства программ и классов программ; — удобно, если структура модели изобрвзнтельно подобна структуре программ, что дает возможность привлекать на некоторых этапах исследований программистскую интуицию.
Схемы программ — зто математические модели программ, вполне отвечающие перечисленным требованиям. В частности, онн отвечают последнему требованию: схемы, так же как и программы, представляют собой тексты в некоторых формализованных яаыках, а зтн яаыкн являются упрощенными репликами языков программирования. Главное отличие схем от программ состоит в следующем.
Арифметические, логические н другие выражения программы образуются с помощью символов операций и укааателей функций, семантика которых фиксирована языком программирования (для базовых операцнй) или выводима по определенным правилам композиции из семантики базовых операций. Поэтому каждый оператор программы единственным образом задает некоторую функцию над данными, а из этих функций образуется (вычнслнмая) функция, задаваемая программой в целом. В схемах же индивидуальные операции н функции ааменены абстрактными символами переменных-операций и переменных-предикатов (илн функциональными и предикатнымн символами). Если вместо каждого такого символа подставить конкретную функцию нли, соответственно, предикат (как говорят, задать интерпретацию схемы), то схема превращается в программу. Сама же схема не задает алгоритма, в отличие от программы, и с помощью схемы нельзя вычислять что-либо.
Схема описывает строение программы или, более точно, строение множества программ, получающихся иа схемы в реаультате задания различных интерпретаций о). Следующий пример поясняет различие между программой и ее схемой. Схема программы ~4.% Программа гычислеиия фако»ариола наказе целые х, у," ввод(х); у.— 1, если х = О то на И; у'= хХу; х:=х — 1; иа Е; И: гыгод (у) конец начало ввод (х); у:= и' й если р(х) то на И; у: = у (х~ у) ~ х:= Ь(х); на Е; И: гсяюд (у) конец 70 о) Существует раэкогласнс, какой термин продпочтатсльной употреблять — «слома программы» как «схома программ». Стороккнкн второго аарванта обосвоаыаают ого том, что одна н та жо схема, будучи раэлкчным образом нптерпрстнроааяа, порождает множество программ.
Однако авторы продпочвтают парный торман, имея а паду то, что а атом контексте слово спрограмма» вмсст собкратолькос значокко так жо, как слово «функцкя» з олозосочотакан»пронааодная функцнн». Савва — программа иа языке Алгол-60, справа — схема программы (из некоторого класса схем, который в этой книге не рассмат ривается, но который близок к классу стандартных схем, определенному в следующем параграфе). Нам достаточно понимать, что схема представляет собой текст на некотором формальном языке, синтаксис которого подобен синтаксису языка Алгол-60, но семантика которого не задана.
Точнее, некоторый «абстракткыйэ смысл объектов етого яаыка может быть указан при строгом определении класса схем нлн, как в нашем случае, может быть интуитивно понятным для тех, кто знаком с программированием яа языке Алгол-60. Для нас важно отметить, что в етом языке есть разные группы символов: символы, которые мы будем называть переменными (в Я« — х и у) и константамн (а); функциональные (в Я«.« — я н Ь) и предикатные (р) символы и, наконец, символы- метки и специальные символы (качало, если и т. д.).
В схеме можно выделить составленные нз символов по определенным правилам объекты, называемые операторами: — операторы присваивания (у:= г (л, у)); — условные операторы (если р (х) то на И); — операторы перехода (на 1); — операторы ввода и вывода. Сравнивая программу и схему программы из примера, заметям, что схема Я«достаточно детально описывает устройство программы, а именно используемые переменные, логическую структуру программы, структуру операторов. Особенно наглядным становится схемное представление программ, если логическая структура изображена в виде графа, вершинами которого являются операторы, а дуги между вершинами указывают (возможные) переходы от оператора к оператору в процессе выполнения программы.
Такая форма изображения схем близка к популярным среди программистов блок-схемам и широко используется нами. Схема Я в тра~овей форме показана на рис. 4Л. В схеме 8«, нет нйяакой информации о семантике переменных, функциональных и предикатных символов, на основании которой можно было бы установить, что, собственно, вычисляет программа, а вычисляет она факториал и1, где л — начальное значение переменной х, задаваемое оператором ввода.
Проведем следующее преобразование схемы Я . Символы-переменные з и у превратим в переменные (в обычяом смысле слова), сопоставив нм в качестве областей значений множество всех целых неотрицательных чисел. Константу а заменим на чксло 1, функциональный символ я — операцией умножения, символ Ь вЂ” операциеи вычитания единицы, предикатный символ р — преднкатом «равно Оэ. Другими словами, зададим интерпретацию схемы с множеством всех чисел в качестве области интерпретации.
В результате получим запись алгоритма на некотором яаыке программирования, а именно уже выписанную выше программу вычисления факториала. Следовательно, схема программы вместе с некоторой интерпретацией образуют программу; одна и та же схема, ннтер- 7$ претированная различным образом, дает разные программы. Тан, возьмем в качестве области интерпретации множество Уе всех слов в некотором алфавите У. Константу а заменим пустым словом е. Функциональные и предикатные символы заменим операциями и предикатом над словамн." функциональный символ л— двухместной функцией СОЖРАВ е), приписывающей первую букву первого слова ко второму слову (т.
е. СО)'г"ИСАВ (аа, р) = а()); Рве. 4А. С*ем« 8«г е трефовой форме функциональный символ а — одноместной функцией СОВ, стирающей первую букву слова (т. е. СОВ (аа) = а). Предикатный символ р заменим преднкатом «равно пустому слову е». Такая интерпретация схемы Я«. порождает программу, которая любое слово а,аг... а„в алфавите Г, подавпое в качестве начального аначения переменной х, превращает в «перевернутое» слово а„... ...
а а (см. гл. 1, гадание 1.2Б). Программа ягргеорачивания слог. начало слова в>уу ввод (х); у:=е; Й есаи х =е то иа И; р:= СО)УПИСАВ (х, у); х:= СХИ(х); на 7; И: д (р) конец Интерпретируя по-разному переменные, функционалыые и предикатные символы, можно получить соверпюино равные программы. Но все они будут устроены одинаково, имея одни и те же ° ) Фу ц СОЛ ЛСАЛ вЂ” гувер ожц фу ц и СОЛ д к СЛЛ вг ° а Лвсв, фуввцаа СЮЛ вЂ” фующва в» ее«ге же ягмве (43). ЧЪ переменные, одни и те же типы операторов, одну и ту же логическую структуру и т. д. Значит, все эти программы имеют одну и ту же схему (здесь мы употребляем слово «схема» в «общем» смысле, что лишь подчеркивает оправданность термина «схема программы»). Анализ схемы позволяет сделать заключения, относящиеся ко всем программам, полученным из этой схемы с помощью всех возможных интерпретаций.
Пример очень простого заключенвя: если в схеме типа схемы 8«» нет ни одного условного оператора и ни одного оператора перехода, то любая программа из множества всех программ, порождаемых атой схемой н различными интерпретациямн, будет выполняться конечное время, после чего остановится. Более сложные утверждения о схемах программ и программах неоднократно встретятся в последующих разделах книги.
Между свовствами программ и свойствами схем программ устанавливается «терминологическая» связь. Например, говорят, что схема пуста, если любая программа, полученная из нее с помощью интерпретации, пуста, т. е. никогда не останавливается (зацикливается); или что две схемы аквизалентвы, если программы, полученные иэ этих схем одинаковой интерпретацией одноименных функциональных и предвкатных символов, эквивалентны, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
