Компьютеры и вычисления [Оберон / Компонентный Паскаль / Вики]

Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.
====== Компьютеры и вычисления ======

Личная точка зрения

Никлаус Вирт     

Оригинал:
https://people.inf.ethz.ch/wirth/Miscellaneous/ComputersAndComputing.pdf

Перевод: [[https://forum.oberoncore.ru/memberlist.php?mode=viewprofile&u=5636|Dimik]]


===== Эпоха становления =====

Историки относят зарождение вычислительной техники далеко назад, в средние века. Мы же предпочитаем начать с того момента, когда компьютеры стали коммерчески доступными и обрели роль в бизнесе и науке. Это был 1960 год.
До электроники были вакуумные лампы. Ранние компьютеры содержали тысячи таких ламп, которые потребляли много электроэнергии. С их многочисленными лампами и тяжелыми блоками питания компьютеры были монструозными и заполняли целые комнаты.

Инновация Джона фон Неймана (1944г) превратила компьютеры в то, чем они сейчас являются. Раньше они состояли из блока управления и отдельного арифметического блока. Первый последовательно получал инструкции из хранилища инструкций, второй интерпретировал их и изменял данные в хранилище данных.

Фон Нейман ввел две фундаментальные концепции. 

Во-первых, два блока были объединены. Это позволило компьютеру генерировать данные, а затем интерпретировать их как инструкции. Таким образом, компьютер превратился из специального устройства (с одной и той же программой) в универсальную машину ‒ программируемый компьютер. И именно это отличает компьютер от всех других технических устройств до сегодняшнего дня.

Второй важной концепцией стала инструкция условия.

Экспериментальные компьютеры, разработанные в качестве прототипов, обычно в университетах, с 1945 по 1960 год, все они использовали эти фундаментальные идеи.

===== Годы пионеров =====

В 1959 году в Квебеке (Канада) я впервые имел дело с компьютером на курсе по численному анализу, который вел профессор Goodspeed. Но компьютер не соответствовал имени профессора. На самом деле, он был не только медленным, но и "падал" всякий раз, когда мы составляли небольшую программу. Таким образом, мое первое знакомство с компьютером было мрачным и обескураживающим. Я не могу объяснить, как я сохранил интерес к вычислительной технике. Но я чувствовал, что это будет важно в будущем.

Доступным  компьютером  был  Alwac  III-3E  c тысячами электронных ламп, и занимавший целую  комнату.  Срок  службы  одной  лампы 10'000 часов. Можно было рассчитать,  что  вся система  будет умирать каждые несколько часов.  Так и происходило!   Программирование   осуществлялось   путем  составления  таблиц инструкций  в  шестнадцатеричном  коде. Я думал ‒ что в этом был потенциал для улучшения.

Второй  раз  я  попробовал  компьютеры через год в Беркли. Там был большой компьютер IBM 704, один из первых компьютеров, на транзисторах вместо ламп, и поэтому  гораздо  более  надежный.  Доступ  к  нему  был  только через колоды перфокарт,  которые  доставлялись в Вычислительный центр. Карточные колоды от различных   клиентов   складывались   операторами,  и  система  автоматически обрабатывала  одну  колоду  за  другой (пакетная обработка). Результаты  были  через  несколько  часов  или  даже дней, на бумаге,  в  виде  текстов,  состоящих  из  цифр и заглавных букв. Программирование осуществлялось на новом языке Фортран (Трансляция формул). Это было улучшение по сравнению с шестнадцатеричным кодом, но я не мог понять, как  работает компьютер. И снова я чувствовал, что здесь есть возможности для совершенствования.

В 1960-1965 годах доминировали большие, удаленные компьютеры. Они назывались мэйнфреймами и занимали большие помещения. Все марки были почти одинаковыми, различаясь размером слов, объемом памяти и скоростью выполнения. Они имели один или два регистра аккумулятора. Три нововведения заслуживают упоминания:

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

Охарактеризуем IBM 704. Он имел память из 32768 (215) слов по 36 бит каждое. В то время наборы символов состояли из 64 (26) символов и размер слов был кратен 6 (6-битные байты!). Числа хранились в знаково-величинной форме: один бит для знака, 35 бит для абсолютного значения. Ядро 704 состояло из 36-битного регистра аккумулятора (в котором якобы накапливались суммы), регистра MQ (в котором хранился множитель и три 15-битных индексных регистра.

Существовало два формата инструкций:

тут вставить рисунок

Типичными инструкциями В-типа были LDA, STA, ADD для загрузки, хранения и добавления переменной (из памяти) в аккумулятор.  Эффективный адрес вычислялся как сумма поля адреса и индексного регистра, указанного полем метки. Было всего несколько инструкций типа А. Примером может служить TIX, подразумевающая пересылку по заданному адресу и вычитание декремента из указанного индексного регистра. Эта сложная инструкция была разработана для реализации быстрых циклов с последовательными значениями индексов.

Вторым новшеством стало прерывание, реализованное в более поздней модели 7090. Здесь внешний сигнал от устройства ввода/вывода приводил к прерыванию текущей команды и вызвал обработчик прерывания. Последствия от этого были значительными.

Третьим нововведением стали числа с плавающей запятой. Было много жарких дискуссий о том, как представлять дробные (вещественные) числа. Варианты были с фиксированной и плавающей запятой. В последнем случае (вещественное) число x представляется двумя целыми числами, упакованными в одно слово, скажем,  e  и  m,

причем     x = Be * m     и     1.0 <= m < B.

Обычно B = 2. 

704-му требовалось около 80 мкс для сложения с плавающей запятой и 8 мкс для целочисленного сложения.
Основными вычислительными машинами были IBM 704, 7090, 7094, UNIVAC 1108, и позже CDC 1604 (с 48-разрядными словами и 6 индексными регистрами). 

Кроме 704, в 1961 году я столкнулся с гораздо меньшим компьютером, имевшимся в институте под руководством профессора Гарри Хаски. Это был Bendix G15, разработанный на основе "компьютера Тьюринга" в NPL в Англии. Это была отдельная машина, и на нее нужно было записываться по часам и на несколько дней вперед. Гениальная конструкция с небольшим количеством ламп и накопителем на магнитном барабане. В ней использовался последовательный сумматор с одной лампой. Программирование состояло из построения таблицы кодированных инструкций, что делало программирование интригующим, или скорее громоздким и запутанным. Размещение на дорожках барабана имело решающее значение для скорости выполнения. Любое слово появлялось под считывающей головкой только один раз за оборот барабана, то есть примерно каждые 40 мс. G15 был интересным устройством для любителей головоломок, но никак не указателем на будущее. Однако теперь я мог понять, как функционирует машина. Это и есть прогресс.

===== Аналог против цифры ‒ двоичный код против десятичного =====

В 1960-х годах компьютерный мир состоял из двух лагерей: аналогового и цифрового. Было совершенно неясно, за кем из них будущее. Как правило, математики принадлежали к цифровому, а инженеры-электрики ‒ к аналоговому лагерю. Цифровые компьютеры были точными, но требовали много дорогих компонентов, в то время как инженеры привыкли жить с приблизительными результатами, точными, возможно, до 3 или 4 десятичных цифр. В аналоговом мире только сложение и интегрирование (по времени) легко достижимы, в то время как умножение и деление трудны или практически невозможны. Сегодня жаркие споры по поводу аналоговых и цифровых технологий полностью исчезли. Это связано не только с огромным снижением цены на цифровые схемы, но и потому, что аналоговые значения было очень трудно (или даже невозможно) хранить. Сегодня, компьютеры  используются не столько для вычислений, сколько для хранения данных. Как следствие, аналоговые компьютеры вымерли.

Цифровые технологии ‒ это иллюзия. Физический мир является аналоговым за исключением атомарного уровня квантовой физики. Даже хранимые значения часто не являются цифровыми . Современная память (2016г) состоит из ячеек, способных различать 8 (аналоговых) значений. Кстати, прилагательное "цифровой" происходит от латинского digis (digitis),означающего "палец". Это наводит на мысль, что цифровые компьютеры считают, поднимая пальцы вверх, как ученики первого класса. Прилагательное "аналоговый" подразумевает что вычисленное значение представлено аналогичной величиной, (напряжением). Здесь разумнее проводить различие между дискретным и непрерывным, а не между цифровым и аналоговыми.

Внутри цифрового сообщества существовал еще один раскол. Он разделил мир на двоичный и десятичный лагеря. Двоичные компьютеры ‒ представляют целые числа как последовательность битов, причем один  в позиции n с основанием 2n. Десятичные компьютеры - представляют целые числа как последовательности десятичных цифр, один из которых в позиции n имеет основание 10n. Kаждая десятичная цифра кодируется 4 битами.

Крупные компании предлагали оба вида компьютеров, хотя очевидно, что двоичное представление было более экономичным. Причина такого разделения в том, что финансовый мир настаивал на том чтобы компьютеры давали точно такие же результаты, как и вычисления вручную, даже если они ошибочны. Такие ошибки могут возникнуть в случае деления. 
Дилемма была "решена" в 1964 году системой 360 от IBM, предложив оба представления чисел с помощью большого набора инструкций.

===== Первые языки программирования (1957-62г) =====

Составление длинных последовательностей инструкций было утомительным и подверженным ошибкам занятием. Решение этой проблемы было впервые представлено компанией IBM с помощью языка Fortran (Транслятор формул). Программа, которую позже назвали компилятором, была разработана группой под руководством Джона Бэкуса в 1957 году. Цель заключалась в том, чтобы заменить ассемблерный код математическими формулами, переменными и выражениями. Если в ассемблерном коде приходилось перечислять каждую отдельную инструкцию, то теперь это можно было выразить более привлекательно в одной строке (перфокарте). Например, инструкция по сложению двух переменных и сохранению результата:

LOD X

ADD Y

STO Z

тоже самое на Фортране:

Z=X+Y

FORTRAN был ориентирован на ввод данных с перфокарт. Они постулировали, что строка состоит из 80 символов (только заглавные буквы), с колонками 73-80, зарезервированными для нумерации карт (полезно, если вы уронили колоду карт!). Символ "С" в колонке 7 означал, что карта содержала комментарий. Не было никаких объявлений и типов данных, за исключением, что имя переменной, начинающееся с I, J, ..., N, обозначает целое число, все остальные - числа с плавающей запятой. FORTRAN содержал подпрограммы. Они должны были компилироваться независимо, и проверка согласованности параметров не производилась. Фортран ввел понятие программных библиотек (в основном для математических функций). Несмотря на появление более мощных языков Фортран оказался выдающимся достижением на протяжении десятилетий. Особенно в исследовательских лабораториях и университетах, где числовые вычисления были доминирующими.

Технику трансляции пришлось изобретать с нуля. С течением времени они накопили огромное количество программ, которые теперь называются  "Программное обеспечение" (ПО), и вложили столько усилий, что казалось невозможно отойти от Фортрана. Это привело к появлению феномена унаследованного ПО.

Первая альтернатива Фортрану была представлена в 1958 году группой европейских ученых. Их язык назывался Алгол (Алгоритмический язык). Он был пересмотрен группой из 13 европейских и американских ученых и был объявлен на конгрессе IFIP (Международная федерация обществ по обработке информации) в Париже в 1960 году. Этот язык стал известен как Алгол 60 и должен был стать международным стандартом. Считалось, что столь важная концепция не должна быть передана в руки одной коммерческой компании. Следующие основные моменты стали отличительной чертой Algol 60:

  - Язык был определен в кратком отчете, отредактированном Питером Науром. Основой лежала формальная нотация для определения синтаксиса языка.
  - Нотация для текстов программ была в свободном формате, просто как последовательности символов, или, скорее, основных символов языка. Эти символы составляли его словарный запас. Не было никаких ссылок на перфокарты.
  - Структура программ задавалась грамматикой (синтаксисом) языка. Этот синтаксис определялся набором правил основанных на БНФ (форма Бэкуса-Наура).
  - Словарный запас состоял из заглавных и строчных букв, цифр и спец-символов (таких как + - < >) и т.д, а также зарезервированных слов (begin, end, ...).
  - Каждая переменная должна была быть объявлена в специальном месте декларации.
  - Каждой переменной, константе или выражению присваевается тип. Стандартными типами данных были Integer, Real и Boolean.
  - Тип Boolean определяет два логических значения True (Истина) и False (Ложь) и логические операторы.
  - Выражения содержали вложенные выражения. Их синтаксис был рекурсивным.
  - Процедуры (в Фортране ‒ подпрограммы) могут быть рекурсивными.
  - Последовательность операторов может быть выражена в виде блока "begin ‒ end" с объявлениями. Переменные, объявленные в блоке, считались локальными для этого блока. Концепция локальности оказалась чрезвычайно важной для программирования.
  - Определение языка было машинно-независимым.


Именно структурированное описание языка, (синтаксис) способствовало распространению термина "язык", хотя на самом деле это неверное название. Язык ‒ это разговорная речь, а язык программирования ‒ нет. Термин "формализм" был бы более подходящим, но термин "язык" сохраняется и по сей день. 

Алгол, как и Фортран, был ориентирован на численные вычисления. Это подходило для коммерческих приложений, таких как бухгалтерский учет и счетоводство. Но в то время как для Фортрана рост сообщества пользователей был обеспечен благодаря поддержке могущественного промышленного игрока, сообщество Algol так и не стало большим. Algol оставался ограничен академическими сообществами, в основном в Европе, и оставался почти неизвестным в США, хотя он был намного лучше.
Чтобы удовлетворить потребности коммерческого мира, в 1962 году был изобретен язык Cobol (Common Business Oriented Language - Жан Саммет из IBM) и продвигался Министерством обороны США (DoD). Академики считали его слишком многословным, с попыткой удовлетворить пользователей, не склонных к математической краткости. Cobol получил очень большое сообщество пользователей. 

Другой заметной разработкой стал язык Lisp (List Processing, McCarthy, 1962г). В отличие от всех остальных, этот язык был очень кратким. Не повторение, а рекурсия была его отличительным свойством. Все элементы данных были узлами динамической структуры данных. Эти узлы были либо числами, либо короткими именами, либо пары, ссылающиеся на два узла-потомка. Таким образом рекурсивные структуры, такие как списки или деревья могли быть созданы во время выполнения программы т.е. динамически. Удивительным свойством Лиспа была его предельная простота. Существовал только один тип данных, представленный в двух вариантах. Первый представлял собой пару указателей на два других элемента. Вторым было значение, обычно число или несколько букв. Существовало лишь несколько базовых функций, позволяющих строить произвольные списки и деревья. A Lisp-программа представляла собой приложение одной функции, которая, вызывала другие (определяемые программистом) функции, поэтому о Лиспе говорили как о функциональном языке:

CONS(x,y)    генерирует новый элемент, указывающий на пару x и y

CAR(x)          первый элемент пары x

CDR(x)          второй элемент пары x

ATOM(x)        указывает, является ли x парой или атомом (число).

Это свойство привлекло внимание к проблеме распределения хранилищ и главным образом, рекультивации хранилища на передний план. Решение заключалось в автоматизации восстановления хранилища. Это вскоре стало известным как сборка мусора. Как ни странно,  Lisp стал известен как язык искусственного интеллекта ‒ тема, которая появилась в это время охватывая многие приложения, которые были нечисловой природы. Но в языке не было "искусственного интеллекта" как такового. Тем не менее, сообщество искусственного интеллекта упорно придерживалось Lisp. В этом может быть повинна одна особенность: сам LISP-код был представлен структурами данных LISP, и поэтому сгенерированная структура может рассматриваться как интерпретируемая программа. Следовательно, LISP-программы могли расширять и изменять себя, что является довольно опасной возможностью.

Хотя Алгол так и не стал широко используемым языком, его влияние было глубоким в области разработки и реализации языков. Это произошло благодаря его точному, формальному определению. В академических кругах началась бурная деятельность, и языки распространялись во всех направлениях. В основном это были локальные разработки, которые вскоре  исчезали со сцены. Новый предмет информатики возник благодаря разработке языков и программированию. Языки с трудом вписывались в математике и электротехнике. Особенно актуальной был тема синтаксического анализа формальных текстов ‒ суть компиляторов. Теперь синтаксические анализаторы получали из синтаксических спецификаций языка и больше не были эмпирическими алгоритмами. Два принципа нисходящего и восходящего синтаксического анализа стали конкурентами. Считалось, что синтаксис может быть определен без рассмотрения синтаксиса, и в результате появились сложные схемы разбора. Это было печально, потому что язык может быть задан синтаксисом, который может быть обработан простым и эффективным синтаксическим анализатором.

Некоторые усилия были направлены на формализацию не только синтаксиса, но и семантики. Формальное определение семантики, однако, является труднодостижимой целью, и поэтому эти попытки были обречены на неудачу. Тем не менее, все эти мероприятия придали компьютерной науке оттенок академической зрелости, противодействуя мнению, что информатика была в основном сферой деятельности практиков.


===== Компьютер с сокращенным набором инструкций RISC =====

С 1950 по 1970 год национальные лаборатории по разработке атомного оружия (Лос-Аламос ‒ Ливермор) предъявляли ненасытные требования к вычислительной мощности. Их призывы к созданию более быстрых компьютеров ставили перед разработчиками серьезные задачи, а их финансовые ресурсы обещали огромные затраты. Целью была, попросту говоря, разработка суперкомпьютера.

Компания, которая первой приняла вызов, была CDC (Control Data Corporation ‒ Миннеаполис), и ее главный конструктор Сеймур Крей. После разработки CDC 1604 он отошел от текущей тенденции, которая привела к появлению компьютеров со все более сложными и большими наборами инструкций. Его идея в том, чтобы предоставить только несколько основных инструкций, исполняемых с максимальной скоростью. Помимо этого, он сделал ставку на новое семейство компонентов с ECL-технологией (Логика с эмиттерной связью), которая обеспечивала быстрые транзисторы, но с потреблением большого количества тока. Как следствие, основной проблемой стало не проектирование логики, а охлаждение транзисторов. Этот компьютер был построен до появления интегральных схем.

Архитектура CDC 6000 выглядит следующим образом. Память состоит из 262144 (218) 60-битных слов, а процессор содержит три набора по 8 регистров. Регистры данных X0 - X7 имеют ширину 60 бит, адресные регистры A0 - A7 и регистры индексов B0 - B7 имеют ширину 18 бит. Инструкции имеют длину 15 или 30 бит, 2, 3 или 4 помещаются в 60-битное слово.

тут вставить рисунок

Компьютер использовал 1-комплементарное представление целых чисел. Это позволило быструю инверсию знаков, но обеспечивало две формы для нуля, что порождало несколько неприятных проблем. Странность заключается в правиле, что присваивание A-регистра имеет побочный эффект на соответствующий X-регистр. Присвоение адреса А-регистру было единственным способом передачи данных из памяти в память. (Эта "особенность" нравилась разработчикам компиляторов).

Ai := a         →         Xi :=  mem[a]               for i < 6      load

Ai := a         →         mem[a]  :=  Xi              for i >= 6    store


===== Создание компиляторов (1960г) =====

В 1962 году проектирование языка и реализация компилятора стали важными темами. Публикация Алгола с его строгим определением синтаксиса привело к активным усилиям по разработке методов синтаксического анализа. Было признано, что компиляторы должны управляться своим синтаксическим анализатором, разлагая текст на структурные элементы, и что затем код должен быть сгенерирован для отдельных сущностей. Учитывая сложный синтаксис, синтаксический разбор должен быть эффективным. 

Возникли два разных метода ‒ нисходящий и восходящий. Направление ‒ это направление обхода синтаксического дерева, подлежащего разбору текста. Следовательно, метод "сверху вниз" всегда начинается с "программы" как цели синтаксического анализа, а затем подразделяет эту цель на подцели. 

Этот метод несколько ограничен и не подходит для некоторых видов грамматик. Более мощным методом является синтаксический разбор снизу вверх, который просто читает текст и распознает структурные единицы, а затем составляет более высокие единицы из субъединиц, пока не будет достигнута цель "программа". Этот метод основан на таблицах. Таблицы могут быть сгенерированы автоматически на основе заданного синтаксиса. 

Если ранние компиляторы были нисходящими синтаксическими анализаторами, то последующие разработки отдавали предпочтение методу "снизу вверх", поскольку он допускал более сложные грамматики, что казалось выгодным для растущей сложности языков, таких как PL/1 (IBM) и Pascal. 

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

Однако на самом деле суть построения компиляторов заключается в генерации кода, которая и по сей день не поддается систематизации . Что сделало эту задачу сложной, так это несоответствие архитектур компьютеров и языка. Компьютеры были спроектированы с учетом языка Фортран, и их наборы инструкций были ориентированы на элементы языка. Но Algol 60 и PL/1 радикально изменили ситуацию. Достаточно привести несколько примеров.

Первой проблемой была обработка сложных выражений, когда доступны только 1 или 2 регистра. Стало проще, с появлением компьютеров с банками регистров, и много усилий было потрачено на оптимизацию кода. Гораздо более серьезной проблемой была работа с процедурами и локальными переменными. Они позволяли повторно использовать хранилище. Рекурсия в Algol сделала возможным выделять место под локальные переменные, динамически, во время выполнения. Поэтому к переменным нужно было обращаться через регистр. Все это привело к использованию кадрового стека со специальными регистрами содержащими базовый адрес, но такие регистры были недоступны для распространенных компьютеров.

Поэтому эти средства приходилось реализовывать программно, разделяя немногочисленные регистры для различных целей и тем самым снижая скорость выполнения. В результате, Algol с его общностью и рекурсией был признан неэффективным и уступающим Фортрану. И потом, численные вычисления не требовали рекурсии. Следовательно, Фортран был предназначен для "реального мира", в то время как Algol казался роскошью для любителей повозиться.

===== B5000 (1963г) =====

Оставалось надеяться, что инновационный дизайн Алгола расширит его влияние на развитие компьютеров. Так и произошло.  Оказалось возможным, сделать Algol конкурентоспособным с Fortran в отношении скорости выполнения. Уже в начале 1960-х годов появились компьютеры, ориентированные на особенности Алгола, с акцентом на реализацию рекурсивных процедур и общих выражений. Для того чтобы перевести выражения общего характера в последовательности простых инструкций, они преобразуются из инфиксной в постфиксную форму:

<code>
x + y                       x y +
x + y + z                   x y + z +
(x + y) * (z-w)             x y + z w - *
</code>

Это позволяет выполнить простую оценку, если операнды задвинуты в стек. Тогда операторы просто заменяют операнды на результат. Поэтому разработчики компьютеров пошли навстречу разработчикам компиляторов, предоставив стек с выталкиванием вместо массива регистров. По сути, стек ‒ это массив со счетчиком вверх-вниз в качестве индекса, и эффект в том, что номера регистров могут быть опущены в коде. Это приводит к более плотному коду. Идея аппаратного стека показалась очень привлекательной  и британском GE KDF9 и голландскомElectronica X8 реализовали ее. Burroughs B5000 также принял эту концепцию, реализовав два верхних элемента в виде регистров. Передача нижних элементов стека в память и из памяти была автоматизирована по сложной схеме. Примечательно, что в B5000 использовалась одинаковая кодировка для целых и вещественных чисел с 39-битной мантиссой, 6-битной экспонентой и основанием B = 8. Код программы состоит из 12-битных слогов, по 4 в слове. В конечном итоге идея стека выражений не прижилась и исчезла из употребления. Прямые номера регистров в коде казались более предпочтительными, и сложные алгоритмы оптимизации делают все возможное. Самой сложной особенностью Алгола, однако, были рекурсивные вызовы процедур. Рассмотрим:

<code>
PROCEDURE P(x: INTEGER); 
BEGIN
    IF x > 0 THEN P(x-1) END
END P
</code>

Для каждого рекурсивного вызова Р создается новое x, для которой должна быть выделена память. То же самое можно сказать и о локальных переменных. Очевидным решением является стек кадров, каждый из которых содержит параметры, локальные переменные и адрес возврата. Следовательно, к каждой переменной нельзя обратиться по статическому адресу, но можно по адресу, к которому добавляется базовый адрес, адрес содержащего фрейма. Эта база должна быть доступна из индексного регистра, который инициализируется при вызове процедуры (и восстанавливается при выходе). 

Неприятной проблемой для существующих main frame-компьютеров было получение адреса возврата (который также должен быть помещен во фрейм). Худшее решение было найдено в суперкомпьютере CDC 6000. Его инструкция вызова помещала адрес возврата в ячейке памяти, предшествующей адресу вызова (т.е. перед первой инструкцией процедуры). Эта схема записывается в программу и тем самым делает код не реентерабельным (невозможность повторного вхождения). Это неприемлемое решение. Эффективная и элегантная реализация рекурсии требует режима адресации с адресными регистрами (указатель стека, указатель кадра). B5000 предлагает эти компоненты. Однако, инструкция вызова это сложная схема с обращением к памяти, требующая сложной схемотехники и времени.

Но у Алгола в запасе были еще несколько крепких орешков. Основным камнем преткновения были  имена  параметров. Он постулировал  замену  формального  параметра на фактический. Лучшим примером его использования является следующая процедура (язык Паскаль):

<code>
PROCEDURE Sum(i, n: INTEGER; x REAL): REAL;
  VAR s: REAL:
BEGIN
  s := 0;
  FOR i := 0 TO n-1 DO s := x + s END ;
  Sum := s
END Sum;
</code>

Учитывая дальнейшие переменные

<code>
 k: INTEGER;
 a: ARRAY 100 OF REAL;
</code>

сумма элементов массива a может быть выражена вызовом функции

 Sum(k, 100, a[k])

преобразование оператора  FOR  в

 FOR k := 0 TO 100-1 DO s := a[k] + s END

Это означает, что для каждого сложения должен быть оценен фактический параметр a[k], и поэтому она должна вызываться как функция (без параметров). Эта особенность значительно усложняет компиляцию вызовов процедур.  B5000 вытеснил эту сложность из программного обеспечения в аппаратное: инструкции для получения значения должны сначала проверить (во время выполнения), является ли операнд переменной или функцией. Распознавание основывалась на бите в каждом операнде, указывающем, является ли он простой переменной или дескриптором функции.
B5000 ввел понятие дескрипторов. Каждый массив представлен дескриптором массива точно так же как процедуры представлены дескрипторами процедур. Дескриптор массива содержит информацию о границах массива, и при доступе к массиву проверяется, что индекс находится в пределах этих границ. Схема дескрипторов требовала перенаправления для доступа к каждой переменной и следовательно занимало больше времени.
Инженеры имели мало представления о языках и компиляторах, а разработчики языков имели мало знаний о проектировании аппаратного обеспечения и еще меньше о компиляции. Они даже гордились этим и считали, что настоящие инновации могут появиться только при игнорировании технических ограничений. В результате образовался разрыв между программным и аппаратным обеспечением. Разработчики B5000 попытались смело преодолеть этот разрыв но зашли слишком далеко. Они реализовали языковые функции, которые оказались не совсем реалистичными и необходимыми. Как следствие, компьютер B5000 1964 года одним из первых в Стэнфордском  университете,  стал  очень  сложным и дорогостоящим устройством. Он мог эффективно обрабатывать сложные функции Algol, но он едва ли мог конкурировать с обычными машинами для повседневных приложений.

===== Понятие семейства и 8-битный байт (1964г) =====

Система 360 от IBM была анонсирована в 1964 году и принесла еще два новшества. Первое ‒ это понятие семейства компьютеров. До этого времени каждый компьютер имел собственную структуру и производительность; он был уникальным. Теперь же System 360 состояла из множества моделей одного и того же набора инструкций. Каждая модель, имела свои показатели производительности, размер и цену. Но все они выглядели одинаково для программиста. В этом смысле они образовывали семейство и обладали одной и той же архитектурой. Именно здесь и появилось слово "архитектура".
Разумеется, разные модели имели разные реализации аппаратного обеспечения, хотя они работали с одним и тем же ПО. Впервые использовалась техника эмуляции. В младших моделях использовалась новая техника микропрограмм. Аппаратное обеспечение всегда интерпретировало набор инструкций 360. Интерпретатор был определен в микрокоде. Этот микрокод находился в небольшой, но быстрой памяти, обычно это память только для чтения, реализованная по запатентованной технологии. Следствием этого было то, что некоторые инструкции 360 были быстрыми, другие ‒ медленными. Можно было включить некоторые очень сложные и трудные для понимания инструкции. Некоторые из них даже включали циклы в микрокод.
Вторая новинка заключалась в том, что наименьшей индивидуально адресуемой единицей в памяти было не слово, а байт, и этот байт состоял из 8 бит. До сих пор эта считалось, что эта единица состоит из 6 бит, а длина слова во всех компьютерах была кратна 6. Негативным последствием было ограничение наборов символов (ASCII и EBCDIC от IBM) до 64 символов. Расширение до 256 символов было долгожданным. Этот революционный шаг также позволил отказаться от "компьютеров с переменной длиной данных", таких как вездесущий IBM 1401, в котором использовались строковые инструкции, оперировавшие с последовательностью 9-битных байтов, 9-й бит выступал в качестве индикатора завершения строки.


===== Миникомпьютеры и система разделения времени (1965г) =====

В тени больших монстров, с 1965 года появилось новое поколение компьютеров ‒  мини-компьютеры. Первым был PDP-1 компании DEC (Digital Equipment Corp.), за которым последовал популярный PDP-8. Они устанавливались в стандартные 19-дюймовые стойки для  использования в лабораториях, и были построены с дискретными транзисторами с биполярным переходом и памятью на магнитных сердечниках. Длина слова составляла 18 бит (PDP-1), 12 бит (PDP-8) и 16 бит (HP 2116). Время цикла составляло около двух микросекунд. На выполнение каждой команды требовалось 1-2 цикла. Для того времени это считалось очень быстро. Их наборы команд содержали инструкции загрузки и хранения, логические операции, однобитные сдвиги, сложение и вычитание. Умножение и деление должны были быть запрограммированы. Поскольку объем их памяти был небольшим, обычно 4К или 8К о компиляторах для языков высокого уровня не могло быть и речи. Они подключались к печатной машинке (телетайпу) для ввода и вывода данных.
Привлекательность миникомпьютеров заключалась в их доступности. Они находились в вычислительных центрах и допускали интерактивное использование. Вернулась старая схема часов регистрации, которая неэффективна.
В качестве примера мы набросаем структуру популярного PDP-8. Его память из магнитных сердечников, была 4096 слов длиной 12 бит. Вычислительный блок содержал аккумулятор, длиной 12 бит. Инструкции поступали в двух вариантах. Инструкции с обращением к памяти и операторы в формате микроинструкций.


Инструкции обращения к памяти включают команды загрузки, хранения, сложения и логические переходы. Становится ясно, что такие миникомпьютеры кодировались "вручную" с помощью ассемблера. О компиляторах не могло быть и речи; получаемый код был бы слишком длинным и неэффективным. Память была небольшой и обеспечивала загрузку только небольших программ, обычно для управления оборудования и сбора данных.

Примечательной новинкой была система разделения времени с целью обеспечить полностью интерактивное использование без монополизации компьютера. Эта система была разработана Деннисом и Ван Хорном в Массачусетском технологическом институте. В сотрудничестве с DEC они разработали расширенный PDP-1. Он был усилен барабанным магазином с 16 дорожками по 4К слов в каждом. Основное хранилище было увеличено до 3 блоков по 4К слов. Первый раздел использовался для небольшой "операционной системы". Система позволяла 16 программистам работать на одном компьютере квази-одновременно. Она работала с квантами времени  длительностью 33 мс. В каждом кванте происходило три действия: дорожка поочередно считывалась с барабана в секцию 2 (или 3) основного хранилища, та же секция хранилища сбрасывалась на соответствующую дорожку барабана, и процессор выполнял программу в секции основного хранилища 3 (или 2). Это создовало впечатление для программиста что  PDP-1 находится только в его распоряжении. Планирование работы процессора, т.е. его выделение отдельному пользователю, было довольно простым. Пользователям статически отводилось место в кольце, следующий временной фрагмент отдавался следующему пользователю в кольце, за исключением случаев, когда он ожидал ввода/вывода.

Вероятно, первая такая система была установлена в Стэнфордском университете в 1964 году в лаборатории для обучения программированию (профессор Суппес). Для того чтобы облегчить ввод текста и управления функциями, в клавиатуру каждой станции была включена специальная клавиша. Позже она стала повсеместной и получила название CTRL-клавиша.
Эта идея совместного использования времени была простой и увлекательной. Вскоре такие системы стали нормой. Производители мэйнфреймов подхватили эту идею и расширили свои продукты соответствующим образом (IBM 360/67, GE 645). Но они верили, что программное обеспечение было всемогущим, и не ограничивали себя ни фиксированной схемой временных квантов, ни фиксированным распределением памяти для каждого пользователя. Индивидуальное, динамическое распределение ресурсов было их видением, размеры памяти в соответствии с потребностями каждого пользователя, и планирование индивидуально в соответствии с приоритетами и доступностью ресурсов. Побочным эффектом стало появление блоков управления памятью в этих многопользовательских компьютерах. Пионером в этой области стал гигантский компьютер Atlas в Манчестере.

Это были цели высокого полета. Никто еще не проектировал системы такой сложности. Трудности были сильно недооценены, тем не менее, сроки поставки были обещаны жаждущим клиентам. Были наняты огромные толпы системных программистов, что привело к непреодолимым управленческим и коммуникационным проблемам. Все закончилось тем, что 1968 год был назван кризисом программного обеспечения, очень метко описанный в книге Фреда Брукса "Мифический человеко-месяц", кульминацией которого стала мудрая мысль о том, что "добавление человеческих ресурсов в запоздалый проект делает его более поздним".
Компиляторы вместе с OS/360 стали первыми системами  которые  опирались на элементы дизайна, созданные армиями программистов, никому не понятные и сомнительной надежности. Отказы были запрограммированы заранее. Обновления стали ежемесячной рутиной.

Программное обеспечение, то есть ОС, компиляторы и библиотеки, поставлялись производителями компьютеров как аксессуар. Поскольку программное обеспечение выросло до огромных размеров и требовало больших затрат, начался процесс "разукрупнения". Программное обеспечение стало самостоятельным объектом, и его ценообразование было отделено от ценообразования аппаратного обеспечения. Это произошло не без вмешательства судебных инстанций. Появились компании, производящие программное обеспечение. Они создавали программы, пригодные для использования на компьютерах различных марок, и создали собственный рынок.

===== Языки второго поколения и Паскаль (1965-1970г) =====

Первым из языков второго поколения, был PL/1, созданный IBM. То, что IBM сделала с аппаратным обеспечением, должно было сделано и с ПО: Объединение научного и коммерческого сообществ путем слияния Cobol и Fortran. Это должно было стать огромным предприятием, в котором участвовало бы много участников, предлагающих свои концепции и идеи. Результат был опубликован в 1965 году вскоре после анонса семейства компьютеров 360 когда реализация PL/1 уже шла полным ходом. В то время как Fortran, Cobol, а теперь и PL/1 процветали, академическое сообщество с идеей "чистого" программирования только набирало обороты. Академическое сообщество с идеей чистого языка, покоящегося на твердых принципах сформировало группу ученых под эгидой IFIP, образовав Рабочую группу 2.1 в 1963 году. Ее целью было продвижение дисциплины программирования в целом и разработка преемника Algol 60 в частности. Эта группа в составе около 40 человек собиралась примерно раз в полгода в различных местах Европы и США.

Очевидно, что такая большая группа плохо подходила для создания согласованного проекта. Там были долгие  дебаты о различных особенностях языка, которые нужно было исключить или добавить в Algol 60. Очевидно, что в Алголе 60 были сомнительные, плохо определенные элементы, но хотя согласие по их удалению было единогласным, их замена вызвала долгие споры. Основными "ораторами" были Аад ван Вийнгаарден из Математического центра в Амстердаме и Фриц Бауэр из Технического университета в Мюнхене. В жарких дискуссиях эмоции взлетали высоко, и антагонисты даже рвали свои воротнички.

Источником долгих споров стали параметры процедуры. Алгол 60 было два параметра: значение и имя-параметр. Некоторые утверждали, что имя параметр был отличительной особенностью и даже  чертой Алгола 60, другие утверждали, что он по своей сути ухудшает эффективность любой реализации и не имеет смысла (см. главу о B5000).
Были и другие особенности Algol 60, которые вызвали недоумение и жаркие дискуссии. Одна из них проявляется в следующем куске программы:

<code>
PROCEDURE P (q, b);
  BOOLEAN b; PROCEDURE q;
BEGIN INTEGER n;
	PROCEDURE Q; n := n + 1;
	n := 0;
	IF b THEN q(~b, Q);
	Write(n)
END ;
</code>

Какую последовательность чисел породит утверждение P(P, TRUE)? 0, 1 или 1, 0? Стало очевидно, что с одной стороны были "теоретики". стремящиеся предложить удовлетворяющий всех дизайн, основанный на мощных, обобщенных фундаментах, а с другой стороны ‒ "практики" с опытом реализации языков, опасаясь, что если в ближайшее время не удастся прийти к разумному соглашению, основы будут потеряны навсегда. Через несколько лет группа раскололась. "Теоретики" продолжили то, что стало называться Algol Y, в то время как "практики" направились к более скромному Algol X. Последний был реализован на IBM 360/50 под руководством автора этих строк  в Стэнфордском университете. В 1966 году он стал известен под названием Algol W, и использовался во многих университетах Европы и США. Он был меньше, чем монстр, но все же слишком тяжелым. Фракция Algol Y продолжила свою работу (в основном в Амстердаме и Ванкувере), надеясь на релиз через несколько месяцев. Но трудности оставались, и то, что получилось осторожно назвали Algol 68,  окончательно реализованный в 1972 году. Что касается вычислительной техники, по мнению всего мира, это оказалось мертворождением. То, что должно было стать еще одной вехой (после Algol 60), превратилось в бремя.

Освобожденный от достижения компромиссов внутри группы,  автор этих строк пошел по собственному пути. Он разработал язык Pascal, опубликованный в 1970 году. Он получил всемирное признание благодаря своей относительной полноте и простоте. Будучи языком без возможности раздельной компиляции и связывания он, тем не менее, удовлетворял основным потребностям структурированного программирования и идеально подходил для преподавания. Усилия по облегчению переноса компилятора на многие другие (не IBM) компьютеры способствовали распространению Паскаля.
Уже в 1966 году Э.В. Дейкстра (также член WG 2.1) опубликовал документ под названием "Структурированное программирование". Он был разработчиком первого компилятора Алгола, включая рекурсию, что было актуальной темой в то время, поскольку считалось, что рекурсия приводит к неэффективным реализациям. Паскаль должен был реализовать структурированное программирование, стать естественным инструментом для выражения этой метафоры. Он расширил концепцию структуры с операторов на данные.

В Algol 60 использовались условные операторы (if-then-else) и оператор for с большим количеством вариантов. Тем не менее, это был единственный способ выразить итерацию, за исключением явных переходов, с помощью операторов GO TO. Они были основным средством для создания невразумительных программ. Они были объектом критики Э.В. Дейкстра в своем знаменитом письме под заголовком "Утверждения Goto считать вредными". В ответ на это в Паскале появились операторы while и repeat. Но сам оператор GO TO остался; это было бы шоком для программистов, если бы им пришлось обходиться без переходов.

В области структур данных Algol предлагал только массив - структуру, все элементы которого были одного типа. Паскаль добавил запись, единицу с элементами разных типов, называемых полями, множеством и файлом (последовательностью). Ключевым свойством было то, что такие структуры можно было свободно вставлять друг в друга. Можно было создавать не только массивы массивов (матрицы), но и массивы записей, а также записи с массивом структурированных полей. Эти структуры были объявлены как типы, такие же как целые числа, вещественные числа и булевы значения.
Тем не менее, широкое признание Паскаля произошло только через шесть лет после его публикации. Тогда Паскаль был на волне микрокомпьютеров, стоимость которых снизилась и стала доступной для школ и для дома. Чтобы облегчить перенос компилятора на другие компьютеры, был создан гипотетический компьютер и наш компилятор сгенерировал для него код, так называемый P-код. Этот эмулятор был прост для программирования в ассемблерном коде для любой другой архитектуры. Этот метод внес значительный вклад в распространение Паскаля.

Наш компилятор был отправлен (среди многих других) в Университет Сан-Диего (UCSD), а также Ф. Кану, который основал компанию Borland. Оба они встроили компилятор в систему для персональных компьютеров с простой ОС, текстовым редактором и отладчиком. Вместе эти компоненты обеспечили очень быстрый цикл написания, компиляции, тестирования и отладки. Помимо этого, система продавалась на дискете за 50 долларов. Это стало залогом ее успеха. Таким образом, Pascal охватил массы людей, которые не были "испорчены" сложными промышленными продуктами;  и которым не нужно было сначала "отучаться" от старых идей. Только позже , Паскаль оказал влияние  в странах за пределами Европы и США, особенно в России и Китае.
Одновременно с Паскалем (1970г) язык Си был разработан Д. Ритчи в лаборатории Bell Labs. Однажды он признался мне, что Pascal и C получились удивительно похожи. Я вряд ли мог согласиться с этим, и до сих пор считаю Си ‒ это ассемблерный код, приукрашенный, менее элегантным синтаксисом. Он утверждал, что типы данных прикрепляются к переменным просто, как ярлыки. Но в чем их польза, если компиляторы не проверяют согласованность, если эта информация о типах рассматривается как комментарии, которые просто игнорируются? Я считал и до сих пор считаю язык Cи (премия Тьюринга) проклятием вычислительной техники.

Хотя, возможно, язык Cи был необходим во времена доминирования Фортрана; проклятием же было его повсеместное принятие. На самом деле, мы даже реализовали (второй) компилятор Pascal в Цюрихе, используя язык, похожий на Cи (Scallop Макса Энгели). После завершения разработки компилятор был переведен вручную (Р. Шилдом) на Паскаль для загрузки. После этого вспомогательная  версия была благополучно отброшена навсегда. Си, однако привлек внимание всего мира.

===== Микрокомпьютеры (1975г) =====

Микрокомпьютеры, упомянутые в предыдущем параграфе, стали результатом огромного прогресса, достигнутого в полупроводниковой технологии,  в результате усилий по миниатюризации. Дискретные транзисторы были заменены интегральными схемами, содержащими множество транзисторов. Компания Fairchild лидировала в этом направлении, за ней следовали Intel, National Semiconductor, Motorola и другие. Сначала появилась недолговечная технология RTL (резисторно- транзисторная логика), которая вскоре уступила технологии TTL (транзисторно- транзисторная логика). 
Интегральные микросхем успешно стали стандартизированными, основав эру TTL-чипов, серии 74xxx. (Только у военных имели свои собственные, более дорогие микросхемы, серии 54xxx). Кроме того, появилось одно напряжение питания 5 В (только вначале дополненное ‒ 5 В и 12 В для микросхем памяти). Это было одно из самых успешных усилий по стандартизации в истории промышленности.

Строительными блоками схем больше не были транзисторы и резисторы (и иногда конденсатор), а элементарные схемы, такие как затворы, мультиплексоры, дешифраторы, сумматоры, массивы регистров и буферы. Сердцем этих микрокомпьютеров был один чип нового измерения сложности, полный, маленький компьютер, включающий в себя простой арифметический/логический блок, набор регистров данных, регистр инструкций и счетчик программ. В (не совсем первых) микропроцессорных чипах тракт данных составлял всего 8 бит. Выдающимися образцами были Intel 8080, Motorola 6800  и Rockwell 6502. Стали доступны микросхемы памяти, сначала с 1К бит, затем, вскоре, с 4К, 16K и даже 64K (1980г). В результате этого, стало относительно легко проектировать и создавать небольшие компьютеры за скромные деньги. Модернизация микропроцессоров, в частности, Motorola 6809 с 16-разрядным внутренним АЛУ.

Вскоре после этого (1975 год) появилась специальная линейка микрокомпьютеров. Они представляли собой полные компьютерные системы на одном чипе, и они стали известны как микроконтроллеры, которые использовались в основном во встраиваемых системах. Они состояли из простого АЛУ, блока управления и небольшого объема статической памяти (SRAM). Они также содержали встроенную (программируемую) память. В ранних версиях эта память можно было записать только один раз (PROM) более поздние версии содержали стираемую память (EPROM).

Наиболее успешные из них были выпущены компанией Intel (8048, 8051) и вскоре они производились миллионами, снижая стоимость до порядка доллара и вошли в автомобили, холодильники и телевизоры.

===== Проблемы корректности =====

Огромный рост вычислительных мощностей, привел к быстрому росту требований к программному обеспечению, которое становилось крупным и сложным, но при этом по-прежнему производилось старыми методами и командами. Постепенно стало признаваться, что программирование стало трудной интеллектуальной деятельностью и  нужно что то делать,  чтобы уменьшить трудности ‒  необходима дисциплина.

Лидером в этом новом понимании был Э.В. Дейкстра, известный своей отменой утверждения GO TO,  приводившему к самобытному недисциплинированному написанию программ. Его первым вкладом было создание стиля структурированного программирования, подразумевающего программы без переходов. Но он также занимался  категоризацией проблем, возникающих с новой дисциплиной параллельного программирования, где несколько программ выполняются одновременно взаимодействуя через общие переменные. Он показал, что эти проблемы не могут быть решены с помощью присваиваний, присутствующих в существующих языках. Он представил свой знаменитый сценарий двух (или более) последовательных процессов каждый из которых имеет критическую секцию, и с правилом, что никогда более чем один процесс не должен выполнять свой критический участок. На первый взгляд, очевидным решением является следующее, используя две переменные состояния:

<code>
(*СS = критическая часть*)
VAR
q0,q1:BOOLEAN;   (*qi означает: Процесс Pi находится в своей    				критической части*)
PROCESS P0;
REPEAT ...
IF ~q1 THEN q0 := TRUE; CS; q0 := FALSE END ; ...
END P0
PROCESS P1;
REPEAT ...
IF ~q0 THEN q1 := TRUE; CS; q1 := FALSE END ; ...
END P1
</code>

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

P(s)

ждать, пока s > 0, затем уменьшается s

V(s)

увеличивается s

После того, как было полностью признано, что программирование является сложным видом деятельности, стало ясно, что языки программирования, будучи базовым, математическими формализмом, должны быть определены со всей строгостью и точностью. Алгол был первым языком, определенным со строгой спецификацией синтаксиса. Но его семантика была менее ясной, а иногда даже расплывчатой, что, безусловно, не подходит для применения формальных, логических доказательств.
Первый шаг к формально определенной семантике был сделан Р. Флойдом в Стэнфорде в 1968 году. Он создал понятие утверждения. Это предикаты включающие переменные программы, условия, которые должны были выполняться всякий раз, когда выполнение программы достигает места, где находится утверждение. Каждое утверждение S должно было предшествовать утверждение P (предварительное условие) и следовать за ним утверждение Q (последующее условие), выполняемое после выполнения S. Считалось, что Q может быть вычислить из P и S с помощью анализатора программ или программы проверки теорем. Семантика (смысл) высказывания S определялась тройкой {P} S {Q}. Назначение может теперь может быть формально определено следующим образом:

P(y) x := y {P(x)

Вскоре после этого К.А.Р. Хоар опубликовал свою основополагающую работу под названием "Аксиоматическое определение языков программирования". Ключевая идея заключалась в том, что семантика составных утверждений может быть получена из семантики их компонентов. В качестве примера можно привести семантику оператора while следующим образом:
Учитывая {P} S {P}, где P - предикат, то для оператора while

{P} WHILE b DO S END {P & ~b)

сохраняется. P называется инвариантом цикла. Вторая часть доказательства о повторяющихся должна показать, что прогресс гарантирован, то есть, что повторение в конечном счете, завершится путем признания b недействительным.
Затем Э.В. Дейкстра усовершенствовал теорию и ввел понятие предикат трансформатор. Учитывая утверждение S и предикат P, S преобразует P в Q, т.е. Q = F(P, S), где F - булева функция. Оказалось, что полезнее определить преобразователь как P = F'(S, Q), т.е. работать в обратномн аправлении от результата к предусловию при доказательстве корректности программы: Постулирование желаемого результата, а затем работать в обратном направлении, чтобы выяснить, какие состояния будут приемлемы в качестве начальной точки вычислений.

Дейкстра был ведущим членом РГ 2.1. и ярым сторонником научного, математического, строгого подхода к программированию. Он был сильным критиком эмпирических подходов проектирования, методом проб и ошибок, и ярым сторонником программирования как математической инженерии. Широко известным остается его скептическое отношение по поводу тестирования программ. Он отмечал, что тестирование может показать наличие ошибок, но  никогда не доказать их отсутствие. Другим его суровым изречением было: "Не давайте промышленности то, что она хочет, а только то, что ей нужно". Он также укорял, что многие люди путают обычное с удобным.

Хотя вскоре стало ясно, что доказательство корректности является трудной задачей, влияние этой разработки на дисциплину программирования было сильным. Это было стимулом к тому, чтобы сохранять языки простыми и продолжать программирование всегда с заботы о корректности. Но все его высказывания привлекли к Дейкстре не только поклонников.
Проблемы с доказательствами корректности имеют три аспекта. 

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

Во-вторых, спецификации предусловий и постусловий программы, очень сложны, как и сами программы, или даже хуже.

В-третьих, большинство программистов не имеют возможности рассуждать о формальной логике в той степени в какой это требуется. Влияние на то, как сейчас разрабатываются программы: С учетом их доказательства.

Тем временем программирование, или скорее, программная инженерия, как его стали называть, стало самостоятельным бизнесом, независимым от аппаратного обеспечения, на котором работают программы. Термин unbundling, возникший в юридических спорах в 1970-х годах, стал образом жизни. Такие компании, как Microsoft, стали видимым результатом.

===== Начало компьютерной эры (1975г) =====

Микрокомпьютеры быстро распространились в домах и школах и превратили вычисления в домашнее занятие. Тем не менее, их приходилось рассматривать как игрушки. Они были недостаточно мощными для серьезной работы. Первый по-настоящему полезный персональный компьютер, с которым я столкнулся во время академического отпуска в исследовательском центре Пало-Альто (PARC) компании Xerox, был Alto (Б. Лэмпсон, Ч. Тэккер, Э. МакКрейт).

Alto не использовал один из этих 8-разрядных микропроцессоров, а был построен с использованием дискретных компонентов микросхем серии 74Sxx. Сердцем АЛУ были 4 микросхемы АЛУ 74S181 с задержкой распространения менее 100 нс. Шина данных имела ширину 16 бит а память имела емкость 64K 16-битных слов. Alto был оснащен картриджным дисковым хранилищем емкостью 2 Мбайт. Он имел дисплей с побитовым отображением, 808 х 606 точек (бит), а также новым указательным устройством под названием "мышь" с тремя кнопками. Это позволяло напрямую программировать каждую точку на всем поле дисплея. Это резко и заметно отличалось от обычных дисплеев с фиксированными наборами символов, 80 символами в строке и 25 строками на странице. Тексты могли отображаться с индивидуально разработанными шаблонами символов, что стало основой для использования множество шрифтов обычного, курсивного и полужирного начертания. Произвольная графика могла быть представлена смешивая тексты, линейную графику и небольшие рисунки. Эти возможности открыли совершенно новый мир для программистов и компьютеров. Фундаментальным новшеством стала интерактивность.

Не менее важным было то, что объем памяти был достаточно велик, для размещения компиляторов языков высокого уровня и для системного программирования. Язык Mesa отвечал всем этим требованиям. Он представлял собой большое расширение Pascal с несколькими функциями, которые считались необходимыми для выражения специфических возможностей аппаратного обеспечения Alto. Mesa принадлежал ко второму, если не к третьему поколению языков программирования. Как и Alto и его мышь, он был собственностью компании Xerox.

Реализация Mesa опирается на байт-код Mesa. Компилятор генерировал байт-код (подобно P-коду Паскаля), а Alto был микропрограммирован для интерпретации его байт-кода. Этот интерпретатор  находился в специальной, очень быстрой памяти микрокода. Такая схема позволяла создавать плотный программный код, и только благодаря этой конструкции большие программы могли быть помещены в ограниченную основную память.

Еще одной отличительной чертой Alto было то, что все рабочие станции были соединены через сеть, 3-МГц Ethernet. Появилась концепция серверов. Был один сервер, выделенный Alto, для первого лазерного принтера, и один для большого, общего хранилища файлов.

То, что до сих пор было возможно только на крупных мэйнфреймах, теперь стало возможным на персональном компьютере. Новая схема была настолько радикальным отходом от общепринятой вычислительной среды, что справедливо назвать ее началом современной компьютерной эры. В конце концов, каждый из миллионов пользователей сегодня использует персональные компьютеры (ноутбуки) прародителем которых является Alto. Вряд ли кто-то помнит как использовались компьютеры до 1975 года а именно через карточные колоды или медленные линии, подключенные к терминалам. Разница между тем временем и сегодняшним днем огромна.

===== Лилит (1978г) =====

Осознавая эту разницу, я просто не мог представить, как вернуться из своего отпуска в обычную компьютерную среду, в которой человек общался с компьютером по тонкому проводу со скоростью 300 бит/с, сидя перед тупым терминалом. Но как я мог избежать этой страшной участи? Поскольку рабочая станция такого калибра была уникальной, и поскольку ее нельзя было купить, единственным выходом было построить ее. Но это было трудное решение. Мне нужно было создать команду и мастерскую с электронным оборудованием. Мне повезло, я преуспел в обоих этих начинаниях, и всего через два года в 1978 году был создан прототип рабочей станции. Мы назвали ее Лилит, по имени первой жены Адама, которая, будучи изгнанной из рая, соблазняла мужчин по ночам, так же как наша Лилит соблазняла исследователей оставаться на работе по вечерам и в выходные. Это был действительно захватывающий проект с одновременной разработкой аппаратного и программного обеспечения командой из 4-7 человек.

Аппаратная часть Lilith представляла собой 16-битный компьютер, построенный в основном из деталей Shottky TTL. Lilith состояла из 8 плат в 19-дюймовой стойке. Сердцем был процессор (плата) с 4 битовыми микросхемами Am2901. Они составляли АЛУ с 16 регистрами и обычными арифметическими и логическими операциями. Мы дополнили их внешней стековой памятью и бочкообразным шифтером (сдвигатель битов).

Lilith должен был стать компьютером с коротким стеком для оценки выражений. Эта быстрая память была построена из 4 микросхем 74S189, 16x4 ОЗУ. Бочкообразный сдвигатель был важной функцией, необходимой для выполнения быстрых битовых операций, размещая данные в любой позиции бита, а не на границах слова, всего за один такт. Шифтер состоял из 8 микросхем Am 25S10.

Основная память была построена из 64 16K-битных микросхем DRAM. Как и Alto, Lilith был микрокодирован. То есть, действительный компьютер был представлен одной программой, интерпретирующей М-код,  сгенерированный компилятором Модула.

Этот микрокод состоял из 40-битных микроинструкций, расположенных в памяти микрокода, состоящей из пяти 2K x 8 EEPROM (2716). За каждый тактовый цикл (7 МГц, 140 мс), одна микроинструкция декодируется и выполняется процессорными микросхемами Am2901. Блок управления, генерирующий адрес следующей инструкции состоял из 3 микросхем секвенсора Am2911, вмещающих адреса по 12 бит. Микрокод был наиболее удобным решением для реализации относительно сложного набора инструкций с помощью скромного количества аппаратных средств.

Набор инструкций Lilith действительно был сложным. Это было связано с необходимостью плотности М-кода, опять же для того, чтобы хранить сложные программы в относительно небольшой основной памяти (64К слов). Один из вкладов в плотность М-кода был сделан за счет стека, но другой, более значительный вклад был сделан за счет инструкций загрузки/хранения адреса с различной длиной или операнда (константы). Они выпускались в версиях с адресами длиной 4, 8 и 16. Обширный анализ программ показал, что около 80% инструкций имели адреса меньше 16 (4бит), потому что они ссылались на локальные переменные. Анализ также показал, что наш M-код был намного короче, чем код для популярных в то время микропроцессоров, короче в 1,5 раза по сравнению с NS32000, в 2 раза по сравнению с Motorola 680х0 и в 2,5 раза по сравнению с Intel 8086. В конце концов, это было существенно, поскольку в то время память была все еще дефицитным ресурсом.

Особым преимуществом микропроцессорной обработки было то, что инструкции могли быть разной сложности. Самые короткие и быстрые из них, такие как загрузка и хранение, занимали всего лишь два или три микроцикла (т.е. менее половины микросекунды), в то время как другие, такие как операции отображения для рисования линий и символов, сами по себе были короткие программы, включающие циклы. В результате Lilith продемонстрировала фантастическую производительность при отображении линий и символов на битовом дисплее.

Однако это было достигнуто только с помощью некоторых хитростей. При использовании 1 бита/пиксель (без цвета!) страница дисплея состояла из 808x606 = 489648 пикселей = 30603 слов. При частоте обновления 50 Гц, это оставляло время доступа (менее) 0,65 мс на слово, что монополизировало бы память под дисплей. Хитрость в том, чтобы помимо обычного 16-битного порта, обеспечивался второй порт чтения шириной 64 бита для процессора дисплея. При таком решении дисплей блокировал память только на 25% времени.


===== Второе поколение микропроцессоров =====


Оглядываясь назад, можно поразиться, какие дополнительные усилия и сложности пришлось придумывать потому что существующей технологии было недостаточно. Инженеров компании Xerox постигла та же участь, но сознательно и добровольно. Они знали, что через несколько лет появится гораздо более мощная технология. Если бы им удастся создать продвинутый персональный компьютер (хотя и с большими затратами) который в будущем станет намного дешевле, они могли бы разработать передовые системные технологии и соответствующее программное обеспечение в настоящее время, получив явное преимущество перед конкурентами в дальнейшем. Такая "философия" лежала в основе компьютера Dorado, построенного по технологии ECL в 1984/5. Логика с эмиттерной связью была очень быстрой, но потребляла очень большое количество энергии, что требовало интенсивного охлаждения. Но обстоятельства изменились, и знаменитый Дорадо так и не оправдал надежд разработчиков. Следствием этого стал отход от концепции собственного, персонального компьютера на столе или под столом, разработанной в PARC. Все Дорадо пришлось запихнуть в кондиционируемую комнату они были соединены индивидуальными кабелями по всему зданию (не шиной), как Ethernet к пользователям.
Однако, пока Alto, Dorado и другие разрабатывались в Xerox, остальной мир также двигался вперед. Компании, которые были пионерами 8-битных микро-процессоров, теперь перешли к 16-битным, а вскоре и к 32-битным процессорам на одном чипе. Они шли не по пути более быстрых, высокотоковых полупроводниковых а перешли на технологию маломощных CMOS FET-транзисторов. Так появился в 1978 году процессорный чип 8086 (16 бит) компании Intel (чьи преемники доминируют на рынке до сегодняшнего дня), и 680х0 от Motorola.

Часть Intel страдала от нехватки ресурсов на кристалле, что привело к появлению большого разнообразия регистров специального назначения и трюков адресации. Последнее было связано с ограничением 16-битного слова и требованием 20-битных адресов. Это привело к появлению ужасной схемы сегментов памяти и сегментированной адресации, которая была мучением для разработчиков компиляторов и источником  неэффективностей. Более поздний Motorola 680х0 был намного чище, но часть Intel уже завоевала рынок. 680х0 стал основой знаменитого Apple Macintosh, игрушки с маленьким дисплеем, похожей на тостер. 

===== Modula-2 (1979г) =====

Ближе к 1975 году взникла потребность в обновлении Pascal. Особенно я почувствовал это после знакомства с Mesa. Поэтому, так же как Mesa была языком для Alto, я разработал Modula-2 для Lilith. Основное вдохновение пришло от Mesa. Но Mesa была уже слишком сложной. Я чувствовал, что Modula должна быть ближе к духу Pascal и подходить для преподавания на курсах по проектированию систем. Для этого он должен был предложить средства для низкоуровневого программирования, т.е. для работы с аппаратными объектами и машинно-зависимыми характеристиками. Это понятие было облегчено благодаря новой концепции модулей, уже присутствующей в Mesa. Модули позволяют скрывать локальные переменные и процедуры, запрещая доступ к ним из других модулей, т.е. инкапсулировать их. Системы теперь будут состоять из иерархии модулей, клиентские модули на более высоком уровне импортируют сервисные модули на низких уровнях. Больше не допускалось, чтобы программы описывались одним монолитным куском текста. Разработка командами программистов стала обязательной, и языки должны были это учитывать. 

Заголовок модулей ‒ это  интерфейс, показывающий, какие объекты будут доступны клиентским модулям. Важно то, что эти объекты должны были проверяться на согласованность типов, так же как это делается для локальных сущностей.  Реализация этих новых требований оказалась сложной задачей. Простым решением было "включить" исходный текст модуля B в исходный текст модуля A, если A должен быть скомпилирован. Но это считалось не только неэффективным, но и  небезопасным, поскольку B мог подвергнуться изменениям с момента разработки A. Тем не менее, коммерческие системы использовали это недостаточное решение. Наше решение заключалось в том, чтобы позволить компилятору генерировать не только файл кода, но и файл символов, содержащий скомпилированные спецификации экспортируемых сущностей. 
Однако Modula превратилась в язык значительного размера и сложности.  Это оказалось неизбежным путем, который должны были пройти языки и системы, чтобы соответствовать растущему числу пользователей. Мир был обречен на усложнение. 
Другой язык, возникший на основе C, постигла та же участь: C++. Его зловещее название уже намекает на монстра огромных размеров. Он проходил через различные версии  с течением времени, каждый раз включая новые возможности, и каждый раз становясь больше тяжелее и сложнее для освоения. Однако, как и C, он получил широкое распространение  и стал фаворитом среди промышленного программного обеспечения. Вместо того чтобы быть лидерами, образовательные учреждения слепо следовали за ним. Вместе с этим появились огромные программные "библиотеки", превратив программирование в искусство выбора подходящих пакетов, которые должны быть объединены в целое. Оправданием для больших библиотек стало то, что программисты больше не должны стоять на своих ногах, а стоять на плечах других, куском монолитного текста.

===== Сокращенный набор инструкций RISC (1985г) =====

В сфере аппаратного обеспечения мир также становился все сложнее. Полупроводниковая технология достигла огромного прогресса. Стало возможным размещать несколько миллионов транзисторов на одном чипе. Уменьшение размеров привело к уменьшению времени распространения сигнала и к более высокой скорости. Дизайнеры соблазнялись использовать армии доступных транзисторов и включить функции, которые раньше откладывались на потом. Прямым следствием этого стало увеличение количества регистров на кристалле, виртуальная адресация, блоков управления памятью и блоков с плавающей запятой. Помимо этого, память стала больше и быстрее, примерно до 1 МБ на кристалл в 1985 году. Еще одним  способом использования транзисторов был сложный набор инструкций, включающий строковые инструкции, инструкции для десятичных и вычислений с плавающей запятой. И еще один способ ‒ это выбор режимов адресации. Наиболее продвинутыми в этом направлении была серия NS 32000 компании National Semiconductor. Они не только предлагали набор адресов длиной 25 (аналогично Lilith), но и большой набор режимов, включая один для связывания модулей. Кроме того, это был первый процессор с 32-битными трактами передачи данных. Но по сравнению с традиционной конструкцией с дискретными компонентами, компьютеры на базе этих чипов (также Intel 80286 и Motorola 680х0), считались медленными. Вопрос  какой технологии будет принадлежать будущее, оставался открытым.

Решение было принято с появлением Mosfet: полевого транзистора на основе оксида металла - полупроводника. Затвор становится проводящим под действием электронов. В транзисторах с биполярным переходом они вводятся током, подаваемым в слой затвора между истоком и стоком, в полевых транзисторах - путем подачи напряжения на слой, изолированный от канала исток - сток. т.е. за счет эффекта поля. Сегодня (2015г) практически все транзисторы являются FET, и эра биполярных транзисторов подошла к концу. Со стороны архитектуры произошла полная революция. Тенденция к все большему усложнению была остановлена. Новые RISC превосходили по простоте.  Как правило, процессор теперь состоял из набора регистров (32 бита), а набор инструкций был сведен к простым логическим инструкциям и инструкциям сложения/вычитания. Даже умножение и деление были исключены. Обоснование такого отхода от традиций в том, что каждая инструкция  требует один тактовый цикл и очень быстра. Плотность кода стала иметь ничтожное значение, поскольку память была доступна в больших объемах. Так как, каждая инструкция занимала только один такт, стало возможным одновременное выполнение нескольких инструкций, каждая из которых состоит из 4 - 5 шагов: 

  - выборка 
  - вычисление адреса (сложение)
  - выполнение
  - сохранение результата.


Эта концепция называлась "конвейеризация", и существенно повышала скорость.
Эта схема была предложена в научных кругах (Дж. Хеннесси в Стэнфорде и Д. Паттерсон в Беркли) в 1985 году. В результате появились компании-стартапы: MIPS и SPARC. В Англии развивались аналогичные разработки: Acorn в Кембридже, что привело к созданию архитектуры ARM. Выжила именно архитектура ARM. Однако со временем появлялись новые версии и каждая обладала новыми возможностями такими, какие позволяла миниатюризация транзисторов. Удивительно, но эта система смогла сохранить свой лейбл даже после замены набора инструкций на 16-битные "пальчиковые" инструкции. 

===== Новая парадигма вычислений (1985г) =====

Когда появились микрокомпьютеры (1975г) они все еще использовали пакетную обработку. Программы запускались одна за другой. Новая парадигма была впервые применена в лаборатории Xerox Palo Alto Reserach Laboratory. Дисплеи высокого разрешения с побитовым отображением требовали более гибкого использования экрана.  Появились так называемые "вьюверы" (средства просмотра), позже ‒ "окна", и стало очевидно, что к каждому вьюверу должен быть прикреплен отдельный процесс. Компьютер теперь позволял пользователю переключаться с одного вьювера (процесса) на другой. Наличие мыши облегчило эту новую парадигму: Щелчок мыши заменял ввод целой команды. 
Ввод текста как таковой стал менее важным. Было признано ‒ то что набирается, уже где-то было набрано. Таким образом, указание на этот текст делало повторный набор текста излишним. Можно утверждать, что концепция вьювера революционизировала использование компьютера. Это было прямым следствием новой парадигмы объектно-ориентированного программирования: процедуры (процессы) могут быть присоединены к структурам данных. 
Эта парадигма уже была представлена в языке Simula (1965г), и позднее в языке Smalltalk (1976г), а концепция вьювера является ее самым известным применением. Она  была усовершенствована в системе Cedar компании Xerox и перенята системой Oberon. Понятие текстовой единицы программы (модуль) стало четко отделено от единицы выполнения программы (процедуры), что значительно повысило ясность концепции. 

Весь этот прогресс в конечном итоге стал возможен только благодаря огромному увеличению объема памяти. После выполнения, процедура не удалялась из памяти, как это делалось при пакетной обработке, она сохранялась в памяти, чтобы иметь быстрый доступ к ней при последующем вызове. 

===== Оберон ─ результат упрощения =====

Это подводит нас к 1990-м годам. Я чувствовал, что продолжающееся усложнение достигло тревожного состояния. Неотложная остановка этой раковой опухоли стала все более необходима, поскольку системы достигли такого размера и веса, под которым они могут рухнуть, поскольку никто не мог полностью понять этих монстров, и скорее приравнивали сложное к мощному. Уменьшение сложности было руководящим принципом, лежащим в основе разработки языка Oberon. Очевидно, что Modula-2 была слишком сложной и, следовательно трудоемкой для реализации. Кроме того, она еще не достигла некой компьютерной независимости, что является необходимым условием для языка, претендующего на "более высокий уровень". Oberon стал значительным шагом на пути к этой трудной, но крайне важной и уникальной цели. 
Ключом к ее достижению стало строгое ограничение основных функций и отказ от всех "колокольчиков и свистелок", подлинное стремление к простоте. Но, несмотря на экономность, Oberon должен был стать мощным языком общего назначения в традициях Pascal и Modula. В результате получился удивительно маленький  язык (который в 2007 году был снова пересмотрен, чтобы стать еще меньше). 

Однако это руководство было не просто эзотерической идеей. Это была необходимость. Было решено реализовать не только компилятор, но и целую, операционную систему по образу Cedar, существовавшей в Xerox PARC в Пало-Альто. Oberon должен был обеспечивать полную интерактивность с помощью дисплея высокого разрешения с битовым отображением и мыши. 
Компилятор и операционная система были  реализованы  только двумя людьми  (автором этих строк и Ю. Гуткнехтом) в их свободное время в течение почти двух лет. Естественно, мы были вынуждены сосредоточиться на том, что считалось необходимым. Успешная реализация всей системы на собственном языке доказала, что оставшихся функций было достаточно, и что на самом деле простой язык больше подходит для сложной системы, чем тот, который является частью проблемы, а не ее решения. Тем не менее, в Oberon была добавлена одна функция, которой не было в Modula: Type extension (Расширение типов). Линия Алгол - Модула представляет собой статическую типизацию. Тип константы, переменной или функции виден только из текста программы, без ее выполнения. Поэтому несоответствия типов всегда могут быть проверены компилятором. Эта жесткая схема должна быть немного смягчена. Благодаря расширению типов стало возможным объявлять иерархии типов и конструировать во время выполнения структуры данных с элементами различных, хотя и связанных типов. Это является ключом объектно-ориентированных программ; Oberon содержит все ингредиенты для объектно-ориентированного программирования, но не более того. Проверка типов во время выполнения может быть реализована очень эффективно.

Объектно-ориентированное направление стало популярной инновацией в сфере программного обеспечения. Прошло много времени с тех пор, как у истоков ООП стоял язык Simula (Dahl & Nygaard) в 1967 году. Он стал более известен в США благодаря языкам Smalltalk (Kay) в 1976 году (реализованный на Alto), и Object-Pascal (Tesler, 1980).  Smalltalk пошел до конца: все должно было быть объектом. Вы не можете сложить два числа x и y. Правильный способ рассмотрения этой проблемы - считать x объектом, который содержит метод сложения y. Гений или извращение? 

В 1995 году компания Sun Microsystems представила свой язык Java, спустя целых 6 лет после Oberon. Он вобрал в себя большую часть "философии" Оберона, но, увы, выбрал стиль и синтаксис языка Си. Примерно в 2000 году Microsoft выпустила свой язык C# в качестве сильного конкурента Java, а Google последовал за ним в 2007 году со своим языком Go, еще более сильно следуя Оберону 18-летней давности. Суть этих языков, которые все они получили широкое распространение благодаря мощной промышленной поддержке, является их размер и сложность. Стремление предоставить "все для всех" взяло верх и позволило им вырасти в сложные тела, которыми трудно овладеть.  В области аппаратного обеспечения развитие было аналогичным. Множество процессорных архитектуры предыдущих десятилетий исчезло. Преобладают лишь несколько архитектур, в основном это архитектуры Intel и ARM. Инженеров подталкивают к тому, чтобы использовать изобилие доступных транзисторов. Один из способов ‒ обеспечить несколько, или много, процессоров на одном кристалле, другой ‒ включать большую кэш-память, а еще другой ‒для обеспечения интерфейсов с внешними устройствами, например, с сетями или цифро-аналоговыми и аналого-цифровыми преобразователями. Здесь сложность также растет без границ. Все труднее и труднее распознать исходное ядро и определить основные принципы среди огромного количества гаджетов. 

Невероятный успех компьютеров в основном объясняется достижениями в области производства полупроводников. Теперь доступны процессоры с огромной мощностью и память с большой емкостью. Как и в любой другой сфере деятельности, изобилие при низкой цене неизменно приводит к расточительному дизайну. Это влечет за собой не только отходы, но и некачественные продукты. Программная инженерия сегодня - это эльдорадо расточительства. 

Дейкстра однажды заявил, что главная обязанность инженера-программиста ‒ бороться с (доморощенной) сложностью, как с дьяволом, каждую минуту. То же самое теперь верно и для инженера по аппаратному обеспечению.
Инструменты пользователя

Инструменты сайта

Инструменты страницы
