1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 37
Текст из файла (страница 37)
Таким образом, решение задачи экономии памяти болыпого объема свелось к последовательности задач, каждая из которых может иметь существенно меньший объем вычислений. Поскольку сложность алгоритмов зкономии памяти пропорциональна по крайней мере квадрату числа вершин в графе переходов, такая факторизация, хотя и приводя к решению нескольких задач вместо одной, может давать болыпой выигрыш во времени, хотя и за счет, быть может, несколько худшего распределения памяти. Рис.
5.2 содержит пример факторизации операторной схемы. ркс. 5.2. Фвкториввпвя графа переходов. Магазинное распределение памяти. Оба способа уменьшения объема задачи экономии памяти основаны на том, что мы умеем выделять такие части программы, в которых гарантированно содержатся маршруты интересующих нас информационных связей. Не без умысла мы назвали величины, реализующие такие внутренние информационные связи, локальными. Вспомним теперь, что такой точно термин имеется и в алголе Локальными в блоке являются те величины, описания которых помещены в начале данного блока. Отвлекаясь ради простоты изложения идеи от наличия процедур в алголе, мы можем по некоторому размышлению заметить, что иа помещения описания величины в некоторый блок автоматически следует, что все маршруты информационных пар, ре- 5 5Л.
СВЯЗЬ С ТЕОРИЕН И ПРАКТИКОЙ $75 ялизуемых через эту величину, будут проходить только через операторы, образующие данный блок. Два блока алгольной программы называются параллельными, если в тексте программы ни одни иа них не вложен в другой. В свете сказанного очевидно, что локальные величины параллельных блоков никогда не конкурируют друг с другом и поэтому могут размещаться на одном и том жэ участке памяти.
Отсюда вытекает очень простой способ экономного распределения памяти для алгольных программ, имеющих блочную структуру. Будем считать, что ячейки памяти, отводимые для хранения величин, располагаются сверху вниз, при этом занятый участок памяти находится наверху, а свободный — внизу. Их разделяет рабочая точка. 1ряачала рабочая точка находитсянаверху — вся память свободна'. Память распределяется при однократном движении слева направо вдоль текста программы. Тогда правило распределения таково: пусть мы при движении по программе проходим открывающую скобку блока В и пустьдля размещения величин, локальных в этом блоке, требуется 1 ячеек. Тогда в момент прохождения открывающей скобки мы сдвигаем рабочую точку .на 5 ячеек вниз и на только что занятом участке размещаем локальные величины блока В. При прохождении закрывающей скобки блока В мы подымаем рабочую точку вверх на те же 5 ячеек.
При таком подходе участок памяти, занятый последним, освобоя«дается первым. Потому-то этот способ распределения памяти называется магааинным — от слова «магазин» в огнестрельном оружии: там точно так же патрон, снаряженный в магазин последним, выстреливается первым. На рис. 5.3 показан пример магазин- лого распределения памяти в нашей программе ЭПОС, имеющей развитую блочную структуру.
Участки памяти в магазине помечены номерами блоков, к которым они относятся. Тела процедур раамножены и подставлены в места их вызова. Схемы и программы. При применении разработанных нами алгоритмов экономии памяти к реальным программам возникает еще одна проблема, которая, хотя и аатрагивалась содержательным анализом, осталась тем не менее за рамками теории. Наша теория гарантирует при перераспределении памяти сохранение множества маршрутов информационных пар, но ничего не говорит о том, что программа (не схема, а программа!), полученная иа исходной таким преобразованием, будет работать так же успешно, как н исходная.
Честно говоря, у нас с вами, читатель, нет сомнений в этом, ио это всего лишь уверенность в правильной постановке аадачи и в корректности основополагающего определения вычисляемости одной схемы другой (з 2.2). Тем не менее, строгого доказательства корректности распределения памяти в применении к программам мы не имеем и в рамках нашего рассмотрения нв можем иметь и в принципе. ГЛ. 5. ЗАКЛЮИИТЕЛЬНЫЙ АНАЛИЗ О О С5 о й 3 о о о о Ф И й й Ф Ф Ф о 55 О о Ф Й $ ЬЬ СВЯЗЬ С ТЕОРИВЙ И ПРАКТИКОЙ 177 Проаналиаируем кратко, чего же нам не хватает.
Прежде всего у нас нет определения, что такое программа, что такое ее работа и что значит сохранение работы при преобразовании программ. Нахождение таких определений — это, по существу, расширение нашей теории и включение указанных понятий в круг математического рассмотрения. Очевидно, что это расширение теории должно быть тесно связано с уже введенными строгими определениями с тем, чтобы беа труда усматривать в формальной программе ее схему'и, наоборот, имея факт, установленный для схемы, хорошо представлять, для каких программ этот факт полезен. Только что сказанная фраза уже дает понять, как связаны понятия программы и ее схемы.
Человек сочиняет программу, машина ее исполняет. Человек не может передать программу машине, не написав ее сначала, т. е. не придав ей некоторую внешнюю текстовую форму. Текст программы сам по себе еще недостаточен, чтобы решить задачу, вызвавшую появление этой программы. Только в машине есть устройство, которое придает смысл, или как говорят, интерпретирует, например, символ операции + в программе или связывает с символом величины х определенное содержимое. Таким оу)7азом, мы вдыхаем жизнь в программный текст, лишь дав ему некоторую интерпретацию, существующую по отношению к составным элементам программы сама по себе, отдельно, в виде исполнительных устройств машины или по крайней мере в виде другой «сверхпрограммы» — точного описания правил работы этих устройств.
Это разделение нашего- знания о программах — на текст и на его смысл — находит свое отражение в разделении описания алгоритмических языков на синтаксис (учение о тексте) и семантику (учение о смысле). Возвращаясь снова к операторным схемам и программам, мы приходим к бесспорному наблюдению, что схема — это есть некоторая абстракция текста программы. В ней содержится кое-что из того, что можно увидеть, прочитать в тексте программы, не выполняя его. Наши операторные схемы содержат имена операторов и величин, а также перечень возможных передач управления от одного оператора к другому. Для того чтобы превратить схему в программу, нам нужно дать интерпретацию формальным символам схемы.
В нашем случае дать интерпретацию величинам— это значит описать множества их значений (задать предметную область), дать интерпретацию оператору — значит задать значения его результатов и способ выбора преемника (оператора, 'выполняемого вслед за данным) как некоторую конкретную функцию значений его аргументов. Эта интерпретация позволит описать точно процесс выполнения программы. Далее, для программы можно определить ее аргументы и результаты. Тогда естественным определением работы программы будет вычисление своих результатов как некоторой результирующей фуякцпи своих аргументов.
178 ГЛ. Ь ЗАКЛЮЧИТЕЛЬНЫЙ АНАЛИЗ Если две программы работают одинаково — это значит, что они вычисляют одну и ту же функцию. И вот теперь узловой момент о связи теории схем программ с самыми программами. Пусть мы располагаем некоторым фактом Р о схеме 6. Первое, что мы должны уметь, это, задав некоторую интерпретацию 1,кревращающуюсхему С в программу Р=(1, г",), истолковать фант Р как некоторый факт (1, Р) о программе Р. Так вот, наш факт о схеме б интересен и всеобщ, если из справедливости Р вытекает справедливость всех (1, Р), какова бы ни была интерпретация 1.
В нашем случае, имея в качестве «схемного» факта утверждение о вычисляемости одной схемы другой (С' ) С), мы хотели бы иметь как следствие из него, что программы (1, С') и (1, б) будут вычислять всегда одну и ту же функцию, какова бы ни была интерпретация 1. Мы не будем развивать дальше наших рассуждений, потому что сделаем это аккуратно для другого класса схем во второй части книги. Заметим только для успокоения, что такого рода обоснование нашей теории экономии памяти на самом деле имеет место. Нам осталось сделать некоторый чисто программистский комментарий к реализационной части нашего исследования. Составленная нами программа носит вполне реальный характер, хотя, ради демонстрации метода структурированного программирования и из-за некоторой бедности алгола 60, мы на первый план поставили естественность, или, более точно, прямолинейность реализации. Каковы другие, не рассмотренные нами факторы, которые надо было бы учесть при аккуратном программировании? Во-первых, структурированное программирование, по крайней мере в выбранном нами формализме, соадает слишком много блоков.
В некоторых трансляторах с алгола вход в блок программируется с большими накладными расходами, неоправданными ради описания, например, одного параметра цикла или другой мимолетной величины. Воаможно, что процесс структурированного программирования должен после завершения непосредственного построения программы и ее проверки сопровождаться систематическим ее преобрааованием, например, сокращающим количество блоков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
