"Арифметика синтаксиса-2"

Предыстория

Несколько лет назад Сергей Свердлов, мой коллега и товарищ из Вологодского педуниверситета опубликовал в журнале PC Week/RE (#42-43, 1998) статью под названием "Арифметика синтаксиса". Идея этой статьи заключалась в том, чтобы найти какие-то более-менее объективные критерии размытому и неопределенному понятию "сложность языка программирования". И если не оценить эту самую сложность отдельного языка с помощью какой-то вычислимой метрики, то хотя бы предложить сравнительную "меру сложности", которая отвечала бы на вопрос "какой язык проще, а какой сложнее?".

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

Статья получила определенную известность и, как это часто бывает, больше за рубежом: Никлаус Вирт в одном из своих выступлений привел график из статьи Сергея в качестве обоснования сравнительной простоты своего Оберона. А выглядело это и вправду убедительно: в отличие от задирающейся вверх линии С->С++->Java, цепочка Паскаль->Модула-2->Оберон имела явную тенденцию к снижению (то есть, языки последовательно упрощались - при увеличении выразительных возможностей языка!).

Впрочем, что это я - словами да словами? Вот эта картинка:


Мне эта статья очень понравилась - не в последнюю очередь потому, что я сам интересовался синтаксисом языков, в частности, довольно много работал с метасинтаксическими инструментами - прежде всего, с YACC/Bison. (Собственно, "синтаксическая часть" нашего компилятора Си++ сделана с помощью YACC'а.)

Мои соображения

Однако, по системе "сбора информации" и существу самой методики сразу возникло несколько сомнений. Попытаюсь кратко их описать.

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

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

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

(1) оператор ::= помеченный-оператор | непомеченный-оператор
(2) помеченный-оператор ::= метка ":" оператор
(3) метка ::= идентификатор
(4) непомеченный-оператор ::= ...

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

(1) оператор ::= помеченный-оператор | непомеченный-оператор
(2) помеченный-оператор ::= метка идентификатор ":" оператор
(3) метка ::= идентификатор
(4) непомеченный-оператор ::= ...

Подобные "ухищрения" авторов грамматик, разумеется, влияют на размер алфавита и, следовательно, могут искажать общую картину при сравнении языков.

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

Ну вот... Эти соображения возникли у меня почти сразу же после прочтения статьи Свердлова - наверное, уже больше десяти лет назад. И тогда же возникла идея провести аналогичное исследование, но уже на более "правильных", как мне представлялось, методологических основаниях. И - написать вместе с Сергеем статью "Арифметика синтаксиса -2"!

Подход для "Арифметики-2"

Вот какие принципы и подходы следовало бы положить в основу второй "Арифметики...":

1. Грамматики выбранных для сравнения ЯП необходимо переписать на некотором едином метасинтаксическом языке. При этом во всех грамматиках следует использовать единообразный подход к представлению правил. Типовые элементы (повторяющиеся конструкции - списки и последовательности, необязательные вхождения терминалов/нетерминалов, рекурсивные правила и т.п.) должны представляться одинаково. Похожие конструкции в грамматиках должны представляться единообразно. Избыточные правила, подобные приведенным в примере выше, следует, насколько это возможно, удалить из всех грамматик.

2. Следует ограничиться синтаксисом. Никакие формализмы, ориентированные на задание семантических атрибутов  или использующие для описания грамматик механизм задания "семантических действий", не должны использоваться. Аналогично, лексика языков не должна быть предметом рассмотрения: терминальные символы языка должны трактоваться как первичные сущности, не обладающие собственной структурой (мы ведь хотим сравнивать синтаксис языков, а не их лексику, правда?).

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

4. Исходя из приведенных требований, наиболее подходящей формальной нотацией для представления грамматик кажется входной язык генератора распознавателей YACC/Bison. Этот язык широко известен, достаточно удобен для использования, а грамматики, представленные на этом языке, могут как служить целям данного исследования, так и использоваться для различных языко-ориентированных процессоров (то есть, предоставлять полезный побочный эффект).

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

Метрика сложности

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

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

если парсер находится в состоянии Xто
если на вход поступил символ T1то
поместить этот символ в стек выполнения и перейти в состояние Y
(такой тип действия называется переносом)
иначе если на вход поступил символ T2то
извлечь из стека выполнения определенное количество ранее положенных туда
терминалов и нетерминалов 
и поместить в стек нетерминал  P,
после чего перейти в состояние Z
(такое действие называется сверткой)
иначе
...

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

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

Назовем сложностью состояния анализатора с порядковым номером i число терминалов, которые могут поступить на вход анализатору, когда он находится в этом состоянии. Обозначим эту величину как Сi. Тогда сложность языка можно определить как сумму значений Сi для всех i в диапазоне от 1 до N, где N - общее число состояний анализатора. Иными словами, рассматриваем все состояния парсера, и для каждого состояния берем число терминалов, которые могут поступить ему на вход в данном состоянии. То есть, сложность языка определяется как сумма сложностей всех возможных состояний анализатора.

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

(Хотел очень кратко - буквально на одну страницу - изложить только основные идеи, а получилась практически та самая статья, которую и планировал написать... J)

Что делать?

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

Однако было сразу понятно, что объем работы, обусловленный принципами и подходами, изложенными выше,- какой-то уж непомерно большой. Собственно, основная работа - разработка грамматик ЯП согласно этим принципам и подходам. И если для сравнения выбрать... ну, скажем, хотя бы с десяток современных языков, то дело это весьма трудо- и времязатратное, уж поверьте. Ну, синтаксис Оберона и Си - дело пары вечеров: всем понятно, что языки несложные (да вот эти грамматики, смотрите: Oberon-2 и ANSI C; только перед тем, как их изучать, стоит прочитать общие принципы, согласно которым они делались).

Но вот синтаксис таких монстров, как Си++, Ада или Java (да-да, Java - тот еще монстр, особенно ее последняя версия!) требует весьма значительных усилий.


Сравниваемые языки

(Пока без комментариев)

Oberon-2
ANSI C
Objective C
C++ 2010
C#
Java
Ada2005
Eiffel
D
Go
Scala

Тезис: Было бы интересно посмотреть эволюцию возрастания (или убывания) сложности для некоторых распространенных языков, подобно тому, как это сделал автор первоначальной статьи для языков семейства Паскаль и для Turbo/Object/Delphi Pascal. В самом деле, известные языки уже накопили изрядную историю своих версий. Вот например:

"Си с классами" -> С++ версии ARM -> С++ 1998/2003 -> С++ 2010
С# от своей первой версии до текущей
Java от первой версии Гослинга до теперешней Java 5
Ada83 -> Ada95 -> Ada2005

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

Заключение

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

В общем, работа продолжается. Несколько грамматик уже готово, другие на подходе. Можете глянуть: