Инструмент для обнаружения ненужных рекурсивных вызовов в программе?

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

int BinaryTreeMax(Tree* root) {
 if (root == null) return INT_MIN;
 int maxValue = root->value;
 if (maxValue < BinaryTreeMax(root->left))
 maxValue = BinaryTreeMax(root->left); // (1)
 if (maxValue < BinaryTreeMax(root->right))
 maxValue = BinaryTreeMax(root->right); // (2)
 return maxValue;
}

Обратите внимание, что эта программа потенциально делает два полностью избыточных рекурсивных вызова BinaryTreeMax в строках (1) и (2). Мы могли бы переписать этот код так, чтобы не было необходимости в этих дополнительных вызовах, просто кешировав значение из ранее:

int BinaryTreeMax(Tree* root) {
 if (root == null) return INT_MIN;
 int maxValue = root->value;
 int leftValue = BinaryTreeMax(root->left);
 int rightValue = BinaryTreeMax(root->right);
 if (maxValue < leftValue)
 maxValue = leftValue;
 if (maxValue < rightValue)
 maxValue = rightValue;
 return maxValue;
}

Теперь мы делаем ровно два рекурсивных вызова.

Мой вопрос: есть ли инструмент, который выполняет статический или динамический анализ программы (на любом языке, который вам нужен, я не слишком придирчив!), который может определить, делает ли программа абсолютно ненужной рекурсивной звонки. Под "совершенно ненужным" я подразумеваю, что

  • Рекурсивный вызов был выполнен ранее,
  • тем же вызовом рекурсивной функции (или одного из ее потомков) и
  • сам вызов не имеет наблюдаемых побочных эффектов.

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

Кто-нибудь знает о таком инструменте?

2 ответа

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

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

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

Некоторые компиляторы знают, как это сделать (у GCC есть специальный флаг, который предупреждает вас, когда он это делает). Вот статья 2003 года, которую я нашел о проблеме: http://www.cs.cmu.edu/~jsstylos/15745/final.pdf.

Я не мог найти инструмент для этого, но, возможно, что-то, что знает Эрик Липерт, если он случайно столкнется с вашим вопросом.


Некоторые компиляторы (такие как GCC) имеют способы явно обозначить определенные функции (точнее, __attribute__((const)) (см. GCC-функции) применяет некоторые ограничения к телу функции, чтобы его результат зависел только от его аргумента и не получал никакой зависимости от общего состояния программы или других недетерминированных функций). Затем они устраняют повторяющиеся вызовы на дорогостоящие функции. Некоторые другие высокоуровневые языковые реализации (возможно, Haskell) автоматически проверяют это.

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

Кстати, не так сложно написать такую ​​программу, когда у вас уже есть доступ к семантическому дереву кода:)

licensed under cc by-sa 3.0 with attribution.