1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (Котов, Сабельфельд 1991 - Теория схем программ)

ББК 22.18 К73 вДК 619.681 К о т о в В. Е., С а б е л ь ф е л ь д В. И. Теоркя схем преграмм.— М.: Наука. Гл. ред. фнз.-мат. лиг., 1991.— 243 с.— 13ВИ 5~02-913974-2. Научное изданве НСГСВ В»Зол В»мн»»аич САВДЛБФВЛБД Внн»кор Кар»о»о» ТЕОРИЯ СХЕМ ПРОГРАММ Ве елумщий рененкаед В. ю. д 0» Редактор»с Г. А. Сленкеоа. Г.

В. Второ»атоса Хузокысгооввый редактор г. и. Вольт»око текввчеснвй редактор В. В. Мораэс»а Корректоры: Ю. В. Тррв»кое»Ь и. В. Гик»но»а ИБ гй 32356 сдано а не6ор 66,06.69. надписано н печати 30.03.91. Формат еохзв7»» Вумзга тип. 90 3. Гарввтуре асыкнозевкаа. Печа»ь амсокаа.

Уел печ. л. 16.6. Уел. кр.-огт. 10,79. Уч.-вод, л, 10,06. Тарик 7360 ова. Век. ЬВЬ Ноак 6 р, 66 н. издательско-проаоводстоенпое и вавготоргоное ор»еловские «Науое» Главная редекавк $кзико-математнчесной литературы М7071 Москва В-7В Ленввсквй проспект, Гз Вторан тапогра4ып издательства «Наука» 737099 М сю Г-зз, ВГусииы»вй пер., Е И М5-91 053(Щ-91 Щ»Наунвь Фвзиатпвт, 19М 1 8БК 6-02-013974-2 Проведено свстематизироваивое изложение раздела теоретического программировании, изучающего иоиптерпрегированвме модели программ — их схемы, отражавицие структурные особенности программ я в определенной мере абстрагирующвеся от их функциональной сущноств.

Излагается теория схем программ, являющаяся матеюпмчесвой бовой для развития методов траполицкв программ в соаднввя новых конструвцвй в язьвах программирования. ля специалистов в области внфо4жатяви и прикладной математики. л. 61. Библвогр. 142 ваза. Памяти иешеее у опеля АНДРЕЯ ПЕТРОВИЧА ЕРШОВА песе ящаетея ПРЕДИСЛОВИЕ В развитии практики программирования для ЭВМ сложилась парадоксальная ситуация.

С одной стороны, благодаря впечатляющим успехам развития вычислительной техники сегодня мы располагаем ЭВМ, которые работают быстрее первых серийных машин начала 50-х гг. в сотни тысяч н миллионы раэ. Это овна- чает, что мы располагаем мощным инструментом, «усиливающим» человеческий интеллект и позволяющим автоматизировать решение широкого круга задач. Парадокс, однако, заключается в том, что средняя производительность труда программистов за это вромя выросла всего лнвгь в десятки раэ, а для системных программистов не выросла даже на порядок. Несмотря на появление языков высокого уровня, мощных операционных систем и ешь ' теллектуалъныхе устройств общения, программисту все еще приходится тратить много времени и усилий на рутинную работу на длинном пути от математической постановки задачи до получения окончательных резулътатов.

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

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

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

Кроме того, н сама теория, и в особенности методы программирования продолжают развиваться, поэтому трудно дать краткое, точное и одновременно динамичное название атой теории. Скажем, в англоязычных странах в настоящее время используются термины «ТЬеоге«!са1 сошрп«ег зс1евсеэ, «Ма«Ьеша«1са1 ФЬеогу о1 сошрп«аМопээ, «ТЬеоге«1са1 (ша$Ьеша«1са1) 1оппба«1опэ о1 сошрмег эс1епсеэ, «ТЬеогу о1 ргойгашз«.

Следуя А. 11. Ерпюву, мы употребляем термин «теореткческое программирование«в качестве названия математической дисциплины, изучающей синтаксические и семантические свойства программ, их структуру, преобразования, процесс их составления я исполнения. Это словосочетание построено по аналогии с названиями таких наук, как теоретическая физика, теоретическая механика и т.

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

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

Зги исследования тесно соприкасаются с теорией алгоритмов и вычвслимых функций, теорией автоматов и формальных языков, логикой, алгеброй, с теорией сложности вычислений. 2. Т е о р и я с х е и п р о г р а и м (с х е м а т о л о г н я). В этих работах внимание концентрируется на изучении структурных свойств и преобразований программ, а именно тех, которые отлвчэют программы от других способов задания алгоритмов Главным объектом исследования становится схема программы— математическая модель программы, в которой с той или иной ~ тоиеиью детализации отражено строение программы, взаимодействие составляющих ее компонентов. 3.

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

В частности, работы по методам проверки семантической правильности программ нацелены на автоматизацию их отладки и автоматический синтез программ. 4. Теория вычислительных, процессов и структур (теория параллельных вычислен и й). Исследования в отой области направлены на разработку и обоснование новых методов и средств программирования, прежде всего методов программирования параллельных процессов.

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

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