2.1. Зачем читать чужие программы?
Прежде чем начать (Чего не могут компьютеры?)
«Разруха сидит не в клозетах, а в головах»
М.Булгаков «Собачье сердце».
Тот, кто считает, что процесс программирования заключается во вводе в компьютер различных команд и выражений, написанных на языке программирования, глубоко ошибается. Программа, на самом деле, пишется в голове и переносится по частям в компьютер, поскольку голова не является самым удобным инструментом для ее выполнения.
Здесь я хотел бы сразу же снять некоторые заблуждения, которые возникают у начинающих:
компьютер - это инструмент программирования, никакие достоинства инструмента не заменят навыков работы с ним. И уж тем более нельзя объяснять низкое качество производимого продукта только несовершенством инструмента;
компьютер никогда не будет «думать за вас». Если вы работаете с готовой программой, тогда может сложиться такая иллюзия. Если же вы разрабатываете свою, следить за ее работой должны именно вы. То есть ее нужно параллельно с компьютером «прокручивать» в собственной голове. Процесс отладки в том и состоит, что вы сами отслеживаете разницу между работой той идеальной программы, которая пока находится у вас в голове, и той реальной, имеющей ошибки, которая в данный момент «крутится» в компьютере;
в любом виде деятельности имеется своя технология - это совокупность знаний, навыков, инструментов, правил работы. В программировании также есть своя технология. Ее нужно изучить и приспособить под свой образ мышления.
Программирование тем и отличается от всех других видов деятельности, что представляет собой в концентрированном виде формально-логический образ мышления. Как известно, человек воспринимает мир «двумя полушариями» - образно-эмоционально и формально-логически. Компьютер содержит в себе вторую крайность - он в состоянии воспроизвести с большой скоростью заданный набор формально-логических действий, именуемых иначе программой. В принципе, человек может делать то же самое, но в ограниченных масштабах. Как было метко сказано: «Компьютер - это идиот, но идиот быстродействующий».
Любой набор формальных действий всегда дает определенный результат, который уже является внешней стороной процесса. Какой-либо «смысл» для самой формальной системы (программы) этот результат не имеет. То есть компьютер в принципе не ведает, что творит. Программист же, в отличие от компьютера, должен знать, что он делает. Он отталкивается от цели, результата, для которых он старается создать соответствующую им программу, используя всю мощь своего разума и интеллекта. А здесь нельзя обойтись без образного мышления, интуиции и, если хотите, вдохновения.
В своей работе программист руководствуется образным представлением программы, он видит ее «целиком» в процессе выполнения и лишь затем разделяет ее на отдельные элементы, которые являются в дальнейшем частями алгоритмов и структур данных. В этом его коренное отличие от компьютера, который не в состоянии сам писать программы.
Чтение – вот лучшее учение
«Не нужно читать много книг»
Мао Дзе Дун. Речь 13 октября 1957 г.
на Верховном государственном совещании
Мое глубокое убеждение, изучение программирования нужно начинать с чтения чужих программ. Риторический вопрос, зачем. Естественно, не для того, чтобы показать, какие это умные люди – другие программисты. И, естественно, не какие-то произвольные программы, а нарочно для этого подобранные.
Обычный разговорный язык не так богат, как кажется. То же самое касается программ. Довольно большой процент программы составляют «стандартные фразы», а многообразие программ на самом деле заключается в их комбинировании. Действительно оригинальные алгоритмы в практике обычного программиста встречаются довольно редко. Обычно он занят рутиной – конструированием тривиальных алгоритмов из стандартных заготовок.
Но к процессу самого проектирования обратимся позднее. Пока предстоит освоить «джентльменский набор» фрагментов программ. Тут необходимо сделать два замечания. Во-первых, в отличие от обычного текста, синтаксические фрагменты программы не только следуют друг за другом, но и вкладываются друг в друга. Поэтому «хвост» фрагмента может отстоять от «головы» на достаточно большом расстоянии. Во-вторых, определяющим является некоторый логический каркас фрагмента, а составные его части могут быть произвольны. Например, поиск максимального значения элемента по- разному выглядит таких структурах данных, как массив, массив указателей, список и дерево, но имеет неизменную, инвариантную ко всем структурам данных часть.
int F(int A[], int n) { // Массив
int i,s;
for (i = 0, s = A[0]; i < n; i++)
if (A[i] < s) s = A[i];
return s;
}int F(int *A[]) { // Массив указателей
int i,k;
for (i = k = 0; A[i] != NULL; i++)
if (*A[i] < *A[k]) k = i;
return *A[k];
}int F(list *ph) {
list *p, *q; // Список
for (p = q = ph; p != NULL; p = p->next)
if (p->val < q->val) p = q;
return q->val);
}int F(xxx *q) { // Дерево
int i, n, m;
if (q == NULL) return 0;
for (n = q->v, i = 0; i < 4; i++)
if ((m = F(q->p[i])) > n) n = m;
return n;
}Из сравнения программ видно, что в них имеется сходные конструкции, заключающиеся в условном присваивании в теле цикла, вид которых не зависит ни от структуры данных, ни от того, находится минимум в виде самого значения, указателя на него или его индекса. Неважно также, каким образом просматривается последовательность элементов. Если оставить только общие части, то получится даже не конструкция языка, а некоторая логическая схема:
for (s = «первый объект», «цикл по множеству объектов»)
if («очередное» < s) s = «очередное»;Эта схема имеет двоякое значение. Во-первых, в каких бы контекстах она не встречалась, она дает один и тот же результат. Во-вторых, она определяет смысл переменной s.
Кроме того, есть еще некоторое количество логических конструкций программы, понимание которых требует обращения не столько к логике, сколько к здравому смыслу. Убедительность и доказательность их состоит в их очевидности. А очевидность заключается в том, что им можно найти аналогии в обычном «физическом» мире, например, в виде перемещений, сдвигов и других взаимосвязанных движений объектов в пространстве.
Таким образом, умение читать программы – это не просто повторение того, что написано на языке программирования при помощи других слов. Это даже не интерпретация, то есть не последовательное выполнение операторов программы в голове или на бумаге. Чтение программы - это умение «видеть» знакомые фрагменты, выделять их, и уже затем воссоздавать результат ее работы путем логического соединения в единое целое. Полезность этого занятия еще и в том, что проектирование программы представляет собой почти обратный процесс: в образном представлении процесса, ведущего к заданному результату, нужно «увидеть» составные фрагменты, а затем «выстроить» их в нужном порядке.
Процесс чтения и понимания программы (также, кстати, как и процессы ее написания и трансляции) не является линейным. Научно выражаясь, он представляет собой диалектическое единство анализа и синтеза:
разложение программы на стандартные фрагменты, формулировка смысла каждого из них, а также смысла переменных;
соединение полученных частей в единое целое и формулировка результата. Вот здесь, для понимания сущности взаимодействия фрагментов друг с другом можно интерпретировать (выполнять, прокручивать) части программы в голове, на бумаге или в отладчике. Это позволяет увидеть вторичный смысл программы, который в явном виде не присутствует в ее тексте.
Для более-менее свободного общения на любом языке программирования необходимо знание некоторого минимума «расхожих фраз» - общеупотребительных программных контекстов.
Наличие «джентльменского набора расхожих фраз», находящихся выше конструкций языка
программирования, показывает, что языки программирования на самом деле не
совсем удобны для программирования как такового. На практике программисты
многократно дублируют одни и те же алгоритмы в разных структурах данных, языках
программирования, а для одного языка – в разных системах программирования (см.
приведенный выше пример поиска минимума). А на более общем уровне – проецируют
одни и те же идеи (алгоритмы) в различные модели и формы представления данных.
И если в рамках одной системы программирования для разных структур данных
предпринимаются попытки унификации (например, библиотека шаблонов STL), то в более широком
контексте это не делается. Приведем ряд примеров такой «избыточности» или
«повторяемости» в программировании:
система динамического распределения памяти, в принципе, одинакова для ядра операционной системы и для приложений (вплоть до совместно используемого программного кода на Си), но каждая реализована в своем адресном пространстве, и, возможно, имеет специфику на архитектурном (машинно-зависимом) уровне, учитывающую особенности систем адресации в различных режимах работы процессора;
структура данных – односвязный список, может быть реализована в памяти с использованием структурированных типов, содержащих указатели. Аналогичный список в двоичном файле поддерживается через функции ввода-вывода, при помощи которых понятие «указатель» интерпретируется в двоичном файле на основе обычной целой переменной типа long. Такая система аналогий позволяет спроецировать программы из одной системы представления данных в другую;
дерево с двумя потомками моделируется в массиве путем вычисления индексов двух потомков в виде 2n и 2n+1. Это позволяет спроецировать алгоритмы, работающие с деревьями на обычные массивы (пирамидальная сортировка);
такие объекты, как таблица реляционной базы данных и динамический массив структур в памяти, являются аналогичными, к ним применимы практически одни и те же алгоритмы упорядочения и поиска данных. Фактически это проекции одного и того же понятия в разные программные среды (ограниченные, неэффективно организованные, не сохраняемые данные в оперативной памяти, и аналогичная более развитая система представлений – для внешней (файловой)).
Отсюда и содержание «джентльменского набора»: это технологические решения и приемы, а также алгоритмы наиболее употребительных действий над множествами объектов, независимо от их природы (сумма, количество, минимум, первый из… и т.п.), которые используются в массовом рутинном программировании (откуда такое берется – сказано было выше) на том уровне представлений, какой дают современные языки программирования.
