Очень хорошо забытое старое

18 март, 2008 - 12:38Андрей Зубинский

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

Давайте попробуем взглянуть на современный массовый компьютинг как на... весы. Понятно, что аналогия мало того что опасная (все аналогии опасны и чаще всего неверны), но еще и весьма сложная. И все же давайте попробуем. На одной чаше этих весов – те человеческие операции с машиной, которые мы называем «персональным компьютингом». На другой чаше – та совокупность аппаратных и программных средств, которые обеспечивают реакции на операции, производимые человеком. Эта аналогия не дает нам, по сути, ничего, кроме возможности на ее основе построить предположение о том, что в мире «персонального компьютинга» все будет относительно спокойно, пока чаши весов уравновешены. Пока нужды пользователей не станут существенно перевешивать возможности аппаратно-программных средств, никакого «взрыва» в последних не будет. Малые колебания от точки равновесия в сторону пользовательских потребностей можно всегда компенсировать «утяжелением» одной из составляющих на противоположной чаше весов, например сложностью программного обеспечения. Больше того, таким приемом можно как бы и стимулировать рост пользовательских потребностей, предлагая новые «утяжелившиеся» возможности. Об одной чаше такой модели Николас Негропонте, основатель и председатель проекта «ноутбук для каждого ребенка» , в шутливой форме сказал так: «Энди дающий, Билл забирающий» (естественно, речь идет об Энди Гроуве, Intel, и Билле Гейтсе, Microsoft).

Итак, «весовая аналогия». Как и всякая аналогия, она очень опасна – главное не увлечься и не забыть, где начинаются и заканчиваются границы ее действенности, а самое же главное – убедиться в ее действенности вообще. Так как искания в области справедливости аналогий очень далеки от специфики нашего журнала, мы ими заниматься не будем, а скажем только, что нечто подобное весовой аналогии можно отыскать в предпосылках очень многих очень альтернативных проектов. И иногда жаль, что суровая жизнь аналогий не понимает, и результаты таких проектов, часто очень яркие и заслуживающие внимания, становятся фактически игрушками узкого круга интеллектуалов, игрушками, которые со временем надоедают, забываются и пылятся на академических, редко посещаемых сайтах (в качестве примера можно привести ОС Bluebottle, bluebottle.ethz.ch). Впрочем, мы не о том – в ярких проектах всегда можно найти вещи, которые не претендуют на изменение судеб человечества, но оказываются на удивление полезными в повседневной жизни и работе. Еще более удивительными могут показаться факт ужасающей дряхлости (по меркам компьютерной эпохи) этих вещей и долгое отсутствие к ним должного интереса. К предмету обсуждения этой статьи, придуманному в 70-е годы прошлого века, все сказанное выше удивительно хорошо подходит. Начнем с того, что цель проекта STEPS назвать скромной и неглобальной никак нельзя – «Изобретение основ новой технологии компьютинга» (vpri.org/html/work/ifnct.htm), ни больше и ни меньше. Более того, описание мотивации участников проекта один в один совпадает с весовой аналогией – «даже непрофессионалы в области компьютерных технологий знают о колоссальных и все возрастающих объемах памяти и показателей производительности, необходимых для инсталляции только базовой операционной системы еще до того момента, как будет загружено и запущено любое из приложений (объемы которых также аномально растут)... Важным вопросом является подлинность необходимости этих затрат – продиктованы ли они спецификой природы программного обеспечения или же вызваны слабостью лежащих в основе идей и инструментария, ленью, отсутствием знаний etc... Поэтому мы спрашиваем – сколько в действительности строк кода требует персональный компьютинг с учетом операционной системы, приложений и прочего обеспечивающего ПО – 2 млрд, 200 млн, 20 млн, 2 млн, 200 тыс., 20 тыс., 2 тыс.?.. Мы понимаем, что в поиске ответа нам не избежать сравнений типа яблоки-апельсины и искривленных пространств, но вопрос остается важным и интересным». Итак, на одной чаше весов – опыт персонального компьютинга, на другой – масштабы (в строках) обеспечивающего его кода. Большие масштабы – сложная система – сложности разработки, эксплуатации, модернизаций. Это аксиома. И сокращение масштабов действительно кажется очень привлекательным, особенно когда речь идет о результатах, уже достигнутых проектом STEPS: 170 строк кода – это интерпретатор JavaScript, работающий быстрее, чем другие реализации (быстродействие обеспечивается тем, что этот интерпретатор фактически является JIT-компилятором), 200 строк кода – реализация стека протоколов TCP/IP, 460 строк – графический «моторчик», функционально аналогичный библиотеке манипуляций с пикселами pixman, лежащей в основе сервера системы X Window, но выгодно отличающийся быстродействием, обусловленным фундаментальными особенностями логики работы, 450 строк – развитая библиотека векторной графики (высококачественная растеризация со сглаживанием, графические примитивы, включая кривые Безье, клипирование для реализации оконных систем). Собственно компилятор языка, о строках кода которого идет речь, реализован всего тысячей строк своего же языка (для сборки методом раскрутки) – в этот объем «утрамбованы» и генераторы кода для разных аппаратных платформ. Эти цифры похожи на фантастику? Безусловно. Мы даже можем оценить – насколько фантастично. Например, для известных реализаций стеков TCP/IP в среднем требуется 10–20 тыс. строк кода, т. е. мы говорим о снижении сложности реализации на три порядка (!). Это даже уже не фантастика, а дерзость – ни одна из существующих разработок не претендовала на такое. И все же эта дерзость обоснована – существует и язык, лежащий в ее основе, наработан и кое-какой инструментарий, но, что главное, – есть очень неплохо и давно проработанная теория, представляющая самостоятельную ценность для практикующих программистов, по вполне понятным причинам не желающих играть в игры «одним махом изменим мир к лучшему».

