Как известно, дьявол скрывается в деталях. Порою, небольшая деталь может сильно изменить смысл. Получается эффект бабочки. Что-то такое иногда происходит с пониманием хвостовой рекурсии. Мне всегда эта тема казалось сложной.
В прошлом году вышел замечательный перевод книги Пола Грэма "ANSI Common Lisp". В оригинале этой книги на странице 216 есть такое предложение: "A good compiler can compile a tail call into a goto, and so can compile a tail-recursive function into a loop". Дальше идет довольно общее описание того, как это может быть сделано.
Проблема в том, что без знания контекста тот текст можно неправильно истолковать. Все встает на свои места, если обратиться к книге PAIP Питера Норвига, которую Пол Грэм безусловно читал. В той книге приведена некая абстрактная машина. Там действительно хвостовая рекурсия компилируется в циклы, но в циклы не языка высокого уровня, а в циклы ассемблера той абстрактной машины (фактически через goto). Вот, в чем загвоздка.
Многие почему-то считают, что хвостовую рекурсию можно всегда преобразовать в циклы Scala, F# или Common Lisp. Мне кажется это неправильным. Можно придумать контр-пример. Достаточно обернуть рекурсивный вызов в лямбду и дальше передать эту лямбду другой функции. Например, компилятор Scala не сможет это превратить в цикл на уровне явовского байт-кода, а на уровне абстрактной машины из PAIP цикл получился бы сам собою.
Пример был бы очень к месту.
ОтветитьУдалить@migmit Почему-то ответ на твой запрос попал вниз.
УдалитьЛямбда превращает (или пытается превращать -- такую лямбду компилятор может и заинлайнить) в более общее понятие -- хвостовой вызов. Вот его в цикл не превратишь в общем случае, а goto справляется с ним, не моргнув.
ОтветитьУдалить@Ivan Boldyrev Тут мне кажется, что могут возникнуть терминологические споры. Да, я немного заострил :)
УдалитьКогда мы оборачиваем рекурсивный вызов в лямбду, то получается, что функция последним своим делом вызывает саму себя, но не на прямую, а опосредованно. При этом все вызовы могут быть вполне хвостовым. Получается довольно непростая хвостовая рекурсия, хотя некоторые могут поспорить с точность формулировки. Еще один пример, где может не быть единого мнения.
Да что тут спорить: хвостовая рекурсия -- это частный случай хвостового вызова.
УдалитьЕсли мы добавляем дополнительную функцию (не важно, анонимную или именованную), то это называется непрямая (или косвенная, не помню точно) хвостовая рекурсия (пример: две функции, flip и flop, которые вызывают друг друга).
А, не знал, что есть термин о непрямой (косвенной) хвостовой рекурсии. Это попадает в точку.
УдалитьПросто, такие посты помогают самому разобраться в терминологии (или еще больше запутаться). Есть у меня еще одна задумка сильно потроллить на тему функционального, императивного и декларативного стилей :)
В Programming in Scala черным по белому написано, что хвостовая рекурсия в Scala тупа, как пробка. Если функция последним действием вызывает саму себя, эта оптимизация применяется, иначе - нет. Упомянутый вами случай явно не является простым.
ОтветитьУдалить@afiskon Я прочитал первое издание Programming in Scala. Да, по-моему там говорится, что оптимизация хвостовой рекурсии в Scala неполная, хотя подтвердить свои слова сейчас не могу.
Удалить> Если функция последним действием вызывает саму себя, эта оптимизация применяется, иначе - нет
УдалитьТак она и может последним действием вызывать саму себя опосредованно через лямбду (см. мой комментарий выше), где скаловский оптимизатор уже не работает, но здесь тонкий терминологический лед.
Желаемая штука возникает при обработке while в F# async workflow и Scala continuation plug-in. В случае F# стек не съедается, поскольку там работает (да и то не всегда) оптимизация хвостового вызова, а вот в Scala ничего уже не могут поделать с бесконечными циклами while внутри вычисления, если само вычисление не прерывается как-то изнутри, когда можно схватить продолжение и куда-то на время положить. Такие дела.
ОтветитьУдалить