Неужели бесконечная рекурсия Эликсира переполняет стек?

Число различные инструкции на Elixir программирование выражает мнение о том, что сохранение состояния или запуск бесконечного цикла выполняется идиоматически либо путем откручивания данных в Агент или Задачу, либо путем бесконечной рекурсии функции, которая нуждается в состоянии. Они не упоминают никаких ограничений в отношении того, насколько глубокой может быть рекурсия или какие-либо другие оговорки.

Так как поиск "переполнения стека эликсира" приводит только к хитам на этом веб-сайте, позвольте мне устранить двусмысленность и спросить здесь: какие гарантии реализации существуют в Elixir, чтобы убедиться, что бесконечная рекурсия как метод "петлирования" выиграла ' t приводит к переполнению стека, особенно когда информация о состоянии перемещается по пути?

Ответы

Ответ 1

Чтобы обобщить отличные комментарии от Hristo, общий механизм называется "Оптимизация Tail Call" (TCO) и гарантирует, что если последнее, что делает функция, является вызовом другой функции (или самой), тогда не будет стековый толчок. Вместо этого произойдет простой переход.

Есть некоторые тонкие нюансы относительно того, что такое хвостовой вызов. Рассмотрим несколько примеров. Самый простой из них:

def foo do
  # ...

  bar(...)  # tail call -> nothing is pushed to the stack
end

TCO также применяется для условных выражений:

def foo do
  # ...

  if (...) do
    # ...
    bar(...)            # tail call
  else
    # ...
    baz(...)            # tail call
  end
end

Это работает, потому что снова последнее, что делает функция, - это вызов функции. Результат if является результатом либо bar, либо baz, поэтому нет необходимости нажимать что-либо на стек.

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

def foo do
  # ...

  # Not a tail call since we're doing something after bar returns
  # (increment the result by 1)
  1 + bar(...)    
end

Другим примером нарушения TCO является вызов функции в try:

def foo do
  try do
    bar(...)    # not a tail call
  rescue
    # ...
  end
end

Также стоит упомянуть, что из-за TCO вы не увидите некоторые функции в трассировке стека при возникновении исключения:

def foo do
  # ...
  bar(...)  # at this point foo "disappears" from stack trace
end

def bar(...) do
  # ...
  raise("error")
end

Дамп этой ошибки не будет содержать foo, поскольку он больше не находится в стеке (он фактически заменяется на bar).