Языки программирования

За последние четыре десятилетия программный инструментарий коренным образом изменил способы проектирования и создания промышленных изделий – автомобилей и лекарств, газет, зданий, мостов, список можно продолжать. Этот инструментарий получил специальное имя – CAD (Computer Aids Design), CAM (Computer Aids Manufacturing), системы автоматизированного проектирования и автоматизированного производства.

ПО – это тоже промышленное изделие, и его производство требует проектирования. Опровергая старую поговорку "Сапожник ходит без сапог", программисты позаботились о создании инструментария, обеспечивающего их потребности, начиная от простых текстовых редакторов до интегрированных сред разработки, подобных EiffelStudio или VisualStudio от Microsoft.

Такой инструментарий является целостной частью профессиональной культуры, которой должен обладать разработчик ПО. Эта лекция предоставляет обзор наиболее важных концепций. Мы начнем с концептуальных средств – языков программирования, и продолжим системным программным инструментарием, помогающим в построении пользовательского ПО.

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

Программный инструментарий предлагает широкий набор возможностей, начиная со средств, непосредственно связанных с языком программирования: компилятор и интерпретатор, которые можно рассматривать как близнецов-братьев. Мы поговорим о средствах подготовки программ – текстовых редакторах. Поговорим и о более мощном средстве автоматизированного проектирования ПО – инструментарии CASE (Computer Aided Software Engineering).

Отладчики, статические анализаторы и средства тестирования позволяют нам оценить и улучшить надежность программ. Средства управления конфигурацией позволяют нам сохранять историю развития компонентов ПО. Браузеры и средства документирования помогают понимать работу ПО на разных уровнях абстракции, что позволяет справиться с его сложностью. Метрический инструментарий дает нам количественные оценки качества разработки. Закончим это перечисление упоминанием IDE – интегрированной среды разработки, включающей, как правило, большинство из отмеченных средств и предоставляющей разработчику единые рамки для его многогранной работы. В последнем разделе лекции будет дана краткая характеристика EiffelStudio, в частности, описан ее подход к компиляции – Технология Тающего Льда (Melting Ice Technology).

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

3.1. Стили языков программирования

Языки программирования играют центральную роль в разработке ПО. Ядро этого курса использует язык Eiffel, который хорош тем, что позволяет в первую очередь сосредоточиться на концепциях программирования, а не на специфике конкретного языка. В приложениях приведена специфика четырех практически наиболее важных для практики языков: Java, C#, C++ и C. Сейчас же мы рассмотрим общие критерии, позволяющие классифицировать языки программирования, познакомимся с семейством ОО-языков и с другим популярным семейством, обладающим своими исключительными свойствами.

Критерии классификации

Языки программирования могут классифицироваться по разным критериям. Вот несколько наиболее важных.

Область применения. Некоторые языки являются языками общецелевого использования. Другие ориентированы на определенную область, например, разработку Web-сайтов или разработку систем реального времени. Языки второй группы относят к языкам DSL (domain-specific languages), ПОЯ – проблемно-ориентированным языкам. Классификация языка со временем может быть подвергнута пересмотру, так как успешные языки в процессе развития преодолевают первоначальные замыслы. Примером является первый язык программирования Фортран, создававшийся как язык численного программирования (вычисления формул), а ставший общецелевым языком программирования в научных вычислениях. Другим примером служит язык Java, который первоначально создавался как язык для разработки ПО различных бытовых приборов, затем, с появлением Интернета, был переориентирован на создание апплетов – программ, загружаемых через Интернет, теперь же язык Java является ОО-языком общецелевого использования.

Область действия программы. Некоторые языки предназначены для создания масштабируемых приложений (большой размер кода, много разработчиков, разработка и сопровождение ведется в течение многих лет). У других – цели более простые: небольшие разработки, проведение различных экспериментов, проверка гипотез. Так называемые Script (скриптовые) языки обычно относят ко второму типу. Конечно, нет гарантии, что первоначально небольшая программа в ходе эволюции не превратится в многофункциональную, долго живущую, большую программу. Как следствие, успешные языки второй категории в конечном итоге часто применяются к большим разработкам. Примером может служить офисное программирование на языке, встроенном в систему Microsoft Office.

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

