O estilo funcional em C++

Estava de mau humor e resolvi ironizar a vida estudando numa aula de Java o artigo "Why Functional Programming Matters", que eu copiei do site do Haskell.

Acabei finalmente entendendo (eu acho!) as primeiras implicações importantes de lazy evaluation. O exemplo mais simples dessas implicações no artigo, na minha opinião, está no programa que computa aproximações da raiz quadrada pelo método de Newton-Raphson.

Esse método é basicamente uma expressão matemática que começa com um resultado anterior e usa esse resultado para computar um próximo, garantindo que o próximo é melhor que o anterior.

Seja N o número cuja raiz quadrada você deseja aproximar, e uma aproximação anterior x. O procedimento começa chutando x, por exemplo 1. O método afirma que o próximo x deve ser ( x + ( N / x ) / 2 .

O artigo descreve um programa para resolver o método. O programa segue abaixo; para entendê-lo completamente, estude o artigo.

repeat f a = cons a ( repeat f ( f a ) )

within e ( cons a ( cons b rest ) ) =

  = b , if abs(a - b) <= eps

  = within e ( cons b rest), otherwise

next N x = ( x + N / x ) / 2

sqrt a0 e N = within e ( repeat ( next N ) a0 )

O espírito geral do programa é assim:

repeat é uma função que gera uma lista contendo um elemento inicial seguido do resultado da função f com argumento elemento-anterior. Observe que repeat gera uma lista infinita, assumindo que f está definida para todo a.

within é uma função que percorre uma lista procurando um par de elementos cuja diferença seja menor que um epsilon.

A notação de parâmetros em within faz o que eu chamo de "desempacotar a lista". O segundo argumento é uma lista; a definição de within desempacota os dois primeiros, chamando-os de a e b.

next computa a próxima aproximação da raiz quadrada de N com aproximação anterior x segundo o método de Newton-Raphson.

sqrt computa a raiz quadrada de um número conforme uma tolerância e e um chute inicial a0; sua definição aplica within a repeat, e repeat a next.

sqrt basicamente avalia within à lista gerada por repeat , e repeat gera a lista de resultados de next.

Este programa, segundo a intuição de um programador acostumado a linguagens imperativas, nunca termina, porque repeat nunca termina de gerar a lista infinita.

Porém, lazy evaluation garante que esse programa termina -- garante que repeat será avaliado apenas o número de vezes necessária para que within se satisfaça. Eu entendo que o segredo disso está no momento em que o interpretador avalia o "desempacotamento" de uma lista, porque este é o momento em que o processamento exige a geração de mais um elemento.

Isso é mesmo sensacional. Como seriam esses pequenos componentes em C++0x?

Vamos começar brincando com uma versão muito eficiente de abs, o que não tem nada a ver com o problema em questão.

template
auto abs (Number x) -> typename std::enable_if< std::is_signed::value, Number>::type
{
  return x < 0 ? -x : x ;
}

template
auto abs (Number x) -> typename std::enable_if< ! std::is_signed::value, Number>::type
{
  return x;
}

A notação acima é a nova notação para funções em C++0x, onde a especificação do retorno fica depois da lista de argumentos.

A definição de abs faz uso de SFINAE para sobrecarregar dois templates, de outro modo indistinguíveis, usando std::enable_if.

Assim, abs pode se reduzir a nada quando nem mesmo faz sentido que o número possua um sinal.

Em seguida, vamos chamar as listas de Range e declarar a forma geral de uma função unpack.

template
auto unpack (Range& r) -> Value;

template
auto unpack (Sequence& s) -> decltype(s.front())
{
  typename Sequence::value_type v = s.front();
  s.pop_front();
  return v;
}

Definimos o significado de unpack providenciando uma sobrecarga, exclusiva para Containers da STL, que faz o que deve fazer. Em português, unpack resulta o elemento à esquerda e modifica a lista para conter o resto.

Assim, definimos within:

namespace detail
{

  template
  auto within (Number eps, Number a, Number b, Range rest) -> Number
  {
    if (abs(a - b) <= eps) return b;
    else {
      const Number c = unpack(rest);
      return within(eps, b, c, rest);
    }
  }

}

template
// requires(ValueType(Range) == Number)
auto within (Number eps, Range list) -> Number
{
  const Number a = unpack(list);
  const Number b = unpack(list);
  return detail::within(eps, a, b, list);
}

within desempacota a e b e delega para uma subrotina; a subrotina faz o que se espera. Observe que a lista a processar é um desses tais Ranges.

O componente equivalente a repeat deve gerar esse Range.

namespace detail
{
  template
  struct repeat_range
  {
    Function f;
    Value x;

    auto operator() () -> decltype(f(x))
    {
      return x = f(x);
    }
  };

  template
  auto unpack (repeat_range& r) -> decltype(r())
  {
    return r();
  }
}

template
// requires(UnaryFunction(Function) && Domain(Function) == Value)
auto repeat (Function f, Value a) -> detail::repeat_range
{
  return detail::repeat_range { f, a };
}

Um Range é um objeto especial, que representa a lista; definimos um repeat_range que continuamente aplica uma função, e definimos unpack para este Range. (Observe como repeat_range usa o último valor gerado na geração do próximo.)
A função repeat é utilitária e constrói o Range com os argumentos certos.

A notação de construção usada na definição de repeat também é nova, e generaliza a inicialização entre structs C e objetos C++.

Por último, implementamos a função importante para a aplicação, sqrt. Escolhi ocultar o equivalente a next porque a mim não interessa muito.

namespace detail
{
  template
  auto sqrt (Number N, Number x) -> Number
  {
    return (x + (N / x)) / 2;
  }
}

template
auto sqrt (Number N, Number x, Number eps) -> Number
{
  return
    within(eps,
      repeat(
        [=] (Number x) { return detail::sqrt(N, x); },
        x
      )
    );
}

Agora, isso é punk. A função no detail computa a próxima aproximação é trivial. O driver principal, por outro lado, é complexo.

Em primeiro lugar, aquela notação esquisita ali é uma expressão lambda. Para todos os efeitos, a avaliação desta expressão produz uma função, que vira argumento para repeat.

repeat, portanto, aplicará uma função lambda -- que por sua vez computa a próxima aproximação da raiz de N com chute x -- ao valor inicial x. O símbolo [=] significa que os nomes dentro do lambda se tornam cópias por valor dos objetos de mesmo nome no escopo maior.

repeat, como vimos antes, produz um Range, sobre o qual within opera. E within procura um par de valores neste Range -- aplicando unpack quando necessário -- em busca de um par cuja diferença seja menor que eps.

Assim, nesmo programa C++, simulamos com significativo esforço a lazy evaluation funcional, para computar a raiz quadrada. Usando __attribute__((const)) esse programa deve otimizar até o Nirvana, mas eu não verifiquei.

O programa esparramado no texto acima funciona de verdade com o GCC 4.5 e provavelmente funciona também com o ICC 11.1.