Существует ли код C++, который компилируется бесконечно долго?

Я часто слышу о том, что "исходники C++ требуют много времени и памяти для компиляции".

Я также слышал о том, что шаблон C++ завершен по Тьюрингу, поэтому он может страдать от проблемы остановки.

Я также создал проект C++, который требует 8 ГБ памяти и 2 часов времени.

Итак, возникает вопрос: Существует ли код C++, который компилируется бесконечно долго?

(Вложенные включения или вложенные шаблоны обнаруживаются, поэтому их не следует учитывать.)

Связанный вопрос: Есть ли код C++, который компилируется с бесконечной памятью? (я разделил их, так как ожидаю другого ответа.)


person Star Brilliant    schedule 03.01.2015    source источник
comment
Откуда кто-нибудь знает - но я думаю, вы можете подождать, пока это не закончится?   -  person Ed Heal    schedule 03.01.2015
comment
Теоретически возможно создать некоторый исходный код, компиляция которого для универсального и чистого компилятора C++ потребует бесконечного времени. Практически и с современным компилятором? Вероятно, это невозможно.   -  person Some programmer dude    schedule 03.01.2015
comment
Ограничения по глубине приводят к тому, что время компиляции конечно, но, вероятно, довольно легко сделать программу, которая компилируется дольше, чем время жизни вселенной.   -  person zch    schedule 03.01.2015
comment
По определению, если для компиляции требуется бесконечное время, компиляция не завершится за конечное время.   -  person Elliott Frisch    schedule 03.01.2015
comment
Поскольку сам шаблон С++, если Тьюринг завершен, он страдает от проблемы остановки (погуглите). Итак, существует ли допустимая программа на C++, удовлетворяющая условиям, благодаря которым компилятор никогда не останавливается? @ЭдХил   -  person Star Brilliant    schedule 03.01.2015
comment
@EdHeal Откуда мне знать, что while ( true ) { } никогда не останавливается? Потому что это четко определено. Вам не обязательно запускать что-то, чтобы знать, как долго оно будет работать.   -  person stefan    schedule 03.01.2015
comment
Это была попытка пошутить над глупым вопросом. Кстати, компьютер в конечном итоге остановится - аппаратный сбой для начала   -  person Ed Heal    schedule 03.01.2015
comment
Это правда, что ваши два вопроса являются отдельными вопросами, но между ними есть следствие: требуется бесконечное количество времени, чтобы выделить бесконечную память из конечных кусков (или, наоборот, если вы предпочитаете, если компиляция завершается за конечное время, посмотрите при том, сколько памяти было использовано: это количество памяти, необходимое для компиляции). Так что можно было бы начать с одного вопроса.   -  person Pascal Cuoq    schedule 03.01.2015
comment
Этот вопрос кажется не по теме, потому что он не касается практической проблемы программирования, с которой сталкивается OP.   -  person Pascal Cuoq    schedule 03.01.2015
comment
@PascalCuoq Может быть, мне следует переместить вопрос в другой тег?   -  person Star Brilliant    schedule 03.01.2015
comment
Я предполагаю, что этот вопрос эквивалентен вопросу Можем ли мы создать шаблон C++, который бесконечно зацикливается, не требуя бесконечной глубины рекурсии? на что я бы наивно ответил Нет.   -  person filmor    schedule 03.01.2015
comment
(Вложенные включения или вложенные шаблоны можно обнаружить, поэтому они не должны учитываться.) -- Все остальное, о чем вы можете подумать, также можно обнаружить. Проблема остановки говорит о том, что не существует программы, которая может обнаружить все программы, которые не останавливаются. Однако для каждой программы A, которая не останавливается, существует программа B, которая может определить программу A как не останавливающуюся. Единственный способ получить разумные ответы — это снять это ограничение: разрешать ответы, если какой-либо компилятор никогда не остановится.   -  person    schedule 03.01.2015
comment
Код — это не вещь.   -  person Griwes    schedule 04.01.2015


Ответы (1)


теоретически это будет компилироваться за «бесконечное» время, потому что расширение шаблона бесконечно рекурсивно:

template <size_t N>
struct eat
{
    static constexpr size_t value = eat<N+1>::value;
};

Однако все компиляторы, которые я использовал, защищаются от такого кода, выдавая примерно такую ​​ошибку:

/Users/richardh/Documents/dev/Scratchpad/tryit/tryit/words.cpp:136:37: fatal error: recursive template instantiation exceeded maximum depth of 256
    static constexpr size_t value = eat<N+1>::value;
                                    ^
/Users/richardh/Documents/dev/Scratchpad/tryit/tryit/words.cpp:136:37: note: in instantiation of template class 'eat<257>' requested here
    static constexpr size_t value = eat<N+1>::value;
                                    ^
/Users/richardh/Documents/dev/Scratchpad/tryit/tryit/words.cpp:136:37: note: in instantiation of template class 'eat<256>' requested here
    static constexpr size_t value = eat<N+1>::value;
                                    ^
/Users/richardh/Documents/dev/Scratchpad/tryit/tryit/words.cpp:136:37: note: in instantiation of template class 'eat<255>' requested here
    static constexpr size_t value = eat<N+1>::value;
                                    ^
/Users/richardh/Documents/dev/Scratchpad/tryit/tryit/words.cpp:136:37: note: in instantiation of template class 'eat<254>' requested here
    static constexpr size_t value = eat<N+1>::value;

...так далее

РЕДАКТИРОВАТЬ: хорошо, я думаю, что это действительно бесконечно:

template <class T>
struct eat2
{
    using inner = eat2<eat2<T>>;
    static constexpr int value() {
        return inner::value();
    }
};

int main()
{
    eat2<int> e;
    cout << e.value() << endl;
    return 0;
}
person Richard Hodges    schedule 03.01.2015
comment
Это не будет бесконечным, даже если вы увеличите глубину рекурсии (для меня это работает до 1139), поскольку size_t имеет конечный набор значений. - person filmor; 03.01.2015
comment
Достаточно справедливо, он (теоретически) перестанет компилироваться, как только N перевернется после 2 ^ 64 (на моем компиляторе) итераций. - person Richard Hodges; 03.01.2015
comment
@filmor Тривиально расширить этот код, чтобы добавить новый параметр шаблона с новым счетчиком, как только значение достигнет максимального значения size_t. - person stefan; 03.01.2015
comment
Я уже читал другой подобный пример stackoverflow.com/a/6079650/2557927 . И я ценю ваш ответ. - person Star Brilliant; 03.01.2015