Уровень абстракции. Некоторые языки опираются непосредственно на ниже лежащий машинный уровень. Другие предпочитают использовать абстрактную модель вычислений.

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

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

Архитектурный стиль. Он определяет то, как происходит декомпозиция системы на модули. Два главных подхода характерны для программирования – строить модули на основе функций или на основе типов объектов. Языки соответствующих двух стилей называются процедурными ("функциональные языки" означает нечто другое, о чем позже пойдет речь) и объектно-ориентированными языками.

Для конкретного языка возможна почти любая комбинация этих характеристик. Стиль программ этого курса, иллюстрируемый программами на Eiffel, характерен и для таких языков, как C# и Java. Он предполагает:

общецелевое использование (специализация допускается благодаря библиотекам), пригодность для больших разработок;

возможность статического контроля текста на этапе компиляции, высокий уровень абстракции (с возможностью учета нижнего машинного уровня опять-таки с помощью библиотек);

учет жизненного цикла (в частности, это верно для языка Eiffel, который повседневно используется для спецификации и проектирования);

императивность и объектную ориентированность языка.

Другим примером является язык С, императивный, но не объектно-ориентированный, с довольно низким уровнем абстракции, но позволяющий управление выполнением на почти машинном уровне. Язык С++ добавляет объектный слой к языку С.

Продолжая обсуждение языков программирования, рассмотрим:

введение в стиль языков программирования, относящихся к "дескриптивной" категории, – языков функционального программирования, радикально отличающихся от доминирующей практики сегодняшнего дня;

некоторые основы ОО-языков.

Функциональное программирование и функциональные языки

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

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

Математический подход – чисто дескриптивный: здесь ничего не меняется, математика говорит о значениях и отношениях между ними.

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

Будем использовать следующую терминологию.

Определения: императивный, аппликативный

Стиль программирования, основанный на изменении состояния, называется императивным. Синоним для противоположного стиля – аппликативный.

Большинство языков программирования, включая Eiffel, поддерживают императивный стиль. Для языка Eiffel характерно строгое разграничение команд и запросов – запросы здесь относятся к аппликативному стилю, не допускающему побочных эффектов изменения состояния. Функциональные языки в основе своей аппликативны. В основе – поскольку многие из них поддерживают несколько императивных отклонений для выполнения операций, императивных по своей природе, таких как операции ввода-вывода, операции с базами данных.

Первым функциональным языком, включающим и некоторые императивные свойства, был язык Лисп (Lisp – List Processing), разработанный Джоном Маккарти и представленный в 1959 году.

(рис 3.1) Джон Маккарти

Центральной концепцией языка является список, записываемый в круглых скобках:

(A B C)
        

Заметьте, в Лиспе термин "список" используется в особом смысле, который отличается от списковой структуры, изучаемой в предыдущих лекциях. Списки Лиспа фактически близки к бинарным деревьям – структуре данных, которую мы будем изучать в отдельной лекции.

Списки являются структурой данных (фактически, единственной структурой данных в Лиспе, достаточно общей для покрытия широкого разнообразия приложений). Более того, они также задают структуру программы. Если A обозначает функцию, то в вышеприведенном примере список обозначает применение этой функции к списку аргументов, заданному оставшейся частью списка, – в более привычной нотации этот список записывается в виде A(B, C). Мощь, простота и элегантность идей вдохновила многих людей и привела к тому, что большинство ранних работ по ИИ (искусственному интеллекту) основывались на Лиспе. Язык и до сей поры продолжает развиваться и активно использоваться, имея многочисленных потомков, в частности, язык Scheme, сохранивший основные концепции.

Даже не детализируя остальные концепции языка, заметим, что в самой базисной концепции заложена возможность использования функционалов – функций высшего порядка, то есть таких функций, аргументами которых являются функции. Рассмотрим список:

((F A B)(G C) D)
        

Это список из трех элементов, первый из которых сам является списком с тремя элементами, второй – список из двух элементов. Можно рассматривать F как функцию от двух аргументов, возвращающую в качестве результата функцию от двух аргументов. Обозначим через H функцию, задающую результат применения функции F к ее аргументам, а через E – результат применения функции G к аргументу C; тогда представленное выражение списка в целом (H E D) может означать применение функции H к ее аргументам E и D. Это общий и замечательно мощный механизм.

В последующих лекциях мы познакомимся с механизмом агентов Eiffel, позволяющим достичь того же эффекта в рамках ОО-подхода; в его основе – теория лямбда-исчисления. Эта же теория лежит и в основе Лиспа и других функциональных языков.

Рис. 3.2. Симон Джонс и Фил Вадлер

Для более близкого знакомства со стилем функционального программирования позвольте перейти от Лиспа к более современному и популярному языку Haskell. Основной вклад в разработку этого языка внесли Симон Пейтон Джонс и Фил Вадлер.

Ограничимся только одним примером, иллюстрирующим идеи функционального программирования, а также представляющим прекрасную подготовку для предстоящего изучения рекурсии.

Вспомним алгоритм обращения списковой структуры. Он включает манипуляции с указателем позиции списка. А нет ли способа получения результата, – ведь само понятие обращенного списка достаточно просто, – без обращения к таким деталям, как указатели позиции? Функциональное программирование такую возможность предоставляет, если вы согласны не обращать внимания на проблемы производительности и возлагаете их решение на "умный" компилятор. Список в Haskell записывается в квадратных скобках. Следующее определение задает функцию, обращающую список:

reverse:: [T] –> [T]
reversed [ ]                     = [ ]                              [1]
        

reversed (first:remainder) = reversed remainder ++ [first]          [2]
        

Это все, что нужно написать. Первая строка является описанием типа и говорит, что reverse – это функция, на вход которой подается список элементов типа T и которая возвращает в качестве результата список элементов того же типа. Определение этой функции дается в последующих двух строчках, представляющих разбор случаев.

Первая строчка (случай [1] задает нерекурсивную ветвь определения), устанавливает, что обращение пустого списка является пустым списком.

Вторая строчка (случай [2] задает рекурсивную часть определения) рассматривает обращение непустого списка.

Непустой список может быть всегда представлен в виде first : remainder, нотации, которая представляет список состоящим из непустого первого элемента – first, и остатка списка – remainder, который является списком, возможно, пустым. При таком представлении обращение списка может быть задано конкатенацией обращения остатка remainder и головы списка – first. Для обращения остатка рекурсивно может использоваться функция reversed. Заметьте, в Haskell для конкатенации применяется знак операции ++, при вызове функции не используются круглые скобки и вызов функции связывает сильнее (имеет больший приоритет, чем операция конкатенации). В более привычной математической нотации правая часть в [2] могла бы быть записана в виде: (reversed(remainder))++ [first].

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

Это определение аппликативно, здесь нет ссылок на состояния и их изменения, не вводятся переменные, которым программа может присваивать новые значения.

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

Почему же мы все не переключились до сих пор на функциональное программирование? Вопрос для полемики – горячие сторонники функционального программирования считают, что мир должен переключиться, но следует отметить три важные проблемы.

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

Масштабируемость. Для структурирования больших систем понятие класса более эффективно, чем понятие функции. Следует заметить, что многие функциональные языки встраивают в язык ОО-конструкции.

Отсутствие понятия состояния. Несмотря на то, что чисто аппликативные языки могут существенно упрощать понятие алгоритма, работая на возможно сложных структурах данных, некоторые аспекты вычислений фундаментально требуют введения понятия состояния. Уже упоминались операции по вводу и выводу данных, можно упомянуть и системы реального времени. Функциональные языки, Haskell, в частности, добавляют императивные аспекты программирования, но они не так просты, как базисная функциональная модель.

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

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

