Обсуждение

Рефал - функциональный язык без функций высших порядков. Java - императивный ОО (виртуальные методы - почти функции высшего порядка) язык. И любые преобразования его сложнее и менее результативно.

Я, кстати, не видел нигде четкого отличие суперкомпиляции от частичных вычислений. Т.е. как только доходит до формул -- ровно то=же самое. За ссылку на диссертацию спасибо -- посмотрю. Чтор касается того, почему направление не развивается -- развивается, но непонятно что с ним делать (как применить), коммерчески source to source transformation это рынок средств разработки, который каннибализирован open source. (Кстати, частичные вычисления на Java мы сделали и довели до продуктв [http://www.gradsoft.ua/products/jpe_rus.html], теперь бы найти партнера что бы что-то сделать с маркетингом ;)] Еще несколько ссылок на смежные темы есть у меня в посте про Рефал (http://rssh.livejournal.com/77559.html#cutid1) -- может Вам будет интересно.

Все они на циклах спотыкаются, а без циклов суперкомпиляторы не практичны. Самый практичный суперкопилятор - это сановский ХотСпот, как ни странно. Он может и не так много умеет, зато вмешательства со стороны программера не требует.

Я думаю, это вы общие соображения привели, а не конкретную информацию -- и поэтому я позволю себе усомниться в вашей оценке. Не думаю, что эти ваши соображения не были известны Климовым и Гертцелю в момент начала работы над ява-компилятором. Тем более, что они поставили довольно много экспериментов с разными языками в разгар работы. И намерены были эту работу закончить. У вас, наверное, нет точной информации.

"Все они спотыкаются" -- это как-то огульно. Насколько я понимаю, scp4 на циклах не спотыкается. Да и практичность у вас как-то особенно определяется -- для разных людей критерии практичности разные (подробнее этот вопрос разбирается австрийской экономической школой). ХотСпот явно помянут в http://www.supercompilers.com/white_paper.shtml -- говорится как раз о том, чем он отличается от суперкомпилятора.

Частичные вычисления явно поминаются в http://www.supercompilers.com/white_paper.shtml И я бы не согласился с определением "каннибализации" со стороны open source. Но это наверняка выльется в философскую дискуссию. Был бы востребованный продукт, а бизнес-модель для этого всегда придумать можно. Только над бизнес-моделью тоже нужно думать, а не надеяться на юристов и помогающую им милицию.

На самом деле нет -- именно особых каких-то проблем в циклах нет (есть потенциальная проблема в решении -- когда их разворачивать, когда нет, которая обычно заканчивается волюбнтаристким решением: "как только счетчик превысит 2".) Есть целый набор оптимизаций (так называемыве глобальные), которые ни хотспот, ни компилятор сделать не могут.

;)

У тулзов общего назначения к сожалению или к счастью есть простой критерий практичности: насколько у них много обзательных настроек. Если моя программа обрабатывается при дефолтных настройках, тогда все хорошо, я могу поиграться с ключами. Если же моя программа требует подбора настроек, чтобы обработаться за разумное время - то все плохо. Я пару лет назад тоже набрел на суперокмпиляторы, но когда увидел его настройки, то понял, что они их вводят чтобы избежать экспоненциального перебора, что означает, что на дефолтных настройках я могу просто не дождаться результата выполнения программы. ХотСпот в этом смысле весьма практичен. Разумеется, он не заменяет настоящий суперкомпилятор/частичный эвалюатор, например, для ембеддед Жабы, когда желательно обрезать лишний код на этапе компиляции. В то же время ХотСпот позволяет кое-как достичь желаемой цели: быстрой и одновременно сопровождаемой программы. Ибо он не требует обязательных настроек, в то же время выполняя весьма крутые оптимизации, в частности он умеет инлайнить виртуальные вызовы, в том числе для интерфейсов у которых одна или две реализации. Массивы только не умеет инлайнить, так бы ему цены не было. Впрочем, после появления в 6й жабе escape analysis на это можно расчитывать в будущем. ХотСпот делает и суперкомпиляторные оптимизации тоже, просто суперкомпиляторщики не внимательно читали литературу по ХотСпоту. Он всегда умел сплиттить код, т.е. делать несколько веток исполнения в зависимости от входыных данных - а это как раз та особенность на которую упирают суперкомпиляторщики. Кстати, это давным давно умеют делать и Лисповые компиляторы тоже.

По поводу спотыкается на циклах - тут дело в принципиальных ограничениях. Если нет циклов и рекурсий, то задача решается относительно просто: дерево входных данных получается конечным, хотя возможно и очень большим. Тем не менее конечное дерево можно как-то пытаться обработать за разумное время, напеример, итеративно. Если есть циклы и рекурсии, то все сложнее - в data flow анализе надо выходные данные учитывать как входные. Т.е. дерево входных данных вообще говоря получается неограниченное. Тут два варианта: либо мы фиксируем размеры массивов, либо приходится делать консервативные обощения, последенее в конечном итоге и зарубает всю идею суперкомпиляции. Первый же вариант - фиксированные размеры массивов - применим только в узких случаях, и вообще говоря, вместо него можно использовать метапрограммирование, т.е. просто генерировать специализированную версию программ. На мой взгляд, это проще и понятнее для программеров. Например, макросы в Lisp/Scheme/Nemerle, Template Haskell, MetaOCaml.

Проблемы в циклах есть - приходится использовать консервативные, т.е. неточные оценки множеств входных данных. Неточность накапливается, в результате в большой программе суперкомпиляция работает плохо: специализировать нечего. Хотспот умеет делать весьма разные оптимизации, в том числе и "суперкомпиляторные". Например, если загружена одна реализация интерфейса, то он может заинлайнить виртуальные вызовы. Он умеет это делать даже если загружены две реализации интерфейса, но в данном месте используется только одна. Умеет делать оптимизации по всему графу управления внутри метода. При агрессивном инлайнинге межпроцедурная оптимизация не критчна, а вот межпроцедурный анализ он делать умеет, например, escape analysis. Вот инлайнить массивы, он сцуко поже не умеет :(. Умел бы - цены бы ему не было. Хотя бы массивы у которых длина известна на этапе компиляции.

Кстати в зарубежной литературе вместо суперкомпиляции используется термин Abstract Interpretation.

А, ну это именно та проблема, которая обходится волюнтаристким решением. (И если говорить о дефаултной настройке - то выбор какого-то числа N, такого что при абстрактной интерпритации цикла мы его разворачиваем либо нет, когда оценка меньше N) дает нам простой и неэкспотенциадльный критерий [как раз в следующей версии JPE такое будет] (А где каноническое описание оптимизаций хотспот почитать ?) P.S. может у себя пост сделаете для специализированной дискуссии ?

Дык все циклы не развернешь (хотя это тоже неплохо), да и кода много получится. Т.е. надо специально писать софт и давать хинты суперкомпилятору (неважно в какой форме) чтобы он догадывался где стоит потратить время на поиск специализаций, а где это делать бесперспективно. Альтернативный подход - профилировать производительность, как это делает ХотСпот. В данном случае, есть объективная информация о том, где имеет смысл проводить оптимизации. > (А где каноническое описание оптимизаций хотспот почитать ?) Есть классический вайтпейпер по ХотСпоту на сановском сайте. Там описано основное, но без деталей. Есть диссертация по языку Self на основе которой ХотСпот и создавался - это база. Конечно, за последнее время было много улучшений, в частности о которых я писал. Отдельной статьи про это нет, но кое-что написано тут http://blogs.sun.com/vmrobot/category/Compilers . > P.S. может у себя пост сделаете для специализированной дискуссии ? А смысл? Народу вряд ли прибавится, а так и тут обсудить можно.

Про циклы -- ну что хотите сказать я понял. Мне кажеться, что сделать достаточно разщумное поведение по умолчанию вполне возможно. (Даже ничего с ними не делать, как сейчас у нас -- вполне разумно). И без этого частичный вычислитель довольно много делает. Хотспоту хорошо, что есть данные оптимайзера, плохо что нет глобального анализа. Т.е. множества оптимизаций пересекаются, но не равны. (Интересно было бы объеденить, но пока непонятно как Хотспот: Из того, что на сановском сайте у меня создалось впечатление что там обычная покадровая оптимизация. Или не разобрался. URL, конечно-же не сохранился [?] P.S. Почта человеку приходит наверное ;) С другой стороны - сам поднял тему, пусть читает ;)))

