Java-суперкомпилятор
Andrei Klimov
Sent: 18 May 2009 21:41
> Здравствуйте! А можно оставить заявку на статью? :) Хотел бы узнать,
> как сейчас обстоят дела с суперкомпилятором Java-программ.
Евгений, большое спасибо за "подталкивание"!
Бинарики того, что сделано к настоящему времени под названием "Java-суперкомпилятор JScp", лежат на сайте:
http://www.supercompilers.ru/
Правда, сейчас там версия годовалой давности, а с тех пор он развивался, но я ленился выкладывать, поскольку сторонних пользователей (кроме меня самого) у него нет. Почему так -- см. ниже.
В прошлом году я, наконец, начал изготавливать статьи по Java-суперкомпилятору, рассказывающих, какие методы в него заложены и какие приложения получаются.
Можете посмотреть пару статей 2008 года, взяв их отсюда (30 и 31):
http://pat.keldysh.ru/~anklimov/pub.html
Уже подготовлены и приняты к публикации еще две. В процессе появления финальных версий выставлю и их.
По приложениям JScp, свежее (прошлогоднее) достижение -- верификация моделей протоколов кеш-когерентного доступа к памяти, воспроизведенная на языке Java и JScp вслед за Андреем Немытых и Алексеем Лисицей, верифицировавших на SCP4 модели, запрограммированные на Рефале. Результаты экспериментов (постановки задач, исходные и остаточные программы, остаточный граф и ссылки на источники) сложены здесь:
http://pat.keldysh.ru/jver/
Правда, на этом сайте еще не хватает пояснений. Одна из статей, которую вскоре выложу, содержит информацию как раз об этом результате.
> Что уже продумано, что реализовано и работает, какие существуют открытые
> проблемы математические/программистские ?
Хотя мощность и "интеллект" JScp еще далеки от того, что хотелось бы (по сравнению с суперкомпилятором Рефала SCP4 Валентина Турчина и Андрея Немытых), но главная проблема не в этом. Его интеллекта уже хватает для многих "хороших дел".
Главная проблема -- программистская: нужно включить суперкомпилятор в какую-нибудь студию (например, Eclipse) и накачать удобства для его использования.
Дело в том, что суперкомпилятор -- это не "черноящичный" инструмент в отличие от классических оптимизирующих компиляторов, работу которых пользователь совсем не замечает. Человек должен ставить задачи для JScp (какие подпрограммы оптимизировать и информацию о каких классах и методах вовлекать), управлять стратегиями суперкомпиляции (выбирать среди степеней свободы, которые есть у алгоритмов суперкомпиляции), задавать дополнительную информацию о подпрограммах, которые не даны ему в исходниках, либо такую, которую он сам не может извлечь из исходников (например, наличие побочных эффектов), и т.п.
Развитие суперкомпилятора JScp дошло до состояния, когда эти проблемы вышли на передний план. Из него выведены "рычажки управления", но сейчас они задаются тяжеловесно через вспомогательный xml-файл. Задавать их рукам мучительно даже авторам, которые, казалось бы, все понимают. По-хорошему, это надо делать через диалоговой интерфейс и в связи с исходным кодом (скажем, задавать разные опции для разных классов и методов).
Другая проблема -- понимание того, что делает суперкомпилятор. Это нужно хотя бы для того, чтобы подкручивать опции. Сейчас пользователь глазами читает остаточную программу (которая, к счастью, получается вполне читабельной) и догадываться, какие ее элементы соответствуют каким элементам исходного кода. Это пример того, что можно автоматизировать: скажем, кликнул мышкой по знаку операции в остаточной программе, а в другом окне подгоняется и выделяется место исходной программы, откуда он возник.
В идеале еще надо бы показывать процесс суперкомпиляции, промежуточные и окончательные конфигурации, соответствующие точкам остаточной программы, -- по аналогии с диалоговыми отладчиками, существующими в студиях. Но для этого потребуется перетряска существующего JScp, а вышеупомянутые возможности можно реализовать в студии лишь с небольшими изменениями в самом JScp. С них и надо бы начать. Они уже резко облегчили бы жизнь.
Но пока находятся силы лишь делать отдельные небольшие задачки на JScp для демонстрации его возможностей. А на большие задачи без средств автоматизации в студии сил не хватит. (Я как-то пытался протолкнуть одну большую задачу. На принципиальные проблемы так и не наткнулся, но на подбор опций и задание дополнительной информации уходило столько времени и сил, что через пару месяцев трудов забросил, -- стало себя жалко.;-))
Однако, не видно принципиальных ограничений, чтобы, в конце концов, суперкомпилятор стал бы таким же легким инструментом для пользователя, как сейчас операции рефакторинга, которые тоже являются преобразованием исходного текста.
Вот такая "есть у меня мечта". ;-)
Андрей Климов
kornevgen
результаты по верификации протоколов. У меня только сразу же возникает
вопрос сравнительный :) Эти протоколы чем только ни верифицируют - в
большинстве случаев разного вида автоматными техниками, model checking
и сопутствующие. Какие преимущества у суперкомпилятора перед ними
всеми в этой задаче? Выигрыш по времени/памяти/удобстве проведения
доказательства/что-то еще ? Просто задача настолько притягательная для
многих исследователей со своими методами решения - а хочется
расставить какие-то приоритеты, чтобы для себя определить, что более
удачно, что менее.
С уважением,
Евгений Корныхин
Sergei Romanenko
> спасибо большое! замечательно, что работа ведется. Очень интересные
> результаты по верификации протоколов. У меня только сразу же возникает
> вопрос сравнительный :) Эти протоколы чем только ни верифицируют - в
> большинстве случаев разного вида автоматными техниками, model checking
> и сопутствующие. Какие преимущества у суперкомпилятора перед ними
> всеми в этой задаче? Выигрыш по времени/памяти/удобстве проведения
> доказательства/что-то еще ?
Если отвечать кратко и абстрактно, то ответ получается примерно такой.
Преимещество суперкомпиляции в том, что это довольно общий метод
(отслеживание возможных путей вычислений "в общем виде"). Поэтому,
можно надеяться на то, что с её помощью можно решать довольно широкий
класс задач.
Возникла потребность решить некую задачу - засовываем её в
суперкомпилятор и смотрим, что получится. Даже если не получится,
имеет смысл внимательно посмотреть, в каком месте сил у
суперкомпиляции не хватило.
Тут ещё надо учесть разницу между "суперкомпиляцией" в чистом виде и
"суперкомпилятором". Суперкомпилятор - это система преобразования
программ, которая, естественно, основана на суперкомпиляции, но имеет
право дополнительно использовать и любые другие, сколь угодно
утончённые методы анализа и преобразования программ. В качестве
примера можно привести суперкомпилятор Андрея Немытых SCP4. Этот
суперкомпилятор обрабатывает программы на языке Рефал (строгий
функциональный язык), и, кроме самой суперкомпиляции, содержит ещё
много хитрых "колёсиков" и усовершенствований. Например, в нём
реализован алгоритм распознавания того, что некоторые определения
функций на самом деле определяют функцию "тождественную на своей
области определения", т.е. если аргумент принадлежит к области
определения функции, то он же и возвращается в качестве результата
Поэтому можно действовать так. Засовываем некую задачу в
суперкомпилятор. Если получилось - хорошо. А если не получилось -
смотрим, почему не получилось, и добавляем к суперкомпилятору какое-
нибудь дополнительное "колёсико".
Достоинство такого подхода, по сравнению с изготовлением
специализированной системы для специализированного класса задач, в
том, что при изготовлении специализированной системы всё равно надо
реализовать некую большую "стандартную" часть, а потом уже что-то
специфическое. А если уже есть работающий суперкомпилятор, то в нём
уже реализована эта занудная "стандартная" часть, и можно сразу
заняться прикручиванием к нему своего "колёсика".
Но, естественно, сказанное справедливо только в том случае, если
доступен суперкомпилятор с открытыми исходниками, с лицензией,
разрешающей его "подхакивать" всем желающим, и если суперкомпилятор
запрограммирован в тмком виде, чтобы в нём был способен разобраться
"человек с улицы". (Имеется в виду не любой человек, гуляющий по
улице, а то, что на улице должен найтись хотя бы один человек,
способный разобраться.)
Вот, из таких соображений и были созданы проекты:
http://code.google.com/p/spsc/
http://code.google.com/p/hosc/
Попытались выставить хоть что-то "для простого народа"... А хорошо ли
получилось - другой вопрос.
Сергей Романенко
Andrei Nemytykh
> "суперкомпилятором". Суперкомпилятор - это система преобразования
> программ, которая, естественно, основана на суперкомпиляции, но имеет
> право дополнительно использовать и любые другие, сколь угодно
> утончённые методы анализа и преобразования программ.
-- Я здесь не вполне согласен.
Во-первых понятие "суперкомпиляции" достаточно размыто. Это скорее
некоторый набор идей, чем конкретный алгоритм.
Если же мы и зафиксируем некоторый алгоритм и объявим его
"суперкомпиляцией", тогда нам на эту тему не о чем говорить и
рассуждать. Нужно только кодировать и быть довольными достаточно
слабыми результатами суперкомпиляции; так как мы себя насильно
ограничили, а задача оптимизации (или специализации и т.п.) программ,
как таковая (то есть, в идеале), алгоритмически неразрешима.
Более того нам не о чем говорить по-существу, так как - таким образом
- исчезает сама задача.
Внесение любой свежей идеи будет порождать "гиперкомпляцию" (а это ещё
страшнее :-()).
Андрей Немытых.
Sergei Romanenko
> > Тут ещё надо учесть разницу между "суперкомпиляцией" в чистом виде и
> > "суперкомпилятором".
>
> -- Я здесь не вполне согласен.
> Во-первых понятие "суперкомпиляции" достаточно размыто. Это скорее
> некоторый набор идей, чем конкретный алгоритм.
>
> Если же мы и зафиксируем некоторый алгоритм и объявим его
> "суперкомпиляцией", тогда нам на эту тему не о чем говорить и
> рассуждать.
Зафиксировать "алгоритм" суперкомпиляции нельзя. Граф конфигураций
содержит в узлах "конфигурации", каждая из которых описывает некое
множество возможных состояний вычислительного процесса. Понятно, что
эти множества состояний должны быть описаны конструктивным способом: в
виде конечных выражений на каком-то языке.
А каким дожен быть этот язык? А вот это - неизвестно, до тех пор, пока
мы не решим, для какого конкретного языка программирования мы
собираемся делать суперкомпиляцию. Должен быть известен синтаксис
языка, какие в нём есть конструкции и операции над данными.
Кроме того, нужно ещё остановиться на каком-то конкретном варианте
операционной семантики обрабатываемого языка. Ведь прогонка - это
обобщение обычного исполнения программы, и должна вырождаться в
обычное исполнение, если на вход поданы полностью известные данные.
Также, чтобы доказать корректность прогонки (а, стало быть, и
суперкомпиляции) нужно иметь что-то, по отношению к чему эта
корректность дожна доказываться. Если прогонка является обобщением
какого-то варианта операционной семантики, то естественный подход
состоит в том, чтобы доказывать её корректность по отношению именно к
этом варианту. (Хотя, абстрактно рассуждая, может быть, можно было бы
доказать и по отношению к чему-то другому.)
Ну, а когда у нас есть язык и есть его операционная семантика
(основанная на какой-то модели вычислений), нужно ещё придумать язык
на котором будут описываться множества вычислительных состояния. Этот
язык зависит от языка и его семантики, но однозначно ими, естественно,
не определяется. Поэтому, даже для заданного языка можно придумать
много разных вариантов суперкомпиляции (не говоря уже о разных
языках).
Согласен с тем, что какой уж тут "алгоритм" суперкомпиляции?
Суперкомпиляция - это не "алгоритм", а "метод" и/или "подход".
> Нужно только кодировать и быть довольными достаточно
> слабыми результатами суперкомпиляции; так как мы себя насильно
> ограничили, а задача оптимизации (или специализации и т.п.) программ,
> как таковая (то есть, в идеале), алгоритмически неразрешима.
Не понял, что означает это утверждение. Как я уже сказал выше, даже
для фиксированного языка и фиксированной модели вычислений, можно
бесконечно заниматься совершенствованием языка, на котором описываются
конфигурации (и повышать точность операций, совершаемых над
конфигурациями). О каком "кодировании" тут можно говорить? Задача -
творческая и неисчерпаемая (в силу всё той же алгоритмической
неразрешимости).
Так же не понимаю, почему, если мы будем отличать суперкомпиляцию как
таковую от других методов анализа и преобразования программ, это как-
то подрежет крылья у разработчиков суперкомпиляторов? Им же никто не
запретит добавлять к суперкомпиляции всё, что им захочется?
> Более того нам не о чем говорить по-существу, так как - таким образом
> - исчезает сама задача.
Я думаю, что дело обстоит ровно наоборот: если мы от жадности начнём
валить в одну кучу с суперкомпиляцией все известные нам методы анализа
и преобразования программ, то тогда обессмыслится само понятие
суперкомпиляции, и, так сказать, торговая марка "суперкомпиляция"
будет безнадёжно изгажена и обессмыслена. Как мы тогда сможем
объяснить людям, в чём состоит специфика нашего подхода и её отличие
от других подходов?
> Внесение любой свежей идеи будет порождать "гиперкомпляцию" (а это ещё
> страшнее :-()).
Именно так! Как учил Турчин, над суперкомпиляцией нужно строить
метасистему, в которой суперкомпиляция будет использоваться уже как
элементарная операция. То, что будет твориться в этой метасистеме
должно и называться по-другому. Например, higher-level
supercompilation или ещё как-нибудь.
Над арифметикой строится школная алгебра, над школьной алгеброй -
высшая алгебра и матанализ. Никто же не называет матанализ
"арифметикой"? Термины, конечно, нужно экономить, но в разумных
пределах. Если какие-то вещи существенно отличаются, они и называться
должны по-разному.
Сергей Романенко