ОО-языки

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

Рис. 3.3. Кристин Нигард и Улле Дал

Достаточно просто проследить за местом, временем и создателями этой технологии. Место – это город Осло в Норвегии, время – начало и середина 60-х годов прошлого столетия, создатели – Уле-Йохан Дал из университета Осло и Кристин Нигард из Норвежского вычислительного центра.

Совместно они спроектировали язык для моделирования дискретных событий. Первая версия языка – Симула 1 – предназначалась для моделирования на компьютере производственных процессов, рассматриваемых как последовательность событий. В 1967 году в журнале Communications of the ACM появилась их статья, посвященная описанию уже общецелевого языка программирования, где были введены основные идеи ОО-программирования. Прошло уже более сорока лет, но можно только удивляться, как много было предусмотрено в этой работе: классы, объекты, динамическое распределение памяти и сборка мусора, наследование (только одиночное), динамическое связывание и полиморфизм.

Странным образом эта работа настолько опередила время, что академическое сообщество оказалось незаинтересованным. Только несколько лет спустя появилась теория, поясняющая объектную технологию. Работа Парнаса по скрытию информации появилась в 1972 году. Абстрактные типы данных (АТД) были представлены в короткой статье в 1974 году Барбарой Лисков и Стефаном Зиллесом. Прочный математический фундамент АТД получили в диссертации Джона Гуттага в 1975 году.

(рис 3.4) Барбара Лисков с Дональдом Кнутом

Первоначально, как было отмечено, язык Симула появился как язык моделирования. С этих пор одна из центральных идей ОО-подхода состоит в том, что программа является средством моделирования. Нигард в своих выступлениях часто использовал лозунг "Запрограммировать – значит понять" и гордился тем, что первый отчет о языке Симула назывался "Язык для Программирования и Моделирования". Моделирование дискретных событий с упором на описание внешних процессов представляло идеальную целевую область для разработки такой точки зрения. Эволюция от специализированной Симулы 1 до общецелевого языка Симула 67 показала общую применимость предлагаемых идей. ОО-концепции успешны, поскольку они эффективно поддерживают моделирование процессов в самых различных проблемных областях – банковских системах, обработке изображений, подготовке текстовых документов. Мы описываем такие системы, вводя соответствующие типы данных (ACCOUNT, IMAGE, PARAGRAPH), организуя иерархию наследования (INTERNAL_ACCOUNT как специальный случай ACCOUNT), применяя скрытие информации, чтобы быть уверенными, что каждый такой тип можно разрабатывать независимо. Введение контрактов позволяет задать спецификацию таких типов объектов. Эти идеи, за исключением последней, были уже представлены в Симуле – ее создатели ясно осознавали потенциал языка.

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

Но идеи со временем пробивают себе дорогу. В университете Юта – центре графических исследований – Алан Кей в своей диссертации объединил идеи Симулы и Лиспа. Он был приглашен в Исследовательский центр фирмы Xerox (PARC), расположенный в Пало-Альто, в Калифорнии – месте, где рождены многие замечательные новинки, аппаратные и программные, Там он создал первую версию языка Smalltalk и его программного окружения. Двумя другими ключевыми членами группы разработчиков были Адель Голдберг и Дан Инголс.

Рис. 3.5. Алан Кей, Адель Голдберг

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

С появлением успешных версий Smalltalk 76 и Smalltalk 80 интерес к языку возрастал, но поклонники языка, подобно поклонникам Симулы, составляли скорее клуб, чем широкий поток в океане программирования. В 1981 году журнал Byte – флагман быстро растущего сообщества энтузиастов персональных компьютеров – решил опубликовать специальный номер, посвященный исключительно Smalltalk, хотя он не был доступен на компьютерах большинства читателей. В Августе 1981 года такой номер (теперь библиографическая редкость) вышел под редакцией Адель Голдберг, открыв широкую дорогу новому взлету ОО-программирования. Когда в 1986 году ACM организовал конференцию OOPSLA (Object-Oriented Programming, Systems, Languages, Applications, с тех пор ежегодную), ожидалось, что число ее участников будет представлять сотню человек, а оказалось, что оно перевалило за тысячу. Стали появляться новые языки. Бред Кокс использовал Smalltalk в ITT – мощной телекоммуникационной компании; Бьерн Страуструп из ATT, рассматривавший Симулу в своей диссертации, решил расширить наиболее модный тогда язык С новыми идеями – так появились языки Objective-C и C++. Появление языка Eiffel также относится к этому периоду.

