воскресенье, 7 сентября 2008 г.

Семантическое представление: ответ Анониму

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

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

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

Ну действительно, Intellisense есть и в Visual Studio, и в Java-средах программированя, и в Dephi - да где только нет... 

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

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

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

А тут и гадать не надо: код, генерируемый для .NET, по определению несет в себе метаданные - некоторую информацию об исходной программе, которой и пользуется Intellisense. Более того, доступ к этой информаици можно производить кому угодно (программным путем) - из самой программы, из другой программы...

Внутреннее семантическое представление есть во всех компиляторах. 

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

Многие системы используют единое внутреннее представление для нескольких языков (на ум приходят Visual Works и gcc, есть и в VS наверняка).

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

У VS нет единого внутреннего представления. Все языки, представленные в VS, создавались в различных условиях, с разными задачами, в разное время и различными командами. Вообще, VS скрывает в себе немало неожиданностей. Например, там, как говорят инсайдеры, на самом деле два компилятора C# - один обычный, подобный тому, который из командной строки (он запускается по команде Build), а второй - "умный", который находит синтаксические ошибки на лету (в процессе наборра программы в редакторе) и обеспечивает Intellisense. Компилятор VB - один на все виды работ. Что касается плюсового компилятора, то с ним вообще непонятно. Он совсем старый, подкрученный на "живую нитку". Говорят, они собираются его капитально переделывать (якобы, уже начали...)

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

Честно говоря, вопросы "свободно/за деньги" мне параллельны, поскольку они не имеют отношения к тому, что мы обсуждаем. Интерес представляет проблемы, связанные собственно с разработкой и реализацией семантического представления, а не с тем, как оно распространяется. Вот сделаем, тогда и решать будем. :-)

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

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

То есть, непонятно, что нового - в использовании какого-то особого внутреннего представления C++.

Новое заключается в том, чтобы придумать целостное, полное, независимое от конкретного компилятора представление семантики языка Си++, а также программный интерфейс к такому представлению, и, конечно, реализовать этот интерфейс. Этого до сих пор никто не сделал, хотя пара проектов с подобными целями известна (но они либо умерли лет пять назад, либо несколько "сменили ориентацию" в пользу более простых задач). Правда, можно двигаться несколько другим путем: начать с того, чтобы специфицировать интерфейс доступа к семантическому представлению, а потом заниматься реализацией этого интерфейса. Именно так сделано в Ада-мире: был принят стандарт на интерфейс доступа к Ада-программам - ASIS (Ada Semantic Interface Specification), и он был реализован для нескольких Ада-компиляторов.

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

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

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

Ну и я о том же самом писал: нет семантической информации. Где спор-то? :-)

 Даже в устаревающем Delphi уже давно есть откомпилированные модули dcu с кучей метаинформации в заголовке. И линковщик только заглядывает в нее и сразу разрешает внешние ссылки. А в C++ линковщик проделывает гигантскую работу - известно же про скорость линковки проектов на C++...

Как пишет Страуструп в той же книге, одним из основных требований при проектировании С++ было обспечить совместимость с существующими инструментами (с линкерами, заточенными под Си, в частности). Именно отсюда проблемы - какой ни будь С++ продвинутый, но вынь и положь возможность плюсовые программы линковать с сишными.

 Я уж не говорю про .NET и Java, где этап линковки ну почти отсутствует - в байт-коде уже хранится нужная информация.

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

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

С байт-кодом (или с MSIL-кодом) проблемы те же: там нет семантической информации об исходной программе. Есть метаданные, но их недостаточно для реализации "умной" линковки. Да и нет метаданных для кода из-под "обычного" С++ (не для Managed C++). А нужда в умной линковке, помимо борьбы с code bloat для шаблонов, заключается еще и в возможности делать глобальную оптимизацию программы, и в возможности ее "умной" и безопасной интерпретации (в частности, для режима отладки). Именно по этим причинам линковка семантического представления предпочтительна.

Мне кажется, что сейчас нужно ставить более прогрессивные вопросы, чем ставил Страуструп 15 лет назад: создание единого семантического представления для группы языков программирования

"Прогресс" - понятие диалектическое. :-) На мой-то взгляд, прогресс в решении даже тех задач, которые Страуструп сформулировл в том разделе, довольно относителен. С другой стороны,
реальный прогресс в той сфере, которую мы обсуждаем, возможен только при наличии соответствующих потребностей со стороны пользователей. Спроси сейчас кого угодно: тебе нужно единое семантическое представление для двух (трех и т.д.) языков? Ответ будет отрицательный. Это не означает, разумеется, что работы в этой области не имеют смысла. Но надо понимать, что это требует довольно фундаментальных исследований. Речь идет, по существу, о том, чтобы спроектировать и обосновать универсальный семантический базис для различных ЯП. Можно запросто (знаю, что говорю :-)) объединить семантические представления, например, для С/С++, Джавы и C# (просто свалить все в одну кучу) и объявить "революцию" свершившейся. Выделить же общие семантические свойства хотя бы двух языков, построить минимальный понятийный базис для них и определить механизм расширения этого базиса - это задача, поверьте, очень-очень нетривиальная...

 и преобразования "во все стороны".

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

 Можно также говорить о стандарте внутреннего представления только для C++ и о стандарте хранения его на диске - иначе каждая фирма будет разрабатывать свое и тщательно скрывать от конкурентов.

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

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

Ну и - что касается C++ - хорошо бы хранить в каком-то стандартном бинарном виде заголовочные файлы - а то они каждый раз перекомпилируются - пещерный век!

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

