Re[7]: бесконечная рекурсия: почему нет ограничений? - C/C++

Здравствуйте, varnie, Вы писали:

V>интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии. в инете искал, не нашел инфы.

Потому что в С/С++ неопределённое поведение реализуется самым дешёвым из доступных способов

V>stack overflow, но разве нельзя было на уровне языка(ов) это предуcмотреть, введя директиву для установления максимальной глубины вызовов, плюс прицепить вызов а-ля abort() при превышении этого значения.

В других языках программирования — ровно так же.
И потом, максимальная глубина тебе ничего не даст. Сравни

void foo()
{
    if(.....)
        foo();
}

void bar()
{
    int local_data[1000];
    if(.....)
        bar();
}

Предельное количество вызовов до исчерпания стека различается, навскидку, в 500 раз (обычно кадр стека отъедает 2*sizeof(intptr_t)).

Далее, размер стека варьируется в широких пределах: каждому потоку выделяется свой стек, необязательно с дефолтным размером.
А на архитектурах со стеком в виде списка блоков (смолток-машины, лисп-машины) стек принципиально не отличается от динамической памяти. Ты же не требуешь ограничение максимального количества вызовов new?
Впрочем, с динамической памятью всё просто — метнётся исключение. А со стеком — бабахнет, и дело с концом.

Практически же, мы стараемся не допускать рекурсию с асимптотикой глубины >= O(n), если количество операций n неограничено или заведомо велико.
Да и O(n^0.5) я бы побоялся...
То есть, в учебных целях оббежать дерево или массив рекурсивно — можно, но на практике это самоубийство. Вдруг огромное дерево выродится в список?
Просто используются другие алгоритмы; хвостовая рекурсия преобразуется в итерации (руками или компилятором, если у него хватит ума).

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, varnie, Вы писали:

V>интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии. в инете искал, не нашел инфы.
V>берем простой пример:

Я не хочу платить за то что не заказывал.

Здравствуйте, varnie, Вы писали:

V>интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии. в инете искал, не нашел инфы.

Во-первых, нельзя формально отделить бесконечную рекурсию от просто глубокой рекурсии (предложи критерий).
Во-вторых, невозможно определять глубину рекурсии (полный статический анализ невозможен сразу по ряду серьёзных причин).
В-третих, она определяется (ты сам получил уведомление о детектировании бесконечной рекурсии).

з.ы. для тривиальных случаев, как в примере, хороший компилятор (msvc) выдаст варнинг во время компиляции.

Здравствуйте, varnie, Вы писали:

V>верно, я ошибся в своем предположении выше. у нас считается именно суммарное кол-во вызовов ф-ций. и это не то что мне нужно. также я понял что статич переменная одна на все инстанциированные объекты этого класса.
V>скажем, если проинтерпретировать
V>

V>void U() { print(21);     }
V>void T(){ print(20); U(); }
V>void S(){ print(19); T(); }
V>void R(){ print(18); S(); }
V>void Q(){ print(17); R(); }
V>void P(){ print(16); Q(); }
V>void O(){ print(15); P(); }
V>void N(){ print(14); O(); }
V>void M(){ print(13); N(); }
V>void L(){ print(12); M(); }
V>void K(){ print(11); L(); }
V>void J(){ print(10); K(); }
V>void I(){ print(9); J(); }
V>void H(){ print(8); I(); }
V>void G(){ print(7); H(); }
V>void F(){ print(6); G(); }
V>void E(){ print(5); F(); }
V>void D(){ print(4); E(); }
V>void C(){ print(3); D(); }
V>void B(){ print(2); C(); }
V>void A(){ print(1); B(); }

V>{ 
V>    A();  //точка входа
V>}
V>

интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии. в инете искал, не нашел инфы.
берем простой пример:

void f(){
   f();
}

int main()
{
    f();
    return 0;
}

компилим, запускаем: "segmentation fault: 11 (core dumped)".
stack overflow, но разве нельзя было на уровне языка(ов) это предуcмотреть, введя директиву для установления максимальной глубины вызовов, плюс прицепить вызов а-ля abort() при превышении этого значения.
или же создатели С/C++ руководствовались правилом "если вы хотите выстрелить себе в ногу, окей, мы не будем вам в этом мешать"? (вольный пересказ известного крылатого высказывания).
спрашиваю из чистого любопытства. спасибо за инфу.

char* ptr = NULL;
ptr[0] = 0xEB
...

В определенных условиях этот код правильный.

Здравствуйте, remark, Вы писали:

R>Во-вторых, невозможно определять глубину рекурсии (полный статический анализ невозможен сразу по ряду серьёзных причин).
в других языках ведь она присутствует.
R>В-третих, она определяется (ты сам получил уведомление о детектировании бесконечной рекурсии).
если считать что уведомление == "segmentation fault (core dumped)", то да, получил.
R>з.ы. для тривиальных случаев, как в примере, хороший компилятор (msvc) выдаст варнинг во время компиляции.
ясно дело, что должен выдать. видимо, gcc 4.2.1 плохой

варнингов не выдал, даже будучи вызван с "-Wall"

Здравствуйте, varnie, Вы писали:

R>>Во-вторых, невозможно определять глубину рекурсии (полный статический анализ невозможен сразу по ряду серьёзных причин).
V>в других языках ведь она присутствует.

Языки в студию?

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

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, varnie, Вы писали:

R>>>Во-вторых, невозможно определять глубину рекурсии (полный статический анализ невозможен сразу по ряду серьёзных причин).
V>>в других языках ведь она присутствует.

К>Языки в студию?
скажем, в Питоне у нас имеется:

sys.setrecursionlimit

setrecursionlimit( limit)

Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.

The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

собственно, я про что-то подобное применительно к миру С/С++ и осведомлялса изначально.

V>компилим, запускаем: "segmentation fault: 11 (core dumped)".
это и есть ограничение

Здравствуйте, varnie, Вы писали:

V>собственно, я про что-то подобное применительно к миру С/С++ и осведомлялса изначально.

У тебя был выход по segmentation fault. Это такая форма abort().
А какой вариант выхода тебе нужен?

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, varnie, Вы писали:

V>>собственно, я про что-то подобное применительно к миру С/С++ и осведомлялса изначально.

CS>У тебя был выход по segmentation fault. Это такая форма abort().
CS>А какой вариант выхода тебе нужен?
такой, чтобы я имел возможность его перехватить в самой программе и корректно его отработать.

V>void f(){
V>   f();
V>}

V>int main()
V>{
V>    f();
V>    return 0;
V>}
V>

V>компилим, запускаем: "segmentation fault: 11 (core dumped)".
V>stack overflow, но разве нельзя было на уровне языка(ов) это предуcмотреть, введя директиву для установления максимальной глубины вызовов, плюс прицепить вызов а-ля abort() при превышении этого значения.
V>или же создатели С/C++ руководствовались правилом "если вы хотите выстрелить себе в ногу, окей, мы не будем вам в этом мешать"? (вольный пересказ известного крылатого высказывания).
V>спрашиваю из чистого любопытства. спасибо за инфу.

напишите

void f()
{
static int cnt=0;
if (cnt++ > maxRecursion) throw(bla-bla);

ваш код

cnt--;
};

так глубина рекурсии и ловится самым общим образом.
компилятор обнаружить беск. рекурсию не может кроме случая безусловного вызова функцией самой себя.
это простейший случай прямой рекурсии.

однако есть и косвенная рекурсия, когда функция вызывает саму себя
1. через другие функции
2. через функциональные переменные
такую рекурсию компилятор не чувствует.

если язык контролирует глубину рекурсии он делает это аналогично.
в рантайме есть дескрипторы функций с полем — "глубина вызова". поле вызова данной функции инкременируется в прологе функции, проверяется и декрементируется при выходе.
фсе.

Здравствуйте, merk, Вы писали:

M>напишите
//skipped
M>так глубина рекурсии и ловится самым общим образом.
вестимо.
как выше уже заметили, это идеология языка С/C++ — не делать лишних телодвижений

походу этим все и объясняется.
в питоне мы используем ф-цию, указанную мной выше, в С/C++ при подобной задаче прибегаем к симуляции подсчета вызовов ф-ций из самой себя, или к чему-то подобному. жаль что С++ не бросает исключения при сабже — все было бы проще ИМХО.
M>компилятор обнаружить беск. рекурсию не может кроме случая безусловного вызова функцией самой себя.
gcc не обнаружил.

V>как выше уже заметили, это идеология языка С/C++ — не делать лишних телодвижений

походу этим все и объясняется.
V>в питоне мы используем ф-цию, указанную мной выше, в С/C++ при подобной задаче прибегаем к симуляции подсчета вызовов ф-ций из самой себя, или к чему-то подобному. жаль что С++ не бросает исключения при сабже — все было бы проще ИМХО.
M>>компилятор обнаружить беск. рекурсию не может кроме случая безусловного вызова функцией самой себя.
V>gcc не обнаружил.
Реализация стека и его защиты отдана на откуп операционной системе. Точно так же как обращение к мусорным указателям и прочие проблемы неверного использования платформы, под которой работаетп программа. Т.е. в винде/MSVS в принципе вы можете сделать так:

void trans_func( unsigned int u, EXCEPTION_POINTERS* pExp )
{
    throw (unsigned int)pExp->ExceptionRecord->ExceptionCode;
}

void foo()
{
    volatile char c;
    foo();
}

int main()
{
    _set_se_translator(trans_func);
    try
    {
        foo();
    }
    catch(unsigned int code)
    {
        printf("caught code 0x%x\n", code);
    }

    return 0;
}

Либо так:

int main()
{
    __try
         {
         foo();
         }__except(EXCEPTION_EXECUTE_HANDLER)
         {
         }
         return 0;
}

При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
Кстати конечно ничего особо сильно не мешало разработчикам ОС не вводить такие драконовские меры (убивание) при возникновении AV/stack overflow а например молча возвращать мусорное значение из мусорного указателя... Подуймате на досуге, почему так не было сделано.

Здравствуйте, Аноним, Вы писали:

А>Реализация стека и его защиты отдана на откуп операционной системе. Точно так же как обращение к мусорным указателям и прочие проблемы неверного использования платформы, под которой работаетп программа.

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

А>При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
это к чему??? вряд ли ос вообще пользуется тут стеком текущей задачи.
думаю у разработчиков ос хватит ума заниматься системными функциями на собственном стеке. в собственном сегменте.

А>Кстати конечно ничего особо сильно не мешало разработчикам ОС не вводить такие драконовские меры (убивание) при возникновении AV/stack overflow а например молча возвращать мусорное значение из мусорного указателя... Подуймате на досуге, почему так не было сделано.
я лично подумал. я подумал, что это чистый бред, вводящий задачу в совершенно непредсказуемое состояние.