PEG, о которых забыли

В феврале 1970 г. в Принстонском университете защитил диссертацию Александр Бирман, впоследствии работавший с Джеффри Ульманом (тем самым, которого многие программисты знают по культовой «книге с драконом» «Компиляторы: принципы, технологии, инструменты»). Именно Бирману мы обязаны надолго забытой и теперь восстанавливающей популярность идеей PEG – грамматик синтаксического разбора выражений (Parsing Expression Grammars). Вообще сам факт того, что PEG каким-то образом так надолго «выпали» из программистского и околопрограммистского дискурса, можно считать настоящим недоразумением – ведь в сегодняшнем профессиональном программировании близкие к PEG, но уступающие им по возможностям, формальные грамматики Бэкуса–Наура и регулярные выражения считаются чуть ли не базовыми понятиями, а владение соответствующими инструментами – базовыми навыками. Впрочем, давайте по порядку.

Когда мы говорим о машинных языках, то традиционно подразумеваем два подхода к работе с ними. Первый – генеративный, предусматривает формальное описание набора правил, на основании рекурсивного применения которых можно генерировать строки некоторого языка. Яркий пример генеративного подхода – регулярные выражения. Например, выражение [а-я]+, по сути, описывает генератор последовательности из одного или более символов русского алфавита нижнего регистра. С помощью соответствующего инструментария можно, например, находить совпадения фрагментов текста с заданными (сгенерированными) регулярным выражением множествами строк – это именно та функция, которую в большинстве текстовых редакторов принято называть «поиском с использованием регулярных выражений». Генеративный подход – это и контекстно-свободные грамматики, заданные в определенных формах, например в форме Бэкуса–Наура (БНФ). И регулярные выражения, и формальные грамматики на самом деле вовсе не являются продуктами «чисто компьютерного назначения» – их создатели больше интересовались анализом естественных (человеческих) языков. А уже потом, после безуспешных в целом попыток создать теорию естественных языков, формальные грамматики и регулярные выражения «подобрали» специалисты по языкам искусственным, машинным – в этих разработках подкупали изящность и выразительная мощь.

Но потребности «компьютерщиков» больше касаются инструментов, чем теоретических разработок, а вот для создания инструментов подходит не генеративный подход, а распознавательный (recognition-based). Суть его ясна из названия – язык определяется в терминах высказываний, которые позволяют проверить на истинность утверждение о принадлежности строки к языку. Такие высказывания, значением которых является истина или ложь, называются предикатами. Очевидно, что между генеративными описаниями и распознавателями строк языка существует некая дистанция, сократить которую – призвание методов, алгоритмов и инструментов синтаксического разбора. И PEG – еще одно удивительное пополнение этого арсенала.

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

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

SOne <- ‘1‘
S2Ones<- SOne SOne

задают распознаватель пары единиц.

