Д. Кнут - Искусство программирования том 1 (1119450), страница 51

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 51)

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

Наприлгер, рассмотрим следующий сценарий. [Подпрограмма С) с зтз ехттс [Подпрограмма В] ЯТЛ ЕХТТВ [Главная программа) [Подпрограмма А] А ЯТЭ ЕХ1ТА ЭМР А ЭМР В ЗМР А ЕХ1ТС ЭМР я (10) ЕХ1ТА ЗМР ь ЕХ1тв ЛР ь Если главная программа вызывает А, которая вызывает В, которая вызывает С, а затем С вызывает А, то адрес в ячейке ЕХ1ТА, по которому осуществляется выход ЗЗР 1В ЗАМР ЕХТТ ЗТХ ТЕМР СМРА ТЕМР ЗСЕ ЕХ1Т ЕМТЗ 1 ЭМР ь,З Выполнить нормальный выход, если шах > гХ. В противном случае выйти через второй выход Вернуться в нужное место з в главную программу, затирается, что делает возврат к этой программе невозможным. Подобные'рассуждения применимы ко всем ячейкам оперативной памяти и к регистрам, используемым подпрограммами.

Поэтому разработать правила связи подпрограмм, которые позволят правильно обрабатывать такие рекурсивные ситуации, совсем несложно; подробности приводятся в главе 8. В завершение этого раздела кратко рассмотрим подходы к написанию сложных и больших программ. Как узнать, какие подпрограммы нам нужны и какие последовательности вызова нужно использовать? Чтобы успешно решить эту задачу, можно воспользоваться методом итераций. Шаг О (Первоначальная идея). Сначала приблизительно выбираем генеральный план действий, которые будут выполняться в программе. Шаг 1 (Черновая схема программы). Начнем с написания "внешних уровней" программы на любом удобном языке.

Снстематизированный подход к этому этапу очень хорошо описан в книге Е. %. Пц1сэтга, Яггис~пгед Ргойгатттй (Асадеппс Ргеээ, 1972), Сйарсег 1, и в работе М. %1ггЬ, САСМ 14 (1971), 221 — 227. Начать можно с разбиения всей программы на неболыпие фрагменты, которые временно можно рассматривать как подпрограммы, хотя они вызываются только один раз. Эти фрагменты можно последовательно разбивать на все более мелкие части, которые будут служить для выполнения все более простых операций.

Каждый раз, когда возникает какая-либо вычислительная задача, которая, похоже, встретится где-то еще либо уже где-то встретилась, следует определить подпрограмму (уже не гипотетическую, а реальную) для выполнения этой задачи. На данном этапе еще не следует писать эту подпрограмму; нужно продолжить написание главной программы, исходя из предположения, что подпрограмма выполнила свою задачу. И наконец, когда схема главной программы будет готова, можно приниматься за подпрограммы, стараясь начинать с самых сложных подпрограмм, постепенно переходя к вложенным в них подпрограммам и т.

д. В результате получится список подпрограмм. Функция каждой подпрограммы, вероятно, менялась уже несколько раз, так что к этому моменту начальные элементы схемы будут неправильными. Ничего страшного, ведь это всего лишь схема. Зато теперь мы имеем достаточно четкое представление о том, как будет вызываться каждая подпрограмма и какова степень ее универсальности, Как правило, имеет смысл сделать калслую подпрограмму более универсальной. Шаг 2 (Первая рабочая программа). Этот шаг по сравнению с шагом 1— движение в противоположном направлении. Теперь будем использовать компьютерный язык программирования, скажем, И1ХА1., Р1./И1Х или язык высокого уровня.

На этот раз начнем с самых низких уровней вложения подпрограмм, затем "поднимемся вверх" и в конце концов напашем главную программу. Рекомендуется, по возможности, не писать какие. либо команды вызова подпрограммы до того, как будет написан код самой подпрограммы. (На шаге 1 мы старались делать прямо противоположное, не рассматривая подпрограмму до тех пор, пока не будут написаны все ее последовательности вызова.) По мере написания все большего и большего числа подпрограмм наша уверенность будет постепенно расти, так как мы постоянно расширяем возможности программируемого модуля.

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

Очевидный способ решения проблем с перекрытием состоит в следующем: нужно выделить для каждой подпрограммы отдельный участок временной памяти, чтобы его использовала только она. Но если такое использование пространства памяти является слишком расточительным, то можно использовать другую схему — присвоить ячейкам имена ТЕМР1, ТЕМР2 и т. д. Нумерации внутри подпрограммы начинается с ТЕМРО', гдето' на единицу больше, чем наибольший номер, который был использован какой-либо вложенной подпрограммой этой подпрограммы.

Шаг 3 (Повторная проверка). Результатом шага 2 должна быть практически рабочая программа, но вполне возможно, что ее удастся улучшить. Для этого существует хороший метод †сно сменить направление, исследуя для каждой подпрограммы есе сделанные по отношению к ней вызовы. Может оказаться, что подпрограмму необходимо несколько расширить, чтобы она выполняла распространенные операции, которые всегда осуществляет внешняя программа непосредственно перед использованием подпрограммы или после него. Возможно, несколько подпрограмм следует объединить в одну; а может быть, некоторая подпрограмма вызывается только один раз и из нее вообще не стоит делать подпрограмму. (Случается и такое: подпрограмма не вызывается ни разу и можно вообще обойтись без нее.) На этом этапе очень часто имеет смысл выбросить все, что было сделано, и снова начать с шага 1! Я вовсе не шучу; время, потраченное на то, чтобы добраться до этого места, не пропало даром, так как вы достаточно глубоко изучили поставленную задачу.

Впоследствии (уже после запуска программы), скорее всего, станет ясно, что в общую схему программы необходимо было внести некоторые улучшения. Поэтому нет причин бояться возврата к шагу 1 — намного легче снова пройти шаги 2 и 3 сейчас, когда аналогичная программа уже готова.

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

Когда совершенно очевидно, что можно внести значительное улучшение, имеет смысл потратить дополнительное время на то, чтобы начать все сначала. Но в конце концов наступает стадия "насьпцения", когда сколько-нибудь существенные изменения внести уже нельзя и результатом их воплощения является лишь незначительный прогресс. Шаг 4 (Отладка). После окончательной 'шлифовки" программы, к которой, видимо, относится распределение памяти и другие последние приготовления, самое время посмотреть на нее под еще одним углом зрения, отличным от тех, которые использовались на шагах 1, 2 и 3. Теперь мы будем исследовать элементы программы в том порядке, в котором нх будет емполнлгпь компьютер.

Это можно сделать вручную или, конечно, с помощью компьютера. Автор пришел к выводу, что на данном этапе очень полезно использовать системные программы, которые прослеживают каждую кдманду, когда она выполняется первые два раза. Очень важно заново продумать идеи, лежащие в основе программы, и убедиться в том, что все действительно прот1сходит так, как ожидалось. Отладка — это искусство, которое требует дальнейшего изучения, и способ ее проведения в значительной степени зависит от имеющихся на компьютере устройств.

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

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

Характеристики

Список файлов книги