bas08-06.txt

   Перечислим теперь основные  п р и н ц и п ы  и  м е т о д ы   структур-
ного программирования.

                                            Вы говорите, что я повторяюсь.
                                            Но я повторю.
                                                               Т.С.Эллиот

          ┌────────────────────────────────────────┐
   I.     │    Как можно меньше переходов GOTO !   │
          └────────────────────────────────────────┘
   Э. Дейкстра выразил это таким образом: "Уже давно  было замечено,  что
квалификация программистов является убывающей функцией от плотности  пред-
ложений GOTO в создаваемых ими программах". Причина этого  заключается  в
том, что основные конструкции структурного программирования гораздо более
лаконичны и просты, чем их аналоги  на неструктурном языке  программирова-
ния, например MSX-BASIC. Отсюда сразу следует, что  программы, написанные
на MSX-BASIC, будут насыщены предложениями GOTO (написанными как явно,так
и неявно!).
   Четыре предложения структурного программирования  на  приведенной ниже
схеме в той или иной форме используются во многих языках программирования
(приведены примеры конструкций языка программирования TURBO Pascal).
┌────────────────────┬─────────────────────┬───────────────────────────┐
│     Предложения    │     Неформальное    │  Соответствующая последо- │
│    структурного    │       описание      │  вательность  операторов  │
│  программирования  │                     │    на языке  MSX-BASIC    │
│────────────────────┼─────────────────────┼───────────────────────────│
│                    │ Если условие истинно│                           │
│                    │ выполнить  предложе-│                           │
│IF C THEN S1 ELSE S2│ ние S1;             │   IF C THEN S1 ELSE S2    │
│                    │ в противном  случае │                           │
│                    │ выполнить  предложе-│                           │
│                    │ ние S2              │                           │
│────────────────────┼─────────────────────┼───────────────────────────│
│                    │ Повторить  предложе-│                           │
│                    │ ние S, пока условие │      GOTO n               │
│    WHILE C DO S    │ С останется истинным│   m: S                    │
│                    │ (0 или более раз)   │   n: IF C THEN GOTO m     │
│                    │                     │                           │
│────────────────────┼─────────────────────┼───────────────────────────│
│                    │ Повторять последова-│                           │
│                    │ тельность  S  (один │                           │
│  REPEAT S UNTIL C  │ или  более  раз) до │   m: S                    │
│                    │ тех пор, пока  усло-│   IF NOT C THEN GOTO m    │
│                    │ вие С не станет  ис-│                           │
│                    │ тинным              │                           │
│────────────────────┼─────────────────────┼───────────────────────────│
│                    │ Выполнить  предложе-│                           │
│       CASE K OF    │ ние Si(только, если │    ON K GOTO N1,N2,...,Nm:│
│    1: S1           │ значение K=i,причем │    GOTO s                 │
│    2: S2           │ i равно либо 1,     │ N1:S1:GOTO s              │
│     ···            │         либо 2,     │ N2:S2:GOTO s              │
│    m: Sm           │          ···        │    ···                    │
│                    │         либо m      │ Nm:Sm                     │
│                    │ (выбор по значению) │    ···                    │
│                    │                     │  s:...                    │
└────────────────────┴─────────────────────┴───────────────────────────┘
   Обратим  Ваше  внимание  на  то, что при  программировании конструкций
структурного программирования на языке  MSX-BASIC невозможно обойтись без
оператора GOTO, с помощью которого  осуществляется переход на ту или иную
ветвь условной конструкции.   Однако  следует иметь в виду,  что оператор 
GOTO используется только для передачи управления   в н у т р и   конструк-
ции, что не противоречит идеям структурного программирования.
   Дейкстра продолжает: "Я пришел к убеждению, что предложение  GOTO долж-
но быть устранено из всех языков программирования "высокого  уровня" (т.е.
отовсюду, за исключением, возможно, простых машинных кодов)".
┌──────────────────────────────────────────────────────────────────────┐
│  Однако сейчас стало ясным, что программирование без оператора GOTO- │
│  это еще не структурное программирование. Можно написать  программу  │
│  без оператора перехода, логическая структура  которой тем не менее  │
│  будет неудачной. И, наоборот, существуют ситуации, в которых  пере- │
│  ход является лаконичным, простым и ясным средством, в то время как  │
│  другие подходы сравнительно неудачны                                │
└──────────────────────────────────────────────────────────────────────┘
   Например, правила структурного программирования  часто предписывают по-
вторять одинаковые фрагменты программы в разных участках модуля, чтобы из-
бавиться от употребления оператора GOTO.  В этом  случае "лекарство  хуже
болезни", т.к. дублирование резко увеличивает возможность внесения ошибок
при изменении модуля в будущем.
   Д.Кнут в работе [70] показал, что можно говорить  о  структурном  прог-
раммировании и при использовании оператора GOTO!Структурное программирова-
ние на языках FORTRAN или BASIC возможно, хотя  с  большими трудностями и
некоторыми нежелательными последствиями. Так, например, Чармонмен и Ведже-
нер [72] показали,что можно сделать программу на языке FORTRAN похожей на
структурную!

   II. Другой метод улучшения качества программирования заключается в при-
менении   н и с х о д я щ е г о   п р о е к т и р о в а н и я, ("top-down
programming" - "программирование "сверху-вниз"").
    ┌───────────────────────────────────────────────────────────────┐
    │    Оператор GOSUB является  о с н о в н ы м  инструментом     │
    │             с т р у к т у р н о г о  программирования.        │
    └───────────────────────────────────────────────────────────────┘
   В методе нисходящего проектирования Вы вначале пишете основную програм-
му, используя оператор GOSUB для вызова подпрограмм,причем в качестве под-
программ вначале Вы вводите "заглушки" вида:
         PRINT "Вызвали подпрограмму номер ...":RETURN
   Затем, будучи уверенным в правильности логического построения основной
программы, Вы детально "расписываете" каждую подпрограмму, вызывая по  ме-
ре необходимости подпрограммы более низкого уровня. Этот последовательный
процесс продолжается, пока программа не будет завершена и проверена.
   При другом методе -  в о с х о д я щ е м   п р о е к т и р о в а н и и 
(программировании "снизу-вверх") - Вы вначале пишете подпрограммы нижнего 
уровня  и тщательно их тестируете и отлаживаете.  Далее Вы добавляете под-
программы более высокого уровня,  которые  вызывают  подпрограммы нижнего 
уровня, и так до тех пор, пока Вы не достигнете программы самого верхнего  
уровня.  Метод проектирования "снизу-вверх"  пригоден при наличии больших 
библиотек стандартных подпрограмм.
   Учтите, что иногда лучшим является гибрид двух методов.  Однако  в обо-
их случаях каждая подпрограмма должна быть небольшой, так, чтобы можно бы-
ло охватить одним взглядом всю ее логику (для персональных компьютеров же-
лательно, чтобы и основная программа,и подпрограммы  ц е л и к о м   поме-
щались в пределах 20÷30 строк экрана дисплея!)
   Всякий велосипедист хорошо знает, что ехать сверху вниз быстрее и удоб-
нее, чем снизу вверх. В программировании  дело  обстоит  примерно  так же:
"сверху-вниз" писать программы удобнее потому,что при таком методе мы точ-
но знаем, какие подпрограммы описывать.
   Но есть у этого метода и недостаток: на верхнем уровне не всегда видно,
куда спускаться, то есть как разделить решение задачи на такие части, каж-
дую из которых было бы легко описать отдельной процедурой. У опытных  про-
граммистов вырабатывается своеобразное чутье: они  сразу видят, какие нуж-
ны процедуры, а новичкам иногда приходится туго. 
   Метод "снизу-вверх", хотя и требует большого труда, бывает очень  поле-
зен на первых порах.  Пусть даже  половину  составленных Вами подпрограмм 
придется потом "выбросить", но зато  Вы хорошо почувствуете, какие подпро-
граммы для исходной задачи необходимы.  Да и отлаживать каждую написанную 
подпрограмму можно сразу: ведь все, что "под ней", уже описано  (а обычно 
и отлажено). Словом, любишь кататься "сверху вниз"  -  люби  и саночки во-
зить (в обратном направлении).  Опытные программисты иногда применяют  ме-
тод "снизу-вверх" для того, чтобы заранее заготовить для новой задачи  на-
бор подпрограмм, которые могут понадобиться в различных случаях.  Так что
"возить саночки" приходится не только новичкам!

   III. Структурное программирование  до сих пор было у нас  представлено
как свойство или оценка   о к о н ч а т е л ь н о г о   текста  программы.
Необходимо добавить еще один ключевой момент - методологию, или особеннос-
ти мыслительного процесса,  управляющего процессом получения  структурной
программы. Этот мыслительный процесс  называется  п о ш а г о в о й  д е -
т а л и з а ц и е й  и был первоначально предложен  Э.Дейкстрой  [73],  а
затем улучшен Н.Виртом [74].
   ┌──────────────────────────────────────────────────────────────────┐
   │    Пошаговая детализация  представляет собой  простой  процесс,  │
   │    предполагающий первоначальное выражение логики  программы в   │
   │    терминах гипотетического  языка "очень  высокого  уровня" с   │
   │    последующей детализацией каждого предложения в терминах язы-  │
   │    ка более низкого уровня, до тех пор,пока, наконец, не будет   │
   │    достигнут уровень используемого языка программирования.       │
   └──────────────────────────────────────────────────────────────────┘
   Причем на протяжении всего процесса логика выражается основными  конст-
рукциями структурного программирования.
   В методе пошаговой детализации можно выделить  следующие  существенные 
этапы [8]:
   1. На уровне 1 создается общее описание программы в целом.Определяются
основные логические шаги, требуемые для решения задачи, даже если пока не-
известно, как их выполнить. Эти логические шаги могут отражать  различные
физические шаги решения или могут быть удобными  групповыми  именами  для
тех действий, выполнение которых представляется довольно смутно.  Последо-
вательности шагов, требуемых для решения задачи, записываются  на обычном
языке или на  п с е в д о к о д е (см. ниже).
   2. На уровне 2 в общих терминах детализируется описание  шагов, введен-
ных на этапе 1).В детализированное описание может входить обозначение цик-
лических структур,в то время как действия внутри циклов могут по-прежнему
оставаться неясными. Таким образом, выполняются только общие  эскизы слож-
ных действий.
   3. На этом  и последующих уровнях в виде последовательных итераций про-
изводятся те же действия, что описаны на этапе 2). При  каждой  новой ите-
рации уточняются детали, оставшиеся неясными после предыдущих итераций, и
создаются более определенные описания. По мере выполнения итераций неопре-
деленные  детали  становятся все проще и проще, так что на каком-то этапе
могут быть полностью описаны.
   4. Разработка завершена:  в модульном виде получено описание требуемой
