Прошу прощения, это автоматический перевод на русский язык материала из архива Дейкстры
Что привело к "Заметки по Структурное программирование"
Цель этой исторической справкой является описание опыта, который задним числом, кажется, повлияли на меня, когда я написал EWD249 "Заметки по Структурное программирование" в 1969 году. Записка основана на том, что я помню, я уверен, что моя память была селективного и, следовательно, не претендуют на объективность профессионального историка.
Я познакомился с программированием на 1951 Летняя школа, учитывая в Кембридже по Уилкс. Уилер и Гилл, и стал в 1952 году на неполный рабочий день ℄ изначально 2 раза в неделю ℄ программист математических центр в Амстердаме; конца недели я изучал теоретической физики в Лейдене.
Моя единственная модель организации программы для EDSAC в Кембридже, я последовал его внимательно при разработке программы обозначения, ввод, вывод и библиотеки для организации ARRA в Амстердаме. Для следующей машины, FERTA, ARMAC и X1, программы обозначения и вход бы очень следовать той же схеме: я, безусловно, был консервативным программиста. Добавьте к этому, что обучение буфера ARMAC с мощностью один трек из барабана, уничтожены однородности магазина, и вы поймете, что я не встать на приключения, как "autocoders".
В 1955 году я принял решение, чтобы не стать физиком-теоретиком, но и стать программистом, а не. Я принял это решение, потому что я пришла к выводу, что теоретической физики и программирования, программирование воплощенные больше интеллектуальный вызов. Видите ли, в те дни я не страдают от интеллектуальной скромности. Это было трудное решение, потому что я была ухоженной, как первоклассный ученый и стать программистом похож прощание с точки зрения науки. Когда я объяснил А. ван Вейнгаардена, мой тогдашний босс, моя дилемма, он сказал мне, что компьютеры были здесь, чтобы остаться и что в мире программирования я могу быть очень хорошо быть одна называется для создания науки, которая по-прежнему не хватает. Начало моей физики степени в Лейдене стал формальностью быть с как можно быстрее. (На самом деле я уже не чувствовал Добро пожаловать в Лейдене. Физиков считали меня как дезертира и математиков, один из которых открыто гордился ", конечно, ничего не зная о компьютерах", были просто презрительно)
В то же время картина возникла для сотрудничества между мной и моими коллегами аппаратных Брэма Дж. Loopstra и Карел S Схолтен. После функциональные спецификации следующей машины были записаны (как правило, меня), что документ служит своего рода договор между нами: он сказал им, что машина на проектирование и строительство, в то время я знал, что я мог рассчитывать на время написания всех Базовое программное обеспечение для машин. Цель этого разделения труда в том, что мои программы будут готовы к моменту строительства машина была завершена.
Оглядываясь назад, я теперь, что выше договоренность была глубокое влияние, как я вырос как программист: я нашел это совершенно нормально, чтобы программа еще не существующих машин. Как побочный продукт стал прочно укоренена в голову, что я запрограммирован для абстрактной машины, как указано в исходный документ, а не для фактического часть оборудования: оригинал документа не было, но описание рецепта, и в случае Расхождение не текст, но имеющемся оборудовании будет виноват.
В то время я считал это разделение труда и в результате практике программирования для несуществующей машины, как совершенно нормальное. Позже я прочитал статью американского о том, почему программа была всегда опаздывает, я помню, очень удивлен, когда я читал, что ограниченная доступность аппаратных было главной причиной, и я пришел к выводу, что обстоятельства, при которых я узнал программирования были менее распространены, чем я взял на себя.
Конечно, я не мог исключить из моих проектов опечатки и подобные огрехи, но таких недостатков не имеет значения, пока машина еще не был готов, и после завершения машины они могут быть легко определены, как только они проявились, Но этот последний утешительная мысль было отказано со мной в 1957 году с введением в режиме реального времени прерывания. Когда Loopstra и Схолтен предложил эту функцию для X1, нашей следующей машине, я получил видения моей программы вызывая невоспроизводимых ошибок и я запаниковал.
В конце концов, Loopstra и Схолтен польщен меня из моего сопротивления, и я изучил их предложение. Первое, что я исследовал был ли я мог бы продемонстрировать, что государственная машина могла быть сохранены и восстановлены таким образом, что прервал программ можно было бы продолжить, как будто ничего не случилось. Я показал, а не что она не может быть сделано, и моим друзьям пришлось изменить свое предложение. Правда сценарии, при которых первоначальное предложение не смогут были очень маловероятно, но это может иметь только укрепило мою уверенность, что я должен был опираться на аргументы, а не на эксперименты. В то время, что осуждение было, видимо, не настолько широко распространены, на срок до семи лет спустя я хотел бы найти недостатки в аппаратных прерываний новых коммерческих машин.
У меня был очень освещающей опыт в 1959 году, когда я задал моих коллег в Математическом Центре следующую задачу. Рассмотрим две программы, которые общаются с помощью атомно читает и пишет в общем магазине, они могут быть запрограммированы таким образом, что выполнение их критических секций исключают друг друга во времени? Решения пришел налива, но все не так, чтобы люди старались все больше и больше разработать контрпримеры для их опровержения, я должен был изменить правила: помимо программы они должны были руки в аргумент, почему решение было правильным.
В течение нескольких часов, Чт. Дж. Деккер передал в истинное решение с его правильность аргументов. Деккер впервые проанализировал доказательства обязательства, то выбрали форму аргумент, что бы встретиться с ними, а затем построили программы, к которой этот аргумент был применимо. Это был очень яркий пример того, как много теряется, когда роль математики сводится к проверке апостериори; в 1968 году я бы опубликовать документ под названием "конструктивный подход к проблеме корректности программ".
А потом был Алгол 60. Мы видели, что это проникает в 1959 году и реализовали его в первой половине 1960 года. Я ужасно боялась, для этой реализации было то, безусловно, мой самый амбициозный проект: Алгол 60 был настолько опередили свое время, что даже его создатели не знали, как осуществить это, я никогда не писал компилятор и должен был достичь своей цели с машины, которая была только 4096 слов хранения. (Последнее ограничение было, конечно, благом, но я не помню, что когда мы начинали.)
По сегодняшним меркам мы не знали, что мы делаем, мы не мечтал о каких-либо гарантий того, что наша реализация будет правильно, потому что мы хорошо знали, что нам не хватает теоретических знаний, которые потребуются для этого. Мы сделали единственное, что мы могли сделать в данных обстоятельствах, а именно. сохранить наш дизайн максимально простым и систематические, как мы могли бы и проверить, что у нас было избежать всех ошибок, которые мы могли думать. В конце концов мы узнали, что мы сделали ошибки, которые мы об этом не подумал, а ведь ремонт компилятор уже не настолько чист, как мы первоначально рассчитывали. (FEJ Kruseman Арец еще обнаруженных и исправленных количество ошибок, после того как я покинул Математический Центр в 1962 году.)
С самого начала мы предполагали два очень разных типов ошибок, ошибками записи, которых ремонт тривиально, и ошибки мышления, что бы отправить нас назад к чертежной доске, и различие помог нам, потому что один борется с ними по разным методикам. Военный прокурор Зонневельд и я combatted Дать ошибок кодирования вместе, каждый со своим собственным текстом перед ним, когда мы закончили, как наши тексты были кулаками самостоятельно, две ленты были сравнению механически, и около двух десятков расхождений ℄ если я правильно помню ℄ появился. Ошибки мышления мы пытались предотвратить, убеждая друг друга, почему предлагаемый раздел будет работать. В этом рассуждении мы могли бы обсудить основном работой компилятор, программа составлена была рассматриваться как данные, и этот опыт был полезен на потом, как это сделало нас привыкли к не-эксплуатационных соображений текстов программ.
Весь опыт сделал меня чувствительны к тому, что позднее будет называться модуляризации или разделяй и властвуй или абстракции, к уходу с которыми интерфейсы были выбраны и потенциальные сферы программирования задача в целом. Он сильно способствовал моему последующих мнение, что создание уверенности в правильности его дизайн был наиболее важным, но трудным аспектом с задачей программиста. В мире, одержимых скоростью, это не универсально популярное мнение.
Я помню те дни две дизайн принципах, которые мне хорошо с тех пор, а именно.
(I), прежде чем приступать к действительно значительным проектом, в частности, перед началом крупных инвестиций кодирования, попытаться убить проекта во-первых, и
(II) начинаются с самых сложных, наиболее рискованной части первой.
Моя первая программа испытаний была почти пустой блок, скажем,
начать реальный X конец,
не самый сложный пример, но моем 4 тест двойная сумма, в которой вложенные вызовы суммирования рутинной были введены с помощью параметра механизма, а суммирование рутинной сама была определена рекурсивно. Попутно мы показали справедливость что стало известно как S устройств Дженсен.
После этой реализации Interlude я вернулся в довольно общих чертах остается открытым вопрос о надлежащей координации в принципе асинхронных компонентов. Без непосредственного участия я видел несколько лет назад усилиями связи всех видов оборудования перфорированные карты X1 и был в ужасе от степени сложности введено включение в режиме реального времени обязательств. Ради простоты "Поэтому я настаивал на" вечные "конструкции, правильность которого может быть создана дискретными рассуждения только.
Почти неизбежно модель взаимодействующих процессов последовательного появились: последовательные процессы с (по определению!) Неопределенная относительных скоростей и, следовательно, для их сотрудничества, оснащенный некоторые примитивы для синхронизации.
Другая возможность для упрощения был представлен признание того, что сроки аспекты между частью коммуникационного оборудования и программы, которые использовали его полностью симметричной между двумя и независимо от того, у нас был вход или выход устройства. Излишне говорить, что это объединение помогло.
Когда мы были вовлечены в разработку мультипрограммирования системы, расширения медленно стал все более и более явной обеспокоенностью. Он должен был. В IBM, и, возможно, в другом месте, а, к нему в качестве предполагается закон природы, что "сложность системы", в некоторых неофициальных смысле будет расти пропорционально квадрату числа компонентов; мотивах его был прост ℄ каждого компонента могут мешать друг другу компоненты и т.д. ℄ но если бы это было правдой было бы де-факто исключают системы за определенного размера. Это вызвало мой интерес к системам структурирован таким образом, что "сложность системы" в том же смысле неофициальных не будет расти более чем линейно с размером. В 1967 году, выражение "слои абстракции" вошел компьютер жаргон.
Позвольте мне в заключение обсуждения этого эпизода, процитировав последние два предложения EWD123 "Сотрудничество последовательная обработка" (сентябрь 1965):
"Если эта монография дает любому читателю четкое указание о том, какой иерархической упорядоченности может быть как ожидается, будет уместно, я пришел один из моих самых близких целей. И пусть мы не надеемся, что конфронтация с тонкостях Мультипрограммирование дает нам четкое понимание того, что Uniprogramming это все о?
В 1968 году я страдала от глубокой депрессии, частично вызванный департамента, который не принял информатики как имеющие отношение к его призвание и распустил группу я создал, и отчасти вызвано мое собственное колебаний, что делать дальше. Я знал, что в ретроспективе, реализации Алгола и мультипрограммирования системы была только ловкость и упражнения, что теперь я должен был решать реальные проблемы, как сделать сложные вещи. В моем подавленном состоянии он взял меня месяцев до набраться смелости, чтобы написать (по терапевтическим причинам) EWD249 "Заметки по Структурное программирование" (август 1969), он положил начало моего выздоровления.
Он пытается синтезировать вышеупомянутых компонентов предыдущее десятилетие. Он упоминает о ранних странице "Структура программы в связи с убедительной демонстрацией правильности программы", упоминается как наши умственные СПИД "1) Перечисление, 2) математической индукции, 3) абстрактное", и о первой и Последнее я цитирую (с EWD249-14)
"Нумерационное рассуждения все в порядке, поскольку она идет, но, как мы довольно тупой это не очень далеко зайти. Нумерационное рассуждения только адекватных психических инструмент под тяжелой граничное условие, что мы только использовать его очень умеренно. Мы должны ценить абстракции, как наши основные психические техники уменьшить требования, предъявляемые перечисления рассуждения. "
У меня было два внешних раздражителей: в 1968 году НАТО конференция "Программная инженерия" в Гармиш-Партенкирхен и основания ИФИП Рабочей группы по методологии программирования ". Благодаря вездесущим ксерокс, мой машинописный текст может распространяться, как лесной пожар, и он сделал это, вероятно, потому, что люди нашли освежающий в сложившейся культуры характеризуется 1968 года IBM рекламы в Datamation, что представлены в полном цвете сияющий Сузи Майер которые решить все ее проблемы программирования путем перехода на PL / I. По-видимому, IBM не любил популярность мой текст, он украл термин "Структурное программирование" и под ее эгидой Харлан Д. Миллс тривиализуется оригинальной концепции к отмене доЬо.
Оглядываясь назад, я не могу не заметить, мой страх формальной математики в то время. В 1970 году я провел более чем десятилетие надеясь и то, рассуждая, что программирование бы и должна стать математической деятельности, я был (повторно), расположенных задачи программирования, с тем чтобы сделать его лучше поддается математической обработке, но тщательно избегать создания необходимых математике себя. Мне пришлось ждать Боб Floyd, который заложил основу для Джим Кинг, который показал мне первый пример, который убедил меня, и для Тони Хора, который показал, как семантика может быть определена в терминах аксиомы, необходимые для доказательства свойств программ, и даже тогда я не видел значение своей работе немедленно. Я был очень медленным.
Наконец рассказ для записи. В 1968 г., Сообщения ACM опубликовала текст мину под названием "доЬо считались вредными", который в последующие годы будет наиболее часто ссылаются, к сожалению, однако, часто, авторы которых не видела больше, чем его титул, который стал краеугольным камнем моей славы, став шаблона: мы хотели бы увидеть все виды статей под названием "X считается вредной" практически для любого X, в том числе один с названием "Дейкстра считались вредными". Но что случилось? Я представил документ под названием "дело против доЬо", который, в целях ускорения ее публикации, редактор изменилось в "Письмо в редакцию", и в процессе он дал ей новое название его собственное изобретение! Редактор был Никлаус Вирт.
Nuenen, 10 июня 2001
prof.dr Эдсгер В. Дейкстра Факультет компьютерных наук Техасский университет в Остине Остин, штат Техас 78712-1188 США
--------------------------------------------------------------------------------
Транскрипция Вольфганга Хоубен. Последняя редакция на Mon, 21 апреля 2008.
Продолжение следует
|