Как erlang обрабатывает операторы case, смешанные с хвостовой рекурсией

Question

Допустим, у меня есть этот код здесь:

do_recv_loop(State) ->
    receive
    {do,Stuff} ->
        case Stuff of
        one_thing -> 
            do_one_thing(),
            do_recv_loop(State);
        another_thing ->
            do_another_thing(),
            do_recv_loop(State);
        _ ->
            im_dead_now
        end
    {die} -> im_dead_now;
    _ -> do_recv_loop(State)
    end.

Теперь, в теории, это хвостовая рекурсия, поскольку ни один из трех вызовов do_recv_loop не требует ничего для возврата.Но поймет ли Эрланг, что это хвостовая рекурсия, и соответственно оптимизирует?Я беспокоюсь, что вложенная структура может сделать ее не способной ее распознать.

Answer 1

Да, будет.Erlang требуется для оптимизации хвостовых вызовов, и это явно хвостовой вызов, поскольку после вызова функции ничего не происходит.

Раньше я хотел, чтобы в Erlang было ключевое слово tailcall, чтобы компилятор мог предупредить менянедопустимое использование, но потом я привык к этому.

Answer 2

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

Оптимизация хвостового вызова применима, если вызов находится в хвостовой позиции. Хвостовая позиция - это «последняя вещь перед тем, как функция вернется». Обратите внимание, что в

fact(0) -> 1;
fact(N) -> N * fact(N-1).

рекурсивный вызов факта не в хвостовой позиции, потому что после вычисления fact(N-1) необходимо запустить продолжение N * _ (т.е. умножить на N).

Answer 3

Это, я думаю, уместно, потому что вы спрашиваете, откуда вы знаете, оптимизирована ли ваша рекурсивная функция компилятором.Поскольку вы не используете списки: reverse / 1, приведенное ниже может не применяться, но для кого-то с точно таким же вопросом, но с другим примером кода это может быть очень уместно.

Из «Восемь мифов об Эрланге»Производительность в Руководстве по эффективности Erlang

В R12B и более поздних выпусках существует оптимизация, которая во многих случаях уменьшает количество слов, используемых в стеке при рекурсивных вызовах тела, так чтофункция рекурсивного списка и хвостовая рекурсивная функция, которая вызывает списки: reverse / 1 в конце будет использовать точно такой же объем памяти.

http://www.erlang.org/doc/efficiency_guide/myths.html#id58884

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

Answer 4

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

• не совершать рекурсивный вызов
• возвращать значение рекурсивного вызова и больше ничего не делать после него

Этот рекурсивный вызов может быть вложен во все if, case или receive звонит, как вы хотите, если после этого ничего не происходит.