программы. Перевод этого описания в программу на конкретном языке програм-
мирования должен быть достаточно простой задачей.
   П с е в д о к о д   включает  в  себя  наборы фраз для написания таких
групп операторов: последовательность, выбор, итерация, - дополняемых текс-
том на обычном языке. Псевдокод не имеет строгого определения, поэтому Вы
всегда можете сконструировать  свой  с о б с т в е н н ы й   п с е в д о -
к о д, используя, например,  конструкции школьного алгоритмического языка:
если , пока , для , выбор , а также комментарии, формулы и словесное  опи-
────   ────   ───   ─────
сание действий и процессов.
   В описание процессов могут входить и такие операторы конкретного языка
программирования (например, BASIC), как INPUT, PRINT, READ и присваивания,
но не операторы  п е р е х о д а  или другие средства передачи управления,
применение которых должно ограничиваться реализацией трех  указанных выше
типов структур на заключительном этапе процесса проектирования.
   Концепцию псевдокода легче всего уяснить на примере.
   Пусть требуется определить наибольшее значение в некотором наборе  дан-
ных и вывести эти данные, поделенные на наибольшее значение. Скажем, если
данные представляют собой последовательность чисел
                      4., 2.51, 10.0, -5.0, 7.5      ,
то вывод должен выглядеть следующим образом:
                    0.40, 0.251, 1.00, -0.5, 0.75    .

   Первый уровень разработки ясен:
   У р о в е н ь  1:
   ────────────────
   1) ввести данные;
   2) найти максимум введенных данных;
   3) вывести результаты.
   Д е т а л и з а ц и я  1.1.  В в о д  д а н н ы х можно детализировать
   ──────────────────────────   на псевдокоде следующим образом:
   1) определить количество чисел;
   2) пока не все элементы введены, прочитать и запомнить значение элемен-
