Почему TCO требует поддержки со стороны виртуальной машины?

Говорят, что некоторые виртуальные машины, в первую очередь JVM, не поддерживают совокупную стоимость владения. В результате такой язык, как Clojure, требует, чтобы пользователь вместо этого использовал loop recur.

Однако я могу переписать самостоятельные вызовы, чтобы использовать цикл. Например, вот факториал хвостового вызова:

def factorial(x, accum):
    if x == 1:
        return accum
    else:
        return factorial(x - 1, accum * x)

Вот эквивалент цикла:

def factorial(x, accum):
    while True:
        if x == 1:
            return accum
        else:
            x = x - 1
            accum = accum * x

Это может быть сделано компилятором (и я написал макросы, которые делают это). Для взаимной рекурсии вы можете просто встроить вызываемую функцию.

Итак, учитывая, что вы можете реализовать совокупную стоимость владения, не требуя ничего от виртуальной машины, почему языки (например, Clojure, Armed Bear Common Lisp) не делают этого? Что я пропустил?


clojure lisp tail-recursion tail-call-optimization
person Wilfred Hughes    schedule 19.04.2014    source источник
comment
Обратите внимание, что совокупная стоимость владения не относится конкретно к саморекурсивным вызовам. Это только частный случай.   -  person Rainer Joswig    schedule 20.04.2014
comment
Истинный. Но либо вы вызываете ту же функцию (которую вы можете написать как цикл), либо вы вызываете другую функцию (которую вы можете встроить). Я считаю, что эти два метода вместе являются общим решением.   -  person Wilfred Hughes    schedule 20.04.2014
comment
Встраивание не является решением.   -  person Rainer Joswig    schedule 20.04.2014
comment
Можно ли просто встроить вызов функции в Clojure? Случаи, которые я видел, прикрепляют (надеюсь, соответствующий) макрос в качестве метаданных к файлу defn.   -  person Thumbnail    schedule 20.04.2014
comment
Вы говорите о самой тривиальной форме хвостовой рекурсии. Теперь рассмотрим хвостовой вызов виртуального метода. Вы не обязательно знаете, какую функцию вы вызываете.   -  person SK-logic    schedule 20.04.2014

Ответы (3)


arrow_upward
11
arrow_downward

Встраивание не является решением общей проблемы устранения хвостовых вызовов по ряду причин. Приведенный ниже список не является исчерпывающим. Это, однако, отсортировано — оно начинается с неудобства и заканчивается полным провалом.

  1. Функция, вызываемая в хвостовой позиции, может быть большой, и в этом случае ее встраивание может оказаться нецелесообразным с точки зрения производительности.

  2. Предположим, что есть несколько хвостовых вызовов g в f. В соответствии с обычным определением встраивания вам пришлось бы встраивать g в каждый сайт вызова, потенциально делая f огромным. Если вместо этого вы выберете goto начало g, а затем вернетесь назад, то вам нужно помнить, куда нужно перейти, и вдруг вы будете поддерживать свой собственный фрагмент стека вызовов (который почти наверняка будет демонстрировать низкую производительность по сравнению с «настоящий» стек вызовов).

  3. Для взаимно рекурсивных функций f и g вам придется встроить f в g и g в f. Ясно, что это невозможно при обычном определении встраивания. Итак, у вас остается то, что фактически является пользовательским соглашением о вызовах внутри функции (как в подходе на основе goto к 2. выше).

  4. Real TCE работает с произвольными вызовами в хвостовой позиции, в том числе в контекстах более высокого порядка:

    (defn say-foo-then-call [f]
  (println "Foo!")
  (f))

    Это может быть использовано с большим эффектом в определенных сценариях и явно не может быть эмулировано с помощью встраивания.

person Michał Marczyk    schedule 19.04.2014
comment
Блестящий ответ, много моментов, которые я не учел. Спасибо :) - person Wilfred Hughes; 20.04.2014

arrow_upward
1
arrow_downward

  1. Это может удивить и затруднить отладку, поскольку вы не видите стек вызовов.

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

  3. Программисты часто не пишут свой код с хвостовой рекурсией, если только язык не побуждает их к этому. Например. рекурсивный факториал обычно записывается с шагом рекурсии как n * fact(n-1), что не является хвостовой рекурсией.

person Barmar    schedule 19.04.2014
comment
На какие случаи не распространяется переписывание в виде цикла и встраивания? Не могли бы вы привести пример? - person Wilfred Hughes; 20.04.2014
comment
Ну, обычно вы бы не хотели, чтобы все вызовы функций были встроенными. - person Barmar; 20.04.2014

arrow_upward
1
arrow_downward

TCO сама по себе не требует поддержки виртуальных машин. То есть не для локальных функций. Хвостовые вызовы, охватывающие внешние функции, требуют поддержки виртуальной машины. В идеале полная реализация хвостовой рекурсии позволяет функциям в отдельно скомпилированных модулях программы взаимно рекурсивно выполняться в постоянном пространстве, а не только функциям, которые являются локальными для одной родительской функции, или функциям, которые одновременно видны компилятору.

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

Устранение хвостовых вызовов можно смоделировать без поддержки виртуальной машины, используя нелокальные возвраты и диспетчеризацию. Другими словами, когда хвостовой вызов имеет место синтаксически, он преобразуется в нелокальный возврат, который отказывается от текущей функции через динамическую передачу управления, передавая аргументы (возможно, упакованные как объект) в скрытый цикл диспетчеризации, который передает управление целевой функции, передавая ей эти аргументы. Это позволит выполнить требование, чтобы рекурсия происходила в постоянном пространстве и "выглядела и ощущалась" как хвостовой вызов. Однако это медленно и, возможно, не совсем прозрачно.

person Kaz    schedule 10.08.2016