Оптимизация вызова хвоста помимо хвостовой рекурсии?
Возможна ли какая-либо оптимизация хвостового вызова, кроме хвостовой рекурсии? Я пытался найти или подумать о том, что не связано с рекурсией, но безуспешно. Является ли это возможным? Есть примеры?
Решение
Несомненно, «оптимизация хвостового вызова» на самом деле является термином для этого вида оптимизации в его наиболее общей рекурсивно-независимой форме. Эта оптимизация не заменяет рекурсию эквивалентом while петля или что-то в этом роде. Вместо этого хвостовые вызовы преобразуются так, что кадр стека вызывающей стороны используется повторно. любой код формы return f(...) или же f(...); return поправимо к этому. Это работает для любой fдаже для указателей на функции / замыканий / виртуальных методов, когда компилятор не может знать, что вызывается. Поэтому он также лучше работает с отдельной компиляцией, функциями высшего порядка, поздним связыванием и т. Д.
Если вы посмотрите на достаточное количество кода, будь то функциональный или обязательный, вы найдете случайные вызовы, за которыми ничего не следует. Распространенный случай — когда вызывающий абонент делегируется вызываемому пользователю для основной задачи и выполняет только некоторые дополнительные приготовления. В функциональном коде вы часто найдете много небольших функций, которые выполняют только одну функцию и реализуются в терминах других небольших функций, поэтому вы получаете несколько уровней применения простого преобразования к аргументам, а затем выполняете хвостовой вызов для следующий слой (с преобразованными данными в качестве аргумента). ТШО оптимизирует второй шаг, он (в идеале) делает вызов таким же дешевым, как простой jump и делает красивый модульный код занимающим меньше места в стеке, чем более монолитная реализация. В объектно-ориентированном дизайне вы можете захотеть составить объект из других объектов и предоставить удобные методы, которые делегируют:
SomeClass doSomething(Argument a) {
log.debug("Doing something");
return this.somethingDoer.doIt(a, this.someExtraData);
}
Другим примером, который технически является взаимно рекурсивным, но обычно имеет очень мало активаций любой данной функции (с десятками или сотнями других активаций между ними), являются конечные автоматы, реализованные с помощью функции для каждого состояния и вызова ее для входа в это состояние:
void stateA() {
// do actual work
// determine which transition applies
stateB();
}
void stateB() {
// do actual work
// determine which transition applies
state...();
}
// dozens, possibly hundreds of other states
Другие решения
int bar(int x);
int foo(int x) { return bar(x); }
foo может просто перейти к bar кто возвращается к звонящему напрямую; рекурсия не нужна нигде.