Короткозамкнутые операторы и хвостовая рекурсия - PullRequest
Новая
       5

Короткозамкнутые операторы и хвостовая рекурсия

6 голосов
/ 15 декабря 2011

Допустим, у меня есть простая функция, подобная этой: 

int all_true(int* bools, int len) {
    if (len < 1) return TRUE;
    return *bools && all_true(bools+1, len-1);
}

Эта функция может быть переписана в более очевидно хвостовой рекурсивной манере следующим образом: 

int all_true(int* bools, int len) {
    if (len < 1) return TRUE;
    if (!*bools) return FALSE;
    return all_true(bools+1, len-1);
}

Логически, естьнулевая разница между двумя;предполагая, что bools содержит только TRUE или FALSE (разумно определены), они делают одно и то же.

Мой вопрос: если компилятор достаточно умен, чтобы оптимизировать второй как хвост-рекурсивныйвызовите, разумно ли ожидать, что он оптимизирует первый таким же образом, учитывая, что "&&" короткое замыкание?Очевидно, что если бы использовался оператор без короткого замыкания, то , а не был бы хвостово-рекурсивным, потому что оба выражения были бы оценены еще до того, как оператор был применен, но мне любопытно, в случае короткого замыкания.

(Прежде, чем я получу поток комментариев, говорящих мне, что компиляторы C обычно не оптимизируют хвостовые рекурсивные вызовы: рассмотрим это как общий вопрос об оптимизации хвостовых рекурсивных вызовов с операторами короткого замыкания, независимымиЯ буду рад переписать это на Scheme, Haskell, OCaml, F #, Python, или что за хрень для вас, если вы не понимаете C.)

1 Ответ

2 голосов
/ 15 декабря 2011

Ваш вопрос действительно "насколько умен компилятор?"но вы не указываете, какой компилятор вы используете.

Учитывая гипотетический разумный компилятор, который преобразует исходный код в промежуточный граф потока перед оптимизацией, оба фрагмента кода, которые вы написали, могут быть представлены одинаково(Оператор &&, хотя и удобен для ввода, не так тривиально скомпилирован, как оператор &; поэтому я не удивлюсь, если его развернуть за один этап на гипотетическом компиляторе).Исходя из этого предположения, разумно утверждать, что ответом на ваш вопрос является «да».

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

...