та;
   3) конец цикла.
   Это описание можно перевести на язык MSX-BASIC следующим образом:
          100 INPUT"Укажите количество элементов";N
          110 FOR I=1 TO N:INPUT A(I):NEXT I
   Д е т а л и з а ц и я  1.2.  О т ы с к а н и е  м а к с и м у м а  мож-
   ──────────────────────────   но детализировать следующим образом:
   1) выбрать в качестве максимума первый элемент данных;
   2) пробежать все введенные значения, заменяя  текущий максимум  на оче-
редное значение, если оно не превысило его.
   Д е т а л и з а ц и я  1.3.  В ы в о д   р е з у л ь т а т о в   можно
   ──────────────────────────   детализировать следующим образом:
   1) пока не все результаты выведены;
   2) ВЫВОД  значение очередного элемента, поделенное на максимум;
   3) конец цикла.
   Это описание можно немедленно перевести на MSX-BASIC следующим образом:
                300 FOR I=1 TO N:PRINT A(I)/M:NEXT I
   У р о в е н ь  2.
   ────────────────
   Он включает в себя  три  детализованные  выше части, из которых только 
детализация (1.2) требует дополнительного внимания. Ее  можно  детализиро-
вать на псевдокоде следующим образом:
   1) положить М, равное первому элементу данных;
   2) пока не все элементы просмотрены;
   3) если М<текущий элемент, то M = текущий элемент; 
   4) конец цикла.
   Это описание можно перевести на MSX-BASIC следующим образом:
         200 M=A(1)
         210 FOR I=1 TO N
         220   IF M<A(I) THEN M=A(I)
         230 NEXT I
   Так как приведенные выше модули  используются только по одному разу  и
