Почему компилятор F# не создает хвостовой вызов для этой функции?

У меня проблемы с комбинатором с фиксированной точкой в ​​F#:

let rec fix f a = f (fix f) a

fix (fun body num -> 
    if num = 1000000 
    then System.Console.WriteLine "Done!" 
    else body (num + 1)
) 0

(Этот код просто для демонстрации проблемы, он был написан специально для того, чтобы сгенерированный код IL легко читался.)

Этот код - при компиляции с включенной оптимизацией и хвостовыми вызовами - вызывает StackruException, Я посмотрел на код IL и мог проследить проблему до лямбды внутри звонка fix:

.method assembly static void f@1 (class FSharpFunc`2<int32, class Unit> body,int32 num)
{
ldarg.1
ldc.i4 1000000
bne.un.s IL_0014

ldstr "Done!"
call void Console::WriteLine(string)
ret

IL_0014: ldarg.0 // Load the 'body' function onto the stack.
ldarg.1 // Load num onto the stack.
ldc.i4.1
add

// Invoke the 'body' function with num+1 as argument.
callvirt instance !1 class FSharpFunc`2<int32, class Unit>::Invoke(!0)
// Throw away the unit result.
pop
ret
}

(Я немного изменил код, чтобы его было легче читать.)

Причина для StackruException это призыв к body не хвостовой вызов (callvirt инструкция внизу). И причина этого в том, что компилятор создал вызов лямбда, который на самом деле возвращает Unit!

Итак, в терминах C#: тело Func<Int32,Unit> когда это действительно должно быть Action<Int32>, Поскольку вызов возвращает что-то, что должно быть отброшено, он не может быть вызовом. Также обратите внимание, что метод f@1 составлен как voidне UnitВот почему результат вызова аргумента должен быть отброшен.

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

Я просто хочу добавить, что пока вы что-то возвращаете в результате, все работает нормально. Только функции, которые ничего не возвращают, не работают должным образом.

Это работает:

let rec fix f a = f (fix f) a

fix (fun body num ->
    if num = 1000000
    then System.Console.WriteLine "Done!"; 0
    else body (num + 1)
) 0
|> ignore

И это теперь код, сгенерированный для лямбды:

.method assembly static int32 f@11 (class FSharpFunc`2<int32, int32> body, int32 num)
{
ldarg.1
ldc.i4 1000000
bne.un.s IL_0015

ldstr "Done!"
call void Console::WriteLine(string)
ldc.i4.0
ret

IL_0015: ldarg.0
ldarg.1
ldc.i4.1
add
tail.
callvirt instance !1 class FSharpFunc`2<int32, int32>::Invoke(!0)
ret
}

Теперь есть звонок. И все работает отлично.

Код IL для fix (для обсуждения в комментариях):

.method public static !!b fix<a, b> (class FSharpFunc`2<class FSharpFunc`2<!!a, !!b>, class FSharpFunc`2<!!a, !!b>> f, !!a a) 
{    
    ldarg.0
    ldarg.0
    newobj instance void class Program/fix@11<!!a, !!b>::.ctor(class FSharpFunc`2<class FSharpFunc`2<!0, !1>, class FSharpFunc`2<!0, !1>>)
    ldarg.1
    tail.
    call !!0 class FSharpFunc`2<class FSharpFunc`2<!!a, !!b>, !!a>::InvokeFast<!!b>(class FSharpFunc`2<!0, class FSharpFunc`2<!1, !!0>>, !0, !1)
    ret
}

Так что мне кажется, что (fix f) внутри определения исправления не рекурсивный вызов, который происходит в это время, а просто ссылка на fix Сам, что - вместе с аргументом f - хранится в закрытом помещении Program/fix@11 и передается в лямбду в качестве аргумента, который затем фактически вызывает fix через это закрытие.

В противном случае это будет бесконечная рекурсия с самого начала и fix было бы бесполезно.

Я использую F# версию 3.1.2, F# Интерактивная версия 12.0.30815.0

Пожалуйста:

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

Источник

2 ответа

Решение

На самом деле, вы уже ответили на свой вопрос. Цитируя комментарий из исходного кода,

// Throw away the unit result

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

Есть отличное сообщение в блоге Кейта Баттокки "Хвостовые вызовы в F#" (прокрутите раздел "Единицы возврата ограничений / вызова функций"), в котором рассказывается о многих деталях.

В двух словах:
Обычно функции F# … -> unit компилируются в методы.NET, возвращающие void,
Однако функции, обрабатываемые как значения (например, передаваемые в качестве аргументов функциям более высокого порядка), хранятся в объектах типа ('a->'b) поэтому они на самом деле возвращаются Microsoft.FSharp.Core.Unit не void,
Компилятору нужно выдвинуть пустышку unit значение из стека перед возвратом.
Следовательно, после рекурсивного вызова существует ожидающая операция, и поэтому компилятор не может оптимизировать ее до хвостового вызова.

Хорошие новости:

Обратите внимание, что эта проблема возникает только при использовании функций первого класса в качестве значений. Вызов обычных методов.NET, которые возвращают void, не представляет этой проблемы, потому что нет никакого возвращаемого значения, чтобы выскочить из стека.

Источник

Чтобы оптимизировать код с помощью вызовов, компилятор должен оптимизировать вызовы fix, С исправленной функцией более высокого порядка компилятор запутался.

Если вы хотите хвост-рекурсивный fixпопробуйте определить это по-другому:

let rec iter p f x =
  if p x then x
  else iter p f (f x)

iter ((=) 100000000) ((+) 1) 0

Интересный факт: ваш fix не будет переполнять стек в Haskell из-за того, как Haskell оценивает выражения: Haskell использует сокращение графов, которое отличается от использования стеков вызовов.

let fix f = f (fix f)
fix (\f x -> if x == 100000000 then -1 else f (x + 1)) 0

Говоря о вашем втором примере,.NET вовремя может оптимизировать хвостовые вызовы во время выполнения. Поскольку это оптимизация, это зависит от того, насколько умна среда выполнения: наличие возвращаемого значения или нет может поставить в тупик оптимизатор JIT. Например, Mono на моей машине не оптимизировал ваш второй пример.

Смотрите также: Сгенерируйте код операции хвостового вызова

Источник
Другие вопросы по тегам