Re: [mskhug:0] Сводка для группы mskhug@googlegroups.com - Сообщения: 2 в Темы: 2
Serguey Zefirov
29 января 2010 г. 2:38 пользователь <mskhug+...@googlegroups.com> написал:
> Сводка по сегодняшним темам
>
> Группа: http://groups.google.com/group/mskhug/topics
>
> "Превращение неявной рекурсии в явную с помощью суперкомпиляции"
> [Обновлений: 1]
> "Тёмные углы суперкомпилятора HOSC: неполные case-выражения и рекурсивные
> определения данных" [Обновлений: 1]
>
> Тема: "Превращение неявной рекурсии в явную с помощью суперкомпиляции"
>
> Sergei Romanenko <sergei.r...@gmail.com> Jan 28 03:04PM -0800 ^
>
> Превращение неявной рекурсии в явную с помощью суперкомпиляции
>
> http://metacomputation-ru.blogspot.com/2010/01/hosc-rec-thru-reduction.html
>
> Сергей Романенко
>
>
>
> Тема: "Тёмные углы суперкомпилятора HOSC: неполные case-выражения и
> рекурсивные определения данных"
>
> Sergei Romanenko <sergei.r...@gmail.com> Jan 28 03:03PM -0800 ^
>
> Тёмные углы суперкомпилятора HOSC: неполные case-выражения и
> рекурсивные определения данных
>
> http://metacomputation-ru.blogspot.com/2010/01/hosc-inex-case-rec-data.html
>
> Сергей Романенко
>
>
>
> --
> Данное сообщение отправлено Вам, так как Вы являетесь подписчиком группы
> "MskHUG" на группах Google.
> Для того, чтобы отправить сообщение в эту группу, пошлите его по адресу
> msk...@googlegroups.com
> Чтобы отменить подписку на эту группу, отправьте сообщение по адресу:
> mskhug-un...@googlegroups.com
Serguey Zefirov
Поэтому, и потому, что именно здесь был задан вопрос, отвечу здесь.
Вот, собственно, и мой вопрос Андрею Климову:
http://groups.google.ru/group/mskhug/browse_thread/thread/37fc86199a40ed5f
Теперь - ваши ответы:
>* Является ли Си "хорошим/плохим" языком?
Вы так и не написали, что же имел в виду под дихотомоией
"хороший/плохой" Андрей Климов. И является ли это разделение
распространённым, или это просто частное мнение Андрея.
>* Почему (почти) никто не занимается суперкомпиляцией для Си?
>* В C/C++ есть арифметика над указателями. Можно двигать указатели туда-сюда, как в голову придёт. А вылезет указатель куда не надо - авторы спецификации не виноваты (они ведь написали, что результат "зависит от реализации"). А авторы реализации - тоже не виноваты: раз в спецификации сказано, что результат не определён, так он в реализации и "не определён": при одном запуске одно получится, а при другом - другое.
> * В C/C++ система типизации вроде бы и есть. Но при этом разрешается приводить что угодно к чему угодно. Например, приводим число с плавающей точкой к указателю, достаём по этому указателю... А дальше - результат "зависит от реализации" (и при каждом запуске программы может быть разный).
Это означает, что для вполне определённого компилятора (реализации)
можно определить вполне понятную семантику. Если мы фиксировали
реализацию, выбрав, например, gcc на x86, то мы уже нигде не зависим
неё.
Так чем же указатели и приведение типов мешают суперкомпиляции?
> Sergei Romanenko <sergei.r...@gmail.com> Jan 29 05:34AM -0800 ^
>
> 2010/1/29 Serguey Zefirov <...@...>
>
>> А насчёт суперкомпиляции Си и почему он "плохой" мне так и не ответили. ;)
>
> Хороший вопрос. Но ответ на него представляет больший интерес для
> членов группы metacomputation-ru, поэтому (чтобы идентичный текст не
> торчал в двух группах) ответ отправил туда:
>
> http://groups.google.ru/group/metacomputation-ru/t/bee11f5b59088ae0
Serguey Zefirov
Тут "зависимости от реализации" и "разных результатов при разных
запусках" нет ни код каким углом. ;)
Sergei Romanenko
> Вы так и не написали, что же имел в виду под дихотомоией
> "хороший/плохой" Андрей Климов. И является ли это разделение
> распространённым, или это просто частное мнение Андрея.
По отношению к тому, что написал Андрей Климов мы находимся в равном
положении: почему бы Вам самому не ответить на вопрос о том, что он
подразумевал? :-)
А если говорить о моём собственном мнении, то если мы собираемся
выполнять сложные преобразования над программами на каком-то языке, то
желательно, чтобы было хотя бы известно, какова семантика этих
программ. Если семантика плохо определена, то тому, кто будет делать
систему преобразований будет плохо. Т.е. лично для него этот язык
будет "плохим".
Но если просто заниматься программированием на этом языке, и эта
деятельность будет хорошо оплачиваться, то для таких целей язык может
считаться "хорошим". (Особенно если работодатель не ставит размер
зарплаты в зависимость от надёжности изготавливаемых программ.)
> >* Почему (почти) никто не занимается суперкомпиляцией для Си?
Частичными вычислениями для Си занимался Lars Ole Andersen
Andersen, L. O. 1992. Partial Evaluation of C and Automatic Compiler
Generation (Extended Abstract). In Proceedings of the 4th
international Conference on Compiler Construction (October 05 - 07,
1992). U. Kastens and P. Pfahler, Eds. Lecture Notes In Computer
Science, vol. 641. Springer-Verlag, London, 251-257.
Andersen, L. O. 1993. Binding-time analysis and the taming of C
pointers. In Proceedings of the 1993 ACM SIGPLAN Symposium on Partial
Evaluation and Semantics-Based Program Manipulation (Copenhagen,
Denmark, June 14 - 16, 1993). PEPM '93. ACM, New York, NY, 47-58. DOI=
http://doi.acm.org/10.1145/154630.154636
Но "весь пар у него ушёл в свисток": потратил много сил на борьбу с
арифметикой над указателями, и в этой борьбе увяз где-то в самом
начале пути. А после него, видимо, не нашлось желающих залезать в это
же самое болото.
> Это означает, что для вполне определённого компилятора (реализации)
> можно определить вполне понятную семантику. Если мы фиксировали
> реализацию, выбрав, например, gcc на x86, то мы уже нигде не зависим
> неё.
Абсолютно верное утверждение! Для каждой конкретной реализации
семантика определена самой этой реализацией: для gcc на x86 - одна
семантика, а для gcc на amd64 - уже другая...
Но работать с такой "спецификацией" очень трудно. Нормальная
спецификация языка тщательно полируется группой людей, потом
публикуется в некотором "съедобном" виде, и не меняется несколько лет.
Её можно изучить и изготовить систему преобразований, которая будет
корректной по отношению к этой спецификации по крайней мере в течение
нескольких лет.
А если в качестве "спецификации" берётся некая реализация, то от этого
возникают некоторые трудности:
* Не так-то просто понять смысл такой "спецификации": даже если
реализация - open source (что верно далеко не для всех реализаций C/C+
+), то нужно сидеть и читать исходные тексты этой реализации. И
выковыривать полезную информацию (которая в нормальной спецификации
лежала бы на поверхности) примерно как изюм из булочки.
* Всякая реализация (в отличие от обычной спецификации) находится в
состоянии непрерывного развития. Сегодня она одна - а завтра уже
другая (и её снова нужно изучать).
* Варианты одной и той же реализации для разных архитектур (например,
x86 и amd64) отличаются. Под какую из них нужно делать систему
преобразований?
* Даже если делать систему преобразований под конкретную реализацию +
конкретную версию этой реализации + конкретное "железо", то всё равно
результат работы программы на C/C++ может отличаться от запуска к
запуску. Приводим double к указателю. Получается некий адрес, который
на что-то указывает. А при следующем запуске программы распределение
памяти получится другим, и результат работы тоже будет другим. Т.е.
всё равно, даже для конкретной реализации семантика остаётся
определённой не до конца.
А в гугловском Go как раз и устранены самые неприятные проблемы такого
рода.
Поэтому получается такая ситуация: есть бетонная стена (C/C++), а в
этой стене прорезана дверь (Go). Как поступить? Можно лезть напролом и
биться головой о стену (делая суперкомпилятор для C/C++), а можно
рядом пройти через дверь (сделать суперкомпилятор для языка вроде Go).
Сергей Романенко
Sergei Romanenko
> Или другой вопрос: сложна ли суперкомпиляция ассемблера конкретного процессора?
>
> Тут "зависимости от реализации" и "разных результатов при разных
> запусках" нет ни код каким углом. ;)
А тут дело обстоит гораздо лучше. Люди такими делами занимаются, но
чаще всего под вывесками вроде run-time byte-code specialization.
Сразу заметим, что существенной разницы между байткодом и языком
конкретного процессора принципиальной разницы нет. Но процессоров
много, а байткодов в несколько раз меньше. Поэтому люди предпочитают
делать для байткодов: с практической точки зрения результат почти тот
же самый, а мороки меньше.
Вот пример проекта, где идёт работа с байткодом CIL:
CILPE, a program specializer for CIL
http://code.google.com/p/cilpe/
CILPE хотя и "основан" на частичных вычислениях, но кое-где вылезает
из частичных вычислений в сторону суперкомпиляции.
Сергей Романенко