очень просты, то можно не делать из них подпрограммы, а объединить их вме-
сте в одну программу:
         10 'Пример программы, полученной из псевдокода
         20 DIM A(20)
     ┌───────────────────────────────────────────┐
     │   100 INPUT "Введите число элементов";N   │
     │   110 FOR I=1 TO N:INPUT A(I):NEXT I      │
     └───────────────────────────────────────────┘
     ┌───────────────────────────────────────────┐
     │   200    M=A(1)                           │
     │   210    FOR I=1 TO N                     │
     │   220       IF M<A(I) THEN M=A(I)         │ 
     │   230    NEXT I                           │
     └───────────────────────────────────────────┘
     ┌───────────────────────────────────────────┐
     │   300 FOR I=1 TO N:PRINT A(I)/M;:NEXT I   │
     └───────────────────────────────────────────┘
         500 END
         run
         Введите число элементов? 5
         ? 4
         ? 2.51
         ? 10.0
         ? -5.0
         ? 7.5
          .4  .251  1 -.5  .75
         Ok             

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


                                Известно, что отладка  в два раза сложнее
                                написания  программы. Поэтому, если Вы бы-
                                ли предельно хитроумны при написании прог-
                                раммы, то что же Вы будете делать  при ее
                                отладке?
                                                    Б.Керниган, Ф.Плоджер


            ┌────────────────────────────────────────────────┐
   IV.      │   Никаких трюков и заумного программирования!  │
            └────────────────────────────────────────────────┘
   Т р ю к а м и  мы называем необычные приемы программирования. Трюк дол-