M>это сработала аппаратная защита с выходом за границу сегмента. ос просто привинтила свой обработчик к этому прерыванию. но верно, что именно дело ос определять политику работы приложения, если происходят такие грубые нарушения целостности задачи
stack overflow тоже растет из page fault'а на последней зарезервированной странице стека потока (на обычный платформах).

А>>При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
M>это к чему??? вряд ли ос вообще пользуется тут стеком текущей задачи.
M>думаю у разработчиков ос хватит ума заниматься системными функциями на собственном стеке. в собственном сегменте.
Срочно читать crash course — http://www.microsoft.com/msj/0197/Exception/Exception.aspx
Системные функции работают на системном стеке ядреного "лика" потока. Выплюнутая же в юзер мод ntdll!KiUserExceptionDispatcher работает на стеке и в контексте потока в котором собственно произошел обвал, что легко проверить поставив бряку в обработчике исключения. В случае венды, если вы позовете ExitThread оттуда приложение продолжить себе работать, а тред просто тихо уйдет. А 4кб — потому что в случае stack overflow юзермодный обработчик исключения работает на той самой последней странице стека, при guard page exeption на которой ядро поднимает stack overflow. Кстати если потом ваш ESP стек выйдет за границы и этой последней страницы и у вас выпадет какой нить еще системной исключение — KiUserExceptionDispatcher вызван не будет и ядро молча убьет процесс. Просто перед вызовом KiUserExceptionDispatcher ядро проверяет то что ESP юзермодного контекста укладывается между base и limit стека потока, которые записаны в TEB'е. Это собственно и является причиной тому, что процессы в венде от stack overflow обычно тихо дохнут — дефолтовый UnhandledExceptionFilter попросту не укладывается в эти 4 кб.

А>>Кстати конечно ничего особо сильно не мешало разработчикам ОС не вводить такие драконовские меры (убивание) при возникновении AV/stack overflow а например молча возвращать мусорное значение из мусорного указателя... Подуймате на досуге, почему так не было сделано.
M>я лично подумал. я подумал, что это чистый бред, вводящий задачу в совершенно непредсказуемое состояние.
Вот именно. stack overflow тоже.

Здравствуйте, Аноним, Вы писали:

M>>это сработала аппаратная защита с выходом за границу сегмента. ос просто привинтила свой обработчик к этому прерыванию. но верно, что именно дело ос определять политику работы приложения, если происходят такие грубые нарушения целостности задачи
А>stack overflow тоже растет из page fault'а на последней зарезервированной странице стека потока (на обычный платформах).

А>>>При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
M>>это к чему??? вряд ли ос вообще пользуется тут стеком текущей задачи.
M>>думаю у разработчиков ос хватит ума заниматься системными функциями на собственном стеке. в собственном сегменте.
А>Срочно читать crash course — http://www.microsoft.com/msj/0197/Exception/Exception.aspx
я чета слабо уверен, что разговор касается майкрософта

стек при бесконечной рекурсии обвалится в любой уважающей себя ос, и потому курить майкрософта тут не совсем корректно. тут можно даже категорически наплевать на эти тонкости от MS.
в своем высказывании я лишь имел ввиду, что ос не станет пускать тут свои функции на стеке текущего пользовательского треда, просто в силу некоректности такого подхода. так делать, короче, нельзя.

А>Системные функции работают на системном стеке ядреного "лика" потока. Выплюнутая же в юзер мод ntdll!KiUserExceptionDispatcher работает на стеке и в контексте потока в котором собственно произошел обвал, что легко проверить поставив бряку в обработчике исключения.
это уже выход код пользователя, а я говорил о работе кода оси по выпутыванию из ситуации. естессно при уходе в код юзера, ос обязана каким-то образом "добавить" ему стека для работы, и продолжить код текущего треда.

А>>>>При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
M>>>это к чему??? вряд ли ос вообще пользуется тут стеком текущей задачи.
M>>>думаю у разработчиков ос хватит ума заниматься системными функциями на собственном стеке. в собственном сегменте.
А>>Срочно читать crash course — http://www.microsoft.com/msj/0197/Exception/Exception.aspx
M>я чета слабо уверен, что разговор касается майкрософта

M>стек при бесконечной рекурсии обвалится в любой уважающей себя ос, и потому курить майкрософта тут не совсем корректно. тут можно даже категорически наплевать на эти тонкости от MS.
M>в своем высказывании я лишь имел ввиду, что ос не станет пускать тут свои функции на стеке текущего пользовательского треда, просто в силу некоректности такого подхода. так делать, короче, нельзя.
Добропорядочная ОС и так не "пускает свои функции" на пользовательском стеке. В случае венды и линуха у каждого потока есть специальный, ядреный стек. Аж целых 12кб, а иногда даже больше

А stack overflow это ОС-specific исключительнаы ситуация. В случае венды при этом кидается обычный SEH с кодом 0xc00000fd, в случае линуха процессу шлется kill, или как там у них принято... И ловить такие вещи нужно средствами ОС, а лучше — не допускать их возникновения.

А>>Системные функции работают на системном стеке ядреного "лика" потока. Выплюнутая же в юзер мод ntdll!KiUserExceptionDispatcher работает на стеке и в контексте потока в котором собственно произошел обвал, что легко проверить поставив бряку в обработчике исключения.
M>это уже выход код пользователя, а я говорил о работе кода оси по выпутыванию из ситуации. естессно при уходе в код юзера, ос обязана каким-то образом "добавить" ему стека для работы, и продолжить код текущего треда.
О чем спорим тогда? Спать пора...