В течение нескольких лет эти языки преодолели первоначальное сопротивление индустрии, в частности, доказав эффективность реализации, и стали вначале важными игроками, а затем заняли доминирующие позиции. Позже, в 1995 году, появился язык Java, а еще через четыре года – и язык C#.

Со времен первой конференции OOPSLA критики предсказывают конец "эры объектов". Но никаких признаков такого исхода никогда не наблюдалось. Объекты продолжают процветать, как говорил один из героев – "в городе нет другой игры".

3.2. Компиляция против интерпретации

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

Целью компиляции является реализация возможности выполнения реальным компьютером кода, написанного для абстрактной машины. Компиляция, однако, – лишь одна из двух базисных технологий, применяемых для достижения нашей цели.

Базисные схемы

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

(рис 3.6) Компиляция и интерпретация (без ввода данных)

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

Интерпретатор должен быть способен определить эффект выполнения каждой конструкции языка программирования. Как пример того, как интерпретатор выполняет свою задачу, рассмотрим интерпретацию присваивания x: = x +1. Интерпретатор должен хранить таблицу всех используемых переменных и связанных с ними значений. Он вычисляет новое значение x, добавляя 1 к старому значению, хранящемуся в таблице, а затем выполняет присваивание, заменяя старое значение x значением вычисленного выражения.

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

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

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

На следующем рисунке процессы компиляции и интерпретации дополнены вводом данных:

(рис 3.7) Компиляция и интерпретация

Рисунок демонстрирует еще одну разницу между компилятором и интерпретатором. У интерпретатора два источника ввода – исходная программа и входные данные; а компилятору подается только программа. В последующем обсуждении этому различию придадим математическую форму.

Компилировать или интерпретировать? Эта проблема – предмет широко рассмотрения в компьютерных науках. Что лучше: непосредственно обрабатывать исходную информацию в том виде, как она есть, или предварительно привести ее к более удобной форме? Этот вопрос стоит не только при обработке программ, мы будем сталкиваться с ним и при изучении алгоритмов.

У компиляторов и интерпретаторов имеются свои достоинства. Возможны различные критерии. По производительности – времени выполнения программы – компиляторы побеждают.

Выход компилятора является машинным кодом, непосредственно выполняемым компьютером. Дополнительно при создании этого кода компилятор мог применять оптимизацию, улучшающую эффективность кода.

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

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

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

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

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

Комбинирование компиляции и интерпретации

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

Заметим, что 100% схема интерпретации имеет мало смысла: каждый раз, когда интерпретатор выполнял очередной оператор, например, оператор цикла, он должен был бы возвращаться многократно к фактической последовательности символов и осуществлять ее разбор. Любое реалистическое решение не могло бы согласиться с такой неразумной тратой ресурсов. Так что фактически интерпретатор также начинает с преобразования входа в форму, приемлемую для интерпретации, например, строя абстрактное синтаксическое дерево. В ходе этого процесса, как отмечалось, возможен контроль проверки типов. Так что даже тогда, когда можно прочесть, что используется интерпретатор языка, частичная компиляция подразумевается.

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

(рис 3.8) Компиляция плюс интерпретация

Смешанная стратегия предполагает, что компилятор создает код на промежуточном языке, понимаемом некоторой виртуальной машиной – VM на рисунке. Такой подход объединяет преимущества компиляции и интерпретации. Благодаря тщательно спроектированной виртуальной машине возможно получить:

переносимость, так как VM-код не зависит от специфики физических процессоров;

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

