в главную программу, затирается, что делает возврат к этой программе невозможным. Подобные рассуждения применимы ко всем ячейкам оперативной памяти и к регистрам, используемым подпрограммами. Поэтому разработать правила связи подпрограмм, которые позволят правильно обрабатывать такие рекурсивные ситуации, совсем несложно; подробности приводятся в главе 8.

В завершение этого раздела кратко рассмотрим подходы к написанию сложных и больших программ. Как узнать, какие подпрограммы нам нужны и какие последовательности вызова нужно использовать? Чтобы успешно решить эту задачу, можно воспользоваться методом итераций.

Шаг О (Первоначальная идея). Сначала приблизительно выбираем генеральный план действий, которые будут выполняться в программе.

Шаг 1 (Черновая схема программы). Начнем с написания "внешних уровней" программы на любом удобном языке. Систематизированный подход к этому этапу очень хорошо описан в книге Е. W. Dijkstra, Structured Programmmg (Academic Press, 1972), Chapter 1, и в работе N. Wirth, САСМ 14 (1971), 221-227. Начать можно с разбиения всей программы на небольшие фрагменты, которые временно можно рассматривать как подпрограммы, хотя они вызываются только один раз. Эти фрагменты можио последовательно разбивать на все более мелкие части, которые будут служить для выполнения все более простых операций. Каждый раз, когда возникает какая-либо вычислительная задача, которая, похоже, встретится где-то еще либо уже где-то встретилась, следует определить подпрограмму (уже не гипотетическую, а реальную) для выполнения этой задачи. На данном этапе еще не следует писать эту подпрограмму; нужно продолжить написание главной программы, исходя из предположения, что подпрограмма выполнила свою задачу. И наконец, когда схема главной программы будет готова, можно приниматься за подпрограммы, стараясь начинать с самых сложных подпрограмм, постепенно переходя к вложенным в них подпрограммам и т. д. В результате получится список подпрограмм. Функция каждой подпрограммы, вероятно, менялась уже несколько раз, так что к этому моменту начальные элементы схемы будут неправильными. Ничего страшного, ведь это всего лишь схема. Зато теперь мы имеем достаточно четкое представление о том, как будет вызываться каждая подпрограмма и какова степень ее универсальности. Как правило, имеет смысл сделать каждую подпрограмму более универсальной.

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

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

как в (4). Важно также, чтобы не перекрывались ячейки временной памяти. Если каждая подпрограмма будет обращаться к ячейке TEMP, то последствия могут быть катастрофическими, но во время разработки схемы на этапе 1 нам было удобно не беспокоиться об этом. Очевидный способ решения проблем с перекрытием состоит Б следующем: нужно выделить для каждой подпрограммы отдельный участок временной памяти, чтобы его использовала только она. Но если такое использование пространства памяти является слишком расточительным, то можно использовать другую схему - присвоить ячейкам имена TEMPI, ТЕМР2 и т. д. Нумерация внутри подпрограммы начинается с TEMPj, где j на единицу больше, чем наибольший номер, который был использован какой-либо вложенной подпрограммой этой подпрограммы.

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

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

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

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

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

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

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

Замечание. Большинство предьщущих комментариев было написано автором в 1964 году, после того как он успешно завершил несколько программных проектов среднего масштаба, но до того как он приобрел зрелый стиль программирования. Впоследствии, в 80-х годах, он понял, что, вероятно, еще более важным является метод, который называется структурным документированием или грамотным программированием. Анализ современных представлений об оптимальных способах написания всевозможных программ содержится в книге Literate Programming (Cambridge Univ. Press), впервые опубликованной в 1992 году. Кстати, в главе 11 этой книги приведен подробный перечень всех ошибок, которые были устранены из программы lX в период между 1978 и 1991 годами.

До некоторого момента лучше допустить наличие ошибок в программе, чем потратить на ее разработку столько времени, сколько необходимо для устранения всех ошибок (сколько десятилетий на это потребуется?).

- А. М. ТЬЮРИНГ, Proposals for АСЕ (1945)

УПРАЖНЕНИЯ

1. [10] Сформулируйте характеристики подпрограммы (5). В качестве образца используйте (4), где даются характеристики подпрограммы 1.3.2М.

2. [10] Предложите код, заменяющий (6). Не используйте команду JSJ.

3. [М15] Дополните информацию, которая дана в (4), точно указав, что происходит с регистром J и флагом сравнения при выполнении подпрограммы. Определите также, что происходит в случае, когда в регистре II содержится неположительное число.

► 4. [21] Напишите обобщающую MAXN подпрограмму нахождения максимального значения для последовательности Х[о], Х[о-Ьг], Х[о4-2г], Х[п], где г и п - параметры, а а - наименьшее положительное число, для которого а = п (по модулю г), т. е.