Кстати вот занятный код:

class SehException
{
public:
    DWORD code;
    PVOID stk_handler, stk_exception, address;

    SehException(EXCEPTION_POINTERS* pExp)
        : code(pExp->ExceptionRecord->ExceptionCode),
        address(pExp->ExceptionRecord->ExceptionAddress)
    {
        stk_handler = (PVOID)&pExp;
        stk_exception = (PVOID)pExp->ContextRecord->Esp;
    }
};

void trans_func( unsigned int u, EXCEPTION_POINTERS* pExp )
{
    throw SehException(pExp);
}


void foo()
{
    volatile char c;
    foo();
}

int main()
{
    volatile char stk;
    MEMORY_BASIC_INFORMATION mbi = {0};
    VirtualQuery((LPCVOID)&stk, &mbi, sizeof(mbi));
    ULONG size = 0;
    for(;;size+=0x1000)
    {
        MEMORY_BASIC_INFORMATION mbi_test = {0};
        VirtualQuery((PCHAR)mbi.AllocationBase+size, &mbi_test, sizeof(mbi_test));
        if (mbi_test.AllocationBase!=mbi.AllocationBase)  break;
    }
    _set_se_translator(trans_func);
    try
    {
        foo();
    }
    catch(SehException &seh)
    {
        printf("caught code=0x%x address=0x%x\nstack: base=0x%x before=0x%x handler=0x%x exception=0x%x remain=0x%x size=0x%x\n", 
            seh.code, seh.address, mbi.AllocationBase, &stk, seh.stk_handler, seh.stk_exception, 
            (unsigned int)seh.stk_exception - (unsigned int)mbi.AllocationBase, size);
    }

    return 0;
}

результат у меня
[quote]
caught code=0xc00000fd address=0x401060
stack: base=0x30000 before=0x12ff18 handler=0x32ab8 exception=0x33000 remain=0x3000 size=0x100000
[/quote]
Походу я ошибся насчет 4 кб, ядро венды кидает SEH на 3й странице от базы, обработчику остается 12кб

Здравствуйте, Аноним, Вы писали:

А>>>>>При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
M>>>>это к чему??? вряд ли ос вообще пользуется тут стеком текущей задачи.
M>>>>думаю у разработчиков ос хватит ума заниматься системными функциями на собственном стеке. в собственном сегменте.
А>>>Срочно читать crash course — http://www.microsoft.com/msj/0197/Exception/Exception.aspx
M>>я чета слабо уверен, что разговор касается майкрософта

M>>стек при бесконечной рекурсии обвалится в любой уважающей себя ос, и потому курить майкрософта тут не совсем корректно. тут можно даже категорически наплевать на эти тонкости от MS.
M>>в своем высказывании я лишь имел ввиду, что ос не станет пускать тут свои функции на стеке текущего пользовательского треда, просто в силу некоректности такого подхода. так делать, короче, нельзя.
А>Добропорядочная ОС и так не "пускает свои функции" на пользовательском стеке. В случае венды и линуха у каждого потока есть специальный, ядреный стек. Аж целых 12кб, а иногда даже больше

ну он должен быть в данном случае. поскольку осевые функции тут будут выполняться под защитой, и потому треду пользователя нужен и свой кусок стека в ядре. но оси то бывают разныя. да и понятие ядра не строго специфицировано. оно может быть и микроядром и наноядром каким-нить. и то что в одной ос считается осевой функцией под защитой, в другой вообще орудует на пользовательском стеке, без защиты. ну там всякие ртос например.
лично мне импонируют микроядра.

А>А stack overflow это ОС-specific исключительнаы ситуация. В случае венды при этом кидается обычный SEH с кодом 0xc00000fd, в случае линуха процессу шлется kill, или как там у них принято... И ловить такие вещи нужно средствами ОС, а лучше — не допускать их возникновения.
ну винду я особо изнутри не знаю... я рассуждаю концептульно. типа вот есть некая ос, вот она должна делать то-то и то-то..как это должно работать, чтобы оно работало.
и фсе.

Здравствуйте, Аноним, Вы писали:

А>Кстати вот занятный код:

А>

А>class SehException
А>{
А>public:
А>    DWORD code;
А>    PVOID stk_handler, stk_exception, address;

А>    SehException(EXCEPTION_POINTERS* pExp)
А>        : code(pExp->ExceptionRecord->ExceptionCode),
А>        address(pExp->ExceptionRecord->ExceptionAddress)
А>    {
А>        stk_handler = (PVOID)&pExp;
А>        stk_exception = (PVOID)pExp->ContextRecord->Esp;
А>    }
А>};

А>void trans_func( unsigned int u, EXCEPTION_POINTERS* pExp )
А>{
А>    throw SehException(pExp);
А>}


А>void foo()
А>{
А>    volatile char c;
А>    foo();
А>}

