StackOverflowException e Tail Call Optimization

Dado o seguinte código a ser executado em um Console Application...

    public static void Main(string[] args)
    {
        try
        {
            Action @do = null;
            @do = () =>
            {
                WriteLine("Hellow World!");
                @do();
            };
            @do();
                
        }
        catch (Exception ex)
        {
            ForegroundColor = ConsoleColor.Red;
            WriteLine(ex);
            ResetColor();
        }

        WriteLine("Pressione  para continuar.");
        ReadLine();
    }

... se o executarmos como Any CPU, o código estourará StackOverflowException. Note, entretanto, que este tipo de exception não é capturado pelo Try-Catch. Isto corre pois StackOverflowException é uma exceção não gerenciada. Por consequencia ela leva ao encerramento abrupto do processo.

Agora, se executarmos o mesmo código em Release/x64, a exception não ocorre. Há duas razões pelas quais isso acontece:

1. A função Do(int) é classificada como um Tail-Call Function
2. Ao compilarmos em Release/x64, o compilador inclui otmizações no código para Tail-Call functions, removendo a recursividade.

Uma Tail-Call function é uma função cuja última operação realizada é a chamada de uma outra função. Neste caso, como Do é recursiva, ela é classificada como `Tail-Recursion Function`.

Vamos então, a efeito de testes, fazer uma modificação no nosso código.

    @do = () =>
    {
        WriteLine("Hellow ");
        @do();
        WriteLine("world!");
    };
    @do(1);

Ao executar o código agora em Release/x64, novamente é gerado StackOverflowException! E fica a pergunta: Porquê? Porque ao incluirmos o WriteLine, descaracterizamos a função Do como uma Tail-Call Function.

Loops infinitos por si só já são um perigo para as aplicações. Apesar disso, temos reações diferente ao usarmos ou não Tail-Call functions: Num loop infinito, consome-se recursos computacionais. Desta forma, ao usar Tail-Call functions seu processo só vai abendar quando não houver mais memória, ou ainda que a alocação de memória adicional não seja realizada pela função, ainda sim o consumo do processador levará a máquina a instabilidade ou lentidão. Imagine quão devastador seria ter algumas threads no IIS rodando loops infinitos em backgroud! Caso abendasse (no caso de não serem usadas Tail-call functions), estes efeitos colaterais não ocorreriam.

Utilizar tail-call functions nos livra da preocupação da profundidade do stack em casos legítimos.

Com stack overflow ou não, a Microsoft recomenta que "devemos escrever nosso código para detectar e prevenir stack overflow. Por exemplo, se sua aplicação depende de recursão, use um contador ou uma condição de estado para finalizar o loop recursivo." (https://msdn.microsoft.com/en-us/library/system.stackoverflowexception)

Escrevendo Tail-Call Functions

Por exemplo, tomemos por exemplo uma função que calcule o fatorial:

    private static int Fatorial(int i)
    {
        if (i == 1) return 1;
        return i*Fatorial(i - 1);
    }

Reparem que esta função não é Tail-recursive, pois a ultima operação realizada é multiplicação. Para transformar esta função em uma Tail-Call function nós podemos usar algumastécnicas de programação funcional:

Técnica 1 - Accumulator Passing Style

Esta estratégia basea-se em passar uma variável acumuladora para o método. Poderíamos transformá-la em tail recursive, informando um acumulador no argumento da função.

    private static int Fatorial(int i, int acc == 1)
    {
        if (i == 1) return acc;
        return Fatorial(i - 1, acc * i);
    }

Infelizmente esta abordagem acrescenta um argumento não-funcional na nossa função. Reparem que preciso invocá-la passando o argumeto opcional 1. Porém isso pode ser contornado:

    private static int Fatorial(int i)
    {
        Func<int, int, int> _fatorial = null;
        _fatorial = (x, acc) => x == 1 ? acc : _fatorial(x - 1, acc*x);
        return _fatorial(i, 1);
    }

Técnica 2 - Continuation Passing Style

A segunda estratégia resume-se em passar o ponteiro de uma função que será usado na continuação da rotina. É uma espécie de callback.

    public static int Fatorial(int n)
    {
        Func<int, Func<int, int>, int> _fatorial = null;
        _fatorial = (_n, continuation) =>
        {
            return _n == 1
                ? continuation(1) 
                : _fatorial(_n - 1, result => continuation(result * _n));
        };
        return _fatorial(n, result => result);
    }

Mais informações:

• https://blogs.msdn.microsoft.com/clrcodegeneration/2009/05/11/tail-call-improvements-in-net-framework-4/