жен быть лаконичным и давать выигрыш  в  быстродействии  или в объеме про-
граммы; каждый трюк несет в себе элемент неожиданности.
   Отношение к трюкам может быть различным. Некоторые уравновешенные люди
признают, что в этом что-то есть, но  избегают фокусов, дабы не усложнять
жизнь.  Другие получают в трюках  эстетическое удовольствие и восхищаются 
ими настолько, что забывают о назначении программы. Третьи находят прямую 
связь между трюками, трюкачеством и "бит-жонглерством" и считают все  это  
безусловно вредными привычками плохо воспитанных программистов.
   Вероятно, в каждом из этих мнений  есть  что-то  от истины. Однако  мы
считаем, что к  м е с т у  употребленный трюк, снабженный, когда надо,ком-
ментариями, ничего, кроме пользы, принести не может. Некоторые трюки, вхо-
дя в обиход, становятся привычными и воспринимаются как нормальные приемы
программирования. В большинстве случаев чистый выигрыш от них невелик, но
бывают ситуации, когда время работы программы жестко ограничено  и только
трюк может спасти положение.  Наконец, знакомство с трюками полезно и тем, 
кто их не использует, так как позволяет глубже осознать особенности компь-
ютера и чувствовать себя свободно. Из-за своей необычности трюки, как пра-
вило, реализуются только на языках ассемблерного типа или непосредственно 
в машинных кодах.
   Однако, никогда не используйте трюков там, где можно использовать  про-
стые методы. Заметим,что  э л е г а н т н о е  решение задачи - это такое
решение, которое  одновременно  и  просто, и оригинально. Простые решения
всегда желательны, но вопрос о том, всегда ли приемлемы оригинальные реше-
ния (трюки), остается открытым.
   Под  о р и г и н а л ь н о с т ь ю  решения подразумевается  его неоче-
видность.
   Кстати, Оксфордский словарь английского языка определяет э л е г а н т-
н о с т ь   как  "утонченное изящество;  корректность;  искусная простота;
изысканность..."
   Возникающие при использовании трюков проблемы можно  проиллюстрировать
на следующем "модельном" трюке:  10 A=A+B:B=A-B:A=A-B  .
   Здесь две переменные меняются значениями без  промежуточного  копирова-
ния значения одной из переменной. Этот прием используется системными  про-
граммистами в том случае, когда при перемене мест  содержимого  регистров
важно сэкономить дополнительный регистр.
   О р и г и н а л ь н о с т ь очевидна, но  э л е г а н т н ы м этот при-
ем можно считать, лишь принимая во внимание особенности конкретной задачи.
Он, очевидно, не эффективен, когда  используется вне рассматриваемого кон-
текста, например, для перестановки элементов  многомерного массива в обыч-
ной программе, и к тому же может привести к ошибке округления, если А и В
описаны как вещественные числа. Например:
                 10 INPUT A,B:A=A-B:B=A+B:A=B-A:PRINT A;B
                 run
                 ? 1.5E15,1
                  0  1.5E+15   ◀── Результат ужасен!
                 Ok
   Итак, никогда не используйте трюки только для того, чтобы продемонстри-
ровать свои умственные способности!
   V. Наконец, обсудим  и  о р г а н и з а ц и о н н ы е  приемы.
   Почти непременным элементом методологии программирования является прин-
цип   б р и г а д н о й  организации работ в программировании.  Практичес-
кая реализация больших программных проектов требует умения и опыта многих
программистов.
   Почему в программировании необходима бригадная организация работ?
   Ответ прост:
 ┌─────────────────────────────────────────────────────────────────────┐
 │  задача может потребовать бригадной организации ее решения, потому  │
 │  что она слишком трудна, или слишком велика, или слишком разнородна │.
 └─────────────────────────────────────────────────────────────────────┘
   В 1971г. Г.Д.Миллз предложил схему организации программистской деятель-
ности, известную как  б р и г а д а  г л а в н о г о  п р о г р а м м и с-
т а.Этот подход успешно использовался при разработке и реализации несколь-
ких крупных программных проектов.
   По словам Миллза, "бригада главного программиста - это  небольшой  кол-
лектив сотрудников,созданный для эффективной работы и рассматриваемый как
единое целое". Бригада состоит из нескольких человек, обычно  от  трех до
пяти; среди них - главный  программист, резервный  программист, секретарь
бригады и по мере необходимости другие специалисты.
   Основная идея бригады заключается в том, что она работает как суперпро-
граммист, т.е. как один программист  с очень высокой  производительностью 
труда, что обеспечивается участием в работе всех членов бригады,  действу-
ющих (благодаря внутренним связям в бригаде) с полным единомыслием.
   Г л а в н ы й  программист - это компетентный  программист, доказавший
свои незаурядные технические способности. Он руководит бригадой, ему непо-
средственно подчиняются все остальные ее члены.
   В обязанности главного программиста входит проектирование программы,на-
писание самых важных ее модулей и определение остальных модулей,  которые
программируют другие члены его бригады. Вся работа бригады находится  под
постоянным контролем главного программиста; он объединяет результаты в од-
но целое.
   Р е з е р в н ы й  программист, работающий в непосредственном контакте
с главным программистом и полностью посвященный во все его решения, может
в случае необходимости возглавить бригаду. Обычно  резервный  программист
отвечает за независимую подготовку  тестов для разрабатываемой  программы;
он может также помогать главному программисту в исследовательской деятель-
ности, изучая альтернативные стратегии и тактики бригады.
   Основная  задача   с е к р е т а р я   бригады - это  документационное
обеспечение проекта как в машинно-ориентированной форме, так и в виде, до-
ступном для человека. Секретарь отражает текущее состояние проекта  и его
историю.
   ┌──────────────────────────────────────────────────────────────────┐
   │  Каждый член бригады обязан тщательно регистрировать все те свои │
   │  действия, которые изменяют положение дел в проекте,и передавать │
   │  эти записи секретарю.                                           │
   └──────────────────────────────────────────────────────────────────┘
   Подчеркнем, - основная функция секретаря заключается не столько в  том,
чтобы избавить программистов от бумажной работы, сколько в том, чтобы обе-
спечивать наглядную информацию о положении дел в проекте и о  достигнутых
успехах. Достоинство такой организации - в наличии источника единообразно
представленной и свежей информации о ходе разработки программы.
   При реализации большого проекта одной бригады главного программиста мо-
жет быть недостаточно, как недостаточно одного программиста  для  решения
многих программистских задач.  Миллз предлагает  организовать в таком слу-
чае иерархию бригад главного программиста, начиная с одной бригады на  са-
мом высшем уровне. Бригады следующих уровней создаются  лишь  после  того,
как бригада предыдущего (более высокого) уровня подготовила им задание. В
противоположность ориентированной на управление иерархии  в  классической
организации программистских коллективов здесь  не  существует  разделения
функций на высших уровнях иерархии: бригады главного программиста  на выс-
ших уровнях проходят различные этапы и отвечают за различные виды деятель-
ности (проектирование, кодирование, тестирование,проверка), на каждом эта-
пе устанавливая конкретные задания для подчиненных групп.
   Бригада высшего уровня завершает проектирование  (в самых  абстрактных
терминах), кодирование (в этих же терминах) и тестирование  (тоже  в этих
терминах!) на самых ранних этапах разработки проекта.  И только когда эта 
бригада успешно прошла все тесты (больше похожие на доказательства),можно
безбоязненно передавать задания бригадам низших уровней.Все остальное вре-
мя выполнения проекта бригада высшего уровня  посвящает  верификации (про-
верке) результатов, поступающих с нижних уровней.
   Однако  учтите, что  п а с с и в н ы е  методы, способствуя  значитель-
ному повышению качества программ,  не могут гарантировать  удовлетворения 
всех заданных требований к программам,  а главное, не полностью предотвра-
щают ошибки.
   Поэтому а к т и в н ы е  методы поиска и устранения  ошибок  дополняют
пассивные в процессе достижения заданного качества программ.