Ничего нового по сравнению с БНФ здесь нет. Но. Во-первых, в PEG распознавание последовательности выражений синтаксического разбора pe1 pe2 трактуется так: проверить предъявляемую строку на совпадение c pe1 pe2, и, если совпадение не найдено, «откатиться» на место в предъявляемой строке, с которого начиналась проверка. То есть речь идет о как бы безусловной проверке на совпадение с последовательной парой шаблонов pe1 и pe2. Во-вторых, есть и условная проверка, нечто вроде ветвления, которая записывается в форме pe1/pe2. В этом случае предъявленная строка проверяется на совпадение с шаблоном pe1, и, если совпадение не обнаружено (предикат ложен), отдельная вторая проверка на совпадение с pe2 начинается с того места, в котором первая проверка оказалась неудачной. В-третьих, в PEG существуют так называемые синтаксические предикаты, для записи которых используются символы & и !. Выражение &pe означает попытку поиска совпадения во всей предъявляемой строке с шаблоном pe с последующим «откатом» к стартовой точке и возвратом только информации о том, было ли найдено совпадение (возвращается истина) или нет (возвращается ложь). Предикат !pe делает то же самое, но c инвертированным результатом (когда &pe – истинный, !pe – ложен, и наоборот). И наконец, в-четвертых. В PEG входят операторы, свойственные регулярным выражениям, но отличающиеся «жадностью» – оператор «+» повтора «один раз или более» и оператор * «более одного раза». Под «жадностью» понимается гарантированное нахождение всех возможных совпадений, а не некоторого неопределенного их количества (что, к слову, свойственно аналогичным операторам обычных регулярных выражений).

Эта краткая информация уже позволяет разобрать некоторые свойственные PEG идиоматические конструкции. Например, такую – pe1+ pe1. Так как повторы в PEG – «жадные», pe1+ «выедает» все возможные совпадения с pe1, не оставляя второму предикату никаких шансов стать истинным, в результате чего pe1+ pe1 никогда ни в какой строке не отыщет совпадений, независимо ни от строки, ни от pe1. pe1+ / pe1 также никогда не найдет совпадений, но уже по другой причине – если в строке нет хотя бы одного или более фрагментов, совпадающих с pe1, в ней точно нет и одного такого фрагмента.

Эти механизмы, уникальные для PEG, позволяют описывать и разбирать с помощью соответствующего инструментария конструкции, недоступные их традиционным, основанным на контекстно-свободных грамматиках, конкурентам. Так, обычные контекстно-свободные грамматики (например, в БНФ-представлении) нуждаются в отдельном описании лексических элементов с помощью регулярных выражений и абсолютно не приспособлены для решения обширных классов практических задач из-за отсутствия, скажем, «жадности», которая обычно нужна для выделения во входном потоке символов идентификаторов и чисел. Регулярные выражения, с другой стороны, принципиально не способны описывать рекурсивный синтаксис, позволяющий из маленьких простых выражений методом индукции формировать сложные. Зато для PEG, как уже понятно, все это – не проблемы, что освобождает программиста от массы ограничений и дает ему возможность освободиться от ограничений, налагаемых свободой от контекста (этот каламбур на деле – великая сила).

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

vector<vector<float> > Matrix1 ;

С++ требует обязательного наличия пробела между «закрывающими» символами ‘>'. Если пробел не поставить, компилятор будет считать пару ‘>>' оператором побитового сдвига вправо. Со всеми вытекающими последствиями. Традиционными способами решить эту проблему нельзя – если бы это было можно, ваш компилятор не «ругался» бы на подобное непристойное поведение. PEG же дает возможность без особых усилий придавать идентификаторам и лексемам иерархические свойства и тем самым сокращать количество подобных нюансов до минимума. С другой стороны, ничто не бывает бесплатным, и расплатой за дополнительную гибкость является более высокая требовательность PEG к качеству разработки и отладки. К слову, задача отладки до сих пор требует решения, и талантливым смельчакам здесь есть где разгуляться.

Вместо заключения

В этой небольшой статье автор не ставил перед собой задачу рассказать в деталях о PEG и, само собой, подразумевал некоторый уровень подготовки читателя. К сожалению, желающим начать самостоятельное серьезное изучение PEG и языка программирования OMeta, созданного на основе этого мощного формализма (того самого языка, 200 строк которого хватает для реализации стека TCP/IP), придется несладко. Материалов о PEG, несмотря на продолжительную историю, очень немного. Фундаментальной работой можно считать небольшую по объему статью Брайна Форда из Массачусетского технологического института Parsing Expression Grammars: A Recognition-Based Syntactic Foundation (ее можно найти на сайте Форда на странице публикаций. Тематическая статья википедии ценна больше перечнем инструментария, поддерживающего PEG. Увы, инструментарий или весьма экзотичен в использованных средствах (впрочем, функциональные языки Haskell и OCaml уже большой экзотикой не считаются), или довольно «сырой», или и то и другое одновременно. Пользователям и UNIX-подобных ОС, и ОС семейства Windows, вероятнее всего, окажется полезным набор PEG-аналогов знаменитой пары lex и yacc – leg и peg, реализованный на стандартном C. Ну а язык OMeta... он, безусловно, интересен и заслуживает отдельного внимания. Но все же, PEG дает в руки программисту инструментально-независимую идею, которая очень часто много ценнее конкретного инструмента.