Никогда ранее не участвовал в подобных дискуссиях. Попробую … По поводу отличия суперкомпиляции от частичных вычислений. Идеи разработки оптимизаторов на основе метаинтерпретации возникли в 70-х годах. Тогда, независимо, А.П. Ершовым (Новосибирск), В.Ф. Турчиным (Москва) и Ё. Футамарой (Япония) были обозначены направления исследований в этой области. Таким образом, появились три термина, соответственно: смешанные вычисления, суперкомпиляция, generalized computations. Попытки решить поставленные задачи сразу обнаружили принципиальные трудности; что и не удивительно - любая более-менее содержательная задача на оптимизацию (как таковая) алгоритмически неразрешима. Здесь, кстати, ответ по поводу "циклов". В 80-х годах N.D. Jones принял кардинальное решение по упрощению оригинальных идей Ершова, Турчина и Футамары. Появился термин "частичные вычисления". Именно в частичных вычислениях, благодаря принципиальному упрощению, и были достигнуты основные успехи. Попробую объяснить, не вдаваясь в технические подробности, какое упрощение предложил Jones. Рассмотрим конечный набор элементарных преобразований: t1, …, tN. Другими словами - исчисление. Задача состоит в умелом автоматическом жонглировании этими элементарными преобразовании с целью оптимизации программы. Jones предложил разбить множество {t1, …, tN} на два подмножества { t1, …, tK } и { tK+1, …, tN }. Далее, он решил принять на работу ещё одного фокусника и разделил сферу ответственности между этими двумя цирковыми служащими. Первый фокусник, в первую смену, жонглирует преобразованиями { t1, …, tK }. Во вторую смену, второй фокусник берет результат работы первого фокусника и жонглирует с ним преобразованиями { tK+1, …, tN }. То, что получится после второй смены, и называется результатом преобразований при частичных вычислениях. Чтобы прочувствовать насколько при этом Jones ограничил возможности оптимизации, полезно провести следующую аналогию. Рассмотрим машину Тьюринга (МТ). Программист является жонглером конечного набора элементарных преобразований, допустимых в МТ {t1, t2, здвинуть_указатель_влево, здвинуть_указатель_вправо, t5, t6}. Композиция этих преобразований позволяет показать фокус с любым алгоритмом. Далее, мы разделим множество элементарных преобразований МТ на два {t1, t2, здвинуть_указатель_влево} и {здвинуть_указатель_вправо, t5, t6}; наймем на работу двух программистов и выдадим им инструкцию, аналогичную Jones-овской. Вопрос: что они смогут запрограммировать?

