Оптимизирует ли Frege оптимизацию вызовов?

Ответ 1

Frege делает оптимизацию рекурсии хвоста, просто генерируя while.

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

При этом уже статическая глубина стека по своей природе глубже на функциональном языке, чем на Java. Следовательно, некоторым программам нужно будет предоставить больший стек (т.е. С -Xss1m).

Существуют патологические случаи, когда большие трюки строятся, и когда они оцениваются, произойдет переполнение стека. Известным примером является функция foldl (та же проблема, что и в Haskell). Следовательно, стандартная левая складка в Фреге является складкой, которая является хвостовой рекурсивной и строгой в аккумуляторе и, следовательно, работает в постоянном пространстве стека (например, Haskells foldl).

Следующая программа не должна переполнять переполнение, но печатать "false" после 2 или 3s:

module Test
    -- inline (odd) 
  where

even 0 = true
even 1 = false
even n = odd (pred n)

odd n = even (pred n)

main args =  println (even 123_456_789)

Это работает следующим образом: println должен иметь значение для печати, поэтому пытается оценить (даже n). Но все, что он получает, - это thunk to (нечетное (pred n)). Поэтому он пытается оценить этот thunk, который получает еще один thunk (даже (pred (pred n))). даже должен оценивать (pred (pred n)), чтобы увидеть, был ли аргумент 0 или 1, прежде чем возвращать другой thunk (нечетный (pred (n-2)), где n-2 уже оценивается. Таким образом, все вызовы (на уровне JVM) выполняются из println. Ни в коем случае не вызывает даже нечетное, или наоборот.

Если кто-то удаляет директиву inline, получается хвостовая рекурсивная версия четной, и результат получается в десять раз быстрее.

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

Вот еще одна версия, которая является патологией и будет переполнена:

even 0 = true
even 1 = false
even n = not . odd  $ n
odd    = even . pred

Проблема заключается в том, что not - это хвостовой вызов, и он строгий в своем аргументе (т.е. что-то отрицать, вы должны сначала иметь что-то). Следовательно, Когда even n вычисляется, тогда not должен полностью оценить odd n, который, в свою очередь, должен полностью оценить even (pred n) и, следовательно, он будет принимать 2 * n кадров стека.

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

Ответ 2

@LANDei TCO не поддерживается полностью в Scala... попробуйте этот.

def foo() { def bar() { println("bar"); foo() }; println("foo"); bar() }

Заметьте, у меня недостаточно репутации для комментариев. Найти комментарий Я отвечаю в комментариях оригинального вопроса.