А>int main()
А>{
А>    volatile char stk;
А>    MEMORY_BASIC_INFORMATION mbi = {0};
А>    VirtualQuery((LPCVOID)&stk, &mbi, sizeof(mbi));
А>    ULONG size = 0;
А>    for(;;size+=0x1000)
А>    {
А>        MEMORY_BASIC_INFORMATION mbi_test = {0};
А>        VirtualQuery((PCHAR)mbi.AllocationBase+size, &mbi_test, sizeof(mbi_test));
А>        if (mbi_test.AllocationBase!=mbi.AllocationBase)  break;
А>    }
А>    _set_se_translator(trans_func);
А>    try
А>    {
А>        foo();
А>    }
А>    catch(SehException &seh)
А>    {
А>        printf("caught code=0x%x address=0x%x\nstack: base=0x%x before=0x%x handler=0x%x exception=0x%x remain=0x%x size=0x%x\n", 
А>            seh.code, seh.address, mbi.AllocationBase, &stk, seh.stk_handler, seh.stk_exception, 
А>            (unsigned int)seh.stk_exception - (unsigned int)mbi.AllocationBase, size);
А>    }

А>    return 0;
А>}

А>

А>результат у меня
А>[quote]
А>caught code=0xc00000fd address=0x401060
А>stack: base=0x30000 before=0x12ff18 handler=0x32ab8 exception=0x33000 remain=0x3000 size=0x100000
А>[/quote]
А>Походу я ошибся насчет 4 кб, ядро венды кидает SEH на 3й странице от базы, обработчику остается 12кб
я вот тоже подумал, почему они должны оставлять одну страницу в запас, а не N? оказалось три. где-то может и конфигурируется

типо хак

Здравствуйте, varnie, Вы писали:

V>интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии.

Видимо, потому что в языках C/C++ бесконечная рекурсия вполне легальна. Ее незачем предотвращать.

V>берем простой пример:

V>void f(){
V>   f();
V>}

V>int main()
V>{
V>    f();
V>    return 0;
V>}

Это полностью корректная программа, которую абстрактная машина должна выполнять бесконечно.

V>stack overflow, но разве нельзя было на уровне языка(ов) это предуcмотреть

А на уровне языка нет никакого stack. Соответственно, не может быть никакого overflow.

вопрос в догонку. правильно ли я понимаю, что в коде ниже под каждый инстанциированный объект класса Test в его методе-функции foo() при её вызове будет заведена _своя_ статическая переменная?

#define MAX_EXECUTION_DEPTH 100
class Test{
public:
   //...
   void foo() const{
       static int cnt = 0;
       if (cnt++ < MAX_EXECUTION_DEPTH){
          
           //do smth useful here

           --cnt;
       }
   }
};

int main(){
  Test t1, t2, t3;
  t1.foo(); t2.foo(); t3.foo();

  return 0;
}

Здравствуйте, Аноним, Вы писали:

А>Кстати вот занятный код:

А>

А>...
А>    _set_se_translator(trans_func);
А>...
А>

А старый обработчик кто будет восстанавливать ?

V>void f(){
V>   f();
V>}

V>int main()
V>{
V>    f();
V>    return 0;
V>}
V>

Но ведь и сборки мусора нет в С++. И в этом его прелесть. Программы получаются быстрые, максимально приближенные к программам на ассемблере.

все понял (собственно, что я предполагал, то и оказалось верным), но все же хотел на всякий случай поинтересоваться ввиду моего пытливого ума.
еще бы кто-нибудь прояснил мне касаемо моего утверждения двумя постами выше, и я бы успокоилса

Здравствуйте, varnie, Вы писали:

Поведенческого анализа нет практически во всех языках.
Его очень сложно реализовать. Вы привели простой пример, а если в f() много еще чего натыкано и даже return есть (но никогда не вызовется).
Проверка есть только синтаксическая ...

Думаю этого анализа нет, так как по идее нужно анализировать одновременно и код и синтаксис, то есть в общем случае сделать невозможно для release компиляции, но для debug реально.

Вероятно в скором времени появится. Сейчас идет работа над внедрением PHP в структуру ASP.NET. А PHP нетипитизированный язык, придется делать какие-то проверки ... тогда и это внедрят по ходу дела.

ЗЫ: а кто Вам мешает подобную проверку разработать самому?

Здравствуйте, varnie, Вы писали:

V>вопрос в догонку. правильно ли я понимаю, что в коде ниже под каждый инстанциированный объект класса Test в его методе-функции foo() при её вызове будет заведена _своя_ статическая переменная?
V>

V>#define MAX_EXECUTION_DEPTH 100
V>class Test{
V>public:
V>   //...
V>   void foo() const{
V>       static int cnt = 0;
V>       if (cnt++ < MAX_EXECUTION_DEPTH){
          
V>           //do smth useful here

V>           --cnt;
V>       }
V>   }
V>};

V>int main(){
V>  Test t1, t2, t3;
V>  t1.foo(); t2.foo(); t3.foo();

V>  return 0;
V>}
V>

Здравствуйте, merk, Вы писали:
//skipped

эээ, а ответ где?

V>#define MAX_EXECUTION_DEPTH 100
V>class Test{
V>public:
V>   //...
V>   void foo() const{
V>       static int cnt = 0;
V>       if (cnt++ < MAX_EXECUTION_DEPTH){
          
V>           //do smth useful here

V>           --cnt;
V>       }
V>   }
V>};

V>int main(){
V>  Test t1, t2, t3;
V>  t1.foo(); t2.foo(); t3.foo();

V>  return 0;
V>}
V>

нет конечно. все static переменные входят в область глобальных переменных. размер которой расчитывается линкером. таким образом это переменная одна на весь класс вообще.
static это просто декларация ГЛОБАЛЬНОЙ переменной ограниченной видимости. инициализируется тоже при инициализации глобальных переменных.