Виртуальные машины, байт-код и JIT (Just In Time) компиляторы

Реализация современных языков – Java, C#, других языков .Net – основана на смешанном решении. Промежуточный код для Java называется байт-кодом. В термине отражается тот факт, что виртуальная машина использует компактные команды, подобные командам фактического процессора, где каждая команда содержит код команды – типично задаваемый одним байтом, – после которого следует 0, 1 или 2 аргумента команды.

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

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

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

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

Для улучшения эффективности времени выполнения байт-кода применяются JIT (Just In Time) компиляторы, называемые джитерами, – осуществляющие компиляцию по требованию. Основная идея состоит в том, что машинный код для некоторого модуля создается "на лету", в тот момент, когда он первый раз вызывается на выполнение (не следует путать любителя джаза –jitterbug, с ошибками такого компилятора – jitter bug). Внесем соответствующие дополнения в предыдущий рисунок, который теперь выглядит так:

(рис 3.9) Компиляция плюс интерпретация и джитинг

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

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

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

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

Стратегия компиляции в EiffelStudio также включает байт-код, но, как мы увидим, она использует различные способы комбинирования интерпретации и компиляции.

3.3. Основы компиляции

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

Задачи компилятора

Компиляторы могут существенно различаться в деталях, но для всех вариантов есть общие задачи. Рассмотрим их примерно в том порядке, в котором компилятор должен применять их при обработке исходного текста.

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

Синтаксический анализ воссоздает синтаксическую структуру программы.

Проверка правильности включает контроль типов и другие согласованные проверки. Eiffel, например, имеет примерно 90 "правил контроля правильности", таких как:

в операторах присваивания и при передаче аргументов тип источника должен соответствовать типу цели;

класс B не может назвать класс A своим родителем, если родителем B назван предок A. Это правило защищает от возникновения циклов при наследовании.

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

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

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

распределение регистров – оптимизация периода выполнения. Математически $$3\times b+a$$ имеет то же значение, что и $$a+3\times b$$, но одна из этих форм может выполняться быстрее другой из-за более эффективного распределения регистров. Оптимизация приводит к тому, что генератор кода выберет быстрейший вариант;

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

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

Фундаментальные структуры данных

Задачи лексического и синтаксического анализа взаимосвязаны: "парсер" вызывает "лексер" (сокращения для синтаксического и лексического анализатора) для получения очередной лексемы. Главным результатом работы парсера является АСТ (абстрактное синтаксическое дерево), которое задает структуру программы, очищенную от чисто текстуальных свойств, таких как ключевые слова. Другой фундаментальной структурой данных является таблица идентификаторов, в которой записаны имена, используемые в программе, – имена классов, методов, локальных переменных, других сущностей, – и свойства, связанные с каждым из этих имен. Например, для локальной переменной хранится тип этой переменной, метод, которому она принадлежит. Другие свойства, полезные для семантического анализа и оптимизации, могут включать списки операторов, использующих значение этой переменной, и списки операторов, модифицирующих ее значение. Хэш-таблицы, изучаемые в этой лекции, хорошо подходят для реализации таблицы идентификаторов.

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

Проходы

Традиционное описание процесса компиляции включает понятие "прохода". На каждом проходе компилятор просматривает всю программу, выполняя специфические операции на ее компонентах. Важность этого понятия обусловлена еще и историей. На каждом проходе программа имеет свое представление – вначале это исходный текст, затем АСТ и так далее. В старые почтенные времена такие представления не помещались в оперативной памяти изза ее ограниченных размеров и хранились во внешней памяти в виде отдельных файлов на диске, а еще раньше – на магнитных лентах. Компиляция состояла из последовательности проходов, каждый из которых обрабатывал ранее полученный файл и создавал новый. Естественное требование сокращения времени компиляции диктовало необходимость минимизации числа проходов.

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

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

Компилятор как инструмент верификации

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

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

Загрузка и связывание

