пятница, 22 марта 2013 г.

Комментарий о хвостовой рекурсии


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

В прошлом году вышел замечательный перевод книги Пола Грэма "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 цикл получился бы сам собою.

10 комментариев:

  1. Пример был бы очень к месту.

    ОтветитьУдалить
    Ответы
    1. @migmit Почему-то ответ на твой запрос попал вниз.

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

    ОтветитьУдалить
    Ответы
    1. @Ivan Boldyrev Тут мне кажется, что могут возникнуть терминологические споры. Да, я немного заострил :)

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

      Удалить
    2. Да что тут спорить: хвостовая рекурсия -- это частный случай хвостового вызова.

      Если мы добавляем дополнительную функцию (не важно, анонимную или именованную), то это называется непрямая (или косвенная, не помню точно) хвостовая рекурсия (пример: две функции, flip и flop, которые вызывают друг друга).

      Удалить
    3. А, не знал, что есть термин о непрямой (косвенной) хвостовой рекурсии. Это попадает в точку.

      Просто, такие посты помогают самому разобраться в терминологии (или еще больше запутаться). Есть у меня еще одна задумка сильно потроллить на тему функционального, императивного и декларативного стилей :)

      Удалить
  3. В Programming in Scala черным по белому написано, что хвостовая рекурсия в Scala тупа, как пробка. Если функция последним действием вызывает саму себя, эта оптимизация применяется, иначе - нет. Упомянутый вами случай явно не является простым.

    ОтветитьУдалить
    Ответы
    1. @afiskon Я прочитал первое издание Programming in Scala. Да, по-моему там говорится, что оптимизация хвостовой рекурсии в Scala неполная, хотя подтвердить свои слова сейчас не могу.

      Удалить
    2. > Если функция последним действием вызывает саму себя, эта оптимизация применяется, иначе - нет

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

      Удалить
  4. Желаемая штука возникает при обработке while в F# async workflow и Scala continuation plug-in. В случае F# стек не съедается, поскольку там работает (да и то не всегда) оптимизация хвостового вызова, а вот в Scala ничего уже не могут поделать с бесконечными циклами while внутри вычисления, если само вычисление не прерывается как-то изнутри, когда можно схватить продолжение и куда-то на время положить. Такие дела.

    ОтветитьУдалить