Итак, про глупость.
В этом посте я пока разберусь только с одной глупостью - с непониманием понятия сложности компиляции и тьюринговской полноты одним отдельно взятым плюсовиком.
Про автоматы, IBM и другие интересные глупости поговорим в отдельном посте.
Повторю свои слова - для сферического компилятора в вакууме (т.е. без дополнительных фич, без препроцессора, без оптимизации и без ограничений - чистый парсинг и кодогенерация) имеем следующие верхние пороги времени компиляции.
C - линейная.
C++ - бесконечная.
Доказательство.
1. Теоретическое.
Посылки:
Шаблоны реализуют Тьюринг-полную модель вычислений во время компиляции.
Программа на Тьюринг-полном языке может выполняться бесконечно.
Не существует алгоритма, способного определить - бесконечно ли выполняется программа.
Вывод:
Для компилятора С++ с учетом отсутствия ограничений возможно создание программы, компилирующейся вечно.
Для С (даже с учетом препроцессора) модель компиляции тьюринг-полной не является.
Препроцессор не рекурсивен, знаете ли.
2. Экспериментальное.
Pal к сожалению, как его ни просили, не захотел указать список кошерных компиляторов С++. По моему мнению этот список эквивалентен пустому множеству.
Но так как что-то взять надо - возьмем обычный gcc4.
Вспомнив слова Pal
Сообщение от
pal
потому что, если бы ты узнал об этом из стандарта, то ты бы также знал, что все, что требует больше 17 шагов - не с++
можно удивиться, что gcc - это не С++, поскольку у него стоит ограничение шаблонной рекурсии не 17, а 500.
Но вспомнив другие слова Pal, можно уже ничему не удивляться.
Чтобы привести компилятор к сферическому коню в вакууме мы будем использовать параметр -ftemplate-depth-5000.
Программа 1 - функция Аккерманна.
Код:
template <int x, int y> struct Ackermann
{
enum { val = Ackermann<x-1, Ackermann<x, y-1> ::val>::val };
};
template <int y> struct Ackermann<0, y>
{
enum { val = y + 1 };
};
template <int x> struct Ackermann<x, 0>
{
enum
{
val = Ackermann<x-1, 1>::val
};
};
int main(void)
{
return Ackermann<XXX,YYY>::val;
}
Функция растет очень быстро, тем кто прогуливал и не знает, что это за функция - в педивикию.
Итак, что имеем на 25 строк кода.
Код:
[dEEpl0y@delirium template]$ time g++ -DXXX=1 -DYYY=1 -ftemplate-depth-5000 -c ackermann.cc
0.00user 0.02system 0:00.03elapsed 93%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+16outputs (0major+4371minor)pagefaults 0swaps
[dEEpl0y@delirium template]$ time g++ -DXXX=4 -DYYY=1 -ftemplate-depth-5000 -c ackermann.cc
x86_64-alt-linux-g++: Internal error: Segmentation fault (program cc1plus)
Please submit a full bug report.
See <http://bugzilla.altlinux.org> for instructions.
Command exited with non-zero status 1
132.28user 0.27system 2:12.55elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+32539minor)pagefaults 0swaps
Через 132 секунды компиляции 25 строк кода компилятор пукнул и умер.
PS
Да, кстати про 17 уровней.
Pal написал вот такой интересный текст.
Сообщение от
pal
потому что, если бы ты узнал об этом из стандарта, то ты бы также знал, что все, что требует больше 17 шагов - не с++
Но вот стандарт, говорит совсем другое.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2798.pdf
AnnexB p1246
The limits may constrain quantities that include those described below or others. The bracketed number following each quantity is recommended as the minimum for that quantity. However, these quantities are only guidelines and do not determine compliance.
И на следующей странице читаем
- Recursively nested template instantiations [17].
Не соблаговолит ли господин Pal объяснить это мелкое несоответствие, и на каком основании он присвоил себе право решать - что является С++, а что - нет.
И не соблаговолит ли господин Pal сообщить все-таки список кошерных (по его мнению) компиляторов С++? Второй раз прошу, между прочим.
Социальные закладки