О надежности аппаратуры
По профессии я программист и обсуждаю в этой работе программы; истинной темой этого раздела является, в сущности, надежность программ. Тем не менее в заголовке я упоминаю "аппаратуру", так как считаю программы специфической формой аппаратов и желаю хоть раз выразить глубокую уверенность в том, что многие мои соображения, относящиеся к программному обеспечению, справедливы с соответствующими поправками и применительно к проектированию машинной аппаратуры.
Современные вычислительные машины - это изумительные комплексы оборудования, но еще более изумляет неопределенность критериев оценки правильности результатов работы машины. Все основывается на предположении, что аппаратура функционирует правильно.
Ограничимся временно рассмотрением машинной аппаратуры; удивительно, насколько легко убедить человека в том, что она сконструирована безошибочно. Несколько лет назад в университете, где я работаю, появилась новая машина. В сопроводительной документации утверждалось, что среди многого прочего имеется схема умножения 27-разрядных чисел с фиксированной запятой. Казалось бы, законный вопрос: "Правилен ли этот умножитель, работает ли он в соответствии со своим описанием?"
Вот наивный ответ: "Ну что же, число различных перемножений, которые должны выполняться правильно этим умножителем, конечно и равно 254; поэтому давайте проверим их все". Однако, каким бы разумным ни казался этот ответ, он непригоден, так как, хотя одно перемножение занимает всего несколько десятков микросекунд, общее время, требуемое для этого конечного числа перемножений, составило бы более чем 10 000 лет! Отсюда следует вывод, что исчерпывающее тестирование даже одиночной компоненты типа умножителя оказывается совершенно нереальным. (Тестирование всей машины по тому же принципу требовало бы доказательства правильной работы всех возможных программ!)
Подсчитанный нами десятитысячелетний срок означает, что за время своего существования умножитель должен будет выполнить только ничтожную часть огромного числа всех возможных перемножений, на которые он способен: практически ничего он сделать не успеет.
Как ни странно, мы все же требуем, чтобы он был способен правильно выполнить любое перемножение, если поступит соответствующий приказ. Это фантастическое качество требуется потому, что мы не знаем заранее, какие именно ничтожно малые по своему количеству умножения потребуется выполнить. В наших рассуждениях о программах мы говорим о "произведении", абстрагируясь от конкретных значений сомножителей: мы не знаем их и не хотим их знать; не наше дело их знать, наше дело их не знать! Мы вполне законно хотим мыслить в терминах общего понятия "произведения" без учета специфики конкретных вычислений, но платой за это является именно требование, чтобы правильно выполнялось любое умножение из огромного множества. Вот так обстоит дело с желанием иметь правильный умножитель.
Но как установить правильность убедительным способом? Поскольку умножитель рассматривается как черный ящик, единственное, что мы можем сделать, это "проверить на примерах", т, е. предложить умножителю обозримое количество пар сомножителей и проверить результаты. Но с точки зрения десяти тысяч лет очевидно, что мы можем проверить только ничтожную часть возможных перемножений. Целые классы в некотором смысле "критических" перемножений могут остаться непроверенными, и в отношении столь желаемой надежности наш контроль остается в высшей степени неудовлетворительным. Поэтому такой способ не годится.
Непосредственный вывод состоит в следующем: убедительная демонстрация правильности невозможна, пока аппаратура рассматривается как черный ящик; единственная наша надежда в том, чтобы не считать аппаратуру черным ящиком. Я назову это "принятием во внимание структуры аппаратуры".
Аппараты, которыми мы собираемся заниматься впредь, - это программы. (С программной аппаратурой во многих отношениях легче иметь дело, чем с электронными схемами, которые в сущности являются аналоговыми устройствами и подвержены износу.) И для программ совершенно безнадежно пытаться устанавливать правильность тестированием, исключающим малейшие сомнения, если не принимается во внимание структура этих программ.
Другими словами, мы отмечаем, что степень возможной уверенности в правильности программы определяется не только внешним описанием программы и режима ее работы, но существенно зависит от ее внутренней структуры.
Возвращаясь к основному предмету наших рассмотрении, т. е. к по-настоящему большим программам, мы заключаем из предыдущего, что их величина сама по себе требует высокого уровня уверенности в отдельных компонентах программы. Если вероятность правильности отдельной компоненты равна р, то вероятность правильности всей программы, состоящей из N таких компонент, равна примерно P = pN
Если число N будет очень велико, то значение р должно быть очень и очень близко к 1, если мы хотим, чтобы значение Р существенно отличалось от нуля!
Если теперь принять предпосылку, что задача программиста не только в том, чтобы изготовить правильную программу, но и в том, чтобы убедительно продемонстрировать ее правильность, то приведенные выше соображения существенно влияют на деятельность программиста: его продукция должна иметь удобную структуру.
Последующая часть этой монографии посвящена в основном исследованию того, какая структура программы может оказаться наиболее удобной для применения. В дальнейшем читателю станет ясно, что правильность программ не является единственным предметом моих рассмотрении; я буду заниматься также проблемой приспособляемости, или управляемости программ. Я выделяю проблему управляемости программ преднамеренно и постараюсь обосновать этот выбор.
Хотя в прошлом возрастание мощности универсального оборудования смягчало остроту проблемы эффективности программ, именно это возрастание породило и новые трудности. Если человек получает в свое распоряжение мощную машину, то он пытается ее использовать, и объем задач, за которые он берется, определяется масштабом оборудования: никто не станет программировать алгоритм, выполнение которого заняло бы двадцать лет. В связи с тем что за последние десять или пятнадцать лет производительность вычислительных машин увеличилась в тысячи раз, пользователи стали гораздо более бесцеремонными при выборе проблем, которые они считают "технически разрешимыми".
Пользователи хотят, чтобы размеры, сложность и изощренность программ увеличивались исключительно быстрыми темпами, и в последние годы стало очевидным, что в целом наши программистские возможности не поспевают за этими неумеренными аппетитами.
Мощность доступного оборудования будет продолжать расти: можно ожидать, что инженеры разработают еще более быстрые машины, и даже независимо от таких разработок мы станем свидетелями того, как класс машин, которые теперь считаются исключительно быстрыми, будет получать все более и более широкое распространение. Соответственно будут расти и задачи, которые мы захотим решать на этих машинах; именно на этой экстраполяции основывается мое представление о сущности программирования. Я прихожу к выводу, что возникает настоятельная необходимость перестать подходить к программированию с точки зрения минимизации коэффициента отношения стоимости к результату. Следует осознать, что уже теперь программирование в гораздо большей степени стало интеллектуальным состязанием: искусство программировать - это умение организовать сложную систему и управлять ее бесчисленными элементами, пресекая всеми силами присущую им тенденцию к изначальному хаосу. Мое нежелание считать эффективность первоочередной заботой программиста не означает, что я вообще пренебрегаю эффективностью. Напротив, я признаю, что соображения эффективности могут послужить убедительным основанием для изменения логически правильной программы. Однако я твердо уверен, что мы можем разрешить себе оптимизацию (какова бы она ни была) только при условии, что это не повлечет за собой потерю управляемости. Я закончу этот раздел замечанием о значении вычислительных машин. Эти машины представляют собой самые "удобные и мощные орудия", и, по мнению многих, они преобразовали всю нашу цивилизацию. Я рискнул бы высказать мнение, что пока .мы относимся к ним как к орудиям, мы можем существенно недооценивать их значение. Возможно, что в качестве орудий они проводят лишь малую борозду на ниве нашей цивилизации, тогда как гораздо большее влияние на всю нашу культуру оказывает их способность выступать в качестве партнера в интеллектуальном состязании. Следствие из первой части этого раздела: Тестирование программ может служить для доказательства наличия ошибок, но никогда не докажет их отсутствия!