F # использует аккумулятор, все еще получая исключение переполнения стека - PullRequest
Новая
       31

F # использует аккумулятор, все еще получая исключение переполнения стека

3 голосов
/ 06 ноября 2010

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

//F# attempting to make a tail recursive call via accumulator
let rec calc acc startNum =
    match startNum with
    | d when d = 1      -> List.rev (d::acc)
    | e when e%2 = 0    -> calc (e::acc) (e/2)
    | _                 -> calc (startNum::acc) (startNum * 3 + 1)

Насколько я понимаю, использование acc позволило бы компилятору увидеть, что нет необходимости хранить все кадры стека для каждого рекурсивного вызова, поскольку он может заполнять результат каждого прохода в acc и возвращать каждый кадр. Очевидно, что я не понимаю, как правильно использовать значение аккумулятора, чтобы компилятор выполнял хвостовые вызовы.

Ответы [ 2 ]

3 голосов
/ 06 ноября 2010

Стивен Свенсен был прав, отметив в качестве комментария вопрос, что если вы отлаживаете, VS должен отключить хвостовые вызовы (иначе у него не будет стековых фреймов, чтобы следовать за стеком вызовов).Я знал , что VS сделал это, но просто забыл.

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

'Stack Overflow Exception: a recursive function does not 
tail call by default when in debug mode'
1 голос
/ 06 ноября 2010

Это действительно кажется, что это правильно преобразуется в вызов хвоста при компиляции с .NET Framework 4. Обратите внимание, что в Reflector он переводит вашу функцию в while(true), как вы ожидаете хвостФункциональность в F # для выполнения: 

[CompilationArgumentCounts(new int[] { 1, 1 })]
public static FSharpList<int> calc(FSharpList<int> acc, int startNum)
{
    while (true)
    {
        int num = startNum;
        switch (num)
        {
            case 1:
            {
                int d = num;
                return ListModule.Reverse<int>(FSharpList<int>.Cons(d, acc));
            }
        }
        int e = num;
        if ((e % 2) == 0)
        {
            int e = num;
            startNum = e / 2;
            acc = FSharpList<int>.Cons(e, acc);
        }
        else
        {
            startNum = (startNum * 3) + 1;
            acc = FSharpList<int>.Cons(startNum, acc);
        }
    }
}

Ваша проблема не связана с отсутствием, это является хвостовой вызов (если вы используете F # 2.0, я не знаю, каковы будут результаты).Как именно вы используете эту функцию?(Входные параметры.) Как только я получу более четкое представление о том, что делает функция, я могу обновить свой ответ, надеясь решить его.

...