Текст книги "Редкая профессия"
Автор книги: Евгений Зуев
сообщить о нарушении
Текущая страница: 2 (всего у книги 5 страниц) [доступный отрывок для чтения: 2 страниц]
Первые радости
Начнем с синтаксиса (самого, казалось бы, простого аспекта, однако борьбой с ним завершаются попытки очень многих). Несколько первых впечатлений. Во-первых, язык просто очень большой. Это означает, что синтаксические таблицы – составленные вручную или построенные каким-нибудь генератором распознавателей, вроде YACC, будут довольно велики, что, естественно, замедлит скорость синтаксического разбора.
Однако при внимательном анализе оказывается, что в языке имеется сравнительно большое число «микро»-регулярностей – часто повторяющихся устойчивых последовательностей лексем. Например, пары пустых скобки: (), [], пустой список параметров (void), завершитель списка параметров ...) встречаются очень часто. После служебных слов if, switch, while всегда должна стоять левая круглая скобка, после break и continue – точка с запятой, а после слова goto располагаются идентификатор и точка с запятой. Таких регулярностей набирается несколько десятков, так что если рассматривать их как отдельные лексемы, объем синтаксиса заметно сокращается. Введение каждой такой «суперлексемы» экономит по крайней мере одно обращение синтаксического анализатора к таблице разбора. Усложнение распознавателя лексем (сканера), вынужденного составлять суперлексемы из пар или троек обычных лексем, при этом получается весьма незначительное; более того, если сканер во время одного вызова распознает, например, не только служебное слово switch, но и левую круглую скобку, идущую за ним, получится экономия и на числе обращений к сканеру!
Во-вторых, в синтаксисе есть неоднозначности. Это надо оценить: в Стандарте (!) языка программирования прямо написано, что некоторые конструкции можно трактовать двояко – либо как объявление, либо как оператор! В несколько упрощенном виде формулировка из стандарта выглядит так: "выражение, содержащее в качестве своего самого левого подвыражения явное преобразование типа, которое записано в функциональном стиле, может быть неотличимо от объявления, в котором первый декларатор начинается с левой круглой скобки". Классический пример: что такое T(a); если T – некоторый тип? С одной стороны, это как бы объявление переменной с именем a, тип которой задан как T. С другой – конструкцию можно трактовать как преобразование типа уже объявленной где-то ранее переменной a к типу T. Все дело в том, что в Си++ статус операторов и объявлений полностью уравнен; последние даже и называются declaration-statements – операторы-объявления, то есть традиционные операторы и объявления могут записываться вперемежку. Все же радости с круглыми скобками перекочевали в Си++ прямо из Си, в котором типы конструируются подобно выражениям, и тривиальное объявление можно задать либо как "int a;", либо как "int(a);". Все это понятно, но от этого не легче. И такой язык любят миллионы программистов?! Мир сошел с ума. Яду мне, яду!..
Смысл правил разрешения неоднозначностей сводится, по существу, к поразительной фразе, простодушно выведенной в "Зеленой книге": "если конструкция выглядит как объявление, то это и есть объявление. В противном случае это оператор". Иными словами, чтобы разрешить неоднозначность, следует рассмотреть всю конструкцию целиком; фрагмент "T(a)" для анализа недостаточен – за ним сразу может следовать либо точка с запятой, тогда выбор делается в пользу объявления, либо «что-то еще». Например, вся конструкция может выглядеть как "T(a)→m = 7;" или "T(a)++;" – это, конечно, операторы (точнее, операторы-выражения, в терминах стандарта). Ну а как понимать следующее: "T(e)[5];" или "T(c)=7;"? А это, будьте уверены, еще не самые разительные примеры – загляните в разд. 6.8 Стандарта.
Человеку хорошо, он ко всему привыкает, рано или поздно он разберется, но как заставить анализатор понимать эту чехарду? Пока он не доберется до точки с запятой, он, в общем случае, ничего не сможет сказать о конструкции. Друзья, не пишите объявления, которые невозможно отличить от операторов! Пожалейте компилятор, ему же тяжело! Кроме того, можно запросто ошибиться и самому…
Несколько дней прошли в бесплодных попытках выразить неоднозначности на входном языке YACC. Выход был похоже, только в организации просмотра вперед, причем на заранее не известное количество лексем. Алгоритм разбора, заложенный в YACC, этого делать не умеет. В принципе известны и доступны системы, в которых заявлена подобная возможность, однако мы были ограничены требованием: синтаксический анализатор писать на YACCе, более того, на его версии, сделанной в одном европейском университете… Пришлось пойти на ухищрения и "сломать" классическую схему разбора: делать предварительный анализ еще на уровне разбора лексем и, встретив левую скобку после имени типа (а еще пойди распознай, что идентификатор – имя типа, а не какой-то другой сущности!), "отменять" автоматический анализ и организовывать "ручной" перебор последующих лексем, складывая их про запас в буфер.
Спасибо, в "Зеленой книге" подсказали схему такого анализа. Не знаем, как и благодарить, сами бы ни за что не придумали…
Что такое идентификатор?
Помимо неоднозначностей в синтаксисе быстро обнаружились другие неприятности. На примерах их показать сложнее, так что придется рассказывать словами.
Синтаксис языка Си++ неудобен еще и в другом отношении. Если говорить коротко, то прямое использование в формальном описании одного из базовых синтаксических понятий – идентификатора – приводит к тому, что YACC расценивает грамматику языка как некорректную и на ее основе не может построить синтаксический анализатор. Для традиционных языков синтаксическому анализатору для разбора конструкции достаточно информации о том, что в данной позиции этой конструкции может (или должен) находиться идентификатор. Более простые языки сконструированы так, что семантика идентификатора не влияет на корректность синтаксического разбора. Вид программной сущности, обозначаемой этим идентификатором (подпрограмма, переменная, имя типа, исключение, метка и т.п.), смысл данного конкретного вхождения (объявление или использование) – все это выявляется далее, как правило, являясь предметом следующей фазы компиляции – семантического анализа.
Для языка Си++ такая схема не проходит. Чтобы быть в состоянии синтаксически распознать многие конструкции, требовалась семантическая интерпретация имени. Иными словами, на вход синтаксическому анализатору следовало поставлять не абстрактную лексему "идентификатор", а результат анализа того, что именно представляет собой этот идентификатор: "имя типа", "новое имя в объявлении", "имя не-типа в выражении" и т.д. Заметим, что синтаксическому анализатору для Java – непосредственного потомка Си++ – вполне хватает понятия идентификатора без каких-либо уточнений.
Всего для Си++ получилось около десятка таких "суперлексем", а лексема "идентификатор" вообще исчезла из синтаксиса. Понятно, что лексический анализатор, который и поставляет лексемы, пришлось наделить дополнительным "интеллектом". Теперь он должен был не просто выделять из текста программы очередную лексему, но и обращаться в таблицы трансляции за информацией о том, что за идентификатор он выловил. Реально эти действия выполняет отдельный модуль, названный "расширенным лексическим анализатором". Введение дополнительного модуля не привело к усложнению компилятора в целом, так как идентификация имен так или иначе должна производиться; мы просто перенесли ее на более ранний этап компиляции. А синтаксис заметно упростился, стал более наглядным, информативным и в конечном счете более эффективным.
Компилятор как таковой: таблицы и деревья
Однако синтаксис – это мелочи жизни. Основное в любом компиляторе – это интерпретация семантики языковых конструкций, и подавляющая часть кода приходится именно на семантические алгоритмы.
Есть два основных вида семантической информации, которые компилятор извлекает из текста исходной программы. Во-первых, это информация о различных объектах, которые используются в программе (переменные, типы, функции и т.д.), причем не только об объектах как таковых, но и об областях действия, в которых эти объекты существуют (имеют смысл), а также об отношениях этих областей между собой (контекстах). Чем сложнее устроен язык, тем больше в нем правил, связанных с объектами, и тем более изощренной должна быть та структура в компиляторе, которая описанную информацию содержит. Такая структура обычно называется семантическими таблицами.
Во-вторых, компилятор должен формировать некоторый образ исходной программы – внутреннее представление программы в целом или ее некоторой части, которая в данный момент обрабатывается. Именно на основе такой структуры обычно выполняется семантический анализ программы, производятся различные оптимизации и осуществляется генерация результирующего кода. Как правило, такое внутреннее представление строится в виде дерева и потому называется деревом программы.
Эта пара – таблицы и деревья, вместе с различными алгоритмами, работающими над ними, без преувеличения составляет две трети текста компилятора. Почти вся наша работа на протяжении всех этих лет так или иначе была связана с ними.
Структура таблиц была придумана в целом по образцам из книг по теории и практике компиляции, которые в изобилии выходили у нас в 70-80-х годах и описывали, как правило, языки с относительно простой и, самое главное, регулярной структурой и несложной семантикой,– такие как Алгол-60, Паскаль, Модула-2. Многое из того, что есть в Си++, с трудом "втискивалось" в академические построения, и приходилось дополнять и развивать их. В результате таблицы представляют собой причудливую смесь классической стековой модели с дисплеем для отображения текущего контекста и наворотов вроде средств динамического перестроения контекста для обработки функций-членов классов, нетривиальной поддержки областей действия имен (namespaces), буферов для отложенной компиляции и т.д. К тому же таблицы должны быть динамически расширяемыми, чтобы быть в состоянии вобрать в себя очень большое количество имен, типичное для программ на Си++. Помучиться пришлось изрядно, и далеко не сразу таблицы заработали стабильно и надежно.
Опуская технические детали, следует сказать, что сейчас мы в целом недовольны тем, как спроектированы семантические таблицы. В свое оправдание отметим, что все "навороты" в них – вещи вполне объективные, которые так или иначе должны присутствовать в компиляторе. Наша неудовлетворенность имеет, скорее, эстетическую природу: таблицы не выглядят стройной системой, где каждый компонент точно подогнан к тому месту, которое для него предназначалось.
С деревом программы ситуация была обратной. Будучи один раз спроектированными, принципы организации дерева далее практически не изменялись. В противоположность таблицам, структура которых создавалась, чтобы непосредственно отражать контекстные отношения языка Си++, дерево оказалось практически полностью языко-независимым. Иными словами, используя основной строительный элемент дерева – терминальный узел – можно конструировать произвольные конфигурации, отображающие конструкции любых языков программирования. Все узлы дерева имеют идентичную структуру, различаясь лишь значениями своих (немногочисленных) атрибутов. Каждый узел имеет четыре ссылки (вверх, вниз, влево и вправо), с помощью которых легко формировать "плоские" конфигурации, соответствующие тем или иным конструкциям входного языка. Как правило, горизонтальные ссылки отражают верхний уровень структуры некоторой конструкции, а вертикальные используются для поддеревьев, соответствующих элементам этой конструкции, или вложенным конструкциям.
Несомненными достоинствами такой схемы являются высокая регулярность, простота и универсальность. Дерево для любой языковой конструкции строится по единым правилам, и все разнообразие выразительных свойств Си++ приводится к строгой единообразной регулярной конфигурации, для которой очень удобно строить всевозможные рекурсивные алгоритмы анализа, трансформации и генерации.
Однако у этих достоинств есть и оборотная сторона, которую можно определить как низкий уровень структуры дерева. В чистом виде оно не несет в себе никакой семантической информации – это лишь определенная структура и ничего более. Иными словами, для дерева как такового можно определить только достаточно примитивные операции, например, "связать два узла горизонтальными ссылками", "построить из данных узлов бинарное дерево" и т.п. Любое же мало-мальски серьезное действие, учитывающее семантику того или иного поддерева, например, его перестроение в процессе оптимизации или при генерации кода, приходится программировать специально для каждого вида конфигураций. На практике это приводит к тому, что операции над деревом не располагаются в одном или нескольких модулях, а рассредоточены по всему тексту компилятора.
Этот раздел хочется завершить несколько неожиданным выводом. Наличие в компиляторе двух базовых структур – семантических таблиц и дерева программы – сейчас расценивается нами как один из самых серьезных недостатков компилятора. Эти структуры реализованы на различных принципах, работа с ними организована по-разному, однако они существуют вместе, пронизаны взаимными ссылками (можно сказать, переплетены, как корни растущих рядом деревьев) и в некоторых случаях просто дублируют друг друга. Сходная информация о структуре программы присутствует и в таблицах, и в дереве, что долго приводило к путанице, и сейчас выглядит довольно нелепо. Например, в дереве имеются узлы, соответствующие объявлениям; это естественно, так как образы объявлений могут попадать в результирующий код. Что же касается таблиц, то они как раз и составлены на основе информации, извлеченной из объявлений. Поэтому в узлах-объявлениях содержится ссылка на соответствующее слово в таблицах. Семантическое слово, в свою очередь, имеет обратную ссылку на узел "своего" объявления, которая в ряде случаев оказалась необходимой. Инициализатор переменной из объявления представляется поддеревом, на которое имеются ссылки как из узла-объявления, так и из семантического слова. И так далее… Все это работает и даже вполне эффективно, но, конечно, с точки зрения программного дизайна весьма далеко от совершенства.
Описанное построение компилятора свидетельствует о нашем честном следовании классическим образцам, а также… о нашей боязни отойти от этих образцов. Даже подступая к языку, который заведомо отличался от "правильно" построенных, элегантных и простых языков, хорошо подходящих для книжного описания базовых концепций и методов компиляции, мы преувеличили степень универсальности решений, предлагаемых в подобных книгах.
Теперь мы это хорошо понимаем. В следующей версии компилятора все будет сделано по-другому.
Лебедь, рак и щука, или Гадкий утенок
Мой коллега и товарищ, Саша Кротов, вдвоем пару с которым мы, собственно, и сделали практически всю работу, имеет прекрасное образование (по моим наблюдениям, выпускники мехмата зачастую имеют более высокую программистскую квалификацию, чем окончившие ВМК – да простят меня мои однокашники!). Несмотря на естественное для его возраста отсутствие опыта крупных разработок, он поразительно быстро «въехал» в проект и вообще в проблемную область и очень скоро стал совершенно равноправным его участником. К этому времени он вполне осознал, насколько интереснее программировать компиляторы, чем наполнять базы данных, рисовать на экране вертящиеся фигуры или писать байты в порт и ожидать их оттуда.
Третий участник проекта был (и есть) настолько талантлив как программист, что мог с одинаковым успехом участвовать, кажется, решительно в любом программном проекте. Базы данных и сети, протоколы обменов и многозадачность, графика и издательские системы, вычислительные алгоритмы, распределенная обработка и искусственный интеллект – во всем он чувствовал себя уверенно и имел на то полное основание.
Так что шеф, глядя на нашу троицу с неподдельной гордостью, вполне мог считать, что вместе мы горы свернем. Однако далеко не все было гладко…
В компиляторе есть проектные ошибки (хотя к настоящему моменту большинство из них мы извели, поначалу их было немало). "Снаружи" эти ошибки практически никак не проявляются и не дают покоя только нам, знающим наизусть все его внутренности. Некоторые из них были просто неизбежны, так как, закладывая то или иное решение несколько лет назад, мы никак не могли представить, к чему приведет непредсказуемая эволюция языка. Другие ошибки объяснялись недостаточным опытом – практически впервые мы пытались делать то, что называется коммерческим программным продуктом и исходили только из академических представлений о том, какова должна быть архитектура компилятора.
Но самая неприятная категория проектных ошибок – это те, которые возникли из-за недостаточно тщательного анализа на начальных этапах проекта и, что хуже, из-за того, что по некоторым принципиальным вопросам имелись различные мнения. Принимать решение всегда сложно еще и потому, что чье-то мнение, как правило, приходится отвергать. Тяжело и тому, кто отвергает, и неприятно тому, чье мнение не учитывается. Зачастую бывает так, что трудно предпочесть какой-либо конкретный вариант из нескольких альтернатив просто потому, что все они достаточно обоснованы и могут быть использованы; в таких случаях необходимо чье-то волевое решение, которое все участники должны безоговорочно принять. У нас в свое время просто не хватило духу проговорить все до конца и определиться полностью по всем принципиальным вопросам. В результате некоторые существенные решения принимались "по умолчанию" тем или иным участником проекта без согласования с другими. Винить в этом, естественно, следует прежде всего старшего участника – автора этой статьи (как самого опытного, а не самого умного!).
Так, компилятор сначала выполняет полный семантический анализ всего исходного текста, и только потом генерирует для всей программы результирующий код. Почему такая организация компилятора была выбрана третьим участником, до сих пор непонятно. Какое-то объяснение было тогда дано, но оно тут же выпало из нашей памяти, и вспомнить сейчас невозможно, а попытаться самим объяснить – не получается. Такое решение (удивительно, но принятое без всякого обсуждения) приводит к тому, что компилятор сохраняет полное дерево программы (и, следовательно, вынужден сохранять и семантические таблицы, так как они друг с другом сильно связаны) вплоть до завершения обработки всего исходного текста. Более логичным и экономичным был бы подход, согласно которому для каждой функции выполняется вся обработка, вплоть до генерации кода, после чего в структурах компилятора сохраняется только информация из ее заголовка, необходимая для компиляции вызовов. Исключение достаточно сделать для встраиваемых (inline) функций, да и то не всегда.
Сохранение полного дерева программы было необходимо, если бы компилятор "затачивался" на выполнение иных, кроме генерации кода, функций, например, на анализ программ (снятие метрических характеристик, статическое профилирование и т.п.) или в том случае, если бы мы собирались делать машинно-независимую глобальную оптимизацию на уровне входного текста. Ничего подобного в проекте не было.
Получилось так, что семантические таблицы были спроектированы, имея в виду второй, более естественный подход, а структура дерева – согласно первому подходу. Разработчику семантических таблиц (мне, попросту говоря), будучи поставленному перед фактом уже в процессе реализации, ничего не оставалось, как срочно перекроить их структуру. Крайне неприятно, но эта ситуация сохранилась и по сей день. Надо ли уточнять, что эти структуры были в свое время придуманы двумя участниками, которые в свое время не смогли (не захотели) вместе обсудить свои решения и возможные проблемы…
Справедливости ради следует сказать, что такое проектное решение неожиданно оказалось весьма уместным и даже естественно необходимым в «следующей жизни» нашего компилятора. Однако, в том, первоначальном, проекте оно сильно осложнило разработку компилятора, и, конечно, было недопустимым.
Комментарий 2001 года
Подобных, более мелких, но крайне неприятных рассогласований и неувязок было много, и, самое ужасное, с течением времени их число нарастало. Возникало тяжелое ощущение того, что компилятор – это большая темная комната, а у тебя только маломощный фонарик, который в состоянии осветить небольшой аппарат – твои модули. От аппарата тянутся в темноту провода и вереницы зубчатых колес. Что делается в дальних углах, неизвестно. Иногда вокруг раздаются какие-то звуки, из темноты выступают части каких-то движущихся механизмов, назначение которых остается неведомым, даже если осветить их. Время от времени из темноты раздается голос, настоятельно требующий: «нажми на кнопку с надписью ABC», «переведи рычаг XYZ в правое положение». Что делается в комнате и как все работает вместе, понять совершенно невозможно.
Пришло время говорить о неприятном – через некоторое время от нас ушел третий участник. Он весь был ориентирован на получение результата, а не на процесс его достижения. Само по себе это исключительно ценное качество, его наличие (подкрепленное высокой квалификацией) гарантирует успешное завершение работы в заданные сроки. Однако в данном случае оно обернулось своей худшей стороной – откровенно небрежным кодированием ("компилятор соптимизирует" – классический ответ на все замечания), принятием важных решений "на ходу", без всякого обсуждения и плохо скрываемым недовольством коллегами, которые непонятно почему копаются там, где надо скорее программировать. Главное – скорее! За один день сделать работоспособный синтаксис, за месяц – добиться трансляции программы "Hello world!". Сложность системы не играет никакой роли, все программы устроены одинаково. Модули должны взаимодействовать согласно своим интерфейсам, обсуждать и комментировать которые нет смысла, они и так сами за себя говорят – на то они и интерфейсы.
Однако компилятор – такая система, которая объективно (исключая вырожденные случаи) не может быть сделана за три месяца, даже если предположить, что найдется гений, который физически смог бы написать за этот срок нужный объем кода. Как процесс его разработки, так и процесс кодирования должен предполагать совместную работу, постоянное обсуждение всех мало-мальски существенных решений и крайне аккуратное продвижение вперед, по крайней мере, до тех пор, пока не будет достигнут этап отладки. Слишком велико число связей между всеми компонентами компилятора и невозможно предвидеть, насколько серьезными окажутся последствия самого, казалось бы, невинного решения, принятого "на проходе" как очевидное.
Скрытое напряжение в команде возрастало, и первым не выдержал тот, кто не связывал с проектом все свои помыслы. В один прекрасный день мы двое обнаружили в общем каталоге с рабочими тестами полторы сотни примеров, которые ломали компилятор, причем ломали его вроде бы на тех модулях, которые писали мы. Третий участник исчез. Мы поняли это однозначно: мое терпение кончилось, разберитесь, наконец, с тем, что у вас не работает, догоните меня, а я пока займусь другими делами.
Ошибки были исправлены примерно за неделю (половина из них оказалась "не нашими", а как раз того третьего), однако он так и не вернулся в проект никогда… Мы остались вдвоем.
Как ни покажется странным, мы с Сашей не восприняли происшедшее как катастрофу, хотя вроде бы потерю такого классного специалиста невозможно возместить. Наоборот, мы почувствовали, что у нас появилось второе дыхание, распределили "ничейные" теперь модули между собой и с подлинным энтузиазмом принялись переделывать их. К настоящему времени в них не осталось, наверное, ни единой строчки первоначального кода. Но, к сожалению, осталось несколько тех самых "волевых" проектных решений, которые были приняты без всяких обсуждений как очевидные, которые оказались впоследствии ошибочными и которые к тому времени настолько вросли в ткань компилятора, что духу и сил не хватает их из него вырезать.
Я хочу, чтобы нас правильно поняли. У нас нет к ушедшему абсолютно никаких претензий. Нас не обманули, не предали, не нарушили никаких обязательств. Более того, я вполне допускаю, что сами мы не без греха, и работа в то время шла не слишком ритмично (надеюсь, что и ему уход не принес много горечи). И если я рассказываю об этом эпизоде, то только потому, что мы сами многое при этом поняли и многому научились.
Чем меньше коллектив, тем большее, часто определяющее, значение приобретает проблема личностной совместимости – характеров, темпераментов, привычек и манер, т. е. вещей, которые прямо не относятся к профессии. Примером, близким к идеалу, можно считать Дениса Ритчи и Кена Томпсона. Вот как последний говорил об этом в выступлении при вручении ему премии имени Тьюринга: "Наше сотрудничество было образцом совершенства. За десять лет, которые мы проработали вместе, я могу вспомнить только один случай нескоординированной работы. Тогда я обнаружил, что мы оба написали одинаковую ассемблерную программу из 20 строк. Я сравнил наши тексты и был поражен, обнаружив, что они совпадают посимвольно. Результат нашей работы был намного больше, чем вклад нас обоих по отдельности". Но это, как говорится, от Бога, один случай на миллион. Каких-либо рекомендаций давать невозможно, единственное – надо быть очень и очень осторожным при формировании коллектива.
Что же касается тщательного проектирования и особенностей процесса реализации, то изначальное жесткое разбиение на модули, снабжаемые строгими спецификациями, после чего реализацию этих модулей можно отдать даже и студентам, проходит для хорошо формализуемых и не впервые решаемых типовых задач, а не для систем с предельно сложной логикой, где решительно все взаимосвязано. Традиционная этапность разработки ПО (спецификация и анализ требований, проектирование архитектуры системы, спецификация модулей, реализация и т. д.) в данном случае неизбежно размывается, модифицируется и приобретает существенно итеративный характер: проектирование (и перепроектирование) многих структур данных и алгоритмов компилятора происходит неоднократно уже на этапе реализации. Такой возвратно-поступательный процесс, как мне кажется, органически характерен для создания любой сложной программной системы, семантика которой не может быть осознана и формализована полностью на этапе проектирования в приемлемые сроки. К тому же надо иметь в виду, что в процессе работы над компилятором изменялся и сам язык – процесс стандартизации зачастую преподносил совершенно неожиданные сюрпризы, и многого нельзя было предугадать заранее.
Эта точка зрения, точнее, конкретный опыт, быть может, входит в противоречие с современными моделями процесса создания ПО, описанными классиками,– Г.Бучем, Э.Йоданом и другими, однако повторю еще раз, компилятор Си++ – не вполне типичная программная система, по крайней мере, с точки зрения семантической и логической сложности.
Так или иначе, мы приобрели ценнейший опыт, полностью пройдя все этапы жизненного цикла программного продукта (в том числе и его сопровождение) и набив на этом пути много шишек. Теперь, надеюсь, мы не наступим еще раз на те же самые грабли.
А вы?