14 комментариев:

ABreslav комментирует...
Этот комментарий был удален автором.
ABreslav комментирует...

(предыдущий комментарий был случайно отправлен недописанным)

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

Я не зря упоминал в комментариях к предыдущему посту Eclipse CDT (C++ Development Tools) - дело в том, что этот продукт умеет отвечать на все опросы, упомянутые Страуструпом. Семантическое представление у них наверняка есть и скорее всего оно открыто для использования внутри среды Eclipse (сам не проверял, но для Java это именно так, а Eclipse - вещь довольно консистентная). Не то, чтобы я хотел сказать, что это и есть то самое независимое от компилятора семантическое представление, но посмотреть на него, наверное, интересно.

Спроси сейчас кого угодно: тебе нужно единое семантическое представление для двух (трех и т.д.) языков? Ответ будет отрицательный
Ответ, конечно, положительный! Представьте себе, что нужна (всего лишь) среда разработки для некоторого языка, и я могу получить доступ к богатейшим возможностям существующей среды (такой как Eclipse или IntelliJ Idea), всего лишь поддержав в компиляторе стандартное семантическое представление. Это революция в создании IDE, а IDE - это весьма существенно (посмотрите, что недавно развернулось вокруг NetBeans).

На самом деле стандартизированное семантическое представление - очень нужная вещь и очень здорово, что Вы этим занимаетесь.

rssh комментирует...


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


Не знаю - уместен ли будет следующитй комментарий: мы занимаемся похожими задачами (только для Java) и действительно семантическое представление это не AST а нечто вроде
AST + средства резолвинга

Мы для такого "семантического" дерева, где кроме имен есть еще перекрестные ссылки для - применяем названия "модельные термы"

Подробности описанны в
http://eprints.isofts.kiev.ua/395/

Если выйдет какой-то фронт-енд для С++,
было бы интересно подгрузить его в нашу систему (хотя бы путем чтение информации из дампа с нормальным синтаксисом, если не загрузки библиотеки)

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

ABreslav комментирует...

Вопрос rssh:
мы занимаемся похожими задачами (только для Java) и действительно семантическое представление это не AST а нечто вроде
AST + средства резолвинга


Зачем вы это делаете, если есть JDT AST API - открытая, отлично работающая реализация этой идеи?

rssh комментирует...

Зачем вы это делаете, если есть JDT AST API - открытая, отлично работающая реализация этой идеи?


Причин наверное две:
1. JDT API - это не высокоуровневый DSL, там rewrite rules на Java пишутся.
То есть API доступа к модели это где-то половины работы. У нас эта часть своя по историческим причинам.
(и если уж говорит о аналогах именно API, то их можно сходу назвать 4: в eclipse, в netbeans, Sun APT Mirror API и наше. Еще какое-то есть в idea) Кстати в netbeans есть свой DSL, немного перекликающийся с нашим.
- Мы не зависим от IDE

Анонимный комментирует...

Есть довольно хорошая коммерческая реализация подобной функциональности - http://www.scitools.com/
Только вот шаблоны С++ до сих пор не анализируют.

SClown комментирует...

А в чем принципиальное отличие разрабатываемого Вами представления от Datrix-схемы или Columbus-схемы?

Кстати насчет использования внутреннего представления GCC - в проекте SPQR используется именно оно. Причем в результате получается и промежуточное представление на базе сигма-исчисления Карделли, и его XML представление.
http://rockfish.cs.unc.edu/pubs/TR06-025.pdf

Анонимный комментирует...

IMHO, Вы "ломитесь" в открытые ворота ... недалеко от Вас, в Женеве, в ЦЕРНе
разработана система, позволяющая включать в бинарный код всю
метаинформацию о классе:
href=http://root.cern.ch/root/html/CORE_META_Index.html

Вся эта система активно используется для Reflection/RTTI( href=http://root.cern.ch/root/Dictionary.html), automatic streaming(href=http://root.cern.ch/root/HowtoWrite.html), HTML generation ( href=http://root.cern.ch/root/html/HTML_Index.html)
дело доходит, что известно, какой
комментарий стоит напротив имени члена класса или метода (и делается это программным образом), C++ interpreter
( href=http://root.cern.ch/twiki/bin/view/ROOT/CINT),
signal-slots connections
( href=http://root.cern.ch/root/HowtoSignalSlot.html),
web server running C++ scripts (a la PHP), on fly C++ script compilation.
Ведутся работы по созданию IDE на основе этой системы
Бьярн прекрасно знает об этом проекте и мы с ним
и C++ коммитетом в контакте.

Regards. Valeriy Onuchin

Анонимный комментирует...

>http://www.scitools.com/
несомненно менее функционален, чем CINT
http://root.cern.ch/twiki/bin/view/ROOT/CINT
+ платный ++ закрытый +++
гораздо меньшая "community"

Анонимный комментирует...

сам CINT "весит" ~2Мб и подходит для
embedded systems

Анонимный комментирует...

> http://rockfish.cs.unc.edu/pubs/TR06-025.pdf

типа gcc2xml?

VO

Анонимный комментирует...

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

Анонимный комментирует...

Глубокоуважаемый Евгений. Спасибо большое за статьи и вывешенный в сеть компилятор.

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

И готовы "2 представления: одно текстовое, другое объектное". Этот человек непосредственно не связан с Проектом, поэтому слова столь путаные.

Анонимный комментирует...

Добавление. Евгений, взгляните на описание проекта Pivot - http://parasol.tamu.edu/pivot/

Не оно ли это самое и есть?