(редакция от 17.04.86)
Лекции о культуре программирования будут сопровождаться примерами из реальной жизни. Эти примеры должны показать вам, как не надо программировать. А как надо? Чтобы показать это, мы с вами разработаем конкретный программный продукт, предназначенный для сравнения программ.
Задача перед нами стоит такая. (Заметьте, кстати, что сейчас я выступаю в роли заказчика : я пытаюсь объяснить вам, что я хочу). Так вот, часто приходится сравнивать либо колоды - исходную и отдублированную, либо просто тексты программ (чтобы узнать, что изменилось). Хотелось бы это дело как-то автоматизировать, а то уж очень неблагодарная работа.
Итак, вам задача ясна? Вы уже пошли писать программу? Не торопитесь. Выслушайте-ка притчу об эн-факториале, может быть, это охладит ваш пыл. А, чтобы лучше дошло, представьте, что все это произошло с вами лично.
Итак, вы - разработчик программного обеспечения. Вы только что заключили договор с неким заказчиком. Договор, в сущности, состоит из одной фразы : к такому-то числу поставить программу вычисления факториалов.
Заказчик считает, что задача поставлена корректно. Вам тоже все понятно - что может быть проще факториала? Думать нечего, вы садитесь и пишете нечто вроде
fаk:рrос орtiоns(маin);
gеt list(n);
k=1;
dо i=1 tо n;
k=k*i;
еnd;
рut list(k);
еnd fаk;
Если же вы человек с фантазией и желаете показать, что не лаптем щи хлебаете, вы сделаете то же самое, но с рекурсией.
Готово дело. Вы проверяете программу на первом попавшемся числе. 5!=120. Все нормально. Вы пишете документацию и совсем было собираетесь передать продукт заказчику, но ради интереса пробуете подсчитать 100! И получаете ноль!
Вы запускаете 50! - ноль...
25! - ноль...
6! - 720...
Вы долго ломаете голову, пробуете так и эдак, и в конце концов вас осеняет, что факториал растет так быстро, что скоро перестает входить в машинное слово. А ПЛ/1 устроен так, что при двоичном целом переполнении он заменяет результат нулем.
Сроки уже поджимают, поэтому вы просто заменяете описание переменной с целого на вещественное и печатаете факториал по формату е(13). В таком виде вы и передаете программу заказчику, успев-таки вписаться в график.
Однако заказчик недоволен. Ему, оказывается, нужны были все значащие цифры факториала, а не первые десять. Вы с ним немного спорите и тычете друг друга в договор. Вы утверждаете, что то, что печатает ваша программа - это факториал, а что касается точности, то она в договоре не была указана. Заказчик говорит, что и ежу ясно, что раз факториал, то он должен быть со всеми значащими цифрами, и что это подразумевалось само собой, и что, может быть, мы включим в договор соглашение о том, что дважды два - действительно четыре?
Делать нечего - виноваты оба, поэтому заказчик выделяет дополнительные средства на переделку, а вы снова принимаетесь за работу. Теперь вы храните факториал в символьной форме. Символьную строку под факториал вы выделяете по максимуму - 32767 байт, чтобы уж насчет точности разговоров больше не было. Поскольку арифметические операции над строками такой длины в ПЛ/1 не определены, вы моделируете поразрядное умножение, а разряды извлекаете при помощи функции suвstr.
Потом вы долго отлаживаетесь и, наконец, вывешиваете на стену перед своим столом длиннющую распечатку 150!, как доказательство силы своего интеллекта.
Заказчик меж тем вами недоволен. Ваша программа, видите ли, работает больше получаса, а ему нужно, чтобы любой факториал выдавался не более чем за минуту. К тому же она занимает сорок килобайт памяти, из которых использует от силы десять.
Вы опять долго машете друг перед другом договором, а потом программу опять приходится переделывать. Вы убираете умножение незначащих нулей, заменяете символьную строку на массив целых чисел, да еще и делаете этот массив переменной длины. Длину эту должен задавать пользователь. Если факториал не поместился, нужно запустить программу еще раз, на большей длине. Чтобы извещать пользователя о переполнении массива, вы включаете ситуацию suвsсriрtrаngе - в случае ошибки он получит длинное сообщение на машинно-английском языке, в котором будет все, что нужно, вплоть до номера сбойного оператора программы и его шестнадцатеричного адреса.
Теперь ваша программа занимает 8к и работает сорок секунд. А заказчик недоволен. Его, видите ли, бросает в дрожь от длинных машинно-английских сообщений. Он, видите ли, не программист и в институте изучал французский язык. И ему, видите ли, нет дела до каких-то шестнадцатеричных адресов и он не желает знать, как устроена ваша программа и какие в ней есть массивы. И поэтому он просит избавить его от подсчета каких-то там длин.
На что вы отвечаете, что любой грамотный человек в состоянии оценить количество разрядов в n!, зная n, что это вообще элементарно.
На что заказчик резонно отвечает, что раз это элементарно, то почему же программа сама это не делает?
И вы встраиваете в программу блок подсчета длины массива по n.
Наконец-то все довольны. Правда, график давно сорван, ресурсы перерасходованы, а нервы на пределе.
Ну как, вы пошли программировать? Нет? Ну, тогда давайте попробуем определить задачу почетче, чтобы обошлось без недоразумений.
Но как догадаться, как выделить именно те вопросы, которые нужно согласовать? Было бы просто замечательно, если бы существовал некий список таких вопросов, и нам оставалось бы только на них ответить.
Документ, содержащий все требуемые вопросы, существует. Более того, этот документ является стандартом. По нашим стандартам это - техническое задание, по американским - соглашение о требованиях. Но для нас сейчас неважно, как он называется, нас интересуют вопросы, в нем содержащиеся.
Вопрос первый:
1.Как называется наш продукт?
Это надо решить сразу же. Во-первых, нам нужно в дальнейшем говорить такие слова : "система имярек предназначена для..." или "система имярек имеет такие особенности...", и потому лучше, если с самого начала там будет стоять конкретное имя.
Во-вторых, следует согласовать имя с заказчиком, если он есть. Я помню, как сначала мы назвали нашу систему так: "МОНИКА" и, соответственно так она и называлась в документации. Заказчику же это имя не понравилось, у него все системы, оказывается, обозначались греческими буквами. В результате нам пришлось перелопатить всю документацию и заменить МОНИКУ на ДЕЛЬТУ.
Вообще, нужно учитывать еще и тот момент, что вы делаете продукт, предназначенный для распространения, и красивое имя сыграет некоторую роль в рекламе.
Как правило, имена программных систем - это аббревиатуры. Та же МОНИКА - это МакроОбработка Наименованных И Кодированных Анкет. Еще примеры : САФРА, АИСТ, СИНБАД, МАРС, ФОКУС. Бывают и другие способы - мне нравится, например, имя программы-документатора : ДОКТОР - из слова "документатор" выброшены буквы "умента".
Я предлагаю не нарушать аббревиатурную традицию : давайте назовем систему простенько, но со вкусом "АС" (автоматический сравниватель).
Второй вопрос значительно сложнее первого :
2.Для чего предназначен наш продукт?
Казалось бы, ясно для чего - для сравнения! Но для сравнения чего? Перфокарт? Но ведь программы могут находиться и в библиотеках, и вообще в каких-нибудь файлах.
Тогда, может быть, для сравнения программ? Но и это неточно. Во-первых, мы сравниваем не только программы, но и ,например, задания. А, во-вторых, сравнение программ - это все же нечто другое. Вот пример:
а=1;
а=1;
Как фрагменты программ, эти строки идентичны. Но как, например, перфокарты, они различаются.
Сказать "для сравнения текстов" было бы вообще расплывчато. Ведь текст - это непрерывная последовательность символов, а мы имеем дело с данными, разбитыми на довольно независимые строки.
Должен вам сказать, что все эти поиски слова не являются чем-то абстрактным и теоретическим. Чем менее четко мы определим сейчас назначение продукта, тем меньше будет вероятность того, что мы сделаем то, что нужно. Все эти вопросы рано или поздно встанут перед нами, и лучше решить их сразу. Вспомните - наша задача сегодня - научиться делать, не переделывая.
Итак, попробуем уяснить себе, какова природа данных, которые мы намерены сравнивать. Это данные, состоящие из строк одинаковой длины, и именно строка является минимальным независимым элементом данных. Строки можно вставлять, переставлять, удалять и изменять. Пользователя интересует именно соответствие строк - ему хочется знать, какие строки изменены и как именно.
Поэтому, видимо, следует ответить на второй вопрос так:
Продукт АС предназначен для сравнения текстов, состоящих из строк одинаковой длины и выявления вставленных, переставленных, измененных и удаленных строк.
Следующий немаловажный вопрос:
3. Для кого предназначен продукт?
Этот вопрос немаловажен вот почему: он задает нам уровень компетенции пользователя. Если мы пишем нечто, предназначенное для системного программиста, то мы предполагаем, что он имеет определенные знания и умения, а значит, мы имеем право написать в документации, например, такие слова: "в этом случае следует проверить такие-то разряды рsw". Если же мы делаем систему для бухгалтеров, то ссылки на рsw и какие-либо машинно-английские сообщения в шестнадцатеричных адресах, конечно, неуместны. Не пользователь должен подстраиваться под вашу программу, а ваша программа должна подстраиваться под пользователя.
В нашем случае очевидно, что пользователь АСа - это обычный прикладной программист, работающий в пакетном режиме, не имеющий доступа в машзал и знающий ОС ровно настолько, чтобы запустить свою программу в режиме "трансляция-счет". Возможно, он пользуется какой-нибудь системой типа ДУВЗа или ПРИМУСа.
Поэтому ответ на третий вопрос будет звучать так : АС предназначен для прикладных программистов, работающих в пакетном режиме на ЕС ЭВМ. Предполагается минимальное знание ОС.
4.Какое оборудование требуется?
В данном случае мы предполагаем писать систему для машин серии ЕС.
Вообще говоря, мы должны бы были указать конфигурацию устройств, т.е. количество и тип дисководов, предполагаемые терминалы, и т.д. но в нашем случае, поскольку АС предназначен для использования в пакетном режиме, мы можем сказать, что это любая конфигурация ЕС ЭВМ, допускающая прогон в пакетном режиме. Это означает, что имеется процессор, память (такая, чтобы на задачи пользователей оставалось хотя бы 100к), хотя бы один дисковод, АЦПУ и устройства для ввода данных: УВК, терминалы или магнитные ленты.
5.Какое программное обеспечение требуется?
Тут мы фиксируем, что АС будет работать в ОС ЕС, начиная с версии 6.1 и выше. Если бы АС требовал еще какое-либо программное обеспечение, это нужно было бы указать. Например, мы захотели сделать АС как подзадачу системы рriмus. это означает, что у заказчика рriмus должен быть и он согласен с ним работать. другой случай - возможно, АС будет использовать подпрограммы из пакета; например, из пакета научных программ на фортране (пнп-фортран).
Этот момент нужно согласовать заранее, чтобы не получилось так : вы уже сделали систему, а заказчик говорит: "против АСа мы ничего не имеем, но вот рriмus нам не нужен: мы ведь работаем с системой "фокус"
6. Что будет делать продукт?
Этот вопрос не равноценен второму - о назначении. Там мы описали назначение "пакета" кратко, а теперь мы должны достаточно четко описать входные и выходные данные и соответствие между ними. достаточно четко не означает, что мы должны выписать номера колонок перфокарт и т.д. мы должны описать задачу достаточно четко, но на содержательном уровне.
Кроме того, мы должны удержаться от соблазна и не скатываться за разработку алгоритма. Сейчас нас интересует то, что должен делать продукт, а не то, как он должен это делать.
Итак, вспомним, что АС предназначен для сравнения текстов, разбитых на строки. Один текст - эталонный (мы будем называть его эталоном), а второй текст - сравниваемый (для краткости назовем его дублем).
В этом месте мы должны удержаться от соблазна поставить пункт 6.1. входные данные" и написать, что входными данными являются эталон и сравниваемый текст. Не будем торопиться. принято делать все наоборот -сначала описать выходные данные, а уже потом все то, что нам потребуется для того, чтобы их получить. Может быть, кроме эталона и дубля нам потребуется еще что-нибудь, и тогда нам придется изменять пункт 6.1. Золотое правило программирования: откладывай на завтра то, что не нужно делать сегодня.
Итак, на входе у нас - как минимум - эталон и дубль, а на выходе? Идеалом было бы напечатать исходный текст с примечаниями типа "эта строка в дубле переставлена туда-то" "эти строки в дубле удалены" "сюда вставлены строки" А сами строки распечатываются справа.
Это было бы пользователю максимально удобно и приятно. Вообще говоря, мы не утверждаем еще, что на распечатке должны быть именно такие слова - мы говорим только, информация какого вида должна быть здесь представлена.
Но для того, чтобы такая выдача была возможной, нужно сначала определить абсолютно точно, что означают слова "строка удалена" и т.д. Начнем с самого простого случая. строка n удалена из эталона, если в дубле нет соответствующей строки. Логично? логично. Красиво? Красиво. А теперь посмотрим такой пример:
эталон: дубль:
еnd; dо i=1 tо 10;
dо i=1 то 10; k=k+а(i);
k=k+а(i); еnd;
еnd;
По определению первый еnd не удален из эталона! Тогда, может быть строка n удалена из эталона, если количество строк, совпадающих с n в эталоне, больше соответствующего количества строк, совпадающих с n в дубле? Совсем нехорошо!
Вырисовывается такая проблема: поскольку строки в эталоне не уникальны, мы вообще не можем корректно определить удалена ли именно эта строка или какая-нибудь другая, точно такая же.
То же самое можно сказать относительно перестановки: эталон: дубль:
1 а=1; 1 b=2;
2 b=2; 2 с=4;
3 с=4; 3 еnd;
4 еnd; 4 а=1;
Можно сказать, что строка а=1 переставлена после строк 1-3, а можно сказать, что строки в=2,с=4 и еnd переставлены перед а=1. Могло быть и так и так.
В конечном счете мы убеждаемся, что единственное, что мы можем сказать четко для каждой строки эталона - это то, есть ли такая же строка в дубле и какой номер она там имеет (и то же самое относительно строк дубля). При этом мы должны обеспечить, чтобы каждой строке эталона ставилось в соответствие не более одной строки дубля. Плюс к этому мы можем отметить в выходном документе те строки в эталоне и дубле, на которых прерывается последовательность их номеров. Например, в случае соответствия строк
1-4
2-1 нарушение
3-2
4-3
Именно в этом месте происходят изменения - вставка, удаление и т.д. Но определение того, какое изменение было, мы вынуждены возложить на пользователя.
Итак, теперь мы можем выделить пункты:
6.1 Выходные данные
АС распечатывает эталонный текст, в котором каждой строке присваивается номер, и для каждой строки эталона указывается либо номер соответствующей строки в дубле, либо информация об отсутствии такой строки в дубле. Кроме того, отмечаются все строки эталона, на которых прерывается последовательное соответствие номеров строк эталона и дубля (например, 2-6, 3-7, 4-8, 5-12 - последняя строка нарушает последовательность, значит, именно в этой строке произошло изменение).
Затем точно так же распечатывается дубль. И в эталоне, и в дубле особо отмечены повторяющиеся строки .
Таким образом, пользователь будет располагать достаточной информацией для того, чтобы отследить изменения в тексте.
6.2 Процесс обработки
Эталон и дубль сравниваются, выявляются соответствующие строки и номера нарушения последовательности и повторяющиеся строки. Каждой строке эталона ставится в соответствие не больше одной строки дубля, и наоборот.
6.3 Исходные данные
Эталон и дубль подаются отдельно и могут быть колодами перфокарт, разделами библиотек и последовательными файлами. следует учесть, что некоторые диалоговые системы нумеруют строки; в этом случае номер не должен присутствовать в сравниваемой строке.
Кроме того, подаются параметры, регулирующие работу АС - например, границы сравниваемых полей в текстах.
Следующий вопрос звучит так:
7. Какими свойствами и в какой степени должен обладать продукт
Здесь, во-первых должны быть перечислены все свойства хорошей программы, но только в порядке убывания их важности для данного продукта, а также еще какие-то свойства (например, требование безопасности и секретности). Их нужно выписать в таком порядке, поскольку они часто друг другу противоречат (например эффективность и надежность - с целью обеспечить надежность мы добавляем в программу какие-то дополнительные операторы, которые могут существенно ее замедлить). Поэтому нужно сразу определиться, к чему мы должны стремиться в первую очередь. особенно это важно, если систему разрабатывают несколько человек. тогда, если один программист стремится к максимальной эффективности в ущерб надежности, а другой - к максимальной надежности в ущерб эффективности, то система в итоге
получится ненадежной и неэффективной.
Итак, важнейшие требования в нашем случае:
а) Удобство в работе.
АС должен быть настолько удобен в работе, чтобы пользователь предпочел работу с ним по крайней мере ручному сравнению.
б) Эффективность.
Поскольку продукт работает в пакетном режиме, и назначение его - оперативное выявление изменений, то задание, вызывающее АС, должно быть таким, чтобы попасть в самую приоритетную очередь. Для этого АС должен для средних (200-300 строк) текстов работать не больше минуты и занимать не больше 90К памяти.
в) Надежность.
Повышенная живучесть не требуется, т.к. никакие постоянные файлы не поддерживаются, ввод со стороны пользователя практически отсутствует, но надежность в смысле отсутствия ошибок обязательно должна быть, так как даже мелкая ошибка подорвет уверенность пользователя и заставит его проверять работу программы, те самым сведя к нулю ее значимость.
г) Модифицируемость.
д) Мобильность.
Вы заметили, наверное, что отсутствуют такие свойства как "соответствие требованиям пользователя" и "понятность". Они отсутствуют не потому, что к этим целям не следует стремиться, а потому, что эти требования не противоречат ни одному из указанных. Программа в любом случае должна им удовлетворять.
И, наконец, последний вопрос.
8. А не изобретаем ли мы велосипед?
Вопрос существенный. Вполне возможно, что система, удовлетворяющая всем перечисленным требованиям уже есть, и тогда не стоит тратить усилия и создавать то, что уже существует. С другой стороны, даже если эти системы не устраивают нас, то познакомиться с ними полезно - уже для того, чтобы не повторить ошибок их разработчиков и принять к сведению их ценные мысли. Как говорится, корабль на мели - моряку маяк!
В нашем случае имеется только одна программа, близкая к требуемым целям - утилита iевсомрr. Кроме того, имеется еще авdах, в которой есть функция сравнения перфокарт. Разберем их.
8.1. Функция ккс программы авdах.
Программа аbdах - системно-независимая программа, включающая в себя функцию сравнения колод. Использование авdах для целей, описанных в п.2, невозможно, т. к. сравниваются только перфокарты. кроме того, работа с авdах требует сброса ОС, присутствия пользователя в машзале и квалификации, необязательной для прикладного программиста.
8.2. Утилита iеbсоmрr
Эта утилита входит в состав ОС ЕС и может сравнивать любые два набора данных в пакетном режиме. К достоинствам системы следует отнести довольно широкий диапазон вызываемых данных, но для целей, описанных в п. 2 утилита не подходит, т.к., например, в случае удаления одной строки для всех следующих записей будет выдаваться несовпадение, в то время как достаточно сообщить, что одна запись отсутствует.
Последнее замечание весьма существенно - когда мы будем разрабатывать алгоритм, нам следует учесть этот недостаток iевсомрr и проводить сравнение иначе.
Ну вот, теперь мы можем констатировать, что задачу мы поняли, все вопросы решили и доказали, что наша система необходима. Ну что же, давайте программировать? Уже пора, не так ли? Ну, ну -давайте: что там у нас первым оператором - чтение эталона? gеt еdit... что еdit? По какому формату еdit? Из какого файла gеt?
Как это ни прискорбно, но программировать еще рано. Нужно составить, как минимум, еще один документ, в котором будут подробно описаны входные и выходные данные. Но это - тема уже следующей лекции.
© Алексей Бабий 1980-1986