Д. Кнут - Искусство программирования том 1 (1119450), страница 50
Текст из файла (страница 50)
Подпрограммы имеют и другие преимущества. Благодаря им структура больших и сложных программ становится более наглядной. Они разбивают всю задачу на логические сегменты, что обычно облегчает отладку программы. Многие подпрограммы имеют дополнительную ценность, поскольку ими могут воспользоваться не только авторы, но и другие пользователи. Большинство компьютерных средств разработки имеют обширные встроенные библиотеки полезных подпрограмм, что значительно облегчает программирование стандартных прикладных задач. Но программист не должен думать, что подпрограммы предназначены только для какой-то одной цели. Не следует всегда рассматривать подпрограммы только как программы общего назначения, которыми все могут пользоваться.
Не менее важны и подпрограммы специального назначения, даже если они используются только в одной программе. В разделе 1.4.3.1 рассматриваются типичные примеры подпрограмм. Простейшими являются подпрограммы, которые имеют только один вход и один выход, как, например, подпрограмма ИАХ1МОМ, рассмотренная выше (см. раздел 1.3.2, программа М). Еще раз приведем текст этой программы, изменив ее таким образом, чтобы поиск максимума велся по фиксированному числу ячеек, равному 100. ь ИАХ1МОМ ОР Х[1..100) МАХ100 ЗТЗ ЕХ1Т Связь с подпрограммой. Мтя 111 М~~.
И„ дМР 2Р 1н сна х,з нз. с ЮОЕ в+3 2Н ЕИТ2 0,3 М4. Замена гп. 1.0А Х,З Найден новый максимум. 0ЕСЗ 1 145. Уменьшение /с. ЮЗР 1В П32. В.* ЕХ11 ЗМР ь Вернуться к основной программе. 3 В большой программе, содержащей этот код в качестве подпрограммы, с помощью единственной команды 1 ЯМР МАХ100" можно занести в регистр А значение текущего максимума для ячеек с41+ 1 по Х+ 100 и поместить информацию о положении максимума в г12. Связь с подпрограммой в этом случае достигается с помощью команд "ИАХ100 ЯТЯ ЕХ1Т" и позднее — "ЕХ1Т ЭМР ь". Регистр Л работает таким образом, что команда выхода затем перейдет в ячейку, следующую за той, из которой было сделано первоначальное обращение к МАХ100.
Ф В более новых модификациях компьютеров, таких как машина ММ1Х, которой суждено заменить М11, предусмотрены более эффектпвпые способы запомпнанпя адресов возврата. Главное отличие состоит в том, что команды программы больше не модифицируются в памяти; пеобходнмая информация сохраняется в регистрах нлп в специальном массиве, а пе в самой программе (см. упр. 7). В слелуюшем пзданцн данной к~лги будет прггменен современный подход к этим вопросам, а пока будем по-прежнему использовать старый самомоднфтгпруюгцийся код. Нетрудно получить количественные характеристики степени экономичности кода и потери времени при использовании подпрограмм. Предположим, некоторый фрагмент кода занимает А ячеек и встречается в т местах программы.
Чтобы оформить этот фрагмент в качестве подпрограммы, понадобится дополнительная команда ЯТЛ, строка для команды выхода из подпрограммы плюс по одной команде ЭМР в каждом из т мест, откуда будет вызываться подпрограмма. В целом, необходимо т + А + 2 ячеек, а не тй, поэтому экономия составляет (2) (т — 1) (Ус — 1) — 3 ячеек.
Если А равно 1 либо т равно 1, то, очевидно, мы не сможем сэкономить место в памяти за счет использования подпрограмм. Если )с равно 2, то для получения выигрыша т должно быть больше 4., и т. д. Время теряется из-за применения дополнительных команд ЗМР, ЯТЗ и ЗМР, которые не присутствуют в программе, если подпрограмма не используется. Поэтому, если во время выполнения основной программы подпрограмма применяется Г раз, потребуется 41 дополнительных тактов. К этим оценкам следует подходить с определенной долей скепсиса, так как они делались в расчете на идеальную ситуацию. Многие подпрограммы нельзя вызвать просто с помощью единственной команды ЛИР.
Более того, если фрагмент кода повторяется во многих частях программы и он не оформляется в виде подпрограммы, то для каждой части данный код можно модифицировать так, чтобы получать преимущества от особых характеристик конкретной части программы, в которой он находится.
С другой стороны, если принято решение использовать подпрограмму, то ее код нужно писать для наиболее общего, а не частного, случая, и обычно это требует добавления нескольких дополнительных команд, Если подпрограмма написана для общего случая, то она, как правило, зависит от парамегпров. Параметры — это величины, которые управляют работой подпрограммы; они могут изменяться от одного вызова подпрограммы к другому. Фрагмент кода внешней программы, который передает управление подпрограмме и должным образом запускает ее, называется последовательностью вызова.
Конкретные значения параметров, которые передаются при вызове подпрограммы, называются аргументами. В нашей подпрограмме МАХ100 вызывающая последова- тельность — это просто команда "ЛМР МАХ100". Но в случае, когда необходимо передать аргументы, обычно необходима более длинная вызывающая последовательность. Например, программа 1.3.2М вЂ” это обобщенный вариант МАХ100; она находит максимум среди первых и элементов таблицы.
Параметр и появляется в индексном регистре 1,и его последовательность вызова ЬР1 и= ЕМТ1 и ЛМР МАХ1МОМ ЛМР МАХ1МОМ включает два шага. Если последовательность вызова занимает с ячеек памяти, то формула (2) вычисления объема сэкономленного места принимает вид (3) (т — 1) (/с — с) — сопвгапг, а время, которое тратится на связь с подпрограммой, немного увеличивается. Может возникнуть необходимость внесения дальнейших корректив в приведенные формулы, если потребуется сохранить и восстановить некоторые регистры.
Например, работая с подпрограммой МАХ100, следует помнить, что, записывая "ЭМР МАХ100", мы не только заносим максимальное значение в регистр А, а его позицию— в регистр 12, но и обнуляем регистр 13. Нужно иметь в виду, что подпрограмма может испортить содержимое регистров. Чтобы предотвратить изменение подпрограммой МАХ100 содержимого г13, необходимо включить дополнительные команды. Самый короткий и самый быстрый способ сделать это на М1Х состоит в том, чтобы вставить команду "ЯТЗ ЗР(0: 2)" сразу после МАХ100 и команду "ЗМ ЕМТЗ э"— непосредственно перед ЕХ1Т. В итоге это выльется в две дополнительные строки кода плюс три машинных такта для каждого вызова подпрограммы.
Подпрограмму можно рассматривать как расширение машинного языка компьютера. Внеся в память машины подпрограмму МАХ100, получим единственную команду (а именно — "1МР МАХ100"), которая находит максимум. Важно определить результат работы каждой подпрограммы так же тщательно, как были определены сами операторы машинного языка. Поэтому программист обязательно должен записать характеристики каждой подпрограммы, даже если больше никто не будет пользоваться этой программой или ее спецификацией. Например, подпрограмма МАХТМОМ, приведенная в разделе 1.3.2, имеет следующие характеристики.
Последовательность вызова: 1МР МАХ1МОМ. Состояние при входе: Л1 = и; в предположении, что и > 1. (4) Состояние при выходе: гА = шах ООМТЕМТЗ(Х+ А) = ООМТЕИТЗ(Х+ г12); 1<ь<ь г13 = 0; содержимое г3 и С1 также меняется. (Обычно мы не будем упоминать о том, что подпрограмма оказывает влияние на регистр Л и флаг сравнения; здесь об этом говорится только для полноты.) Заметьте, что на гХ и гП подпрограмма действия не оказывает, в противном случае эти регистры были бы упомянуты в описании состояния при выходе.
В спецификации должны также перечисляться все внешние для подпрограммы ячейки памяти, на которые она может оказать воздействие. В нашем случае спецификация позволяет заключить, что в памяти ничего не сохранялось, так каК в (4) ничего не говорится об изменениях в памяти. А теперь давайте рассмотрим несколько входов в подпрограммы Предположим, существует программа, которой требуется общая подпрограмма МАХ1МОМ Но дело в том, что обычно использувтся частный случай МАХ100.
для которого и = 100. Эти две подпрограммы можно объединить следующим образом. МАХ100 ЕМТЗ 100 Первый вход МАХМ ЯТЛ ЕХ1Т Второй вход ЗМР 2Р Продолжать, как в (1) ЕХ1Т ЗМР е Вернуться к основной программе 'э Подпрограмма (5) практически такая же, как (1), только первые две команды поменялись местами. Здесь использовался тот факт, что команда "ЕИТЗ" не изменяет содержимое регистра Л. Чтобы добавить к этой подпрограмме трешиО вход, МАХ50, в начало нужно вставить строки МАХЯО ЕМТЗ 50 (6) 353 МАХМ (Напоминаю, что ЯЗЯГ' означает переход без изменения регистра 3.) Если число параметров невелико, то желательно передавать их в подпрограмму одним нз двух способов занеся их в подходящие регистры (аналогично тому.
как мы использовали г13 для хранения параметра и в МАХИ, а гП вЂ” для хранения параметра и в МАХ1МОМ) либо сохранив их в фиксированных ячейках памяти. Другой удобный способ передачи аргументов состоит в том, чтобы просто перечислить их после команды ЭМР. Подпрограмма сможет обратиться к своим параметрам, поскольку она знает содержимое регистра д. Например, если бы понадобилось создать для МАХИ последовательность вызова ЛМР МАХМ (Т) СОМ и то подпрограмму можно было бы написать следующим образом: МАХМ ЯТ3 а+1 ЕИТ1 ь гП +- г3 ЕОЗ О, 1 г13+- и ЗМР 2Р Продолжать, как а (1) (Я) 3ЗР 1В ЛМР 1,1 Возврат э На таких машинах, как 1ВМ 360, на которых связь с подпрограммами обычно осуществляется путем помещения адреса ячейки возврата в индексный регистр, приведенный выше способ особенно удобен. Он используется также, когда у подпрограммы много аргументов либо если программа создана компилятором Метод нескольких входов, который использовался выше, в этом случае не подходит.
Его можно "подделать', написав МАХ100 ЯТЭ 1Р ЭМР МАХМ СОМ 100 1Н Л1Р но это выглядит уже не так привлекательно, как (5). Для подпрограмм с несколькими выходами обычно используется метод, аналогичный перечислению аргументов. Множественный выход означает, что подпрограмма возвращается в одно из нескольких различных мест в зависимости от условий, обнаруженных подпрограммой. В самом строгом смысле место, в которое возвращается подпрограмма после выхода,— это параметр. Поэтому, если существует несколько мест, в которые она может выйти в зависимости от обстоятельств, они должны быть предоставлены в качестве аргументов.
В нашем завершающем примере в подпрограмме поиска максимума будет два входа и два выхода. Последовательность вызова имеет такой вид. Для произвольного и Ейтз и ЛМР МАХЕ Выйти здесь, если гпах < 0 или гпах > гХ Выйти здесь, если 0 < шах < гХ Для и = 100 ЭМР МАХ100 Выйти здесь, если шах < О или шах > гХ Выйти здесь, если 0 < шах < гХ (Другими словами, выход производится на две ячейки ниже команды перехода, если максимум положителен и меньше значения, которое содержится в регистре Х) Для этих условий подпрограмму написать несложно. МАХ100 ЕМТЗ 100 Вход лля п = 100 МАХЕ ЗТЛ ЕХ1Т Вход лля произвольного и ЗМР 2Р Далее, как в (1) Выполнить нормальный выход, если шах < 0 ЕХ1Т Одни подпрограммы могут вызывать другие подпрограммы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