Правильно было бы зарегистрироватьс в ЖЖ -- тогда ответы на реплики будут автоматически приходить к вам на почту, как в списках рассылки. И вы сможете редактировать свои реплики, если в них найдутся ошибки и опечатки. Заодно дискуссия будет не с анонимом (хотя при регистрации совсем необязательно указывать реальное имя и место работы), т.е. более структурирована. И правильно реплику давать в ответ на ту реплику, в которой был обсуждаемый тезис (чтобы не терялась логика тредового обсудения). Так, вы явно отвечаете на реплику rssh http://ailev.livejournal.com/544965.html?thread=4306117#t4306117, в которой есть фраза "не видел нигде четкого отличие суперкомпиляции от частичных вычислений. Т.е. как только доходит до формул -- ровно то=же самое". Увы, еще много-много поставленных в репликах вопросов неотвечены. И еще вдогонку: есть тренд на языково-ориентированное программирование (http://www.google.com/search?q=language-oriented) -- как суперкомпиляция с ним соотносится?

Вот еще ссылочка по теме: http://www-users.cs.york.ac.uk/~ndm/supero/ Суперкомпиляция Haskell, с практическими результатами.

Да, это очень свеженькое -- 2007г. Но обратите внимание, например, на список литературы в http://www.csee.ltu.se/~pj/papers/scp/ifl07-scp.pdf -- там большинство работ до 1997г., затем все замирает, и продолжается уже в 2007г.. Удивительно.

Конечно, даже ограниченный частичный вычислитель - это хорошо. Но без умения анализировать произвольные циклы/рекурсию, светлое будущеее недостижимо. Под светлым будущим я имею в виду быстрый и одновременно сопровождаемый код. Ибо надо уметь преобразовывать программу так, чтобы частичный вычислитель догадался как эффективно заспециализировать код. К сожалению, это умение трудно формализовать и передовать, т.е. это несопровождаемо :(. Про хотспот тут можно почитать http://java.sun.com/products/hotspot/whitepaper.html#3 > P.S. Почта человеку приходит наверное ;) С другой стороны - сам поднял тему, пусть читает ;))) Дык ему может ему интересно :).