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.