Программам в машинном коде необходимы адреса памяти. Присваивание x: = expr будет помещать значение выражения expr по адресу памяти, связанному с x. В условном операторе if c then a … управление будет передаваться в зависимости от вычисленного значения условия c по различным адресам, связанным с соответствующими участками кода. Вызов метода r(…) или x.r(…) приведет к передаче управления по адресу соответствующего кода, а затем вернет управление в точку, следующую за вызовом метода.

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

Когда обрабатываются элементы программы, принадлежащие некоторому модулю, например, методы класса, компилятор управляет только относительными адресами в области памяти, отведенной модулю. Например, когда он обрабатывает неквалифицированный вызов r(…), появляющийся в методе того же класса C, что и r, компилятору известно смещение кода для r внутри области, отведенной для C. Компилятору неизвестны соответствующие абсолютные адреса, которые могут быть установлены только в момент загрузки и могут меняться от одного сеанса выполнения к другому.

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

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

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

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

Время выполнения

Сегодняшние амбициозные языки программирования требуют не только изощренного инструментария в период компиляции (включая изощренный компилятор), но также серьезной поддержки на этапе выполнения. Когда программа выполняется, ей необходимо динамическое распределение памяти (для таких операторов, как конструкторы класса create x), нужна автоматическая сборка мусора, которая освобождает память от объектов, ставших недоступными программе, требуется обработка исключений и поддержка ввода и вывода. Аппаратура обычно напрямую не поддерживает эти механизмы. Эффективное управление памятью, в частности, основано на сложных алгоритмах и структурах данных.

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

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

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

Для современных ОО-языков исполняемая среда необходима в той же степени, что и компилятор.

Отладчики и инструментарий выполнения

После того, как программа скомпилирована и скомпонована, возникает естественное желание запустить ее на выполнение. Окончательная версия программы типично является исполняемым exe-файлом. Но до завершения разработки необходимо контролировать выполнение, чтобы иметь возможность, например, в случае возникновения ошибки, исследовать контекст выполнения – анализировать содержимое объектов в точке ее проявления. Для этого необходим отладчик (debugger). Роль отладчика не только в том, чтобы отладить программу, разыскивая в ней ошибки (bug). Современные отладчики представляют инструментарий, предназначенный, как теперь модно говорить, для мониторинга за процессом выполнения программы.

Типичный отладчик включает такие средства, как задание точек останова (прерывания) в исходном тексте, запуск, прерывание, продолжение и завершение выполнения. Когда выполнение останавливается, что может быть вызвано одной из трех причин: достижением точки останова, возникновением ошибки или прерыванием, инициированным пользователем, – отладчик позволит исследовать код, приведший к текущему состоянию, проанализировать структуру объектов, видя их содержимое, динамически вычислять выражения, выполнять различные другие проверки программы и ее данных. В некоторых случаях отладчики, такие как отладчик EiffelStudio, позволяют выполнить откат по программе, чтобы повторно в пошаговом режиме проследить и понять причину, приведшую к такому состоянию (появлению ошибки). Следующий рисунок показывает типичное состояние отладчика EiffelStudio.

Наличие хороших отладчиков не дает нам права на "плохое" программирование (не надейтесь, что любая ошибка будет обнаружена в процессе отладки). Контроль выполнения может помочь только в некоторых случаях из несметного числа возможных сеансов выполнения.

(рис 3.10) Сеанс отладки в EiffelStudio

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

3.4. Верификация и проверка правильности

Отладчики типично поддерживают проверку программы, выполняемую самими разработчиками. Перед тем, как работа над программой будет считаться законченной и она может быть передана пользователям, программа обычно подвергается систематическому процессу верификации и проверки правильности (verification and validation – V V), который выполняется специальными людьми – тестировщиками.

Под верификацией понимают проверку внутренней согласованности, под проверкой правильности – проверку на соответствие внешним спецификациям. В лекции, посвященной инженерии программ, процессу V V будет уделено больше внимания. На данный момент просто стоит понимать, что соответствующие средства относятся к двум разным категориям.

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

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