Здравствуйте, varnie, Вы писали:

V>Здравствуйте, merk, Вы писали:
V>//skipped

V>эээ, а ответ где?

кнопочку нажал не ту...ответ ниже

template<int>
struct Test
{
  void foo() const{
       static int cnt = 0;
       //...
  }
};

int main()
{
  Test<__LINE__> t1, t2;
  Test<__LINE__> t3;
  Test<__LINE__> t4;

  t1.foo();
  t2.foo();
  t3.foo();
  t4.foo();
}

Здесь будет три статических объекта.

Здравствуйте, varnie, Вы писали:

V>Здравствуйте, c-smile, Вы писали:

CS>>Здравствуйте, varnie, Вы писали:

V>>>собственно, я про что-то подобное применительно к миру С/С++ и осведомлялса изначально.

CS>>У тебя был выход по segmentation fault. Это такая форма abort().
CS>>А какой вариант выхода тебе нужен?
V>такой, чтобы я имел возможность его перехватить в самой программе и корректно его отработать.
Ага, обработаешь. у тебя ведь стековая память кончилась. запуск процедуры, у которой будут локальные параметры приведёт к исключению (нет то где их разместить), хотя банально может не быть места под собственно само сохранение адреса возврата.

... << RSDN@Home 1.2.0 alpha rev. 787>>

Здравствуйте, Юрий Жмеренецкий, Вы писали:

ЮЖ>Здравствуйте, varnie, Вы писали:

V>>вопрос в догонку. правильно ли я понимаю, что в коде ниже под каждый инстанциированный объект класса Test в его методе-функции foo() при её вызове будет заведена _своя_ статическая переменная?

ЮЖ>Нет, будет одна на всех, от количества вызовов не зависит.
ЮЖ>Вот так будет несколько:
ЮЖ>

ЮЖ>template<int>
ЮЖ>struct Test
ЮЖ>{
ЮЖ>  void foo() const{
ЮЖ>       static int cnt = 0;
ЮЖ>       //...
ЮЖ>  }
ЮЖ>};

ЮЖ>int main()
ЮЖ>{
ЮЖ>  Test<__LINE__> t1, t2;
ЮЖ>  Test<__LINE__> t3;
ЮЖ>  Test<__LINE__> t4;

ЮЖ>  t1.foo();
ЮЖ>  t2.foo();
ЮЖ>  t3.foo();
ЮЖ>  t4.foo();
ЮЖ>}
ЮЖ>

ЮЖ>Здесь будет три статических объекта.

вы человека путаете. если тут будут три обьекта, то тут будут три разных инстанцированных типа. а это уже высокие материи. а что такое __LINE__?

Здравствуйте, OdesitVadim, Вы писали:

OV>Здравствуйте, varnie, Вы писали:

V>>Здравствуйте, c-smile, Вы писали:

CS>>>Здравствуйте, varnie, Вы писали:

V>>>>собственно, я про что-то подобное применительно к миру С/С++ и осведомлялса изначально.

CS>>>У тебя был выход по segmentation fault. Это такая форма abort().
CS>>>А какой вариант выхода тебе нужен?
V>>такой, чтобы я имел возможность его перехватить в самой программе и корректно его отработать.
OV>Ага, обработаешь. у тебя ведь стековая память кончилась. запуск процедуры, у которой будут локальные параметры приведёт к исключению (нет то где их разместить), хотя банально может не быть места под собственно само сохранение адреса возврата.

стековая память еще не кончилась в нормальной ос.
ос начинает такую панику несколько ранее, имея в запасе некую часть пользовтательского стека, именно для возможности им обработки ошибок. например ос вводит в доступные еще одну страницу стека пользователя. но если пользователь и этот кусок исчерпает ос уронит весь процесс.
тут мы это с анонимом обсуждали.
и это правльное поведение оси.

Здравствуйте, merk, Вы писали:
...
M>вы человека путаете. если тут будут три обьекта, то тут будут три разных инстанцированных типа. а это уже высокие материи.
Да, тут три разных типа. Просто хотел показать когда может быть "несколько" объектов.

M>а что такое __LINE__?
Число — номер строки.

Здравствуйте, varnie, Вы писали:

V>интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии. в инете искал, не нашел инфы.

Стоит подумать, сколько раз в жижни среднего программиста — С++-ника встречается такая бага и сколько времени в среднем уходит на отладку. Я думаю и то и другое незначительно.

--
Sergey Chadov

... << RSDN@Home 1.2.0 alpha rev. 685>>

Здравствуйте, merk

хмм, а как тогда объяснить вот это:

у меня есть класс примерно как класс Test выше (реализующий семантику "функция"), один в один с таким же механизмом предотвращения выполнения ф-ции на глубину превышающую MAX_EXECUTION_DEPTH (перед и после вызова самого исполнения ф-ции я воткнул printf("counter=%d\n", counter)

void CFunction::invoke() { 
    // printf("exec");
    
    static std::size_t counter = 0;
    
    if (_pStmtPtr != NULL) {
       if (counter++ < MAX_FUNCTION_EXECUTION_DEPTH){
          printf("counter=%d\n", counter);
        _pStmtPtr->exec();
         printf("counter=%d\n", counter);
        --counter;
       }else{
          throw CRunTimeException(NULL, "stack depth exceeded");
       }
        
    }
}

и интерпретируется у меня к примеру вот такой код на моем языке:
test1.src

bool test(){}          //для этой ф-ции заведется объект класса CFunction
void C(int i){ C(); }  //для этой еще один

{ //точка входа        //и для этой.
  C(1);
}

для этого случая я вижу:

counter=1
counter=2
counter=3
counter=4
counter=5
counter=6
...
counter=20
"stack depth exceeded" //сработала моя проверка на глубину больше 20. все верно.

далее, интерпретируемый сорец на своем языке я заменяю на:
test2.src

bool test(){}
void C(int i){ test(); test(); test(); test(); test(); test(); test(); test(); test(); test();

{ //точка входа
  C(1);
}

вывод:

counter=1
counter=2
counter=2
counter=1

это не беск. рекурсия, и мой вывод подтверждает корректность реализованных действий. (счетчик увеличился только дважды)
я несколько запутан о том, как понимать эти выводы, но факт в том что я вышерасписанным способом через заведние статич. переменной и отслеживанием её значения реализовал простое предотвращение превышение глубины вызова ф-ций самих из себя.

если взять на вооружение что вы сказали что статич. переменная в методе класса одна на все объекты этого класса, тогда я не догоняю, как тогда понять результаты выше?
спасибо за прояснение.

добавочка:
если в src2 будут какие-либо действия в ф-ции test()

void test(){print(2);}
void C(int i){ test(); test(); test(); }

{ C(1); }

то вывод будет:

counter=1
counter=2
counter=3
2 //вывод из тела test()
counter=3
counter=3
2 //вывод из тела test()
counter=3
counter=3
2 //вывод из тела test()
counter=3
counter=2
counter=1

все логично опять же

Здравствуйте, varnie, Вы писали:

V>Здравствуйте, merk

V>хмм, а как тогда объяснить вот это:

V>у меня есть класс примерно как класс Test выше (реализующий семантику "функция"), один в один с таким же механизмом предотвращения выполнения ф-ции на глубину превышающую MAX_EXECUTION_DEPTH (перед и после вызова самого исполнения ф-ции я воткнул printf("counter=%d\n", counter)

.
V>

V>void CFunction::invoke() { 
V>    // printf("exec");
    
V>    static std::size_t counter = 0;
    
V>    if (_pStmtPtr != NULL) {
V>       if (counter++ < MAX_FUNCTION_EXECUTION_DEPTH){
V>          printf("counter=%d\n", counter);
V>        _pStmtPtr->exec();
V>         printf("counter=%d\n", counter);
V>        --counter;
V>       }else{
V>          throw CRunTimeException(NULL, "stack depth exceeded");
V>       }
        
V>    }
V>}
V>

V>и интерпретируется у меня к примеру вот такой код на моем языке:
V>test1.src
V>

V>bool test(){}          //для этой ф-ции заведется объект класса CFunction
V>void C(int i){ C(); }  //для этой еще один

V>{ //точка входа        //и для этой.
V>  C(1);
V>}
V>

V>для этого случая я вижу:
V>

V>counter=1
V>counter=2
V>counter=3
V>counter=4
V>counter=5
V>counter=6
V>...
V>counter=20
V>"stack depth exceeded" //сработала моя проверка на глубину больше 20. все верно.

V>далее, интерпретируемый сорец на своем языке я заменяю на:
V>test2.src
V>

V>bool test(){}
V>void C(int i){ test(); test(); test(); test(); test(); test(); test(); test(); test(); test();

V>{ //точка входа
V>  C(1);
V>}
V>

V>вывод:
V>

V>counter=1
V>counter=2
V>counter=2
V>counter=1

V>это не беск. рекурсия, и мой вывод подтверждает корректность реализованных действий. (счетчик увеличился только дважды)
V>я несколько запутан о том, как понимать эти выводы, но факт в том что я вышерасписанным способом через заведние статич. переменной и отслеживанием её значения реализовал простое предотвращение превышение глубины вызова ф-ций самих из себя.

V>если взять на вооружение что вы сказали что статич. переменная в методе класса одна на все объекты этого класса, тогда я не догоняю, как тогда понять результаты выше?
V>спасибо за прояснение.

зачем вам переменная на класс, если у вас должна быть своя переменная на каждую функцию.
если ваша invoke просто типо вызов произвольной функции в каком-то интерпретаторе, то вы считаете общую глубину вызовов в вашем интерпретаторе...или я чета не понял.
у меня сейчас ребенок на руках, нет времени долго всматриваться в текст.
смогу точней ответить только позже.

верно, я ошибся в своем предположении выше. у нас считается именно суммарное кол-во вызовов ф-ций. и это не то что мне нужно. также я понял что статич переменная одна на все инстанциированные объекты этого класса.
скажем, если проинтерпретировать

void U() { print(21);     }
void T(){ print(20); U(); }
void S(){ print(19); T(); }
void R(){ print(18); S(); }
void Q(){ print(17); R(); }
void P(){ print(16); Q(); }
void O(){ print(15); P(); }
void N(){ print(14); O(); }
void M(){ print(13); N(); }
void L(){ print(12); M(); }
void K(){ print(11); L(); }
void J(){ print(10); K(); }
void I(){ print(9); J(); }
void H(){ print(8); I(); }
void G(){ print(7); H(); }
void F(){ print(6); G(); }
void E(){ print(5); F(); }
void D(){ print(4); E(); }
void C(){ print(3); D(); }
void B(){ print(2); C(); }
void A(){ print(1); B(); }

{ 
    A();  //точка входа
}

то мы также получим сообщение что "stack depth exceeded", хотя никакой рекурсии, очевидно, и нет.
значит подходом с статик переменной мою задачу не решить и надо заводить доп. член на кажд ф-цию для хранения числа её вызовов. при вызове ф-ции мы инкрементируем этот счетчик, при выходе из нее -- декрементируем. если привышаем, скажем, 20, кидаем исключение как в коде выше. сейчас попробую. спасибо за помощь выше.

V>void U() { print(21);     }
V>void T(){ print(20); U(); }
V>void S(){ print(19); T(); }
V>void R(){ print(18); S(); }
V>void Q(){ print(17); R(); }
V>void P(){ print(16); Q(); }
V>void O(){ print(15); P(); }
V>void N(){ print(14); O(); }
V>void M(){ print(13); N(); }
V>void L(){ print(12); M(); }
V>void K(){ print(11); L(); }
V>void J(){ print(10); K(); }
V>void I(){ print(9); J(); }
V>void H(){ print(8); I(); }
V>void G(){ print(7); H(); }
V>void F(){ print(6); G(); }
V>void E(){ print(5); F(); }
V>void D(){ print(4); E(); }
V>void C(){ print(3); D(); }
V>void B(){ print(2); C(); }
V>void A(){ print(1); B(); }

V>{ 
V>    A();  //точка входа
V>}
V>

V>то мы также получим сообщение что "stack depth exceeded", хотя никакой рекурсии, очевидно, и нет.
V>значит подходом с статик переменной мою задачу не решить и надо заводить доп. член на кажд ф-цию для хранения числа её вызовов. при вызове ф-ции мы инкрементируем этот счетчик, при выходе из нее -- декрементируем. если привышаем, скажем, 20, кидаем исключение как в коде выше. сейчас попробую. спасибо за помощь выше.

вы чета путаете. рекурсия не является проблемой, пока она не приводит к проблеме невычислимости. бесконечная рекурсия — это просто невычислимость. на попытку вычислить которую тратятся ресурсы и в конце концов истощаются.
что вас таким образом волнует?
счетчик на каждую функцию не является показательным. потому что рекурсия может быть косвенной, когда как в вашем этом примере N-функций будут друг друга вызывать по цепочке, и глубина стека(что есть на самом деле — глубина "вычислений") будет расти и потом последняя функция вызовет первую.
тогда при оьщей глубине стека в 2N вызовов, каждая функция будет вызвана только дважды.
вам на самом деле нужна именно глубина "вычислений", которая является показателем "сложности", и вам нужно ограничивать именно сложность.
то есть вам нужна именно общая переменная на все вызовы.
с учетом того, что если есть треды, нужно либо держать по такой переменной на каждый тред, либо иметь общую на все треды, но тогда делать доступ к ней атомарным или через мьютекс.

Здравствуйте, merk, Вы писали:
M>вам на самом деле нужна именно глубина "вычислений", которая является показателем "сложности", и вам нужно ограничивать именно сложность.
M>то есть вам нужна именно общая переменная на все вызовы.
теперь понял, угу. согласен. сразу как-то не мог все это в голове удержать.
M>с учетом того, что если есть треды, нужно либо держать по такой переменной на каждый тред, либо иметь общую на все треды, но тогда делать доступ к ней атомарным или через мьютекс.
тредов нету.
большое спасибо вам еще раз.

Добрый вечер, remark, Вы писали:

R>нельзя формально отделить бесконечную рекурсию от просто глубокой рекурсии (предложи критерий).
Вроде тут даже критерии не особо нужны — это утверждение математически доказывается (т.н. "проблема остановки")

R>з.ы. для тривиальных случаев, как в примере, хороший компилятор (msvc) выдаст варнинг во время компиляции.
Да! Я люблю Microsoft

Здравствуйте, Константин, Вы писали:

R>>нельзя формально отделить бесконечную рекурсию от просто глубокой рекурсии (предложи критерий).

К>Вроде тут даже критерии не особо нужны — это утверждение математически доказывается (т.н. "проблема остановки")

Можно переформулировать — как отличить очень глубокую желательную рекурсию от очень глубокой желательной рекурсии (ошибки в программе). Допустим глубина рекурсии зависит от входных данных, и формально останавливается. Домен входных данных компилятору не известен.

	От:	Кодт
	Дата:	08.07.08 19:37
	Оценка:	6 (1) -1

	От:	Daevaorn
	Дата:	08.07.08 19:10
	Оценка:	1 (1) +1

От:	remark	http://www.1024cores.net/
Дата:	08.07.08 19:15
Оценка:	1 (1) +1

	От:	merk
	Дата:	09.07.08 19:02
	Оценка:	3 (1)

	От:	varnie
	Дата:	08.07.08 19:07
	Оценка:

От:	c-smile	http://terrainformatica.com
Дата:	08.07.08 20:29
Оценка:

От:	Юрий Жмеренецкий	ICQ 380412032
Дата:	09.07.08 13:06
Оценка:

От:	Infix	http://polos75.livejournal.com/
Дата:	09.07.08 16:03
Оценка:

От:	Clevelus	http://clevelus.ru
Дата:	09.07.08 16:33
Оценка:

	От:	Константин
	Дата:	09.07.08 23:29
	Оценка: